
DIRECTORY G2dBasic, G3dBasic, G3dShape, G3dPlane;

G3dPolyNet: CEDAR DEFINITIONS
~ BEGIN
NatSequence:		TYPE ~ G2dBasic.NatSequence;
Plane:				TYPE ~ G3dPlane.Plane;
Shape:			TYPE ~ G3dShape.Shape;
Triple:			TYPE ~ G3dBasic.Triple;
Vertex:			TYPE ~ G3dShape.Vertex;
Validity:			TYPE ~ G3dShape.Validity;

Poly:					TYPE ~ REF PolyRep;
PolyRep:				TYPE ~ RECORD [
visible:						BOOL м TRUE,			-- is this polygon valid in this shape?
vertices:						NatSequence м NIL,		-- ccw list of vertices
neighbors:					NatSequence м NIL,		-- unordered list of edge-sharing polys
plane:							Plane,						-- the plane of this poly
clientData:					REF ANY м NIL			-- the conventional escape hatch
];

Vert:					TYPE ~ REF VertRep;
VertRep:				TYPE ~ RECORD [
visible:						BOOL м TRUE,			-- is this polygon valid in this shape?
polyRing:						NatSequence м NIL,		-- ordered list of polys around this vertex
vertex:						Vertex м NIL,			-- standard vertex info
clientData:					REF ANY м NIL			-- the conventional escape hatch
];

PolyNet:				TYPE ~ REF PolyNetRep;
PolyNetRep:			TYPE ~ RECORD [
vertices:						VertSequence м NIL,	-- the vertices that make up the shape
polygons:						PolySequence м NIL,	-- the polygons that make up the shape
clientData:					REF ANY м NIL			-- the conventional escape hatch
];

VertSequence:		TYPE ~ REF VertSequenceRep;
VertSequenceRep:	TYPE ~ RECORD [
valid:							ARRAY Validity OF BOOL м ALL[FALSE],
length:						CARDINAL м 0,
element:						SEQUENCE maxLength: CARDINAL OF Vert
];

PolySequence:		TYPE ~ REF PolySequenceRep;
PolySequenceRep:	TYPE ~ RECORD [
length:						CARDINAL м 0,
element:						SEQUENCE maxLength: CARDINAL OF Poly
];
PolyNetProc: TYPE ~ PROC [polyNet: PolyNet, p0, p1: INT, clientData: REF ANY] RETURNS [continue: BOOL м TRUE];
PolyNetFromShape: PROC [shape: Shape] RETURNS [PolyNet];
ShapeFromPolyNet: PROC [polyNet: PolyNet] RETURNS [Shape];
FindVisibleNeighborsOfPoly: PROC [polyNet: PolyNet, poly: INT] RETURNS [NatSequence];
RelinkEdge: PROC [polyNet: PolyNet, v0, v1, oldPoly, newPoly: INT];
VisitPolyNet: PROC [polyNet: PolyNet, proc: PolyNetProc, clientData: REF ANY м NIL];
RemovePolyFromNet: PROC [polyNet: PolyNet, poly: INT];
RebuildPolyNet: PROC [polyNet: PolyNet];
UpdateAllPolygonInformation: PROC [polyNet: PolyNet];
UpdatePolygonInformation: PROC [polyNet: PolyNet, polyID: INT];
UpdateVertexInformation: PROC [polyNet: PolyNet, vertexID: INT];

GetPolygonNeighbors: PROC [polyNet: PolyNet, polyID: INT] RETURNS [NatSequence];
IsGenus0: PROC [polyNet: PolyNet] RETURNS [BOOL];
ConcaveEdge: PROC [polyNet: PolyNet, poly0, poly1: INT] RETURNS [BOOL];

