<<>> <> <> <> <> <<>> DIRECTORY G2dBasic, G3dVector, G3dPolyNet, G3dBasic, G3dShape, Rope, G3dNats, G3dPlane, Real; G3dPolyNetImpl: CEDAR PROGRAM IMPORTS G2dBasic, G3dBasic, G3dShape, G3dNats, G3dVector, G3dPlane, Real EXPORTS G3dPolyNet ~ BEGIN <> 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; <> 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; }; <> 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] ~ { <> 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; }; <> GetVertexPolyRing: PROC [polyNet: PolyNet, vertexId: INT] RETURNS [ring: NatSequence¬NIL] ~ { <> oldPoly, firstPoly, currentPoly, na, nb: INT ¬ -1; <> 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 <> 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] ~ { <> 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]; }; <> IsGenus0: PUBLIC PROC [polyNet: PolyNet] RETURNS [spherical: BOOL ¬ TRUE] ~ { <> 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; <> 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] ~ { <> 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]; }; <> 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]; }; <> 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.