<<>> <> <> <> DIRECTORY G2dBasic, G3dBasic, G3dOctree, G3dPolygon, G3dMatrix, G3dVector, ImplicitDefs, ImplicitPoints, ImplicitPolygons, ImplicitSurface, MessageWindow, IO, Real, Rope, RuntimeError; ImplicitPolygonsImpl: CEDAR PROGRAM IMPORTS G2dBasic, G3dBasic, G3dOctree, G3dPolygon, G3dMatrix, G3dVector, ImplicitPoints, ImplicitSurface, IO, MessageWindow, Real, Rope, RuntimeError EXPORTS ImplicitPolygons ~ BEGIN Triple: TYPE ~ G3dBasic.Triple; NatSequence: TYPE ~ G3dBasic.NatSequence; NatSequenceRep: TYPE ~ G3dBasic.NatSequenceRep; SurfaceSequence: TYPE ~ G3dBasic.SurfaceSequence; SurfaceSequenceRep: TYPE ~ G3dBasic.SurfaceSequenceRep; TripleSequence: TYPE ~ G3dBasic.TripleSequence; TripleSequenceRep: TYPE ~ G3dBasic.TripleSequenceRep; Matrix: TYPE ~ G3dMatrix.Matrix; Viewport: TYPE ~ G3dMatrix.Viewport; Corner: TYPE ~ G3dOctree.Corner; Corners: TYPE ~ G3dOctree.Corners; Cross: TYPE ~ G3dOctree.Cross; CrossedEdge: TYPE ~ G3dOctree.CrossedEdge; CrossedEdges: TYPE ~ G3dOctree.CrossedEdges; CrossPolygonProc: TYPE ~ G3dOctree.CrossPolygonProc; CrossSequence: TYPE ~ G3dOctree.CrossSequence; CrossSequenceRep: TYPE ~ G3dOctree.CrossSequenceRep; Cube: TYPE ~ G3dOctree.Cube; CubeProc: TYPE ~ G3dOctree.CubeProc; Direction: TYPE ~ G3dOctree.Direction; Edge: TYPE ~ G3dOctree.Edge; Face: TYPE ~ G3dOctree.Face; Octant: TYPE ~ G3dOctree.Octant; ThreeEdges: TYPE ~ G3dOctree.ThreeEdges; TwoOctants: TYPE ~ G3dOctree.TwoOctants; PolygonProc: TYPE ~ G3dPolygon.PolygonProc; PolygonOkProc: TYPE ~ ImplicitDefs.PolygonOkProc; Surface: TYPE ~ ImplicitDefs.Surface; ValueProc: TYPE ~ ImplicitDefs.ValueProc; ROPE: TYPE ~ Rope.ROPE; maxNTriples: CARDINAL ~ ImplicitDefs.maxNTriples; maxNNats: CARDINAL ~ ImplicitDefs.maxNNats; <> BoundsFault: ERROR ~ RuntimeError.BoundsFault; CrossPolygonizeCube: PUBLIC PROC [ cube: Cube, crossPolygonProc: CrossPolygonProc, scratchCrossSequence: CrossSequence ¬ NIL, recurseTrackFace: BOOL ¬ TRUE] RETURNS [result: ATOM ¬ $Normal] ~ { <> <> <> IF ImplicitPoints.IsCrossed[cube] AND NOT ImplicitPoints.IsOutOfRange[cube] THEN { AddCrossToPolygon: PROC [crossedEdge: CrossedEdge] ~ { <> cross: Cross ¬ ImplicitPoints.CrossFromCrossedEdge[crossedEdge]; IF NOT cross.ok THEN nBadVertices ¬ nBadVertices+1; <> IF scratchCrossSequence.length = scratchCrossSequence.maxLength THEN { old: CrossSequence ¬ scratchCrossSequence; scratchCrossSequence ¬ NEW[CrossSequenceRep[2*scratchCrossSequence.length]]; FOR i: INT IN [0..old.length) DO scratchCrossSequence[i] ¬ old[i]; ENDLOOP; scratchCrossSequence.length ¬ old.length; }; scratchCrossSequence[scratchCrossSequence.length] ¬ cross; scratchCrossSequence.length ¬ scratchCrossSequence.length+1; }; RecursiveTrackFace: PROC [cube: Cube, face: Face, edge: Edge] RETURNS [Edge] ~ { <> <> <<(recursively if necessary) around the next level's face, as shown below, until the next>> <> << [Artwork node; type 'Artwork on' to command tool] >> <> <<>> dFace: Direction ~ G3dOctree.DirectionFromFace[face]; dFaceOpp: Direction ~ G3dOctree.OppositeDirection[dFace]; corners: Corners ~ cube.corners; octs: TwoOctants ~ G3dOctree.EdgeOctants[edge]; mid: Corner ~ cube.kids[octs.o0].corners[octs.o1]; octant: Octant ¬ IF mid.inside = corners[octs.o0].inside THEN octs.o1 ELSE IF mid.inside = corners[octs.o1].inside THEN octs.o0 ELSE IF mid.inside THEN octs.o1 ELSE octs.o0; -- edge anomaly DO kid: Cube ¬ cube.kids[octant]; edges: ThreeEdges ~ G3dOctree.EdgesFromOctant[octant]; <> crossedEdges: CrossedEdges ~ ImplicitPoints.CubeCrossedEdges[kid]; IF NOT kid.terminal THEN edge ¬ RecursiveTrackFace[kid, face, edge] ELSE { start: Edge ¬ edge; DO edge ¬ G3dOctree.NextCCWEdge[edge, face]; -- CCW tracking! IF edge = start THEN ERROR; IF crossedEdges[edge].cIn # NIL THEN EXIT; ENDLOOP; AddCrossToPolygon[crossedEdges[edge]]; }; IF edge = edges.e0 OR edge = edges.e1 OR edge = edges.e2 THEN RETURN[edge] ELSE { <> dEdge: Direction ¬ G3dOctree.DirectionFromEdge[edge]; dOctant: Direction ¬ G3dOctree.DirectionFromOctant[octant]; d: Direction ¬ G3dOctree.AddDirection[dEdge, dFaceOpp]; dOctant ¬ G3dOctree.AddDirection[dOctant, d]; dOctant ¬ G3dOctree.AddDirection[dOctant, d]; octant ¬ G3dOctree.OctantFromDirection[dOctant]; edge ¬ G3dOctree.OppositeEdge[edge, face]; } ENDLOOP; }; NextCrossedEdge: PROC [edge: Edge] RETURNS [Edge] ~ { <> face: Face ~ G3dOctree.FaceFromEdgeOctant[edge, crossedEdges[edge].oOut]; neighbor: Cube ~ G3dOctree.FaceNeighbor[cube, face]; IF recurseTrackFace AND neighbor # NIL AND NOT neighbor.terminal THEN { <> oppFace: Face ~ G3dOctree.OppositeFace[face]; invEdge: Edge ~ G3dOctree.InverseEdge[edge, face]; IF result = $Normal THEN result ¬ $RecurseTracked; edge ¬ G3dOctree.InverseEdge[ RecursiveTrackFace[neighbor, oppFace, invEdge], oppFace]; } ELSE { start: Edge ¬ edge; DO edge ¬ G3dOctree.NextCWEdge[edge, face]; IF crossedEdges[edge].cIn # NIL THEN EXIT; IF edge = start THEN ERROR RecurseError; ENDLOOP; AddCrossToPolygon[crossedEdges[edge]]; }; RETURN[edge]; }; Inner: PROC RETURNS [BOOL] ~ { done: ARRAY Edge OF BOOL ¬ ALL[FALSE]; nBadVertices ¬ 0; FOR edge: Edge IN Edge DO IF crossedEdges[edge].cIn # NIL AND NOT done[edge] THEN { e, start: Edge ¬ edge; scratchCrossSequence.length ¬ 0; DO e ¬ NextCrossedEdge[e ! RecurseError => GOTO recurseError]; done[e] ¬ TRUE; IF e = start THEN EXIT; ENDLOOP; IF nBadVertices = scratchCrossSequence.length THEN RETURN[TRUE]; <> <> IF NOT crossPolygonProc[nPolygon, scratchCrossSequence] THEN RETURN[TRUE]; nPolygon ¬ nPolygon+1; }; ENDLOOP; RETURN[TRUE]; EXITS recurseError => RETURN[FALSE]; }; RecurseError: ERROR = CODE; nBadVertices, nPolygon: INT ¬ 0; <> crossedEdges: CrossedEdges ~ ImplicitPoints.CubeCrossedEdges[cube]; IF scratchCrossSequence = NIL OR scratchCrossSequence.maxLength < 100 THEN scratchCrossSequence ¬ NEW[CrossSequenceRep[100]]; IF NOT Inner[] THEN { recurseTrackFace ¬ FALSE; result ¬ $RecurseFailed; [] ¬ Inner[]; }; }; }; PolygonizeCube: PUBLIC PROC [ cube: Cube, polygonProc: PolygonProc, scratchPolygon: NatSequence ¬ NIL, recurseTrackFace: BOOL ¬ TRUE] RETURNS [result: ATOM ¬ $Normal] ~ { crossPolygonProc: CrossPolygonProc ~ { FOR n: INT IN [0..polygon.length) DO scratchPolygon[n] ¬ polygon[n].id; ENDLOOP; scratchPolygon.length ¬ polygon.length; [] ¬ polygonProc[nPolygon, scratchPolygon]; }; crossSequence: CrossSequence ¬ G3dOctree.ObtainCrossSequence[]; IF scratchPolygon = NIL OR scratchPolygon.maxLength < 100 THEN scratchPolygon ¬ NEW[NatSequenceRep[100]]; result ¬ CrossPolygonizeCube[cube, crossPolygonProc, crossSequence, recurseTrackFace]; G3dOctree.ReleaseCrossSequence[crossSequence]; }; SetSurfacePolygons: PUBLIC PROC [ surface: Surface, root: Cube, triangulate: BOOL ¬ FALSE, valueProc: ValueProc ¬ NIL, threshold: REAL ¬ 0.0, cubeProc: CubeProc ¬ NIL, polygonOkProc: PolygonOkProc ¬ NIL, clientData: REF ANY ¬ NIL] RETURNS [message: ROPE] ~ { TriangulateAbort: ERROR = CODE; TerminalCubeProc: CubeProc ~ { <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<};>> AddPolygonToSurface: PROC [polygon: NatSequence] ~ { CheckLength: PROC [n: INT] ~ { IF CARD[polys.length+n+1] >= polys.maxLength THEN polys ¬ G2dBasic.LengthenNatSequence[polys ! RuntimeError.BoundsFault, Real.RealException => { AddPolysToEndOfSurfaceList[polys]; -- first, store full sequence polys ¬ NEW[NatSequenceRep[1000]]; -- now, start new sequence CONTINUE; }]; }; AddPolygon: PROC [polygon: NatSequence] ~ { surface.nPolygons ¬ surface.nPolygons+1; CheckLength[polygon.length]; polys ¬ G2dBasic.AddToNatSequence[polys, polygon.length]; FOR n: INT IN [0..polygon.length) DO polys ¬ G2dBasic.AddToNatSequence[polys, polygon[n]]; ENDLOOP; }; AddTriangle: PROC [i1, i2, i3: INT] ~ { surface.nPolygons ¬ surface.nPolygons+1; CheckLength[3]; polys ¬ G2dBasic.AddToNatSequence[polys, 3]; polys ¬ G2dBasic.AddToNatSequence[polys, i1]; polys ¬ G2dBasic.AddToNatSequence[polys, i2]; polys ¬ G2dBasic.AddToNatSequence[polys, i3]; }; IF polygon.length > 3 AND triangulate AND valueProc # NIL THEN { v1: REAL; center, vector, point: Triple ¬ []; FOR i: INT IN [0..polygon.length) DO center ¬ G3dVector.Add[center, surface.vertices[polygon[i]].point]; ENDLOOP; point ¬ center ¬ G3dVector.Div[center, REAL[polygon.length]]; v1 ¬ valueProc[center, clientData]; vector ¬ ImplicitPoints.GetPointNormal[center, valueProc, v1, delta, clientData]; vector ¬ G3dVector.Mul[vector, delta]; IF (v1 ¬ valueProc[center, clientData]) < 0 THEN vector ¬ G3dVector.Negate[vector]; FOR i: INT IN [0..100) DO v2: REAL ¬ valueProc[point ¬ G3dVector.Add[point, vector], clientData]; IF (v2 > 0.0) # (v1 > 0.0) THEN { p: Triple ¬ ImplicitSurface.SegmentConverge[center, point, v1, v2, valueProc, threshold, clientData].point; n: Triple ¬ ImplicitPoints.GetPointNormal[ p, valueProc, valueProc[p, clientData], delta, clientData]; vid: INT ¬ ImplicitPoints.AddSurfaceVertex[p, n, surface]; FOR j: INT IN [0..polygon.length) DO AddTriangle[vid, polygon[j], polygon[(j+1) MOD polygon.length]]; ENDLOOP; EXIT; }; REPEAT FINISHED => { MessageWindow.Append["can't triangulate "]; AddPolygon[polygon]; }; ENDLOOP; } ELSE AddPolygon[polygon]; }; StorePolygon: PolygonProc ~ { IF polygonOkProc # NIL THEN { scratchPoints.length ¬ scratchPolygon.length; FOR i: INT IN [0..scratchPolygon.length) DO scratchPoints[i] ¬ surface.vertices[scratchPolygon[i]].point; ENDLOOP; IF NOT polygonOkProc[scratchPoints, clientData] THEN RETURN; }; SELECT nPolygon FROM 0 => { length0 ¬ polygon.length; AddPolygonToSurface[polygon]; cube.refAny ¬ polygon; IF cubeProc # NIL AND NOT cubeProc[cube] THEN ERROR TriangulateAbort; }; <<1 => Finesse[length0, polygon];>> ENDCASE; }; length0: INT; delta: REAL ¬ IF triangulate AND valueProc # NIL THEN 0.01*cube.size ELSE 0.0; SELECT PolygonizeCube[cube, StorePolygon, scratchPolygon] FROM $RecurseTracked => nRecursiveTrackFaces ¬ nRecursiveTrackFaces+1; $RecurseFailed => nRecurseFailures ¬ nRecurseFailures+1; ENDCASE; }; AddPolysToEndOfSurfaceList: PROC [polys: NatSequence] ~ { IF surface.polygons = NIL THEN surface.polygons ¬ LIST[polys] ELSE FOR l: LIST OF NatSequence ¬ surface.polygons, l.rest DO IF l.rest = NIL THEN {l.rest ¬ LIST[polys]; EXIT}; ENDLOOP; }; nRecursiveTrackFaces, nRecurseFailures: INT ¬ 0; scratchPolygon: NatSequence ¬ NEW[NatSequenceRep[24]]; scratchPoints: TripleSequence ¬ NEW[TripleSequenceRep[24]]; polys: NatSequence ¬ NEW[NatSequenceRep[MIN[maxNNats, MAX[1, surface.vertices.length]]]]; G3dOctree.ApplyToTerminal[root, TerminalCubeProc ! TriangulateAbort => {message ¬ Rope.Concat[message, " *aborted, "]; CONTINUE}; < {message ¬ Rope.Cat[message, " *polygons limited, "]; CONTINUE}>> ]; AddPolysToEndOfSurfaceList[polys]; message ¬ IO.PutFR["%g%g polygons", IO.rope[message], IO.int[surface.nPolygons]]; <> <> }; <> ApplyToSurfacePolygons: PUBLIC PROC [surface: Surface, polygonProc: PolygonProc] ~ { IF surface # NIL AND surface.polygons # NIL THEN { nPolygon: INT ¬ 0; polygon: NatSequence ¬ NEW[NatSequenceRep[100]]; FOR l: LIST OF NatSequence ¬ surface.polygons, l.rest WHILE l # NIL DO index: CARDINAL ¬ 0; polygons: NatSequence ~ l.first; WHILE index < polygons.length DO polygon.length ¬ polygons[index]; index ¬ index+1; FOR n: INT IN [0..polygon.length) DO polygon[n] ¬ polygons[index]; index ¬ index+1; ENDLOOP; IF NOT polygonProc[nPolygon, polygon] THEN RETURN; nPolygon ¬ nPolygon+1; ENDLOOP; ENDLOOP; }; }; ApplyToFrontFacingPolygons: PUBLIC PROC [ surface: Surface, view: Matrix, viewport: Viewport, polygonProc: PolygonProc] ~ { abort: ERROR = CODE; Inner: PolygonProc ~ { <> do: BOOL ¬ SELECT TRUE FROM nPolygon >= surface.faceNormals.length => TRUE, persp => NOT G3dVector.FrontFacingWithPerspective[ surface.faceNormals[nPolygon], surface.faceCenters[nPolygon], inverse], ENDCASE => NOT G3dVector.FrontFacingNoPerspective[surface.faceNormals[nPolygon], view]; IF do AND NOT polygonProc[nPolygon, polygon] THEN ERROR abort; }; inverse: Matrix; persp: BOOL ¬ G3dMatrix.HasPerspective[view]; IF persp THEN inverse ¬ G3dMatrix.Invert[view, G3dMatrix.ObtainMatrix[]]; IF ImplicitSurface.VerticesOK[surface, view, viewport] AND ImplicitSurface.FaceNormalsCentersOK[surface] THEN ApplyToSurfacePolygons[surface, Inner ! abort => CONTINUE]; G3dMatrix.ReleaseMatrix[inverse]; }; SetFaceNormalsCenters: PUBLIC PROC [surface: Surface, setNormals, setCenters: BOOL ¬ TRUE] ~ { IF surface # NIL AND surface.polygons # NIL AND (setNormals OR setCenters) THEN { points: TripleSequence ~ NEW[TripleSequenceRep[24]]; normals: TripleSequence ¬ surface.faceNormals; centers: TripleSequence ¬ surface.faceCenters; polygonProc: PolygonProc ~ { points.length ¬ polygon.length; FOR n: INT IN [0..points.length) DO points[n] ¬ surface.vertices[polygon[n]].point; ENDLOOP; IF setNormals THEN normals ¬ G3dBasic.AddToTripleSequence[normals, G3dPolygon.PolygonNormal[points]]; IF setCenters THEN centers ¬ G3dBasic.AddToTripleSequence[centers, G3dPolygon.PolygonCenter[points]]; }; IF setNormals AND (normals = NIL OR normals.maxLength < surface.nPolygons) THEN normals ¬ NEW[TripleSequenceRep[MIN[maxNTriples, surface.nPolygons]]]; IF setCenters AND (centers = NIL OR centers.maxLength < surface.nPolygons) THEN centers ¬ NEW[TripleSequenceRep[MIN[maxNTriples, surface.nPolygons]]]; ApplyToSurfacePolygons[surface, polygonProc ! BoundsFault => CONTINUE]; surface.faceNormals ¬ normals; surface.faceCenters ¬ centers; }; }; DecodePolygons: PUBLIC PROC [surface: Surface] RETURNS [polygons: SurfaceSequence] ~ { IF surface # NIL AND surface.polygons # NIL THEN { Decoder: PolygonProc ~ { poly: NatSequence ¬ NEW[NatSequenceRep[polygon.length]]; polygons[nPolygon] ¬ [NIL, poly]; poly.length ¬ polygon.length; FOR n: INT IN [0..polygon.length) DO poly[n] ¬ polygon[n]; ENDLOOP; nPolygon ¬ nPolygon+1; }; nPolygon: INT ¬ 0; polygons ¬ NEW[SurfaceSequenceRep[surface.nPolygons]]; polygons.length ¬ surface.nPolygons; ApplyToSurfacePolygons[surface, Decoder]; }; }; END. .. <<>> maxTripoints: CARDINAL = (LAST[CARDINAL]-4-SIZE[TripointSequenceRep[0]])/SIZE[Tripoint]; nTripoints: CARDINAL ¬ MIN[maxTripoints, MAX[1, 2*nPoints-4]]; FOR n: INT IN [1..poly.length-2] DO surface.tripoints ¬ AddTripoint[surface.tripoints, [poly[n+1], poly[n], poly[0]]]; ENDLOOP; SetFaceNormals: PUBLIC PROC [surface: Surface] ~ { IF surface # NIL AND surface.tripoints # NIL AND surface.vertices # NIL THEN { num: INT ¬ surface.tripoints.length; surface.faceNx ¬ NEW[RealSequenceRep[num]]; surface.faceNy ¬ NEW[RealSequenceRep[num]]; surface.faceNz ¬ NEW[RealSequenceRep[num]]; surface.faceNx.length ¬ surface.faceNy.length ¬ surface.faceNz.length ¬ num; FOR n: INT IN [0..num) DO p0: Triple ~ surface.vertices[surface.tripoints[n].i0].point; p1: Triple ~ surface.vertices[surface.tripoints[n].i1].point; p2: Triple ~ surface.vertices[surface.tripoints[n].i2].point; v: Triple ~ G3dPolygon.TriangleNormal[p0, p1, p2]; surface.faceNx[n] ¬ v.x; surface.faceNy[n] ¬ v.y; surface.faceNz[n] ¬ v.z; ENDLOOP; }; }; AddTripoint: PUBLIC PROC [tripoints: TripointSequence, tripoint: Tripoint] RETURNS [TripointSequence] ~ { IF tripoints.length >= tripoints.maxLength THEN tripoints ¬ G3dBasic.LengthenTripointSequence[tripoints]; tripoints[tripoints.length] ¬ tripoint; tripoints.length ¬ tripoints.length+1; RETURN[tripoints]; }; NTripoints: PUBLIC PROC [surface: Surface] RETURNS [INTEGER] ~ { RETURN[IF surface = NIL OR surface.tripoints = NIL THEN 0 ELSE surface.tripoints.length]; }; <> <> <> <<>> <> <> <> <<>> <> <<3 => AddTripoint[poly[0], poly[1], poly[2] ! BoundsFault => GOTO TriangleLimit];>> <<> 3 => {>> <> <> < GOTO TriangleLimit]>> < GOTO TriangleLimit];>> <<};>> <> <<>> <> <> <> <<{>> <> <> <> <> <> < 0.0) = (bPot > 0.0)>> <> < 0.0) = (bPot > 0.0)>> <> <> <> <> <> <<};>> <<}>> <<};>> <<>> <> <> <> <> <> <> <<};>> <<>> <> <> <<};>> <<>> <> <> <> <> <<};>> <<>> <> <<(this didn't make much improvement, so the working code is kept simpler.)>> FOR edge: Edge IN Edge DO IF crossedEdges[edge].cIn # NIL AND NOT done[edge] THEN { <> e, start: Edge ¬ edge; poly.length ¬ 0; DO e ¬ NextCWEdgeCrossed[e]; poly[poly.length] ¬ GetVertexId[crossedEdges[e] ! BoundsFault => GOTO PointsLimit]; poly.length ¬ poly.length+1; done[e] ¬ TRUE; IF e = start THEN EXIT; ENDLOOP; <> <> <> <> < 3 DO>> <> <> <> <> <> <<};>> <> <> <> < max THEN {n1 ¬ n; max ¬ lengths[n]};>> <> <> <> <> < lengths[n2]>> < GOTO TriangleLimit]>> < GOTO TriangleLimit];>> <> < GOTO TriangleLimit];>> FOR n: INT IN [0..poly.length-2] DO NewTriangle[poly[0], poly[n], poly[n+1] ! BoundsFault => GOTO TriangleLimit]; ENDLOOP; }; REPEAT PointsLimit => NULL; TriangleLimit => trianglesLimited ¬ TRUE; ENDLOOP; <<>>