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
NatSequence: TYPE ~ G2dBasic.NatSequence;
Plane: TYPE ~ G3dPlane.Plane;
Shape: TYPE ~ G3dShape.Shape;
Triple: TYPE ~ G3dBasic.Triple;
Vertex: TYPE ~ G3dShape.Vertex;
Validity: TYPE ~ G3dShape.Validity;
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.
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
];
PolyNet Processing
FindVisibleNeighborsOfPoly:
PROC [polyNet: PolyNet, poly:
INT]
RETURNS [NatSequence];
Return all neighbors[i] of poly for which poly.neighbors[i].visible=TRUE
RelinkEdge:
PROC [polyNet: PolyNet, v0, v1, oldPoly, newPoly:
INT];
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.
VisitPolyNet:
PROC [polyNet: PolyNet, proc: PolyNetProc, clientData:
REF
ANY ¬
NIL];
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.
RemovePolyFromNet:
PROC [polyNet: PolyNet, poly:
INT];
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.
RebuildPolyNet:
PROC [polyNet: PolyNet];
Rebuild all vertex polyRings and polygon neighbors lists. The vertex lists for each polygon are assumed to be valid.
UpdateAllPolygonInformation:
PROC [polyNet: PolyNet];
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.
UpdatePolygonInformation:
PROC [polyNet: PolyNet, polyID:
INT];
Update the neighbors and plane information for this polygon. See the comment for UpdateAllPolygonInformation - this is an expensive call for just one polygon.
UpdateVertexInformation:
PROC [polyNet: PolyNet, vertexID:
INT];
Update the polyRing information for this vertex. Useful after client modifications to the net.
GetPolygonNeighbors:
PROC [polyNet: PolyNet, polyID:
INT]
RETURNS [NatSequence];
Return the indices of all polygons that point back to polygon polyID
Topology and Geometry Tests
IsGenus0:
PROC [polyNet: PolyNet]
RETURNS [
BOOL];
Returns TRUE iff the polyNet describes a topological sphere.
ConcaveEdge:
PROC [polyNet: PolyNet, poly0, poly1:
INT]
RETURNS [
BOOL];
Returns TRUE iff the edge shared by the two polygons is concave. If they are coplanar, then returns CoPlanarFlipped[polyNet, poly0, poly1].
CoPlanar:
PROC [polyNet: PolyNet, poly0, poly1:
INT]
RETURNS [
BOOL];
Returns TRUE iff the two polygons are coplanar. Note that the normals may be pointing in the same or opposite directions.
CoPlanarFlipped:
PROC [polyNet: PolyNet, poly0, poly1:
INT]
RETURNS [
BOOL];
Returns TRUE iff the two polygons are coplanar but poly0.norm = -poly1.norm.
Utility
GetNormal:
PUBLIC
PROC [polyNet: PolyNet, polyID:
INT]
RETURNS [Triple];
Convenience proc: RETURN[polyNet.polygons[polyId].plane.x, y, z]
GetOffset:
PUBLIC
PROC [polyNet: PolyNet, polyID:
INT]
RETURNS [
REAL];
Convenience proc: RETURN[polyNet.polygons[polyId].plane.w]
CopyPolyNet:
PROC [polyNet: PolyNet, copyVertices:
BOOL ¬
FALSE]
RETURNS [PolyNet];
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
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];