G3dPolyNetImpl.mesa
Copyright Ó 1985, 1992 by Xerox Corporation. All rights reserved.
Glassner, February 25, 1991 4:51 pm PST
Jules Bloomenthal August 26, 1992 3:12 pm PDT
DIRECTORY G2dBasic, G3dVector, G3dPolyNet, G3dBasic, G3dShape, Rope, G3dNats, G3dPlane, Real;
G3dPolyNetImpl: CEDAR PROGRAM
IMPORTS G2dBasic, G3dBasic, G3dShape, G3dNats, G3dVector, G3dPlane, Real
EXPORTS G3dPolyNet
~ BEGIN
Imported Types
NatSequence:    TYPE ~ G2dBasic.NatSequence;
NatSequenceRep:   TYPE ~ G2dBasic.NatSequenceRep;
Plane:      TYPE ~ G3dPlane.Plane;
ROPE:      TYPE ~ Rope.ROPE;
Shape:     TYPE ~ G3dShape.Shape;
ShapeRep:    TYPE ~ G3dShape.ShapeRep;
Surface:     TYPE ~ G3dBasic.Surface;
Triple:     TYPE ~ G3dBasic.Triple;
Vertex:     TYPE ~ G3dShape.Vertex;
Validity:     TYPE ~ G3dShape.Validity;
VertexRep:    TYPE ~ G3dShape.VertexRep;
Poly:      TYPE ~ G3dPolyNet.Poly;
PolyRep:     TYPE ~ G3dPolyNet.PolyRep;
Vert:      TYPE ~ G3dPolyNet.Vert;
VertRep:     TYPE ~ G3dPolyNet.VertRep;
PolyNet:     TYPE ~ G3dPolyNet.PolyNet;
PolyNetRep:    TYPE ~ G3dPolyNet.PolyNetRep;
VertSequence:   TYPE ~ G3dPolyNet.VertSequence;
VertSequenceRep:  TYPE ~ G3dPolyNet.VertSequenceRep;
PolySequence:   TYPE ~ G3dPolyNet.PolySequence;
PolySequenceRep:  TYPE ~ G3dPolyNet.PolySequenceRep;
PolyNetProc:    TYPE ~ G3dPolyNet.PolyNetProc;
Error:     PUBLIC SIGNAL [reason: ROPE] = CODE;
PolyNet to/from Shape Procs
PolyNetFromShape: PUBLIC PROC [shape: Shape] RETURNS [polyNet: PolyNet] ~ {
polyNet ¬ NEW[PolyNetRep ¬ []];
FOR v: INT IN [0 .. shape.vertices.length) DO
vert: Vert ¬ NEW[VertRep ¬ [
visible: TRUE,
vertex: NEW[VertexRep ¬ shape.vertices[v]­]]];
polyNet.vertices ¬ AddToVertSequence[polyNet.vertices, vert];
ENDLOOP;
polyNet.vertices.valid ¬ shape.vertices.valid;
FOR p: INT IN [0 .. shape.surfaces.length) DO
poly: Poly ¬ NEW[PolyRep ¬ [visible: TRUE, vertices: G2dBasic.CopyNatSequence[shape.surfaces[p].vertices]]];
polyNet.polygons ¬ AddToPolySequence[polyNet.polygons, poly];
ENDLOOP;
RebuildPolyNet[polyNet];
};
ShapeFromPolyNet: PUBLIC PROC [polyNet: PolyNet] RETURNS [shape: Shape] ~ {
shape ¬ NEW[ShapeRep ¬ []];
FOR i: INT IN [0 .. polyNet.polygons.length) DO
surf: Surface ¬ [NIL, polyNet.polygons[i].vertices];
shape.surfaces ¬ G3dBasic.AddToSurfaceSequence[shape.surfaces, surf];
ENDLOOP;
FOR i: INT IN [0 .. polyNet.vertices.length) DO
shape.vertices ¬ G3dShape.AddToVertexSequence[shape.vertices, polyNet.vertices[i].vertex];
ENDLOOP;
shape.vertices.valid ¬ polyNet.vertices.valid;
};
PolyNet Processing
FindVisibleNeighborsOfPoly: PUBLIC PROC [polyNet: PolyNet, poly: INT] RETURNS [nats: NatSequence ¬ NIL] ~ {
Action: PolyNetProc ~ {
IF p1=poly AND polyNet.polygons[p0].visible THEN nats ¬ G2dBasic.AddToNatSequence[nats, p0];
};
VisitPolyNet[polyNet, Action];
};
RelinkEdge: PUBLIC PROC [polyNet: PolyNet, v0, v1, oldPoly, newPoly: INT] ~ {
FOR i: INT IN [0 .. polyNet.polygons.length) DO
IF (i # oldPoly) AND polyNet.polygons[i].visible THEN {
neighbors: NatSequence ¬ polyNet.polygons[i].neighbors;
newNeighbors: NatSequence ¬ NIL;
IF neighbors # NIL THEN FOR j: INT IN [0 .. neighbors.length) DO
IF (neighbors[j] = oldPoly) AND PolyHasEdge[polyNet.polygons[i].vertices, v0, v1]
THEN newNeighbors ¬ G2dBasic.AddToNatSequence[newNeighbors, newPoly]
ELSE newNeighbors ¬ G2dBasic.AddToNatSequence[newNeighbors, neighbors[j]];
ENDLOOP;
polyNet.polygons[i].neighbors ¬ newNeighbors;
};
ENDLOOP;
};
VisitPolyNet: PUBLIC PROC [polyNet: PolyNet, proc: PolyNetProc, clientData: REF ANY ¬ NIL] ~ {
call the proc for each [poly, neighbor-of-poly] pair in the net
FOR i: INT IN [0 .. polyNet.polygons.length) DO
neighbors: NatSequence ¬ polyNet.polygons[i].neighbors;
IF polyNet.polygons[i].visible AND neighbors#NIL THEN FOR j: INT IN [0 .. neighbors.length) DO
IF NOT proc[polyNet, i, neighbors[j], clientData] THEN RETURN;
ENDLOOP;
ENDLOOP;
};
RemovePolyFromNet: PUBLIC PROC [polyNet: PolyNet, poly: INT] ~ {
-- delete all pointers into and out of the indicated poly
FOR i: INT IN [0 .. polyNet.polygons.length) DO
neighbors: NatSequence ¬ G3dNats.RemoveNatInSequence[polyNet.polygons[i].neighbors, poly];
ENDLOOP;
polyNet.polygons[poly].neighbors ¬ NIL;
};
RebuildPolyNet: PUBLIC PROC [polyNet: PolyNet] ~ {
UpdateAllPolygonInformation[polyNet];
FOR i: INT IN [0 .. polyNet.vertices.length) DO
UpdateVertexInformation[polyNet, i];
ENDLOOP;
};
UpdateAllPolygonInformation: PUBLIC PROC [polyNet: PolyNet] ~ {
-- the easiest way to do this is to use existing code: make a shape from the polyNet, use G3dShape to make the edges for the shape, and then process the edges. This makes it expensive to process just one polygon. We can't walk the net to capture all the pairs, since we must assume one or more of the neighbor fields are invalid right now - that's why this proc has been called!
shape: Shape ¬ ShapeFromPolyNet[polyNet];
shape.edges ¬ G3dShape.MakeEdges[shape];
FOR i: INT IN [0 .. shape.surfaces.length) DO
verts: NatSequence ¬ polyNet.polygons[i].vertices;
polyNet.polygons[i].neighbors ¬ NIL;
polyNet.polygons[i].plane ¬ G3dPlane.Negate[G3dPlane.FromThreePoints[
polyNet.vertices[verts[0]].vertex.point,
polyNet.vertices[verts[1]].vertex.point,
polyNet.vertices[verts[2]].vertex.point,
TRUE]];
ENDLOOP;
FOR i: INT IN [0 .. shape.edges.length) DO
polyNet.polygons[shape.edges[i].p0].neighbors ¬
G2dBasic.AddToNatSequence[polyNet.polygons[shape.edges[i].p0].neighbors, shape.edges[i].p1];
polyNet.polygons[shape.edges[i].p1].neighbors ¬
G2dBasic.AddToNatSequence[polyNet.polygons[shape.edges[i].p1].neighbors, shape.edges[i].p0];
ENDLOOP;
};
UpdatePolygonInformation: PUBLIC PROC [polyNet: PolyNet, polyID: INT] ~ {
-- the easiest way to do this is to use existing code: make a shape from the polyNet, use G3dModel to make the edges for the shape, and then process the edges
shape: Shape ¬ ShapeFromPolyNet[polyNet];
verts: NatSequence ¬ polyNet.polygons[polyID].vertices;
shape.edges ¬ G3dShape.MakeEdges[shape];
polyNet.polygons[polyID].neighbors ¬ NIL;
polyNet.polygons[polyID].plane ¬ G3dPlane.Negate[G3dPlane.FromThreePoints[
polyNet.vertices[verts[0]].vertex.point,
polyNet.vertices[verts[1]].vertex.point,
polyNet.vertices[verts[2]].vertex.point,
TRUE]];
FOR i: INT IN [0 .. shape.edges.length) DO
IF shape.edges[i].p0 = polyID THEN polyNet.polygons[polyID].neighbors ¬
G2dBasic.AddToNatSequence[polyNet.polygons[polyID].neighbors, shape.edges[i].p1];
IF shape.edges[i].p1 = polyID THEN polyNet.polygons[polyID].neighbors ¬
G2dBasic.AddToNatSequence[polyNet.polygons[polyID].neighbors, shape.edges[i].p0];
ENDLOOP;
};
UpdateVertexInformation: PUBLIC PROC [polyNet: PolyNet, vertexID: INT] ~ {
polyNet.vertices[vertexID].polyRing ¬ GetVertexPolyRing[polyNet, vertexID];
};
GetPolygonNeighbors: PUBLIC PROC [polyNet: PolyNet, polyID: INT] RETURNS [n: NatSequence ¬ NIL] ~ {
FOR i: INT IN [0 .. polyNet.polygons.length) DO
IF polyNet.polygons[i].visible AND
G3dNats.NatInSequence[polyID, polyNet.polygons[i].neighbors] THEN
n ¬ G2dBasic.AddToNatSequence[n, i];
ENDLOOP;
};
Processing Support
GetVertexPolyRing: PROC [polyNet: PolyNet, vertexId: INT] RETURNS [ring: NatSequence¬NIL] ~ {
build the ring of all polygons sharing this vertex
oldPoly, firstPoly, currentPoly, na, nb: INT ¬ -1;
find a seed polygon
IF NOT polyNet.vertices[vertexId].visible THEN RETURN;
FOR i: INT IN [0 .. polyNet.polygons.length) DO
IF polyNet.polygons[i].visible AND G3dNats.NatInSequence[vertexId, polyNet.polygons[i].vertices] THEN {
ring ¬ G2dBasic.AddToNatSequence[ring, i];
EXIT;
};
ENDLOOP;
IF ring = NIL THEN RETURN[NIL]; -- probably nulled out of existance
find neighbors until returning here
oldPoly ¬ firstPoly ¬ ring[0];
[na, nb] ¬ GetNeighborsWithVertex[polyNet, firstPoly, vertexId];
currentPoly ¬ na;  -- choose one at random
IF currentPoly < 0 THEN RETURN [NIL];
ring ¬ G2dBasic.AddToNatSequence[ring, currentPoly];
DO
[na, nb] ¬ GetNeighborsWithVertex[polyNet, currentPoly, vertexId];
IF na=oldPoly
THEN {
IF nb = firstPoly THEN RETURN;
ring ¬ G2dBasic.AddToNatSequence[ring, nb];
oldPoly ¬ currentPoly;
currentPoly ¬ nb;
}
ELSE {
IF nb # oldPoly THEN Error["orphaned neighbor poly"];
IF na = firstPoly THEN RETURN;
ring ¬ G2dBasic.AddToNatSequence[ring, na];
oldPoly ¬ currentPoly;
currentPoly ¬ na;
};
ENDLOOP;
};
GetNeighborsWithVertex: PROC [polyNet: PolyNet, polyId, vertexId: INT] RETURNS [na, nb: INT ¬ -1] ~ {
find the exactly two neighbors of the input triangle that share this vertex
neighbors: NatSequence ¬ polyNet.polygons[polyId].neighbors;
IF neighbors = NIL THEN RETURN;
FOR i: INT IN [0 ..neighbors.length) DO
poly: Poly ¬ polyNet.polygons[neighbors[i]];
IF poly.visible AND G3dNats.NatInSequence[vertexId, poly.vertices] THEN {
IF na < 0
THEN na ¬ neighbors[i]
ELSE {
IF nb < 0
THEN nb ¬ neighbors[i]
ELSE Error["Too many neighbors share this vertex"];
};
};
ENDLOOP;
};
PolyHasEdge: PROC [poly: NatSequence, v0, v1: INT] RETURNS [BOOL] ~ {
match0, match1: BOOL ¬ FALSE;
FOR i: INT IN [0 .. poly.length) DO
IF poly[i] = v0 THEN match0 ¬ TRUE;
IF poly[i] = v1 THEN match1 ¬ TRUE;
ENDLOOP;
RETURN[match0 AND match1];
};
Topology and Geometry Tests
IsGenus0: PUBLIC PROC [polyNet: PolyNet] RETURNS [spherical: BOOL ¬ TRUE] ~ {
check that each neighbor points back
FOR i: INT IN [0 .. polyNet.polygons.length) DO
IF polyNet.polygons[i].visible THEN {
neighbors: NatSequence ¬ polyNet.polygons[i].neighbors;
IF neighbors#NIL THEN FOR j: INT IN [0 .. neighbors.length) DO
match: BOOL ¬ FALSE;
pointBack: NatSequence ¬ polyNet.polygons[neighbors[j]].neighbors;
IF pointBack#NIL THEN FOR k: INT IN [0 .. pointBack.length) DO
IF pointBack[k] = i THEN match ¬ TRUE;
ENDLOOP;
IF NOT match THEN RETURN[FALSE]; -- this neighbor doesn't point back
ENDLOOP;
};
ENDLOOP;
check that each neighbor shares an edge
FOR i: INT IN [0 .. polyNet.polygons.length) DO
IF polyNet.polygons[i].visible THEN {
neighbors: NatSequence ¬ polyNet.polygons[i].neighbors;
surf: NatSequence ¬ polyNet.polygons[i].vertices;
IF (neighbors#NIL) AND (surf#NIL) THEN FOR v: INT IN [0 .. surf.length-1) DO
v0: INT ¬ surf[v];
v1: INT ¬ surf[v+1];
gotOne: BOOL ¬ FALSE;
FOR s: INT IN [0 .. neighbors.length) DO
IF polyNet.polygons[neighbors[s]].visible THEN {
IF PolyHasEdge[polyNet.polygons[neighbors[s]].vertices, v0, v1] THEN
IF NOT gotOne
THEN gotOne ¬ TRUE
ELSE RETURN[FALSE]; -- two neighbors share this edge
};
ENDLOOP;
IF NOT gotOne THEN RETURN[FALSE]; -- no neighbors share this edge
ENDLOOP;
};
ENDLOOP;
};
ConcaveEdge: PUBLIC PROC [polyNet: PolyNet, poly0, poly1: INT] RETURNS [BOOL] ~ {
TestPoint: PROC [point: Triple, plane: Plane] RETURNS [BOOL] ~ {
returns TRUE if point is on positive half-space of poly
val: REAL ¬ G3dPlane.DistanceToPoint[point, plane];
testThresh: REAL ¬ 0.0001;  -- numerical voodoo
IF ABS[val] > testThresh
THEN RETURN [val > 0.0]
ELSE RETURN[CoPlanarFlipped[polyNet, poly0, poly1]];
};
p0: NatSequence ¬ polyNet.polygons[poly0].vertices;
p1: NatSequence ¬ polyNet.polygons[poly1].vertices;
FOR i: INT IN [0 .. p0.length) DO
dup: BOOL ¬ FALSE;
FOR j: INT IN [0 .. p1.length) DO
IF p0[i] = p1[j] THEN dup ¬ TRUE;
ENDLOOP;
IF NOT dup THEN
RETURN [TestPoint[polyNet.vertices[p0[i]].vertex.point, polyNet.polygons[poly1].plane]];
ENDLOOP;
RETURN[CoPlanarFlipped[polyNet, poly0, poly1]];
};
CoPlanar: PUBLIC PROC [polyNet: PolyNet, poly0, poly1: INT] RETURNS [BOOL ¬ FALSE] ~ {
norm0: Triple ¬ GetNormal[polyNet, poly0];
norm1: Triple ¬ GetNormal[polyNet, poly1];
flip1: Triple ¬ G3dVector.Negate[norm1];
IF EqualVectors[norm0, norm1] THEN RETURN [TRUE];
IF EqualVectors[norm0, flip1] THEN RETURN [TRUE];
};
CoPlanarFlipped: PUBLIC PROC [polyNet: PolyNet, poly0, poly1: INT] RETURNS [BOOL] ~ {
flip1: Triple ¬ G3dVector.Negate[GetNormal[polyNet, poly1]];
RETURN[EqualVectors[GetNormal[polyNet, poly0], flip1]];
}; 
EqualVectors: PROC [v0, v1: Triple, thresh: REAL ¬ .00001] RETURNS [BOOL] ~ {
dif: REAL ¬ G3dVector.Length[G3dVector.Sub[v0, v1]];
RETURN [ABS[dif] < thresh];
};
Utility
GetNormal: PUBLIC PROC [polyNet: PolyNet, polyID: INT] RETURNS [Triple] ~ {
RETURN[[
polyNet.polygons[polyID].plane.x,
polyNet.polygons[polyID].plane.y,
polyNet.polygons[polyID].plane.z]]
};
GetOffset: PUBLIC PROC [polyNet: PolyNet, polyID: INT] RETURNS [REAL] ~ {
RETURN[polyNet.polygons[polyID].plane.w]
};
CopyPolyNet: PUBLIC PROC [polyNet: PolyNet, copyVertices: BOOL ¬ FALSE] RETURNS [copy: PolyNet] ~ {
copy ¬ NEW[PolyNetRep ¬ []];
copy.vertices ¬ CopyVertSequence[polyNet.vertices, copyVertices];
copy.polygons ¬ CopyPolySequence[polyNet.polygons];
};
Poly and Vert Sequences
CopyPolySequence: PUBLIC PROC [polys: PolySequence] RETURNS [PolySequence] ~ {
copy: PolySequence ¬ NIL;
IF polys # NIL THEN {
copy ¬ NEW[PolySequenceRep[polys.length]];
copy.length ¬ polys.length;
FOR n: NAT IN [0..polys.length) DO
copy[n] ¬ NEW[PolyRep ¬ polys[n]­];
copy[n].vertices ¬ G2dBasic.CopyNatSequence[polys[n].vertices];
copy[n].neighbors ¬ G2dBasic.CopyNatSequence[polys[n].neighbors];
ENDLOOP;
};
RETURN[copy];
};
AddToPolySequence: PUBLIC PROC [polys: PolySequence, poly: Poly] RETURNS [PolySequence] ~ {
IF polys = NIL THEN polys ¬ NEW[PolySequenceRep[1]];
IF polys.length = polys.maxLength THEN polys ¬ LengthenPolySequence[polys];
polys[polys.length] ¬ poly;
polys.length ¬ polys.length+1;
RETURN[polys];
};
LengthenPolySequence: PUBLIC PROC [polys: PolySequence, amount: REAL ¬ 1.3] RETURNS [new: PolySequence] ~ {
newLength: CARDINAL ¬ Real.Ceiling[amount*polys.maxLength];
newLength ¬ MAX[newLength, 3];
new ¬ NEW[PolySequenceRep[newLength]];
FOR i: NAT IN [0..polys.length) DO new[i] ¬ polys[i]; ENDLOOP;
new.length ¬ polys.length;
};
CopyVertSequence: PUBLIC PROC [verts: VertSequence, copyData: BOOL ¬ FALSE] RETURNS [VertSequence] ~ {
copy: VertSequence ¬ NIL;
IF verts # NIL THEN {
copy ¬ NEW[VertSequenceRep[verts.length]];
copy.length ¬ verts.length;
FOR n: NAT IN [0..verts.length) DO
copy[n] ¬ NEW[VertRep ¬ verts[n]­];
IF copyData THEN copy[n].vertex ¬ NEW[VertexRep ¬ verts[n].vertex­];
ENDLOOP;
};
RETURN[copy];
};
AddToVertSequence: PUBLIC PROC [verts: VertSequence, vert: Vert] RETURNS [VertSequence] ~ {
IF verts = NIL THEN verts ¬ NEW[VertSequenceRep[1]];
IF verts.length = verts.maxLength THEN verts ¬ LengthenVertSequence[verts];
verts[verts.length] ¬ vert;
verts.length ¬ verts.length+1;
RETURN[verts];
};
LengthenVertSequence: PUBLIC PROC [verts: VertSequence, amount: REAL ¬ 1.3] RETURNS [new: VertSequence] ~ {
newLength: CARDINAL ¬ Real.Ceiling[amount*verts.maxLength];
newLength ¬ MAX[newLength, 3];
new ¬ NEW[VertSequenceRep[newLength]];
FOR i: NAT IN [0..verts.length) DO new[i] ¬ verts[i]; ENDLOOP;
new.length ¬ verts.length;
};
END.