CoPlanar: PROC [polyNet: PolyNet, poly0, poly1: INT] RETURNS [BOOL];
CoPlanarFlipped: PROC [polyNet: PolyNet, poly0, poly1: INT] RETURNS [BOOL];
GetNormal: PUBLIC PROC [polyNet: PolyNet, polyID: INT] RETURNS [Triple];
GetOffset: PUBLIC PROC [polyNet: PolyNet, polyID: INT] RETURNS [REAL];
CopyPolyNet: PROC [polyNet: PolyNet, copyVertices: BOOL м FALSE] RETURNS [PolyNet];
CopyPolySequence: PROC [polys: PolySequence] RETURNS [PolySequence];
AddToPolySequence:PROC [polys: PolySequence, poly: Poly] RETURNS [PolySequence];
LengthenPolySequence: PROC [polys: PolySequence, amount: REAL м 1.3] RETURNS [new: PolySequence];

CopyVertSequence: PROC [verts: VertSequence, copyData: BOOL м FALSE] RETURNS [VertSequence];
AddToVertSequence: PROC [verts: VertSequence, vert: Vert] RETURNS [VertSequence];
LengthenVertSequence: PROC [verts: VertSequence, amount: REAL м 1.3] RETURNS [new: VertSequence];

END.

   М  
G3dPolyNet.mesa
Copyright ╙ 1984, 1992 by Xerox Corporation. All rights reserved.
Glassner, February 18, 1991 2:29 pm PST
Jules Bloomenthal July 15, 1992 5:11 pm PDT
Basic Types
Local Types
The PolyNet data structure is intended as a lightweight, compact description for the critical topological and geometric information of a 3D shape.  Every polygon is represented by an instance of the Poly data structure, which provides a list of vertex indices, a list of neighbor indices (these are indices in the polyNet for each polygon that shares an edge with this polygon), the plane information, a visibility flag, and a clientData ref.  The vertices themselves contain a pointer to the standard vertex info, and a list of the polygons around that vertex (in order, but the cw/ccw direction is not consistent across vertices).  Because of the explicit connectivity information represented by the neighbors and polyRing fields, one can make topology changes to the polyNet and easily verify the resulting topology.  Note that you can capture all the edges by visiting the net for all neighbor pairs, and only processing those where p0<p1.
Callback Proc Types
PolyNet to/from Shape Procs
Return the PolyNet that abstracts this shape

Return the Shape described by this PolyNet
PolyNet Processing
Return all neighbors[i] of poly for which poly.neighbors[i].visible=TRUE

For all visible polygons with edge [v0, v1], the neighbor list is updated by replacing oldPoly with newPoly.  The polyRing information for each vertex is also updated.  Useful when a polygon is replaced; call this for each edge in the old poly.

For each visible poly in the net, call the client's proc with that poly and each of its neighbors.  Stop when the proc returns FALSE.

Remove all references of this polygon from the net.  No attempt is made to keep the topology consistent; this is a clean-up step after the net has been changed and the poly is redundant.

Rebuild all vertex polyRings and polygon neighbors lists.  The vertex lists for each polygon are assumed to be valid.

Update the neighbors and plane information for all polygons.  Useful after client modifications to the net.  Due to the pre-processing required, it costs little more to do all the polygons then just one.

Update the neighbors and plane information for this polygon.  See the comment for UpdateAllPolygonInformation - this is an expensive call for just one polygon.

Update the polyRing information for this vertex.  Useful after client modifications to the net.
Return the indices of all polygons that point back to polygon polyID
Topology and Geometry Tests
Returns TRUE iff the polyNet describes a topological sphere.  

Returns TRUE iff the edge shared by the two polygons is concave.  If they are coplanar, then returns CoPlanarFlipped[polyNet, poly0, poly1].
Returns TRUE iff the two polygons are coplanar.  Note that the normals may be pointing in the same or opposite directions.

Returns TRUE iff the two polygons are coplanar but poly0.norm = -poly1.norm.
Utility
Convenience proc: RETURN[polyNet.polygons[polyId].plane.x, y, z]

Convenience proc: RETURN[polyNet.polygons[polyId].plane.w]

Return a complete copy of the polyNet, with all new data (except for the vertices; if copyVertices is FALSE, then just the pointer to the vertex field for each vert is copied; if copyVertices is TRUE, all-new vertex data is created for the copy).    
Poly and Vert Sequences
Ye Olde Standarde Sequence Procs

 Э╩г  ХNewlineDelimiter
