G3dWingedEdgeImpl.mesa
Copyright Ó 1990, 1992 by Xerox Corporation. All rights reserved.
Glassner, March 10, 1990 5:07:22 pm PST
Bloomenthal, July 15, 1992 5:49 pm PDT
DIRECTORY G2dBasic, G2dVector, G3dBasic, G3dPolygon, G3dShape, G3dVector, G3dWingedEdge, IO, Rope;
G3dWingedEdgeImpl: CEDAR PROGRAM
IMPORTS G2dBasic, G2dVector, G3dBasic, G3dShape, G3dVector, IO, Rope
EXPORTS G3dWingedEdge
~ BEGIN
Types
Face:       TYPE ~ G3dShape.Face;
FaceRep:      TYPE ~ G3dShape.FaceRep;
FaceSequence:    TYPE ~ G3dShape.FaceSequence;
FaceSequenceRep:   TYPE ~ G3dShape.FaceSequenceRep;
Validity:      TYPE ~ G3dShape.Validity;
IntSequence:     TYPE ~ G3dBasic.IntSequence;
IntSequenceRep:    TYPE ~ G3dBasic.IntSequenceRep;
NatSequence:     TYPE ~ G3dBasic.NatSequence;
NatSequenceRep:    TYPE ~ G3dBasic.NatSequenceRep;
RealSequence:    TYPE ~ G3dBasic.RealSequence;
ROPE:       TYPE ~ Rope.ROPE;
Shape:      TYPE ~ G3dShape.Shape;
ShapeRep:     TYPE ~ G3dShape.ShapeRep;
Surface:      TYPE ~ G3dBasic.Surface;
SurfaceSequence:   TYPE ~ G3dBasic.SurfaceSequence;
SurfaceSequenceRep:  TYPE ~ G3dBasic.SurfaceSequenceRep;
Triple:      TYPE ~ G3dBasic.Triple;
TripleSequence:    TYPE ~ G3dBasic.TripleSequence;
Vertex:      TYPE ~ G3dShape.Vertex;
VertexRep:     TYPE ~ G3dShape.VertexRep;
VertexSequence:    TYPE ~ G3dShape.VertexSequence;
VertexSequenceRep:   TYPE ~ G3dShape.VertexSequenceRep;
WEdge:      TYPE ~ G3dWingedEdge.WEdge;
WEdgeRep:     TYPE ~ G3dWingedEdge.WEdgeRep;
WEdgeData:     TYPE ~ G3dWingedEdge.WEdgeData;
WEdgeDataRep:    TYPE ~ G3dWingedEdge.WEdgeDataRep;
WFace:      TYPE ~ G3dWingedEdge.WFace;
WFaceRep:     TYPE ~ G3dWingedEdge.WFaceRep;
WShape:      TYPE ~ G3dWingedEdge.WShape;
WShapeRep:     TYPE ~ G3dWingedEdge.WShapeRep;
WVertex:      TYPE ~ G3dWingedEdge.WVertex;
WVertexRep:     TYPE ~ G3dWingedEdge.WVertexRep;
WVertexProc:    TYPE ~ G3dWingedEdge.WVertexProc;
WEdgeProc:     TYPE ~ G3dWingedEdge.WEdgeProc;
WFaceProc:     TYPE ~ G3dWingedEdge.WFaceProc;
ClockDirection:    TYPE ~ G3dWingedEdge.ClockDirection;
Error:      PUBLIC ERROR [code: ATOM, reason: ROPE] = CODE;
WShape/Shape Conversion Procedures
ShapeFromWingedEdge: PUBLIC PROC [wShape: WShape] RETURNS [shape: Shape] ~ {
shape ¬ NEW[ShapeRep ¬ []];
shape.vertices ¬ GetVerticesFromWingedEdge[wShape];
shape.surfaces ¬ GetSurfacesFromWingedEdge[wShape];
shape.faces ¬ GetFacesFromWingedEdge[wShape];
};
WingedEdgeFromShape: PUBLIC PROC [shape: Shape] RETURNS [wShape: WShape] ~ {
localShape: Shape ¬ G3dShape.CopyShape[shape];
G3dShape.SetFaceNormals[localShape];
wShape ¬ NEW[WShapeRep ¬ []];
wShape.vertexRing ¬ VerticesFromShape[localShape];
wShape.faceRing ¬ FacesFromShape[localShape];
wShape.edgeRing ¬ EdgesFromShape[localShape, wShape];
BuildFaceEdgeRings[localShape, wShape];
BuildVertexEdgeRings[localShape, wShape];
BuildEdgeFaceAndWingPointers[localShape, wShape];
SortVertexEdges[wShape]; -- unnecessary; the edges are unsorted around vtx by def'n
};
WingedEdge From Shape Procedures
VerticesFromShape: PROC [shape: Shape] RETURNS [vRing: WVertex ¬ NIL] ~ {
IF shape.vertices.length = 0 THEN RETURN;
FOR i: INT IN [0 .. shape.vertices.length) DO
newVertex: WVertex ¬ NEW[WVertexRep ¬ []];
newVertex.basicVertex ¬ NEW[VertexRep ¬ shape.vertices[i]­];
shape.vertices[i].ref ¬ newVertex;
newVertex.index ¬ i;
vRing ¬ InsertVertexIntoRing[newVertex, vRing];
ENDLOOP;
};
EdgesFromShape: PROC [shape: Shape, wShape: WShape] RETURNS [eRing: WEdge ¬ NIL] ~ {
count: INT ¬ 0;
IF shape.surfaces.length = 0 THEN RETURN;
FOR i: INT IN [0 .. shape.surfaces.length) DO
surface: Surface ¬ shape.surfaces[i];
FOR j: INT IN [0 .. surface.vertices.length) DO
v1: NAT ¬ surface.vertices[j];
v2: NAT ¬ surface.vertices[(j+1) MOD surface.vertices.length];
v1V: WVertex ¬ NARROW[shape.vertices[v1].ref];
v2V: WVertex ¬ NARROW[shape.vertices[v2].ref];
IF GetEdgeFromVertices[v1V, v2V, eRing] = NIL THEN {
newEdge: WEdge ¬ NEW[WEdgeRep ¬ []];
newEdge.edgeData ¬ NEW[WEdgeDataRep ¬ []];
newEdge.edgeData.aVertex ¬ v1V;
newEdge.edgeData.bVertex ¬ v2V;
newEdge.edgeData.index ¬ count;
newEdge.edgeData.owner ¬ newEdge;
count ¬ count+1;
eRing ¬ InsertEdgeIntoRing[newEdge, eRing];
};
ENDLOOP;
ENDLOOP;
};
FacesFromShape: PROC [shape: Shape] RETURNS [fRing: WFace ¬ NIL] ~ {
IF shape.surfaces.length = 0 THEN RETURN;
FOR i: INT IN [0 .. shape.surfaces.length) DO
newFace: WFace ¬ NEW[WFaceRep ¬ []];
IF shape.faces # NIL THEN newFace.basicFace ¬ NEW[FaceRep ¬ shape.faces[i]­];
shape.surfaces[i].clientData ¬ newFace;
newFace.index ¬ i;
fRing ¬ InsertFaceIntoRing[newFace, fRing];
ENDLOOP;
};
BuildFaceEdgeRings: PROC [shape: Shape, wShape: WShape] ~ {
BuildFaceEdgeRing: PROC [f: WFace, surface: Surface] RETURNS [eRing: WEdge¬NIL] ~ {
FOR j: INT IN [0 .. surface.vertices.length) DO
v1: NAT ¬ surface.vertices[j];
v2: NAT ¬ surface.vertices[(j+1) MOD surface.vertices.length];
v1V: WVertex ¬ NARROW[shape.vertices[v1].ref];
v2V: WVertex ¬ NARROW[shape.vertices[v2].ref];
e: WEdge ¬ GetEdgeFromVertices[v1V, v2V, wShape.edgeRing];
newEdge: WEdge ¬ NEW[WEdgeRep ¬ []];
newEdge.edgeData ¬ e.edgeData;
eRing ¬ InsertEdgeIntoRing[newEdge, eRing];
ENDLOOP;
};
-- this is just ApplyToFaceRing but it tracks and passes the associated surface
f: WFace ¬ wShape.faceRing;
index: INT ¬ 0;
WHILE ((index = 0) OR (f # wShape.faceRing)) DO
surface: Surface ¬ shape.surfaces[index];
f.edgeRing ¬ BuildFaceEdgeRing[f, surface];
index ¬ index+1;
f ¬ f.next;
ENDLOOP;
};
BuildVertexEdgeRings: PROC [shape: Shape, wShape: WShape] ~ {
BuildVertexEdgeRing: PROC [v: WVertex] RETURNS [eRing: WEdge ¬ NIL] ~ {
-- this is just ApplyToEdgeRing but it uses the result
e: WEdge ¬ wShape.edgeRing;
didLoop: BOOL ¬ FALSE;
WHILE ((didLoop = FALSE) OR (e # wShape.edgeRing)) DO
IF e.edgeData.aVertex = v OR e.edgeData.bVertex = v THEN {
newEdge: WEdge ¬ NEW[WEdgeRep ¬ []];
newEdge.edgeData ¬ e.edgeData;
eRing ¬ InsertEdgeIntoRing[newEdge, eRing];
};
didLoop ¬ TRUE;
e ¬ e.next;
ENDLOOP;
};
-- this is just ApplyToVertexRing but it uses the result
v: WVertex ¬ wShape.vertexRing;
didLoop: BOOL ¬ FALSE;
WHILE ((didLoop = FALSE) OR (v # wShape.vertexRing)) DO
v.edgeRing ¬ BuildVertexEdgeRing[v];
didLoop ¬ TRUE;
v ¬ v.next;
ENDLOOP;
};
SortVertexEdges: PROC [wShape: WShape] ~ {
SortVertex: PROC [v: WVertex] RETURNS [eRing: WEdge ¬ NIL] ~ {
EdgeFromRingByIndex: PROC [i: INT] RETURNS [WEdge] ~ {
e: WEdge ¬ v.edgeRing;
FOR j: INT IN [0 .. i) DO e ¬ e.next; ENDLOOP;
RETURN[e];
};
FirstUnusedEdge: PROC [ns: IntSequence] RETURNS [INT] ~ {
FOR i: INT IN [0 .. es.length) DO IF es[i] >= 0 THEN RETURN[i]; ENDLOOP;
RETURN[-1];
};
MarkEdge: PROC [target: WEdge] ~ {
FOR i: INT IN [0 .. es.length) DO
IF es[i] = target.edgeData.index THEN {
es[i] ¬ -1;
RETURN;
};
ENDLOOP;
Error[$BookKeeping, "Couldn't clear desired target edge from vertex list"];
};
BackUpEdges: PROC [firstE: WEdge] RETURNS [WEdge] ~ {
newE: WEdge ¬ firstE;
nextE: WEdge ¬ firstE;
DO
IF newE.edgeData.aVertex = v
THEN nextE ¬ newE.edgeData.bCWedge
ELSE nextE ¬ newE.edgeData.aCWedge;
IF nextE.edgeData = firstE.edgeData THEN RETURN[firstE];
IF nextE = NIL THEN RETURN[newE];
newE ¬ nextE;
ENDLOOP;
};
AddToEring: PROC [firstE: WEdge] ~ {
AddEdge: PROC [e: WEdge] ~ {
newEdge: WEdge ¬ NEW[WEdgeRep ¬ e­];
eRing ¬ InsertEdgeIntoRing[newEdge, eRing];
MarkEdge[e];
};
newE: WEdge ¬ firstE;
nextE: WEdge ¬ firstE;
DO
AddEdge[newE];
IF newE.edgeData.aVertex = v
THEN nextE ¬ newE.edgeData.aCCWedge
ELSE nextE ¬ newE.edgeData.bCCWedge;
IF nextE.edgeData = firstE.edgeData THEN RETURN;
newE ¬ nextE;
ENDLOOP;
};
InitEdgeSequence: PROC RETURNS [es: IntSequence] ~ {
numEdges: INT ¬ CountEdgesAroundVertex[v];
e: WEdge ¬ v.edgeRing;
count: INT ¬ 0;
es ¬ NEW[IntSequenceRep[numEdges]];
es.length ¬ numEdges;
DO
es[count] ¬ e.edgeData.index;
count ¬ count+1;
e ¬ e.next;
IF e = v.edgeRing THEN RETURN;
ENDLOOP;
};
es: IntSequence ¬ InitEdgeSequence[];
firstBlank: INT ¬ FirstUnusedEdge[es];
WHILE firstBlank >= 0 DO
keyEdge: WEdge ¬ EdgeFromRingByIndex[firstBlank];
keyEdge ¬ BackUpEdges[keyEdge];
AddToEring[keyEdge];
firstBlank ¬ FirstUnusedEdge[es];
ENDLOOP;
};
-- this is just ApplyToVertexRing but it uses the result
v: WVertex ¬ wShape.vertexRing;
didLoop: BOOL ¬ FALSE;
WHILE ((didLoop = FALSE) OR (v # wShape.vertexRing)) DO
v.edgeRing ¬ SortVertex[v];
didLoop ¬ TRUE;
v ¬ v.next;
ENDLOOP;
};
BuildEdgeFaceAndWingPointers: PROC [shape: Shape, wShape: WShape] ~ {
WalkFace: PROC [face: WFace, surface: Surface] ~ {
FOR j: INT IN [0 .. surface.vertices.length) DO
v0: NAT ¬ surface.vertices[(j-1) MOD surface.vertices.length];
v1: NAT ¬ surface.vertices[j];
v2: NAT ¬ surface.vertices[(j+1) MOD surface.vertices.length];
v3: NAT ¬ surface.vertices[(j+2) MOD surface.vertices.length];
v0V: WVertex ¬ NARROW[shape.vertices[v0].ref];
v1V: WVertex ¬ NARROW[shape.vertices[v1].ref];
v2V: WVertex ¬ NARROW[shape.vertices[v2].ref];
v3V: WVertex ¬ NARROW[shape.vertices[v3].ref];
e: WEdge ¬ GetEdgeFromVertices[v1V, v2V, wShape.edgeRing];
ed: WEdgeData ¬ e.edgeData;
IF ed.aVertex = v1V
THEN { -- this is a clockwise edge
ed.aFace ¬ face;
ed.aCWedge ¬ GetEdgeFromVertices[v2V, v3V, wShape.edgeRing];
ed.aCCWedge ¬ GetEdgeFromVertices[v0V, v1V, wShape.edgeRing];
}
ELSE { -- this is a counter-clockwise edge
ed.bFace ¬ face;
ed.bCWedge ¬ GetEdgeFromVertices[v2V, v3V, wShape.edgeRing];
ed.bCCWedge ¬ GetEdgeFromVertices[v0V, v1V, wShape.edgeRing];
};
ENDLOOP;
};
-- this is just ApplyToFaceRing but it tracks and passes the associated surface
f: WFace ¬ wShape.faceRing;
index: INT ¬ 0;
WHILE ((index = 0) OR (f # wShape.faceRing)) DO
surface: Surface ¬ shape.surfaces[index];
WalkFace[f, surface];
index ¬ index+1;
f ¬ f.next;
ENDLOOP;
};
Shape From Winged Edge Procedures
GetVerticesFromWingedEdge: PROC [wShape: WShape] RETURNS [vs: VertexSequence] ~ {
didLoop: BOOL ¬ FALSE;
v: WVertex ¬ wShape.vertexRing;
vs ¬ NEW[VertexSequenceRep[0]];
vs.valid ¬ wShape.vertexValidities;
IF wShape.vertexRing = NIL THEN RETURN;
WHILE (NOT didLoop) OR (v # wShape.vertexRing) DO
vs ¬ G3dShape.AddToVertexSequence[vs, v.basicVertex];
v ¬ v.next;
didLoop ¬ TRUE;
ENDLOOP;
};
GetSurfacesFromWingedEdge: PROC [wShape: WShape] RETURNS [ss: SurfaceSequence] ~ {
WalkFace: PROC [face: WFace] RETURNS [ns: NatSequence ¬ NIL] ~ {
AddVertex: PROC [v: WVertex] ~ { ns ¬ G2dBasic.AddToNatSequence[ns, v.index]; };
loopCount: INT ¬ 0;
e: WEdge ¬ face.edgeRing;
n1, n2: WVertex;
o1: WVertex ¬ e.edgeData.aVertex;
o2: WVertex ¬ e.edgeData.bVertex;
IF face.edgeRing = NIL THEN RETURN;
WHILE (loopCount = 0) OR (e.edgeData # face.edgeRing.edgeData) DO
e ¬ NextEdgeAroundFaceFromEdge[e, face, cw];
IF e.edgeData = face.edgeRing.edgeData THEN EXIT;
n1 ¬ e.edgeData.aVertex;
n2 ¬ e.edgeData.bVertex;
IF loopCount=0 THEN {
SELECT TRUE FROM
(o1 = n1) OR (o1 = n2) => AddVertex[o1];
(o2 = n1) OR (o2 = n2) => AddVertex[o2];
ENDCASE => Error[$BadTopology, "These edges don't link"];
};
IF e # face.edgeRing THEN SELECT TRUE FROM
(o1 = n2) OR (o2 = n2) => AddVertex[n1];
(o1 = n1) OR (o2 = n1) => AddVertex[n2];
ENDCASE => Error[$BadTopology, "These edges don't link"];
o1 ¬ n1;
o2 ¬ n2;
loopCount ¬ loopCount+1;
ENDLOOP;
};
didLoop: BOOL ¬ FALSE;
f: WFace ¬ wShape.faceRing;
ss ¬ NEW[SurfaceSequenceRep[0]];
IF f = NIL THEN RETURN;
WHILE (NOT didLoop) OR (f # wShape.faceRing) DO
e: WEdge ¬ f.edgeRing;
surface: Surface ¬ [];
surface.vertices ¬ WalkFace[f];
ss ¬ G3dBasic.AddToSurfaceSequence[ss, surface];
f ¬ f.next;
didLoop ¬ TRUE;
ENDLOOP;
};
GetFacesFromWingedEdge: PROC [wShape: WShape] RETURNS [fs: FaceSequence] ~ {
didLoop: BOOL ¬ FALSE;
f: WFace ¬ wShape.faceRing;
fs ¬ NEW[FaceSequenceRep[0]];
fs.valid ¬ wShape.faceValidities;
IF f = NIL THEN RETURN;
WHILE (NOT didLoop) OR (f # wShape.faceRing) DO
IF f.basicFace # NIL THEN fs ¬ G3dShape.AddToFaceSequence[fs, f.basicFace];
f ¬ f.next;
didLoop ¬ TRUE;
ENDLOOP;
};
Construction Utility Procedures
InsertVertexIntoRing: PUBLIC PROC [v: WVertex, vRing: WVertex] RETURNS [WVertex] ~ {
IF vRing = NIL THEN {
v.next ¬ v.previous ¬ v;
RETURN[v];
};
v.previous ¬ vRing.previous;
v.next ¬ vRing;
vRing.previous.next ¬ v;
vRing.previous ¬ v;
RETURN[vRing];
};
InsertCopyOfVertexIntoRing: PUBLIC PROC [v: WVertex, vRing: WVertex] RETURNS [WVertex] ~ {
copy: WVertex ¬ NEW[WVertexRep ¬ v­];
RETURN[InsertVertexIntoRing[copy, vRing]];
};
InsertEdgeIntoRing: PUBLIC PROC [e: WEdge, eRing: WEdge] RETURNS [WEdge] ~ {
IF eRing = NIL THEN {
e.next ¬ e.previous ¬ e;
RETURN[e];
};
e.previous ¬ eRing.previous;
e.next ¬ eRing;
eRing.previous.next ¬ e;
eRing.previous ¬ e;
RETURN[eRing];
};
InsertCopyOfEdgeIntoRing: PUBLIC PROC [e: WEdge, eRing: WEdge] RETURNS [WEdge] ~ {
copy: WEdge ¬ NEW[WEdgeRep ¬ e­];
RETURN[InsertEdgeIntoRing[copy, eRing]];
};
InsertFaceIntoRing: PUBLIC PROC [f: WFace, fRing: WFace] RETURNS [WFace] ~ {
IF fRing = NIL THEN {
f.next ¬ f.previous ¬ f;
RETURN[f];
};
f.previous ¬ fRing.previous;
f.next ¬ fRing;
fRing.previous.next ¬ f;
fRing.previous ¬ f;
RETURN[fRing];
};
InsertCopyOfFaceIntoRing: PUBLIC PROC [f: WFace, fRing: WFace] RETURNS [WFace] ~ {
copy: WFace ¬ NEW[WFaceRep ¬ f­];
RETURN[InsertFaceIntoRing[copy, fRing]];
};
ReverseEdgeRing: PUBLIC PROC [eRing: WEdge] ~ {
e: WEdge ¬ eRing;
IF eRing = NIL THEN RETURN;
DO
tmp: WEdge ¬ e.next;
e.next ¬ e.previous;
e.previous ¬ tmp;
e ¬ tmp;
IF e = eRing THEN EXIT;
ENDLOOP;
};
SetWings: PUBLIC PROC [e1, e2: WEdge] ~ {
Given a pair of edges e1, e2 that have a common vertex, the connecting wings are set according to one of the following eight patterns (see Baumgart74, pg. 22)
[Artwork node; type 'Artwork on' to command tool]
IF e1 = NIL OR e2 = NIL THEN Error[$BadInput, "An input wing is NIL!"];
IF e1.edgeData = NIL OR e2.edgeData = NIL THEN
Error[$BadInput, "An input wing data field is NIL!"];
SELECT TRUE FROM
e1.edgeData.aVertex = e2.edgeData.aVertex => {
SELECT TRUE FROM
e1.edgeData.bFace = e2.edgeData.aFace => {
e1.edgeData.bCWedge ¬ e2.edgeData.owner;
e2.edgeData.aCCWedge ¬ e1.edgeData.owner;
};
e1.edgeData.aFace = e2.edgeData.bFace => {
e1.edgeData.aCCWedge ¬ e2.edgeData.owner;
e2.edgeData.bCWedge ¬ e1.edgeData.owner;
};
ENDCASE => Error[$BadTopology, "The input edges do not share a face"];
};
e1.edgeData.aVertex = e2.edgeData.bVertex => {
SELECT TRUE FROM
e1.edgeData.bFace = e2.edgeData.bFace => {
e1.edgeData.bCWedge ¬ e2.edgeData.owner;
e2.edgeData.bCCWedge ¬ e1.edgeData.owner;
};
e1.edgeData.aFace = e2.edgeData.aFace => {
e1.edgeData.aCCWedge ¬ e2.edgeData.owner;
e2.edgeData.aCWedge ¬ e1.edgeData.owner;
};
ENDCASE => Error[$BadTopology, "The input edges do not share a face"];
};
e1.edgeData.bVertex = e2.edgeData.aVertex => {
SELECT TRUE FROM
e1.edgeData.aFace = e2.edgeData.aFace => {
e1.edgeData.aCWedge ¬ e2.edgeData.owner;
e2.edgeData.aCCWedge ¬ e1.edgeData.owner;
};
e1.edgeData.bFace = e2.edgeData.bFace => {
e1.edgeData.bCCWedge ¬ e2.edgeData.owner;
e2.edgeData.bCWedge ¬ e1.edgeData.owner;
};
ENDCASE => Error[$BadTopology, "The input edges do not share a face"];
};
e1.edgeData.bVertex = e2.edgeData.bVertex => {
SELECT TRUE FROM
e1.edgeData.aFace = e2.edgeData.bFace => {
e1.edgeData.aCWedge ¬ e2.edgeData.owner;
e2.edgeData.bCCWedge ¬ e1.edgeData.owner;
};
e1.edgeData.bFace = e2.edgeData.aFace => {
e1.edgeData.bCCWedge ¬ e2.edgeData.owner;
e2.edgeData.aCWedge ¬ e1.edgeData.owner;
};
ENDCASE => Error[$BadTopology, "The input edges do not share a face"];
};
ENDCASE => Error[$BadInput, "The input edges do not share a common vertex"];
};
Lookup Procedures
VertexFromIndex: PUBLIC PROC [wShape: WShape, vNum: INT] RETURNS [v: WVertex] ~ {
v ¬ wShape.vertexRing;
DO
IF v.index = vNum THEN RETURN[v];
v ¬ v.next;
IF v = wShape.vertexRing THEN RETURN[NIL];
ENDLOOP;
};
EdgeFromIndex: PUBLIC PROC [wShape: WShape, eNum: INT] RETURNS [e: WEdge] ~ {
e ¬ wShape.edgeRing;
DO
IF e.edgeData.index = eNum THEN RETURN[e];
e ¬ e.next;
IF e = wShape.edgeRing THEN RETURN[NIL];
ENDLOOP;
};
FaceFromIndex: PUBLIC PROC [wShape: WShape, fNum: INT] RETURNS [f: WFace] ~ {
f ¬ wShape.faceRing;
DO
IF f.index = fNum THEN RETURN[f];
f ¬ f.next;
IF f = wShape.faceRing THEN RETURN[NIL];
ENDLOOP;
};
GetEdgeFromVertices: PROC [aV, bV: WVertex, eRing: WEdge] RETURNS [WEdge] ~ {
Match: PROC [v1, v2: WVertex, e: WEdge] RETURNS [BOOL] ~ {
RETURN[(e.edgeData.aVertex = aV AND e.edgeData.bVertex = bV) OR
(e.edgeData.aVertex = bV AND e.edgeData.bVertex = aV)];
};
e: WEdge ¬ eRing;
didLoop: BOOL ¬ FALSE;
IF e = NIL THEN RETURN [NIL];
WHILE ((NOT didLoop) OR (e # eRing)) AND (NOT Match[aV, bV, e]) DO
didLoop ¬ TRUE;
e ¬ e.next;
ENDLOOP;
IF Match[aV, bV, e]
THEN RETURN [e.edgeData.owner]
ELSE RETURN [NIL];
};
Counting Procedures
CountEdgesAroundVertex: PROC [v: WVertex] RETURNS [numEdges: INT ¬ 0] ~ {
e: WEdge ¬ v.edgeRing;
WHILE ((numEdges = 0) OR (e # v.edgeRing)) DO
numEdges ¬ numEdges+1;
e ¬ e.next;
ENDLOOP;
};
CountEdgesAroundFace: PROC [f: WFace] RETURNS [numEdges: INT ¬ 0] ~ {
e: WEdge ¬ f.edgeRing;
WHILE ((numEdges = 0) OR (e # f.edgeRing)) DO
numEdges ¬ numEdges+1;
e ¬ e.next;
ENDLOOP;
};
Debug Procedures
DebugVertexRing: PROC [vRing: WVertex] RETURNS [r: ROPE] ~ {
DebugVertex: PROC [v: WVertex] RETURNS [d: ROPE] ~ {
d ¬ IO.PutFR1["basicVertex point = %g\n", IO.int[v.index]];
d ¬ Rope.Concat[d, "edgeRing: "];
IF v.edgeRing = NIL
THEN d ¬ Rope.Concat[d, "NIL RING\n"]
ELSE {
ep: WEdge ¬ v.edgeRing;
DO
d ¬ Rope.Concat[d, DebugEdge[ep]];
ep ¬ ep.next;
IF ep.edgeData = v.edgeRing.edgeData THEN EXIT;
ENDLOOP;
};
IF v.next = NIL THEN d ¬ Rope.Concat[d, "ERROR: v.next = NIL"];
IF v.previous = NIL THEN d ¬ Rope.Concat[d, "ERROR: v.previous = NIL"];
};
vp: WVertex ¬ vRing;
r ¬ NIL;
IF vp = NIL THEN { r ¬ "empty ring"; RETURN; };
r ¬ Rope.Concat[r, DebugVertex[vp]];
vp ¬ vp.next;
WHILE vp # vRing DO
r ¬ Rope.Concat[r, DebugVertex[vp]];
vp ¬ vp.next;
ENDLOOP;
};
DebugEdge: PROC [e: WEdge, verbose: BOOL ¬ FALSE] RETURNS [d: ROPE ¬ NIL] ~ {
IF e = NIL
THEN RETURN
ELSE {
aCW: WEdge ¬ e.edgeData.aCWedge;
aCCW: WEdge ¬ e.edgeData.aCCWedge;
bCW: WEdge ¬ e.edgeData.bCWedge;
bCCW: WEdge ¬ e.edgeData.bCCWedge;
d ¬ IO.PutFR1["edge %d\n", IO.int[e.edgeData.index]];
IF verbose THEN {
d ¬ Rope.Concat[d, IO.PutFR[">>> edge vertices %d to %d -> index %g\n",
IO.int[e.edgeData.aVertex.index], IO.int[e.edgeData.bVertex.index],
IO.int[e.edgeData.index]]];
d ¬ Rope.Concat[d, IO.PutFLR["aCCW=%g aCW=%g bCCW=%g bCW=%g ",
LIST[IO.int[aCCW.edgeData.index], IO.int[aCW.edgeData.index],
IO.int[bCCW.edgeData.index], IO.int[bCW.edgeData.index]]]];
d ¬ Rope.Concat[d, IO.PutFR["aFace=%g bFace=%g\n",
IO.int[e.edgeData.aFace.index], IO.int[e.edgeData.bFace.index]]];
};
};
IF e.next = NIL THEN d ¬ Rope.Concat[d, "ERROR: e.next = NIL"];
IF e.previous = NIL THEN d ¬ Rope.Concat[d, "ERROR: e.previous = NIL"];
};
DebugFaceRing: PROC [fRing: WFace] RETURNS [r: ROPE] ~ {
DebugFace: PROC [f: WFace] RETURNS [d: ROPE] ~ {
d ¬ IO.PutFR1["face index %g\n", IO.int[f.index]];
IF f.basicFace = NIL
THEN d ¬ Rope.Concat[d, "basicFace is NIL\n"]
ELSE d ¬ Rope.Concat[d, IO.PutFR["basicFace normal = %g %g %g\n", IO.real[f.basicFace.normal.x], IO.real[f.basicFace.normal.y], IO.real[f.basicFace.normal.z]]];
d ¬ Rope.Concat[d, "edgeRing: "];
IF f.edgeRing = NIL
THEN d ¬ Rope.Concat[d, "NIL RING\n"]
ELSE {
ep: WEdge ¬ f.edgeRing;
d ¬ Rope.Concat[d, DebugEdge[ep]];
ep ¬ ep.next;
WHILE ep # f.edgeRing DO
d ¬ Rope.Concat[d, DebugEdge[ep]];
ep ¬ ep.next;
ENDLOOP;
};
IF f.next = NIL THEN d ¬ Rope.Concat[d, "ERROR: f.next = NIL"];
IF f.previous = NIL THEN d ¬ Rope.Concat[d, "ERROR: f.previous = NIL"];
};
fp: WFace ¬ fRing;
r ¬ NIL;
IF fp = NIL THEN { r ¬ "empty ring"; RETURN; };
r ¬ Rope.Concat[r, DebugFace[fp]];
fp ¬ fp.next;
WHILE fp # fRing DO
r ¬ Rope.Concat[r, DebugFace[fp]];
fp ¬ fp.next;
ENDLOOP;
};
DebugEdgeRing: PROC [eRing: WEdge] RETURNS [r: ROPE] ~ {
ep: WEdge ¬ eRing;
r ¬ NIL;
IF ep = NIL THEN { r ¬ "empty ring"; RETURN; };
r ¬ Rope.Concat[r, DebugEdge[ep, TRUE]];
ep ¬ ep.next;
WHILE ep # eRing DO
r ¬ Rope.Concat[r, DebugEdge[ep, TRUE]];
ep ¬ ep.next;
ENDLOOP;
};
Apply A Function To All Elements of A WShape
ApplyToFaces: PUBLIC PROC [wShape: WShape, ff: WFaceProc] ~ {
ApplyToFaceRing[wShape.faceRing, ff];
};
ApplyToEdges: PUBLIC PROC [wShape: WShape, ef: WEdgeProc] ~ {
ApplyToEdgeRing[wShape.edgeRing, ef];
};
ApplyToVertices: PUBLIC PROC [wShape: WShape, vf: WVertexProc] ~ {
ApplyToVertexRing[wShape.vertexRing, vf];
};
Vertex Access
NextVertexAroundFaceFromEdge: PUBLIC PROC [edge: WEdge, face: WFace, dir: ClockDirection]
RETURNS [WVertex] ~ {
e: WEdge ¬ NIL;
IF face = NIL THEN Error[$BadInput, "No face specified"];
IF edge = NIL THEN RETURN[AnyVertexOnFace[face]];
IF edge.edgeData = NIL THEN Error[$MissingData, "This edge has no data"];
SELECT TRUE FROM
edge.edgeData.aFace = face => {
SELECT dir FROM
cw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.aCWedge]];
ccw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.aCCWedge]];
ENDCASE;
};
edge.edgeData.bFace = face => {
SELECT dir FROM
cw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.bCWedge]];
ccw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.bCCWedge]];
ENDCASE;
};
ENDCASE => Error[$BadTopology, "This edge is not adjacent to this face"];
RETURN[NIL];
};
NextVertexAroundFaceFromVertex: PUBLIC PROC [vertex: WVertex, face: WFace, dir: ClockDirection]
RETURNS [WVertex] ~ {
edge: WEdge ¬ face.edgeRing;
IF face = NIL THEN Error[$BadInput, "No face specified"];
DO
IF edge.edgeData.aVertex = vertex OR edge.edgeData.bVertex = vertex THEN EXIT;
edge ¬ edge.next;
IF edge = face.edgeRing THEN EXIT;
ENDLOOP;
IF edge = face.edgeRing THEN
Error[$BadTopology, "This face does not contain this vertex"];
SELECT TRUE FROM
edge.edgeData.aFace = face => {
SELECT TRUE FROM
edge.edgeData.aVertex = vertex =>
SELECT dir FROM
cw => RETURN[edge.edgeData.bVertex];
ccw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.aCCWedge]];
ENDCASE;
edge.edgeData.bVertex = vertex =>
SELECT dir FROM
cw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.aCWedge]];
ccw => RETURN[edge.edgeData.aVertex];
ENDCASE;
ENDCASE =>
Error[$BadTopology, "This edge does not contain this vertex"];
};
edge.edgeData.bFace = face => {
SELECT TRUE FROM
edge.edgeData.aVertex = vertex =>
SELECT dir FROM
cw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.bCWedge]];
ccw => RETURN[edge.edgeData.bVertex];
ENDCASE;
edge.edgeData.bVertex = vertex =>
SELECT dir FROM
cw => RETURN[edge.edgeData.aVertex];
ccw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.bCCWedge]];
ENDCASE;
ENDCASE =>
Error[$BadTopology, "This edge does not contain this vertex"];
};
ENDCASE => Error[$BadTopology, "This edge is not adjacent to this face"];
RETURN[NIL];
};
NextVertexAroundVertex: PUBLIC PROC [vertex: WVertex, face: WFace, dir: ClockDirection]
RETURNS [WVertex] ~ {
edge: WEdge;
IF face = NIL THEN Error[$BadInput, "No face specified"];
IF vertex = NIL THEN RETURN[AnyVertexOnFace[face]];
edge ¬ EdgeUsingVertex[face.edgeRing, vertex];
SELECT TRUE FROM
edge.edgeData.aFace = face => {
SELECT TRUE FROM
vertex = edge.edgeData.aVertex =>
SELECT dir FROM
cw => RETURN[edge.edgeData.bVertex];
ccw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.aCCWedge]];
ENDCASE;
vertex = edge.edgeData.bVertex =>
SELECT dir FROM
cw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.aCWedge]];
ccw => RETURN[edge.edgeData.aVertex];
ENDCASE;
ENDCASE => Error[$BadTopology, "Edge does not contain vertex"];
};
edge.edgeData.bFace = face => {
SELECT TRUE FROM
vertex = edge.edgeData.aVertex =>
SELECT dir FROM
cw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.bCWedge]];
ccw => RETURN[edge.edgeData.bVertex];
ENDCASE;
vertex = edge.edgeData.bVertex =>
SELECT dir FROM
cw => RETURN[edge.edgeData.aVertex];
ccw => RETURN[VertexNotOnFirstEdge[edge, edge.edgeData.bCCWedge]];
ENDCASE;
ENDCASE => Error[$BadTopology, "Edge does not contain vertex"];
};
ENDCASE => Error[$BadTopology, "This edge is not adjacent to this face"];
RETURN[NIL];
};
VertexAcrossEdge: PUBLIC PROC [vertex: WVertex, edge: WEdge]
RETURNS [WVertex] ~ {
IF edge = NIL THEN Error[$BadInput, "No edge specified"];
IF vertex = NIL THEN {
IF edge.edgeData = NIL THEN Error[$MissingData, "This edge has no data"];
RETURN[edge.edgeData.aVertex];
};
SELECT TRUE FROM
edge.edgeData.aVertex = vertex => RETURN[edge.edgeData.bVertex];
edge.edgeData.bVertex = vertex => RETURN[edge.edgeData.aVertex];
ENDCASE => Error[$BadTopology, "This vertex is not on this edge"];
};
Edge Access
NextEdgeAroundFaceFromEdge: PUBLIC PROC
[edge: WEdge, face: WFace, dir: ClockDirection] RETURNS [WEdge] ~ {
IF face = NIL THEN Error[$BadInput, "No face specified"];
IF edge = NIL THEN RETURN[AnyEdgeOnFace[face]];
SELECT TRUE FROM
edge.edgeData.aFace = face => {
SELECT dir FROM
cw => RETURN[edge.edgeData.aCWedge];
ccw => RETURN[edge.edgeData.aCCWedge];
ENDCASE;
};
edge.edgeData.bFace = face => {
SELECT dir FROM
cw => RETURN[edge.edgeData.bCWedge];
ccw => RETURN[edge.edgeData.bCCWedge];
ENDCASE;
};
ENDCASE => Error[$BadTopology, "This edge is not adjacent to this face"];
RETURN[NIL];
};
NextEdgeAroundVertex: PUBLIC PROC
[vertex: WVertex, edge: WEdge, dir: ClockDirection] RETURNS [WEdge] ~ {
didLoop: BOOL ¬ FALSE;
e: WEdge;
IF vertex = NIL THEN Error[$BadInput, "No vertex specified"];
IF edge = NIL THEN RETURN[AnyEdgeOnVertex[vertex]];
e ¬ vertex.edgeRing;
WHILE (NOT didLoop) OR (e # vertex.edgeRing) DO
IF e.edgeData = edge.edgeData THEN RETURN[e.next];
e ¬ e.next;
didLoop ¬ TRUE;
ENDLOOP;
Error[$BadTopology, "This edge is not adjacent to this vertex"];
};
NextEdgeAroundFaceFromVertex: PUBLIC PROC
[vertex: WVertex, face: WFace, dir: ClockDirection] RETURNS [WEdge] ~ {
edge: WEdge;
IF face = NIL THEN Error[$BadInput, "No face specified"];
IF vertex = NIL THEN RETURN[AnyEdgeOnFace[face]];
edge ¬ EdgeUsingVertex[face.edgeRing, vertex];
SELECT TRUE FROM
edge.edgeData.aFace = face => {
SELECT TRUE FROM
vertex = edge.edgeData.aVertex =>
SELECT dir FROM
cw => RETURN[edge];
ccw => RETURN[edge.edgeData.aCCWedge];
ENDCASE;
vertex = edge.edgeData.bVertex =>
SELECT dir FROM
cw => RETURN[edge.edgeData.aCWedge];
ccw => RETURN[edge];
ENDCASE;
ENDCASE => Error[$BadTopology, "Edge does not contain vertex"];
};
edge.edgeData.bFace = face => {
SELECT TRUE FROM
vertex = edge.edgeData.aVertex =>
SELECT dir FROM
cw => RETURN[edge.edgeData.bCWedge];
ccw => RETURN[edge];
ENDCASE;
vertex = edge.edgeData.bVertex =>
SELECT dir FROM
cw => RETURN[edge];
ccw => RETURN[edge.edgeData.bCCWedge];
ENDCASE;
ENDCASE => Error[$BadTopology, "Edge does not contain vertex"];
};
ENDCASE => Error[$BadTopology, "This edge is not adjacent to this face"];
RETURN[NIL];
};
Face Access
NextFaceAroundEdge: PUBLIC PROC [vertex: WVertex, edge: WEdge, dir: ClockDirection]
RETURNS [WFace] ~ {
IF edge = NIL THEN Error[$BadInput, "No edge specified"];
IF vertex = NIL THEN RETURN[AnyFaceOnVertex[vertex]];
SELECT dir FROM
cw => RETURN [edge.edgeData.aFace];
ccw => RETURN [edge.edgeData.bFace];
ENDCASE;
RETURN [NIL];
};
NextFaceAroundVertex: PUBLIC PROC [vertex: WVertex, face: WFace, dir: ClockDirection]
RETURNS [WFace] ~ {
NextFaceAroundVertex finds any edge that is on this face and vertex (call this edge e), and then performs one of the following eight cases to determine the next face around the vertex. In the figure, the input vertex is one common to all three shapes; it is marked with a circle. The input face is shaded in grey. Edge e is indicated with an arrow. The horizontal rows show the desired face marked with a star; the triangle is the next face clockwise, the rectangle is the next face counterclockwise. In each case we return the face across an edge with respect to the input face; the correct edge to use is shown in bold. In four cases that edge is just e; the other four cases each use one of the wings. The legends refer to the position of the passed-in vertex and face with respect to e. Each case is marked with the name of the edge used to find the next face, opposite the input face; this edge is marked in bold.
edge: WEdge;
IF face = NIL THEN RETURN[AnyFaceOnVertex[vertex]];
edge ¬ EdgeUsingVertex[face.edgeRing, vertex];
SELECT TRUE FROM
edge.edgeData.aFace = face => {
face: WFace ¬ edge.edgeData.aFace;
SELECT TRUE FROM
vertex = edge.edgeData.aVertex =>
SELECT dir FROM
cw => RETURN[FaceAcrossEdge[edge.edgeData.aCCWedge, face]];
ccw => RETURN[FaceAcrossEdge[edge, face]];
ENDCASE;
vertex = edge.edgeData.bVertex =>
SELECT dir FROM
cw => RETURN[FaceAcrossEdge[edge, face]];
ccw => RETURN[FaceAcrossEdge[edge.edgeData.aCWedge, face]];
ENDCASE;
ENDCASE => Error[$BadTopology, "Edge does not contain vertex"];
};
edge.edgeData.bFace = face => {
face: WFace ¬ edge.edgeData.bFace;
SELECT TRUE FROM
vertex = edge.edgeData.aVertex =>
SELECT dir FROM
cw => RETURN[FaceAcrossEdge[edge, face]];
ccw => RETURN[FaceAcrossEdge[edge.edgeData.bCWedge, face]];
ENDCASE;
vertex = edge.edgeData.bVertex =>
SELECT dir FROM
cw => RETURN[FaceAcrossEdge[edge.edgeData.bCCWedge, face]];
ccw => RETURN[FaceAcrossEdge[edge, face]];
ENDCASE;
ENDCASE => Error[$BadTopology, "Edge does not contain vertex"];
};
ENDCASE => Error[$BadTopology, "This edge is not adjacent to this face"];
RETURN[NIL];
};
FaceAcrossEdge: PUBLIC PROC [edge: WEdge, face: WFace] RETURNS [WFace] ~ {
IF face=NIL THEN RETURN[AnyFaceOnEdge[edge]];
IF edge.edgeData.aFace = face THEN RETURN [edge.edgeData.bFace];
IF edge.edgeData.bFace = face THEN RETURN [edge.edgeData.aFace];
Error[$BadInput, "This edge does not contain this face"];
};
Ring Looping Procedures
ApplyToVertexRing: PUBLIC PROC [vRing: WVertex, vf: WVertexProc] ~ {
didLoop: BOOL ¬ FALSE;
v: WVertex ¬ vRing;
IF vRing = NIL THEN RETURN;
WHILE (NOT didLoop) OR (v # vRing) DO
vf[v];
v ¬ v.next;
didLoop ¬ TRUE;
ENDLOOP;
};
ApplyToEdgeRing: PUBLIC PROC [eRing: WEdge, ef: WEdgeProc] ~ {
didLoop: BOOL ¬ FALSE;
e: WEdge ¬ eRing;
IF eRing = NIL THEN RETURN;
WHILE (NOT didLoop) OR (e # eRing) DO
ef[e];
e ¬ e.next;
didLoop ¬ TRUE;
ENDLOOP;
};
ApplyToFaceRing: PUBLIC PROC [fRing: WFace, ff: WFaceProc] ~ {
didLoop: BOOL ¬ FALSE;
f: WFace ¬ fRing;
IF fRing = NIL THEN RETURN;
WHILE (NOT didLoop) OR (f # fRing) DO
ff[f];
f ¬ f.next;
didLoop ¬ TRUE;
ENDLOOP;
};
Miscellaneous
InvertEdge: PUBLIC PROC [e: WEdge] ~ {
ed: WEdgeData ¬ e.edgeData;
tmpE: WEdge;
tmpV: WVertex;
tmpF: WFace;
tmpV ¬ ed.aVertex; ed.aVertex ¬ ed.bVertex; ed.bVertex ¬ tmpV;
tmpF ¬ ed.aFace; ed.aFace ¬ ed.bFace; ed.bFace ¬ tmpF;
tmpE ¬ ed.aCWedge; ed.aCWedge ¬ ed.bCWedge; ed.bCWedge ¬ tmpE;
tmpE ¬ ed.aCCWedge; ed.aCCWedge ¬ ed.bCCWedge; ed.bCCWedge ¬ tmpE;
};
EvertEdge: PUBLIC PROC [e: WEdge] ~ {
ed: WEdgeData ¬ e.edgeData;
tmpE: WEdge;
tmpF: WFace;
tmpF ¬ ed.aFace; ed.aFace ¬ ed.bFace; ed.bFace ¬ tmpF;
tmpE ¬ ed.aCWedge; ed.aCWedge ¬ ed.bCWedge; ed.bCWedge ¬ tmpE;
tmpE ¬ ed.aCCWedge; ed.aCCWedge ¬ ed.bCCWedge; ed.bCWedge ¬ tmpE;
};
InvertWShape: PUBLIC PROC [wShape: WShape] ~ {
ApplyToEdgeRing[wShape.edgeRing, InvertEdge];
};
EvertWShape: PUBLIC PROC [wShape: WShape] ~ {
ApplyToEdgeRing[wShape.edgeRing, EvertEdge];
};
Adjacencies
AnyVertexOnFace: PUBLIC PROC [face: WFace] RETURNS [WVertex] ~ {
IF face.edgeRing = NIL THEN Error[$MissingEdges, "This face has no edges"];
IF face.edgeRing.edgeData = NIL THEN Error[$MissingEdges, "This edge has no data"];
RETURN[face.edgeRing.edgeData.aVertex];
};
AnyEdgeOnFace: PUBLIC PROC [face: WFace] RETURNS [WEdge] ~ {
IF face.edgeRing = NIL THEN Error[$MissingEdges, "This face has no edges"];
RETURN[face.edgeRing];
};
AnyEdgeOnVertex: PUBLIC PROC [vertex: WVertex] RETURNS [WEdge] ~ {
IF vertex.edgeRing = NIL THEN Error[$MissingEdges, "This vertex has no edges"];
RETURN[vertex.edgeRing];
};
AnyFaceOnVertex: PUBLIC PROC [vertex: WVertex] RETURNS [WFace] ~ {
IF vertex.edgeRing = NIL THEN Error[$MissingEdges, "This vertex has no edges"];
RETURN[vertex.edgeRing.edgeData.aFace];
};
AnyFaceOnEdge: PUBLIC PROC [edge: WEdge] RETURNS [WFace] ~ {
IF edge.edgeData = NIL THEN Error[$MissingData, "This edge has no data"];
RETURN[edge.edgeData.aFace];
};
VertexNotOnFirstEdge: PUBLIC PROC [e1, e2: WEdge] RETURNS [WVertex] ~ {
IF e1 = NIL OR e1.edgeData = NIL OR e2 = NIL OR e2.edgeData = NIL THEN
Error[$BadInput, "Incoming edges incomplete"];
IF e1.edgeData.aVertex = e2.edgeData.aVertex THEN RETURN[e2.edgeData.bVertex];
IF e1.edgeData.aVertex = e2.edgeData.bVertex THEN RETURN[e2.edgeData.aVertex];
IF e1.edgeData.bVertex = e2.edgeData.aVertex THEN RETURN[e2.edgeData.bVertex];
IF e1.edgeData.bVertex = e2.edgeData.bVertex THEN RETURN[e2.edgeData.aVertex];
Error[$BadInput, "These edges have no common vertex"];
};
EdgeUsingVertex: PUBLIC PROC [eRing: WEdge, v: WVertex] RETURNS [WEdge] ~ {
didLoop: BOOL ¬ FALSE;
e: WEdge ¬ eRing;
IF eRing = NIL THEN Error[$BadInput, "Edge ring empty"];
WHILE (NOT didLoop) OR (e # eRing) DO
IF e.edgeData.aVertex = v OR e.edgeData.bVertex = v THEN RETURN [e];
e ¬ e.next;
didLoop ¬ TRUE;
ENDLOOP;
Error[$BadInput, "No edge in the ring includes this vertex"];
};
Toplogical Set Operators
FaceContainingVertices: PUBLIC PROC [v1, v2: WVertex] RETURNS [WFace] ~ {
This is a dumb O(n2) algorithm, but for small numbers of edges on each vertex it should be okay. It would be nice to replace it with something more clever someday.
FaceAInV2: PROC [face: WFace] RETURNS [BOOL] ~ {
doLoop2: BOOL ¬ TRUE;
loop2E: WEdge ¬ v2.edgeRing;
WHILE doLoop2 OR (loop2E # v2.edgeRing) DO
IF (loop2E.edgeData.aFace = face) OR (loop2E.edgeData.bFace = face)
THEN RETURN[TRUE];
doLoop2 ¬ FALSE;
loop2E ¬ loop2E.next;
ENDLOOP;
RETURN[FALSE];
};
doLoop1: BOOL ¬ TRUE;
loop1E: WEdge ¬ v1.edgeRing;
WHILE doLoop1 OR (loop1E # v1.edgeRing) DO
IF FaceAInV2[loop1E.edgeData.aFace] THEN RETURN [loop1E.edgeData.aFace];
IF FaceAInV2[loop1E.edgeData.bFace] THEN RETURN [loop1E.edgeData.bFace];
doLoop1 ¬ FALSE;
loop1E ¬ loop1E.next;
ENDLOOP;
Error[$BadTopology, "These vertices have no face in common"];
};
EdgeContainingVertices: PUBLIC PROC [v1, v2: WVertex] RETURNS [WEdge] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
VertexContainingEdges: PUBLIC PROC [e1, e2: WEdge] RETURNS [WVertex] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
EdgeContainingFaces: PUBLIC PROC [f1, f2: WFace] RETURNS [WEdge] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
VertexContainingFaces: PUBLIC PROC [f1, f2: WFace] RETURNS [WVertex] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
Toplogical Predicates
EdgeAdjacentToFace: PUBLIC PROC [edge: WEdge, face: WFace] RETURNS [BOOL] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
VertexAdjacentToFace: PUBLIC PROC [vertex: WVertex, face: WFace] RETURNS [BOOL] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
VertexAdjacentToEdge: PUBLIC PROC [vertex: WVertex, edge: WEdge] RETURNS [BOOL] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
SpurVertex: PUBLIC PROC [vertex: WVertex] RETURNS [BOOL] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
WireEdge: PUBLIC PROC [edge: WEdge] RETURNS [BOOL] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
Valencies
EdgesAroundVertex: PUBLIC PROC [vertex: WVertex] RETURNS [numEdges: INT ¬ 0] ~ {
e: WEdge ¬ vertex.edgeRing;
WHILE ((numEdges = 0) OR (e # vertex.edgeRing)) DO
numEdges ¬ numEdges+1;
e ¬ e.next;
ENDLOOP;
};
FacesAroundVertex: PUBLIC PROC [vertex: WVertex] RETURNS [INT] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
VerticesAroundEdge: PUBLIC PROC [edge: WEdge] RETURNS [INT] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
FacesAroundEdge: PUBLIC PROC [edge: WEdge] RETURNS [INT] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
VerticesAroundFace: PUBLIC PROC [face: WFace] RETURNS [INT] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
EdgesAroundFace: PUBLIC PROC [face: WFace] RETURNS [numEdges: INT ¬ 0] ~ {
e: WEdge ¬ face.edgeRing;
DO
numEdges ¬ numEdges+1;
e ¬ e.next;
IF e = face.edgeRing THEN EXIT;
ENDLOOP;
};
VerticesInWShape: PUBLIC PROC [wShape: WShape] RETURNS [numVerts: INT ¬ 0] ~ {
v: WVertex ¬ wShape.vertexRing;
IF v = NIL THEN RETURN;
DO
numVerts ¬ numVerts+1;
v ¬ v.next;
IF v = wShape.vertexRing THEN EXIT;
ENDLOOP;
};
EdgesInWShape: PUBLIC PROC [wShape: WShape] RETURNS [numEdges: INT ¬ 0] ~ {
e: WEdge ¬ wShape.edgeRing;
IF e = NIL THEN RETURN;
DO
numEdges ¬ numEdges+1;
e ¬ e.next;
IF e = wShape.edgeRing THEN EXIT;
ENDLOOP;
};
FacesInWShape: PUBLIC PROC [wShape: WShape] RETURNS [numFaces: INT ¬ 0] ~ {
f: WFace ¬ wShape.faceRing;
IF f = NIL THEN RETURN;
WHILE ((numFaces = 0) OR (f # wShape.faceRing)) DO
numFaces ¬ numFaces+1;
f ¬ f.next;
ENDLOOP;
};
Genus: PUBLIC PROC [wShape: WShape] RETURNS [genus: INT ¬ 2] ~ {
numVertices: INT ¬ VerticesInWShape[wShape];
numEdges: INT ¬ EdgesInWShape[wShape];
numFaces: INT ¬ FacesInWShape[wShape];
genus ¬ numFaces - numEdges + numVertices;
};
Node Construction
NewWShape: PUBLIC PROC RETURNS [WShape] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
InsertVertexIntoShape: PUBLIC PROC [wShape: WShape, vetex: WVertex] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
InsertEdgeIntoShape: PUBLIC PROC [wShape: WShape, edge: WEdge] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
InsertFaceIntoShape: PUBLIC PROC [wShape: WShape, face: WFace] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
DeleteWShape: PUBLIC PROC [wShape: WShape] ~ {
IF wShape = NIL THEN RETURN;
DeleteVertexRing[wShape.vertexRing];
DeleteEdgeRing[wShape.edgeRing];
DeleteFaceRing[wShape.faceRing];
};
Euler Operators
SplitEdge: PUBLIC PROC [wShape: WShape, edge: WEdge] RETURNS [newV: WVertex] ~ {
Insert a new vertex in the center of this edge and add a new edge colinear with the input edge. The wings for the edges are updated at the new vertex.
The following diagram shows the order of interconnect of the links. Links marked with P are inherited from the parent configuration. Links marked with a * represent a duplication of the indicated edge data structure (though not the data it points to). The diagrom follows the one above; the bold edge and vertex on the right side are the new elements.
[Artwork node; type 'Artwork on' to command tool]
Step 1: Create the edge and its data structures
newEdge: WEdge ¬ NEW[WEdgeRep ¬ []];
newEdge.edgeData ¬ NEW[WEdgeDataRep ¬ edge.edgeData­];
newEdge.edgeData.owner ¬ newEdge;
newEdge.edgeData.index ¬ EdgesInWShape[wShape];
Step 2: Create the vertex and its data structures
newV ¬ NEW[WVertexRep ¬ []];
newV.index ¬ VerticesInWShape[wShape];
newV.basicVertex ¬
InterpolateVertices[edge.edgeData.aVertex.basicVertex, edge.edgeData.bVertex.basicVertex];
Step 3: Hook the edge into the object edge ring
wShape.edgeRing ¬ InsertEdgeIntoRing[newEdge, wShape.edgeRing];
Step 4: Hook the vertex into the object edge ring
wShape.vertexRing ¬ InsertVertexIntoRing[newV, wShape.vertexRing];
Step 5: Hook the new edge into the edge rings for both faces
edge.edgeData.aFace.edgeRing ¬ InsertCopyOfEdgeIntoRing[newEdge, edge.edgeData.aFace.edgeRing];
edge.edgeData.bFace.edgeRing ¬ InsertCopyOfEdgeIntoRing[newEdge, edge.edgeData.bFace.edgeRing];
Step 6: Point the new vertex at the two edges
newV.edgeRing ¬ InsertCopyOfEdgeIntoRing[edge, NIL];
newV.edgeRing ¬ InsertCopyOfEdgeIntoRing[newEdge, newV.edgeRing];
Step 7: Set up the starting vertex of the new edge
newEdge.edgeData.aVertex ¬ newV;
Step 8: Direct the old edge to the new Vertex
edge.edgeData.bVertex ¬ newV;
Step 9: Hook back the old bVertex into the new edge
newEdge.edgeData.bVertex.edgeRing ¬ ReplaceEdgeInRing[edge, newEdge, newEdge.edgeData.bVertex.edgeRing];
Step 10: Connect the aCW wings
SetWings[newEdge, edge.edgeData.aCWedge];
Step 11: Connect the bCCW wings
SetWings[newEdge, edge.edgeData.bCCWedge];
Step 12: Connect the back wings of the new edge to the old edge
newEdge.edgeData.aCCWedge ¬ newEdge.edgeData.bCWedge ¬ edge;
Step 13: Connect the front wings of the old edge to the new edge
edge.edgeData.aCWedge ¬ edge.edgeData.bCCWedge ¬ newEdge;
};
CollapseEdge: PUBLIC PROC [wShape: WShape, edge: WEdge] RETURNS [WVertex] ~ {
remove the edge and one of its vertices, and move all edges into the deleted vertex to the other vertex
[Artwork node; type 'Artwork on' to command tool]
Error[$Unimplented, "This routine is unimplemented"];
};
RemoveEdge: PUBLIC PROC [wShape: WShape, edge: WEdge] RETURNS [WFace] ~ {
Remove the edge and return the face subsuming the two old faces
[Artwork node; type 'Artwork on' to command tool]
face: WFace ¬ edge.edgeData.aFace;
newRing, edgeLoop: WEdge;
step 1: Delete the pointer from vertex a to the edge
DeleteEdgeFromRing[edge, edge.edgeData.aVertex.edgeRing];
step 2: Delete the pointer from vertex b to the edge
DeleteEdgeFromRing[edge, edge.edgeData.bVertex.edgeRing];
step 3: Repoint all edges pointing to face b to point to face a
edgeLoop ¬ edge.edgeData.bFace.edgeRing;
DO
IF edgeLoop.edgeData # edge.edgeData THEN
IF edgeLoop.edgeData.aFace = edge.edgeData.bFace
THEN edgeLoop.edgeData.aFace ¬ edge.edgeData.aFace
ELSE edgeLoop.edgeData.bFace ¬ edge.edgeData.aFace;
edgeLoop ¬ edgeLoop.next;
IF edgeLoop = edge.edgeData.bFace.edgeRing THEN EXIT;
ENDLOOP;
Step 4: Build the new edge ring for face a
newRing ¬ NIL;
edgeLoop ¬ edge.edgeData.aFace.edgeRing;
DO
IF edgeLoop.edgeData # edge.edgeData THEN
newRing ¬ InsertCopyOfEdgeIntoRing[edgeLoop, newRing];
edgeLoop ¬ edgeLoop.next;
IF edgeLoop = edge.edgeData.aFace.edgeRing THEN EXIT;
ENDLOOP;
edgeLoop ¬ edge.edgeData.bFace.edgeRing;
DO
IF edgeLoop.edgeData # edge.edgeData THEN
newRing ¬ InsertCopyOfEdgeIntoRing[edgeLoop, newRing];
edgeLoop ¬ edgeLoop.next;
IF edgeLoop = edge.edgeData.bFace.edgeRing THEN EXIT;
ENDLOOP;
DeleteEdgeRing[edge.edgeData.aFace.edgeRing];
edge.edgeData.aFace.edgeRing ¬ newRing;
Step 5: Link the old wings on aVertex
SetWings[edge.edgeData.bCCWedge, edge.edgeData.aCWedge];
Step 6: Link the old wings on bVertex
SetWings[edge.edgeData.aCCWedge, edge.edgeData.bCWedge];
Step 7: Delete bFace from object
DeleteFaceFromRing[edge.edgeData.bFace, wShape.faceRing];
Step 8: Delete edge from object
edge.edgeData.owner ¬ NIL;
DeleteEdgeFromRing[edge, wShape.edgeRing];
RETURN[face];
};
InsertBridge: PUBLIC PROC [wShape: WShape, v1, v2: WVertex] RETURNS [newFace: WFace ¬ NIL, newEdge: WEdge ¬ NIL] ~ {
Insert a new edge between two vertices. The edge is directed from v1 to v2. The order of updating the appropriate links is shown below. A * indicates that a copy of the indicated edge is created (but not the data it points to). The new edge is shown in bold. Steps 9 and 11 are in parentheses; they have been subsumed into steps 18 and 19, respectively. Links labeled with P are inherited from the parent configuration.
[Artwork node; type 'Artwork on' to command tool]
FindWings: PROC ~ { -- find edges ej, ek, er, es and set them
GetPairOfEdges: PROC [targetV: WVertex] RETURNS [WEdge, WEdge] ~ {
face: WFace ¬ FaceContainingVertices [v1, v2];
edge: WEdge ¬ AnyEdgeOnFace[face];
lastEdge: WEdge;
WHILE edge.edgeData.aVertex # targetV AND edge.edgeData.bVertex # targetV DO
edge ¬ NextEdgeAroundFaceFromEdge[edge, face, cw];
ENDLOOP;
edge ¬ NextEdgeAroundFaceFromEdge[edge, face, cw];
IF edge.edgeData.aVertex # targetV AND edge.edgeData.bVertex # targetV
THEN edge ¬ NextEdgeAroundFaceFromEdge[edge, face, ccw];
lastEdge ¬ NextEdgeAroundFaceFromEdge[edge, face, ccw];
RETURN[lastEdge, edge];
};
[ek, er] ¬ GetPairOfEdges[v1];
[es, ej] ¬ GetPairOfEdges[v2];
};
newRing, edgeLoop: WEdge ¬ NIL;
ej, ek, er, es: WEdge ¬ NIL;
oldFace: WFace ¬ FaceContainingVertices [v1, v2];
Setup: Find the four wings of the new edge
FindWings[];
Step 1: Create the new edge
newEdge ¬ NEW[WEdgeRep ¬ []];
newEdge.edgeData ¬ NEW[WEdgeDataRep ¬ []];
newEdge.edgeData.owner ¬ newEdge;
newEdge.edgeData.index ¬ EdgesInWShape[wShape];
Step 2: Add the new edge to the object's edge ring
wShape.edgeRing ¬ InsertEdgeIntoRing[newEdge, wShape.edgeRing];
Step 3: Create the new face
newFace ¬ NEW[WFaceRep ¬ []];
newFace.index ¬ FacesInWShape[wShape];
Step 4: Add the new face to the object's face ring
wShape.faceRing ¬ InsertFaceIntoRing[newFace, wShape.faceRing];
Step 5: Assign the first vertex to the new edge's tail
newEdge.edgeData.aVertex ¬ v1;
Step 6: Assign the second vertex to the new edge's head
newEdge.edgeData.bVertex ¬ v2;
Step 7: Insert the new edge into the edge-list at the head vertex
v2.edgeRing ¬ InsertCopyOfEdgeIntoRing[newEdge, v2.edgeRing];
Step 8: Insert the new edge into the edge-list at the tail vertex
v1.edgeRing ¬ InsertCopyOfEdgeIntoRing[newEdge, v1.edgeRing];
Step 9: Link the new edge to the new face
newEdge.edgeData.bFace ¬ newFace;
Step 10: Link the new edge to the old face
newEdge.edgeData.aFace ¬ oldFace;
Step 11: Build the edge ring for the new face
edgeLoop ¬ er;
DO
newFace.edgeRing ¬
InsertCopyOfEdgeIntoRing[edgeLoop, newFace.edgeRing];
IF edgeLoop = es THEN EXIT;
edgeLoop ¬ NextEdgeAroundFaceFromEdge[edgeLoop, oldFace, cw];
ENDLOOP;
Step 12: Set the edges around the new face to point to the new face
edgeLoop ¬ newFace.edgeRing;
DO
IF edgeLoop.edgeData.aFace = oldFace
THEN edgeLoop.edgeData.aFace ¬ newFace
ELSE edgeLoop.edgeData.bFace ¬ newFace;
edgeLoop ¬ edgeLoop.next;
IF edgeLoop = newFace.edgeRing THEN EXIT;
ENDLOOP;
Step 13: Build the edge ring for the old face, and point the edges at the new face
edgeLoop ¬ ej;
DO
newRing ¬ InsertCopyOfEdgeIntoRing[edgeLoop, newRing];
IF edgeLoop = ek THEN EXIT;
edgeLoop ¬ NextEdgeAroundFaceFromEdge[edgeLoop, oldFace, cw];
ENDLOOP;
Step 14: Link the new face to the new edge
newFace.edgeRing ¬
InsertCopyOfEdgeIntoRing[newEdge, newFace.edgeRing];
Step 15: Link the old edge to the new face
newRing ¬ InsertCopyOfEdgeIntoRing[newEdge, newRing];
Step 16: Set the new edge's aCW wings
SetWings[newEdge, ej];
Step 17: Set the new edge's bCCW wings
SetWings[newEdge, es];
Step 18: Set the new edge's bCW wings
SetWings[newEdge, er];
Step 19: Set the new edge's aCCW wings
SetWings[newEdge, ek];
Cleanup: Reclaim old face edge ring, and replace old face edge ring with new
DeleteEdgeRing[oldFace.edgeRing];
oldFace.edgeRing ¬ newRing;
};
RemoveVertex: PUBLIC PROC [wShape: WShape, v1: WVertex] RETURNS [newEdge: WEdge ¬ NIL] ~ {
Error[$Unimplemented, "This routine doesn't do anything yet"];
};
Utility
InterpolateVertices: PROC [va, vb: Vertex] RETURNS [newV: Vertex] ~ {
newV ¬ NEW[VertexRep ¬ va­];
newV.point ¬ G3dVector.Midpoint[va.point, vb.point];
newV.normal ¬ G3dVector.Midpoint[va.normal, vb.normal];
newV.color ¬ G3dVector.Midpoint[va.color, vb.color];
newV.texture ¬ G2dVector.Midpoint[va.texture, vb.texture];
newV.transmittance ¬ (va.transmittance + vb.transmittance)/2.0;
};
ReplaceEdgeInRing: PROC [old, new, ring: WEdge, deleteOld: BOOL ¬ TRUE] RETURNS [newCopy: WEdge] ~ {
e: WEdge ¬ ring;
newCopy ¬ NEW[WEdgeRep ¬ new­];
IF e = NIL THEN RETURN;
DO
IF e.edgeData = old.edgeData THEN {
newCopy.previous ¬ e.previous;
newCopy.next ¬ e.next;
e.previous.next ¬ newCopy;
e.next.previous ¬ newCopy;
e.next ¬ e.previous ¬ NIL;
RETURN;
};
e ¬ e.next;
IF e.edgeData = ring.edgeData THEN
Error[$BadTopology, "This edge is not in this ring"];
ENDLOOP;
};
DeleteVertexFromRing: PROC [old, ring: WVertex, deleteOld: BOOL ¬ TRUE] ~ {
v: WVertex ¬ ring;
IF v = NIL THEN RETURN;
DO
IF v = old THEN {
v.previous.next ¬ v.next;
v.next.previous ¬ v.previous;
v.next ¬ v.previous ¬ NIL;
RETURN;
};
v ¬ v.next;
IF v = ring THEN EXIT;
ENDLOOP;
};
DeleteEdgeFromRing: PROC [old, ring: WEdge, deleteOld: BOOL ¬ TRUE] ~ {
e: WEdge ¬ ring;
IF e = NIL THEN RETURN;
DO
IF e.edgeData = old.edgeData THEN {
e.previous.next ¬ e.next;
e.next.previous ¬ e.previous;
e.next ¬ e.previous ¬ NIL;
RETURN;
};
e ¬ e.next;
IF e = ring THEN EXIT;
ENDLOOP;
};
DeleteFaceFromRing: PROC [old, ring: WFace, deleteOld: BOOL ¬ TRUE] ~ {
f: WFace ¬ ring;
IF f = NIL THEN RETURN;
DO
IF f = old THEN {
f.previous.next ¬ f.next;
f.next.previous ¬ f.previous;
f.next ¬ f.previous ¬ NIL;
RETURN;
};
f ¬ f.next;
IF f = ring THEN EXIT;
ENDLOOP;
};
DeleteVertexRing: PROC [ring: WVertex] ~ {
Cut the links and let the GC pick up the (now non-circular) storage
IF ring = NIL THEN RETURN;
IF ring.previous # NIL THEN ring.previous.next ¬ NIL;
IF ring.next # NIL THEN ring.next.previous ¬ NIL;
ring.next ¬ ring.previous ¬ NIL;
};
DeleteEdgeRing: PROC [ring: WEdge] ~ {
Cut the links and let the GC pick up the (now non-circular) storage
IF ring = NIL THEN RETURN;
IF ring.previous # NIL THEN ring.previous.next ¬ NIL;
IF ring.next # NIL THEN ring.next.previous ¬ NIL;
ring.next ¬ ring.previous ¬ NIL;
ring.edgeData ¬ NIL;
};
DeleteFaceRing: PROC [ring: WFace] ~ {
Cut the links and let the GC pick up the (now non-circular) storage
IF ring = NIL THEN RETURN;
IF ring.previous # NIL THEN ring.previous.next ¬ NIL;
IF ring.next # NIL THEN ring.next.previous ¬ NIL;
ring.next ¬ ring.previous ¬ NIL;
};
END.