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
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;
};