Ц"cedarcode" styleЩ ЪЬЩJЪЬ	╧eЬ5ЩAJЪЬ'Щ'JЩ+JШ ЧЪ╧k	Ь(Ш1JШ ЧJЪ╤bln
ЬЮЬЮШJЪЬЮШheadЪ╧lЩJЪЬЮЬШ*JЪЬ
ЮЬШ JЪЬ	ЮЬШJЪЬ
ЮЬШ!JЪЬ
ЮЬШ!JЪЬЮЬШ%ЧЪаЩJЩпJШ JЪЬ
ЮЬЮЬ	ШЪЬЮЬЮЬШJЪЬЮЬЮЬ╧c'ШDJЪЬЮЬбШ:JЪЬЮЬб'ШJJЪЬбШ2JЪЬЮЬЮЬЮЬб Ш@JШJШ ЧJЪЬ
ЮЬЮЬ	ШЪЬЮЬЮЬШJЪЬЮЬЮЬб'ШDJЪЬЮЬб+ШNJЪЬЮЬбШ4JЪЬЮЬЮЬЮЬб Ш@JШJШ ЧJЪЬЮЬЮЬШ"ЪЬЮЬЮЬШJЪЬЮЬб&ШIJЪЬЮЬб&ШIJЪЬЮЬЮЬЮЬб Ш@JЪЬШJШ ЧJЪЬЮЬЮЬШ*ЪЬЮЬЮЬШ JЪЬЮ╧sЬвЮвЮвЬвЮЬЮЬШ1JЪЬЮЬШJЪЬЮЬЮЬЮЬШ2JЪЬШJШ ЧJЪЬЮЬЮЬШ*ЪЬЮЬЮЬШ JЪЬЮЬШJЪЬЮЬЮЬЮЬШ2JЪЬШЧЧЪаЩJЪ╧bЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬШnЧЪаЩЪ╧nЬЮЬЮЬШ8JЩ,JЩ ЧЪдЬЮЬЮЬ	Ш:JЩ*ЧЧЪаЩЪдЬЮЬЮЬЮЬШUJЩHJЩ ЧЪд
ЬЮЬ.ЮЬШCJЩЇJЩ ЧЪ
дЬЮЬ3ЮЬЮЬЮЬШTJЩЕJЩ ЧЪдЬЮЬЮЬШ6JЩ║JЩ ЧЪдЬЮЬШ(JЩuJЩ ЧЪдЬЮЬШ5JЩ╦JЩ ЧЪдЬЮЬЮЬШ?JЪЬRгЬ2ЩЯJЩ ЧЪдЬЮЬЮЬШ@JЩ_JШ ЧЪдЬЮЬЮЬЮЬШPJЩDЧЧЪаЩЪдЬЮЬЮЬЮЬШ1JЩ>JЩ ЧЪ
дЬЮЬ"ЮЬЮЬЮЬШGJЩМJШ ЧЪ
дЬЮЬ"ЮЬЮЬЮЬШDJЩzJЩ ЧЪ
дЬЮЬ"ЮЬЮЬЮЬШKJЩLЧЧЪаЩЪ
д	ЬЮЬЮЬЮЬЮЬ
ШHJЩ@JЩ ЧЪд	ЬЮЬЮЬЮЬЮЬЮЬШFJЩ:JЩ ЧЪ
дЬЮЬ"ЮЬЮЬЮЬШSJЩ·ЧЧЪаЩЩ JЩ ЧJЪдЬЮЬЮЬШDJЪдЬЮЬ#ЮЬШPЪдЬЮЬЮЬЮЬШaJШ ЧJЪ
дЬЮЬ!ЮЬЮЬЮЬШ\JЪдЬЮЬ#ЮЬШQJЪдЬЮЬЮЬЮЬШaJШ ЧJЪЮЬШJШ Ч ЕЧ    ║   щ  