G3dWingedEdge.mesa
Copyright Ó 1990, 1992 by Xerox Corporation. All rights reserved
Glassner, March 10, 1990 6:37:23 pm PST
Jules Bloomenthal July 15, 1992 5:13 pm PDT
DIRECTORY G3dBasic, G3dShape, Rope;
G3dWingedEdge: CEDAR DEFINITIONS
~ BEGIN
Error: ERROR [code: ATOM, reason: ROPE];
Important Note
This interface is not fully implemented. However, what is implemented probably works - it has passed a number of tests. If you call an unimplemented routine, you will receive an error stating that there is no implementation yet. Please feel free to provide implementations where they are missing.
Imported Types
Quad:      TYPE ~ G3dBasic.Quad;
Face:      TYPE ~ G3dShape.Face;
Shape:     TYPE ~ G3dShape.Shape;
Validity:     TYPE ~ G3dShape.Validity;
Vertex:     TYPE ~ G3dShape.Vertex;
SurfaceSequence:  TYPE ~ G3dShape.SurfaceSequence;
ROPE:      TYPE ~ Rope.ROPE;
Local Types
A Note on These Data Structures
There is a note on the architecture of the interface at the end of this file. The general structure is that faces, edges, and vertices are stored in rings (a doubly-linked list). A WShape contains three rings, one each for faces, edges, and vertices. Each edge points to a data structure called WEdgeData, which contains the information for that edge. Each face contains an edge ring describing the edges around that face. Each vertex contains an edge ring of all edges around that vertex. All duplicate instantiations of an edge point to a single WEdgeData structure (this contains a pointer back to its "owner" in the master edge ring in the WShape). Here is a pictorial description of a WShape:
[Artwork node; type 'Artwork on' to command tool]
The fundamental building block in the system is the edge, represented by WEdgeData. An edge is a directed connection between two vertices (from aVertex to bVertex). Each edge separates two faces (viewing the edge as below, aFace is below and bFace is above). An edge has four "wings"; these are the first edges around the vertex encountered in the specified direction. Again referring to the figure below, on aFace we travel clockwise from the edge to reach aCWedge, and counterclockwise to reach aCCWedge; similarly for bFace and its wings, bCWedge and bCCWedge.
[Artwork node; type 'Artwork on' to command tool]
Much of the architecture of this interface has been designed to insulate the user from dealing directly with these data structures when executing topological and geometrical operations. Changes to the topology are rather hard to implement; because of the redundancy in the data structures, many pointers must be carefully moved, and in the right order. The most important high-level topological operations are given below under "Euler Operators"; the implementation provides details for these routines.
Sometimes you may need to adjust the data structures yourself; I recommend careful study of the data types and the implementations mentioned above, followed by extensive testing; sometimes the correct pointer-stitching order is not obvious, and subtle problems can arise. If you stick to the high-level routines in this interface you should be okay.
WShape:     TYPE ~ REF WShapeRep;
WShapeRep:    TYPE ~ RECORD [
vertexRing:      WVertex ¬ NIL,
edgeRing:      WEdge ¬ NIL,
faceRing:       WFace ¬ NIL,
next, previous:     WShape ¬ NIL,
vertexValidities:     ARRAY Validity OF BOOL ¬ ALL[FALSE], -- to convert back
faceValidities:     ARRAY Validity OF BOOL ¬ ALL[FALSE], -- to a shape
index:        INT ¬ 0,
clientData:      REF ANY ¬ NIL
];
WFace:     TYPE ~ REF WFaceRep;
WFaceRep:    TYPE ~ RECORD [
basicFace:      Face ¬ NIL,
edgeRing:      WEdge ¬ NIL,
next, previous:     WFace ¬ NIL,
index:        INT ¬ 0,
clientData:      REF ANY ¬ NIL
];
WEdgeData:    TYPE ~ REF WEdgeDataRep;
WEdgeDataRep:   TYPE ~ RECORD [
aCWedge, bCWedge:   WEdge ¬ NIL,
aCCWedge, bCCWedge:   WEdge ¬ NIL,
aVertex, bVertex:    WVertex ¬ NIL,
aFace, bFace:     WFace ¬ NIL,
index:        INT ¬ 0,
owner:       WEdge ¬ NIL,
clientData:      REF ANY ¬ NIL
];
WEdge:     TYPE ~ REF WEdgeRep;
WEdgeRep:    TYPE ~ RECORD [
edgeData:       WEdgeData ¬ NIL,
next, previous:     WEdge ¬ NIL,
clientData:      REF ANY ¬ NIL
];
WVertex:     TYPE ~ REF WVertexRep;
WVertexRep:    TYPE ~ RECORD [
basicVertex:      Vertex ¬ NIL,
edgeRing:      WEdge ¬ NIL,
next, previous:     WVertex ¬ NIL,
index:        INT ¬ 0,
clientData:      REF ANY ¬ NIL
];
ClockDirection:   TYPE ~ { cw, ccw };
Function Types
WVertexProc:   TYPE ~ PROC [v: WVertex];
WEdgeProc:    TYPE ~ PROC [e: WEdge];
WFaceProc:    TYPE ~ PROC [f: WFace];
Creation / Conversion to Shapes
ShapeFromWingedEdge: PROC [wShape: WShape] RETURNS [shape: Shape];
Return a shape from a winged edge representation.
WingedEdgeFromShape: PROC [shape: Shape] RETURNS [wShape: WShape];
Return a winged edge from a shape representation.
Apply A Function To All Elements of A WShape
ApplyToFaces: PROC [wShape: WShape, ff: WFaceProc];
Apply the function to all faces in the wShape
ApplyToEdges: PROC [wShape: WShape, ef: WEdgeProc];
Apply the function to all edges in the wShape
ApplyToVertices: PROC [wShape: WShape, vf: WVertexProc];
Apply the function to all vertics in the wShape
Vertex Access Procedures
NextVertexAroundFaceFromEdge: PROC [edge: WEdge, face: WFace, dir: ClockDirection]
RETURNS [WVertex];
Walks around the face in the specified direction from the edge to return the next vertex
NextVertexAroundFaceFromVertex: PROC [vertex: WVertex, face: WFace, dir: ClockDirection]
RETURNS [WVertex];
Walks around the face in the specified direction from the vertex to return the next vertex
NextVertexAroundVertex: PROC [vertex: WVertex, face: WFace, dir: ClockDirection]
RETURNS [WVertex];
Same as NextVertexAroundFaceFromVertex
VertexAcrossEdge: PROC [vertex: WVertex, edge: WEdge]
RETURNS [WVertex];
Returns the vertex across the given edge from the given vertex
Edge Access Procedures
NextEdgeAroundFaceFromEdge: PROC
[edge: WEdge, face: WFace, dir: ClockDirection] RETURNS [WEdge];
Walks around the face in the given direction from the given edge
NextEdgeAroundVertex: PROC
[vertex: WVertex, edge: WEdge, dir: ClockDirection] RETURNS [WEdge];
Returns the next edge around the given vertex. The order of edges is unspecified and may change as edges are added and removed.
NextEdgeAroundFaceFromVertex: PROC
[vertex: WVertex, face: WFace, dir: ClockDirection] RETURNS [WEdge];
Walks around the face in the given direction from the given vertex
Face Access Procedures
NextFaceAroundEdge: PROC [vertex: WVertex, edge: WEdge, dir: ClockDirection]
RETURNS [WFace];
Walks around the vertex from the given edge to find the face containing the given edge
NextFaceAroundVertex: PROC [vertex: WVertex, face: WFace, dir: ClockDirection]
RETURNS [WFace];
Walks around the vertex from the given face to find the next face
FaceAcrossEdge: PROC [edge: WEdge, face: WFace] RETURNS [WFace];
Returns the face on the other side of the given edge
Ring Looping Procedures
ApplyToVertexRing: PROC [vRing: WVertex, vf: WVertexProc];
Apply the given function to each vertex in the ring
ApplyToEdgeRing: PROC [eRing: WEdge, ef: WEdgeProc];
Apply the given function to each edge in the ring
ApplyToFaceRing: PROC [fRing: WFace, ff: WFaceProc];
Apply the given function to each face in the ring
Construction Utility Procedures
InsertVertexIntoRing: PROC [v: WVertex, vRing: WVertex] RETURNS [WVertex];
Inserts the given vertex into the ring and returns the new, updated ring
InsertCopyOfVertexIntoRing: PROC [v: WVertex, vRing: WVertex] RETURNS [WVertex];
Inserts a copy of the given vertex into the ring and returns the new, updated ring
InsertEdgeIntoRing: PROC [e: WEdge, eRing: WEdge] RETURNS [WEdge];
Inserts the given edge into the ring and returns the new, updated ring
InsertCopyOfEdgeIntoRing: PROC [e: WEdge, eRing: WEdge] RETURNS [WEdge];
Inserts a copy of the given edge into the ring and returns the new, updated ring
InsertFaceIntoRing: PROC [f: WFace, fRing: WFace] RETURNS [WFace];
Inserts the given face into the ring and returns the new, updated ring
InsertCopyOfFaceIntoRing: PROC [f: WFace, fRing: WFace] RETURNS [WFace];
Inserts the given face into the ring and returns the new, updated ring
ReverseEdgeRing: PROC [eRing: WEdge];
Reverses the order of edges in the ring
SetWings: PROC [e1, e2: WEdge];
Sets the relevant pair of wings between the two edges (1 wing each is affected)
Miscellaneous
InvertEdge: PROC [edge: WEdge];
A topological no-op, but useful sometimes, this reverses the direction of the edge
EvertEdge: PROC [e: WEdge];
Flips an edge over; useful for turning shapes inside-out
InvertWShape: PROC [wShape: WShape];
Applies InvertEdge to each edge in the shape
EvertWShape: PROC [wShape: WShape];
Applies EvertEdge to each edge in the shape
Utility
AnyVertexOnFace: PROC [face: WFace] RETURNS [WVertex];
Returns any vertex on the given face
AnyEdgeOnFace: PROC [face: WFace] RETURNS [WEdge];
Returns any edge on the given face
AnyEdgeOnVertex: PROC [vertex: WVertex] RETURNS [WEdge];
Returns any edge on the given vertex
AnyFaceOnVertex: PROC [vertex: WVertex] RETURNS [WFace];
Returns any face on the given vertex
AnyFaceOnEdge: PROC [edge: WEdge] RETURNS [WFace];
Returns any face on the given edge
VertexNotOnFirstEdge: PROC [e1, e2: WEdge] RETURNS [WVertex];
Returns the vertex on e2 not in common with e1
EdgeUsingVertex: PROC [eRing: WEdge, v: WVertex] RETURNS [WEdge];
Returns any edge in the ring that contains the vertex
Lookup Procedures
VertexFromIndex: PROC [wShape: WShape, vNum: INT] RETURNS [v: WVertex];
Returns the vertex with the given index number
EdgeFromIndex: PROC [wShape: WShape, eNum: INT] RETURNS [e: WEdge];
Returns the edge with the given index number
FaceFromIndex: PROC [wShape: WShape, fNum: INT] RETURNS [f: WFace];
Returns the face with the given index number
Toplogical Set Operators
FaceContainingVertices: PROC [v1, v2: WVertex] RETURNS [WFace];
Returns a face containing both vertices
EdgeContainingVertices: PROC [v1, v2: WVertex] RETURNS [WEdge];
Returns an edge containing both vertices
VertexContainingEdges: PROC [e1, e2: WEdge] RETURNS [WVertex];
Returns a vertex containing both edge
EdgeContainingFaces: PROC [f1, f2: WFace] RETURNS [WEdge];
Returns the edge common to both faces
VertexContainingFaces: PROC [f1, f2: WFace] RETURNS [WVertex];
Returns a vertex common to both faces
Toplogical Predicates
EdgeAdjacentToFace: PROC [edge: WEdge, face: WFace] RETURNS [BOOL];
Returns TRUE if the edge is adjacent to the face
VertexAdjacentToFace: PROC [vertex: WVertex, face: WFace] RETURNS [BOOL];
Returns TRUE if the vertex is adjacent to the face
VertexAdjacentToEdge: PROC [vertex: WVertex, edge: WEdge] RETURNS [BOOL];
Returns TRUE if the vertex is adjacent to the edge
SpurVertex: PROC [vertex: WVertex] RETURNS [BOOL];
Returns TRUE if the vertex is a spur
WireEdge: PROC [edge: WEdge] RETURNS [BOOL];
Returns TRUE if the vertex is a wire
Valencies
EdgesAroundVertex: PROC [vertex: WVertex] RETURNS [numEdges: INT ¬ 0];
Returns the number of edges around the given vertex
FacesAroundVertex: PROC [vertex: WVertex] RETURNS [INT];
Returns the number of faces around the given vertex
VerticesAroundEdge: PROC [edge: WEdge] RETURNS [INT];
Returns the number of vertices around the given edge
FacesAroundEdge: PROC [edge: WEdge] RETURNS [INT];
Returns the number of faces around the given edge
VerticesAroundFace: PROC [face: WFace] RETURNS [INT];
Returns the number of vertices around the given face
EdgesAroundFace: PROC [face: WFace] RETURNS [numEdges: INT ¬ 0];
Returns the number of edges around the given face
VerticesInWShape: PROC [wShape: WShape] RETURNS [INT];
Returns the number of vertices in the entire shape
EdgesInWShape: PROC [wShape: WShape] RETURNS [INT];
Returns the number of edges in the entire shape
FacesInWShape: PROC [wShape: WShape] RETURNS [INT];
Returns the number of faces in the entire shape
Genus: PROC [wShape: WShape] RETURNS [INT];
Return the topological genus of the surface (usually 2)
Euler Operators
SplitEdge: PROC [wShape: WShape, edge: WEdge] RETURNS [newV: WVertex];
Insert a new vertex in the edge and the vertex
CollapseEdge: PROC [wShape: WShape, edge: WEdge] RETURNS [WVertex];
Shrink the edge down to one vertex
RemoveEdge: PROC [wShape: WShape, edge: WEdge] RETURNS [WFace];
Remove the edge and return the face subsuming the two old faces
InsertBridge: PROC [wShape: WShape, v1, v2: WVertex]
RETURNS [newFace: WFace ¬ NIL, newEdge: WEdge ¬ NIL];
Insert a new edge between the two vertices. Usually these were created with SplitEdge. This operation creates a new face and a new edge, both of which are returned.
RemoveVertex: PROC [wShape: WShape, v1: WVertex] RETURNS [newEdge: WEdge ¬ NIL];
Insert a new edge between the two vertices
Node Construction
NewWShape: PROC RETURNS [WShape];
Returns a new (empty) winged-edge shape
InsertVertexIntoShape: PROC [wShape: WShape, vetex: WVertex];
Insert a new vertex into the shape
InsertEdgeIntoShape: PROC [wShape: WShape, edge: WEdge];
Insert a new edge into the shape
InsertFaceIntoShape: PROC [wShape: WShape, face: WFace];
Insert a new face into the shape
DeleteWShape: PROC [wShape: WShape];
Delete the shape and all its associated data
Architectural Note
The basic architecture of this package is based on "The Winged Edge Geometry-Topology Model" by Pat Hanrahan. This title refers both to a library and the documentation that describes it (an unnumbered tech memo from the New York Institute of Technology Computer Graphics Lab). Further references to the winged-edge model are:
Baumgart, B.G. A Polyhedron Representation for Computer Vision, Proc. NCC, 1975
Baumgart, B.G. Geometric Modeling for Computer Vision, Stanford AI Project memo 249, 1974
Hanrahan, P. Creating Volume Models From Edge-Vertex Graphs, Siggraph '82, pp. 77-84
END.