<<>> <> <> <> DIRECTORY G3dBasic, G3dMatrix, G3dOctree, G3dPolygon, G3dShape, G3dVector, ImplicitDefs, ImplicitPoints, ImplicitPolygons, ImplicitSurface, IO, Rope; ImplicitPointsImpl: CEDAR PROGRAM IMPORTS G3dMatrix, G3dOctree, G3dPolygon, G3dShape, G3dVector, IO, ImplicitPolygons, ImplicitSurface EXPORTS ImplicitPoints ~ BEGIN PairSequence: TYPE ~ G3dBasic.PairSequence; PairSequenceRep: TYPE ~ G3dBasic.PairSequenceRep; RealSequence: TYPE ~ G3dBasic.RealSequence; RealSequenceRep: TYPE ~ G3dBasic.RealSequenceRep; Triple: TYPE ~ G3dBasic.Triple; TripleSequence: TYPE ~ G3dBasic.TripleSequence; TripleSequenceRep: TYPE ~ G3dBasic.TripleSequenceRep; Matrix: TYPE ~ G3dMatrix.Matrix; Viewport: TYPE ~ G3dMatrix.Viewport; Corner: TYPE ~ G3dOctree.Corner; Cross: TYPE ~ G3dOctree.Cross; CrossArray: TYPE ~ G3dOctree.CrossArray; CrossedEdge: TYPE ~ G3dOctree.CrossedEdge; CrossedEdges: TYPE ~ G3dOctree.CrossedEdges; CrossRep: TYPE ~ G3dOctree.CrossRep; Cube: TYPE ~ G3dOctree.Cube; CubeProc: TYPE ~ G3dOctree.CubeProc; Edge: TYPE ~ G3dOctree.Edge; Face: TYPE ~ G3dOctree.Face; Octant: TYPE ~ G3dOctree.Octant; CornerProc: TYPE ~ G3dOctree.CornerProc; Direction: TYPE ~ G3dOctree.Direction; TwoCorners: TYPE ~ G3dOctree.TwoCorners; TwoOctants: TYPE ~ G3dOctree.TwoOctants; PolygonProc: TYPE ~ G3dPolygon.PolygonProc; Vertex: TYPE ~ G3dShape.Vertex; VertexRep: TYPE ~ G3dShape.VertexRep; VertexSequence: TYPE ~ G3dShape.VertexSequence; VertexSequenceRep: TYPE ~ G3dShape.VertexSequenceRep; ColorProc: TYPE ~ ImplicitDefs.ColorProc; EdgeMode: TYPE ~ ImplicitDefs.EdgeMode; NormalProc: TYPE ~ ImplicitDefs.NormalProc; Surface: TYPE ~ ImplicitDefs.Surface; Target: TYPE ~ ImplicitDefs.Target; TextureProc: TYPE ~ ImplicitDefs.TextureProc; ValueProc: TYPE ~ ImplicitDefs.ValueProc; VertexOkProc: TYPE ~ ImplicitDefs.VertexOkProc; ROPE: TYPE ~ Rope.ROPE; origin: Triple ~ G3dBasic.origin; maxNVertices: CARDINAL ~ ImplicitDefs.maxNVertices; NoCrossedEdge: PUBLIC ERROR = CODE; <> ValueNotSet: PUBLIC ERROR = CODE; IsOutOfRange: PUBLIC PROC [cube: Cube] RETURNS [BOOL] ~ { FOR o: Octant IN [Octant.FIRST..Octant.LAST] DO c: Corner ¬ cube.corners[o]; IF cube.corners[o].outOfRange THEN RETURN[TRUE]; ENDLOOP; RETURN[FALSE]; }; IsCrossed: PUBLIC PROC [cube: Cube] RETURNS [BOOL] ~ { c: Corner ¬ cube.corners[lbn]; inside: BOOL ¬ c.inside; IF NOT c.valueSet THEN ERROR ValueNotSet; FOR o: Octant IN [SUCC[Octant.FIRST]..Octant.LAST] DO c: Corner ¬ cube.corners[o]; IF NOT c.valueSet THEN ERROR ValueNotSet; IF c.inside # inside THEN RETURN[TRUE]; ENDLOOP; RETURN[FALSE]; }; CubeCrossedEdges: PUBLIC PROC [cube: Cube] RETURNS [crossedEdges: CrossedEdges] ~ { Test: PROC [e: Edge] ~ { Inner: PROC [o0, o1: Octant] ~ { c0: Corner ~ cube.corners[o0]; c1: Corner ~ cube.corners[o1]; IF c0.outOfRange OR c1.outOfRange THEN RETURN; IF c0.inside THEN {IF NOT c1.inside THEN crossedEdges[e] ¬ [c0, c1, o0, o1]} ELSE {IF c1.inside THEN crossedEdges[e] ¬ [c1, c0, o1, o0]}; }; octants: TwoOctants ~ G3dOctree.EdgeOctants[e]; Inner[octants.o0, octants.o1]; }; FOR e: Edge IN Edge DO Test[e]; ENDLOOP; }; CrossedEdgeCorners: PUBLIC PROC [cube: Cube] RETURNS [TwoCorners] ~ { FOR e: Edge IN Edge DO corners: TwoCorners ¬ G3dOctree.EdgeCorners[cube, e]; IF corners.c0.inside # corners.c1.inside THEN RETURN[corners]; ENDLOOP; ERROR NoCrossedEdge; }; CrossedPoint: PUBLIC PROC [ crossedEdge: CrossedEdge, valueProc: ValueProc, threshold: REAL ¬ 1.0, normalProc: NormalProc ¬ NIL, tolerance: REAL ¬ 0.0001, edgeMode: EdgeMode ¬ binarySectioning, clientData: REF ANY ¬ NIL] RETURNS [cross: Cross] ~ { NewCross: PROC RETURNS [cross: Cross] ~ { t: Target ~ ImplicitSurface.SegmentConverge[crossedEdge.cIn.point, crossedEdge.cOut.point, crossedEdge.cIn.value, crossedEdge.cOut.value, valueProc, threshold, clientData, direction, tolerance, edgeMode]; n: Triple ¬ IF normalProc # NIL THEN normalProc[t.point, t.value+threshold, clientData] ELSE origin; cross ¬ NEW[CrossRep ¬ [point: t.point, value: t.value, normal: n]]; }; direction: Direction ~ G3dOctree.DirectionFromOctants[crossedEdge.oIn, crossedEdge.oOut]; c: Corner ~ SELECT direction FROM l, b, n => crossedEdge.cIn, ENDCASE => crossedEdge.cOut; SELECT direction FROM l, r => {IF c.lCross = NIL THEN c.lCross ¬ NewCross[]; cross ¬ c.lCross}; b, t => {IF c.bCross = NIL THEN c.bCross ¬ NewCross[]; cross ¬ c.bCross}; n, f => {IF c.nCross = NIL THEN c.nCross ¬ NewCross[]; cross ¬ c.nCross}; ENDCASE => ERROR; }; CrossFromCrossedEdge: PUBLIC PROC [crossedEdge: CrossedEdge] RETURNS [cross: Cross] ~ { d: Direction ~ G3dOctree.DirectionFromOctants[crossedEdge.oIn, crossedEdge.oOut]; c: Corner ~ SELECT d FROM l, b, n => crossedEdge.cIn, ENDCASE => crossedEdge.cOut; cross ¬ SELECT d FROM n, f => c.nCross, b, t => c.bCross, l, r => c.lCross, ENDCASE => ERROR NoCrossedEdge; }; VertexId: PUBLIC PROC [crossedEdge: CrossedEdge] RETURNS [id: INTEGER] ~ { d: Direction ~ G3dOctree.DirectionFromOctants[crossedEdge.oIn, crossedEdge.oOut]; c: Corner ~ SELECT d FROM l, b, n => crossedEdge.cIn, ENDCASE => crossedEdge.cOut; id ¬ SELECT d FROM n, f => c.nCross.id, b, t => c.bCross.id, l, r => c.lCross.id, ENDCASE => ERROR NoCrossedEdge; IF id = -1 THEN ERROR NoCrossedEdge; }; <> CheckAndGetCrossedEdges: PUBLIC PROC [ cube: Cube, valueProc: ValueProc, threshold: REAL ¬ 1.0, normalProc: NormalProc ¬ NIL, tolerance: REAL ¬ 0.0001, clientData: REF ANY ¬ NIL] RETURNS [crossedEdges: CrossedEdges] ~ { SetCornerValues[cube, valueProc, threshold, clientData]; crossedEdges ¬ CubeCrossedEdges[cube]; SetCrosses[cube, crossedEdges, valueProc, threshold, normalProc, tolerance,, clientData]; }; SetCornerValue: PUBLIC PROC [corner: Corner, value: REAL] ~ { corner.value ¬ value; corner.valueSet ¬ TRUE; corner.inside ¬ value > 0.0; }; SetCornerValues: PUBLIC PROC [ cube: Cube, valueProc: ValueProc, threshold: REAL ¬ 1.0, clientData: REF ANY ¬ NIL] ~ { FOR o: Octant IN Octant DO c: Corner ~ cube.corners[o]; IF NOT c.valueSet THEN SetCornerValue[c, valueProc[c.point, clientData, c]-threshold]; ENDLOOP; }; SetKidValues: PUBLIC PROC [ parent: Cube, valueProc: ValueProc, threshold: REAL ¬ 1.0, clientData: REF ANY] ~ { cornerProc: CornerProc ~ { IF NOT corner.valueSet THEN SetCornerValue[corner, valueProc[corner.point, clientData, corner]-threshold]; }; G3dOctree.ApplyToNonParentKidCorners[parent, cornerProc]; }; SetCrosses: PUBLIC PROC [ cube: Cube, crossedEdges: CrossedEdges, valueProc: ValueProc, threshold: REAL ¬ 1.0, normalProc: NormalProc ¬ NIL, tolerance: REAL ¬ 0.0001, edgeMode: EdgeMode ¬ binarySectioning, clientData: REF ANY ¬ NIL] ~ { FOR edge: Edge IN Edge DO IF crossedEdges[edge].cIn # NIL THEN [] ¬ CrossedPoint[ crossedEdges[edge], valueProc, threshold, normalProc, tolerance, edgeMode, clientData]; ENDLOOP; }; NextCWEdgeCrossed: PUBLIC PROC [edge: Edge, crossedEdges: CrossedEdges] RETURNS [Edge] ~ { face: Face ~ G3dOctree.FaceFromEdgeOctant[edge, crossedEdges[edge].oOut]; DO edge ¬ G3dOctree.NextCWEdge[edge, face]; IF crossedEdges[edge].cIn # NIL THEN RETURN[edge]; ENDLOOP; }; GetCrossArray: PUBLIC PROC [crossedEdges: CrossedEdges] RETURNS [crosses: CrossArray] ~ { crosses ¬ ALL[NIL]; FOR edge: Edge IN Edge DO crossedEdge: CrossedEdge ¬ crossedEdges[edge]; IF crossedEdge.cIn # NIL THEN { d: Direction ~ G3dOctree.DirectionFromOctants[crossedEdge.oIn, crossedEdge.oOut]; c: Corner ~ SELECT d FROM l, b, n => crossedEdge.cIn, ENDCASE => crossedEdge.cOut; crosses[edge] ¬ SELECT d FROM l, r => c.lCross, b, t => c.bCross, n, f => c.nCross, ENDCASE => ERROR; }; ENDLOOP; }; <> SetTerminalCubeValues: PUBLIC PROC [ root: Cube, valueProc: ValueProc, threshold: REAL ¬ 1.0, clientData: REF ANY ¬ NIL] ~ { cubeProc: CubeProc ~ {SetCornerValues[cube, valueProc, threshold, clientData]}; G3dOctree.ApplyToTerminal[root, cubeProc]; }; SetTerminalCubeCornerValuesAndCrossedPoints: PUBLIC PROC [ root: Cube, valueProc: ValueProc, threshold: REAL ¬ 1.0, normalProc: NormalProc ¬ NIL, cubeProc: CubeProc ¬ NIL, tolerance: REAL ¬ 0.0001, edgeMode: EdgeMode ¬ binarySectioning, clientData: REF ANY ¬ NIL] RETURNS [nImplicitEvaluations: INT ¬ 0] ~ { CountValueProc: ValueProc ~ { nImplicitEvaluations ¬ nImplicitEvaluations+1; RETURN[valueProc[point, clientData, corner]]; }; TerminalCubeProc: CubeProc ~ { IF NOT cubeProc[cube] THEN RETURN[FALSE]; SetCornerValues[cube, CountValueProc, threshold, clientData]; SetCrosses[cube, CubeCrossedEdges[cube], valueProc, threshold, normalProc, tolerance, edgeMode, clientData]; }; IF cubeProc # NIL THEN G3dOctree.ApplyToTerminal[root, TerminalCubeProc]; }; NVerticesInRoot: PUBLIC PROC [root: Cube] RETURNS [nPoints: INTEGER ¬ 0] ~ { <> TerminalCubeProc: CubeProc ~ { Test: PROC [o0, o1: Octant] ~ { IF cube.corners[o0].inside # cube.corners[o1].inside THEN nPoints ¬ nPoints+1; }; rNIL: BOOL ¬ G3dOctree.Neighbor[cube, r] = NIL; tNIL: BOOL ¬ G3dOctree.Neighbor[cube, t] = NIL; fNIL: BOOL ¬ G3dOctree.Neighbor[cube, f] = NIL; rtNIL: BOOL ¬ G3dOctree.Neighbor[cube, rt] = NIL; rfNIL: BOOL ¬ G3dOctree.Neighbor[cube, rf] = NIL; tfNIL: BOOL ¬ G3dOctree.Neighbor[cube, tf] = NIL; Test[lbn, rbn]; -- bn edge Test[lbn, ltn]; -- ln edge Test[lbn, lbf]; -- lb edge IF tNIL THEN { Test[ltn, ltf]; -- lt edge Test[ltn, rtn]; -- tn edge }; IF rNIL THEN { Test[rbn, rtn]; -- rn edge Test[rbn, rbf]; -- rb edge }; IF fNIL THEN { Test[lbf, ltf]; -- lf edge Test[lbf, rbf]; -- bf edge }; <> IF tNIL AND fNIL AND tfNIL THEN Test[ltf, rtf]; -- tf edge <> IF rNIL AND fNIL AND rfNIL THEN Test[rbf, rtf]; -- rf edge <> IF rNIL AND tNIL AND rtNIL THEN Test[rtn, rtf]; -- rt edge }; G3dOctree.ApplyToTerminal[root, TerminalCubeProc]; }; verticesLimited: ERROR = CODE; AddSurfaceVertex: PUBLIC PROC [point, normal: Triple, surface: Surface] RETURNS [vertexId: INT] ~ { v: Vertex; IF surface.vertices.length >= maxNVertices-1 THEN ERROR verticesLimited; v ¬ NEW[VertexRep ¬ [point: point, normal: normal]]; <> <<(also, now we might add vertices to triangulate a polygon)>> IF surface.vertices.length >= surface.vertices.maxLength THEN surface.vertices ¬ G3dShape.LengthenVertexSequence[surface.vertices]; surface.vertices[surface.vertices.length] ¬ v; vertexId ¬ surface.vertices.length; surface.vertices.length ¬ surface.vertices.length+1; }; SetVertices: PROC [ surface: Surface, root: Cube, valueProc: ValueProc, threshold: REAL ¬ 1.0, normalProc: NormalProc ¬ NIL, vertexOkProc: VertexOkProc ¬ NIL, cubeProc: CubeProc ¬ NIL, clientData: REF ANY ¬ NIL] ~ { TerminalCubeProc: CubeProc ~ { AddSurfacePoint: PROC [c: Cross] RETURNS [vertexId: INT] ~ { IF vertexOkProc # NIL AND NOT vertexOkProc[c.point, clientData] THEN c.ok ¬ FALSE; SELECT TRUE FROM c.normal # origin => NULL; normalProc # NIL => c.normal ¬ normalProc[c.point, c.value+threshold, clientData]; ENDCASE => { IF cube.size # cubeSize THEN { cubeSize ¬ cube.size; delta ¬ 0.01*cubeSize; }; c.normal ¬ GetPointNormal[c.point, valueProc, c.value+threshold, delta, clientData]; }; vertexId ¬ AddSurfaceVertex[c.point, c.normal, surface]; }; delta, cubeSize: REAL ¬ 0.0; FOR o: Octant IN Octant DO c: Corner ~ cube.corners[o]; IF c.lCross # NIL AND c.lCross.id = -1 THEN c.lCross.id ¬ AddSurfacePoint[c.lCross]; IF c.bCross # NIL AND c.bCross.id = -1 THEN c.bCross.id ¬ AddSurfacePoint[c.bCross]; IF c.nCross # NIL AND c.nCross.id = -1 THEN c.nCross.id ¬ AddSurfacePoint[c.nCross]; ENDLOOP; IF NOT CheckToProceedNextVertex[v, cube, cubeProc] THEN RETURN[FALSE]; }; v: Vertex; surface.vertices ¬ NEW[VertexSequenceRep[MIN[maxNVertices, NVerticesInRoot[root]]]]; G3dOctree.ApplyToTerminal[root, TerminalCubeProc ! verticesLimited => CONTINUE]; surface.vertexValidities[normal] ¬ TRUE; }; <> SetSurfaceVertices: PUBLIC PROC [ surface: Surface, root: Cube, valueProc: ValueProc, threshold: REAL ¬ 1.0, normalProc: NormalProc ¬ NIL, cubeProc: CubeProc ¬ NIL, vertexOkProc: VertexOkProc ¬ NIL, clientData: REF ANY ¬ NIL] RETURNS [message: ROPE] ~ { SetVertices[surface,root,valueProc,threshold, normalProc, vertexOkProc, cubeProc, clientData]; IF surface.vertices.length >= maxNVertices-1 THEN message ¬ " *vertices limited, "; message ¬ IO.PutFR["%g%g vertices", IO.rope[message], IO.int[surface.vertices.length]]; }; <<>> CheckToProceedNextVertex: PROC [vertex: Vertex, cube: Cube, cubeProc: CubeProc] RETURNS [BOOL] ~ { IF vertex = NIL OR cube = NIL OR cubeProc = NIL THEN RETURN[TRUE]; cube.refAny ¬ vertex; RETURN[cubeProc[cube]]; }; SetVertexNormals: PUBLIC PROC [surface: Surface, cubeProc: CubeProc ¬ NIL] ~ { <> IF surface # NIL AND surface.vertices # NIL THEN { cube: Cube ¬ NEW[G3dOctree.CubeRep]; vertices: VertexSequence ~ surface.vertices; points: TripleSequence ¬ NEW[TripleSequenceRep[24]]; angles: RealSequence ¬ NEW[RealSequenceRep[24]]; polygonProc: PolygonProc ~ { normal: Triple; sum: REAL ¬ 0.0; points.length ¬ angles.length ¬ polygon.length; FOR n: NAT IN [0..points.length) DO points[n] ¬ surface.vertices[polygon[n]].point; ENDLOOP; angles ¬ G3dPolygon.PolygonAngles[points, NIL, angles]; normal ¬ IF surface.faceNormals # NIL THEN surface.faceNormals[nPolygon] ELSE G3dPolygon.PolygonNormal[points]; FOR n: NAT IN [0..angles.length) DO sum ¬ sum+angles[n]; ENDLOOP; sum ¬ 1.0/sum; FOR n: NAT IN [0..polygon.length) DO v: Vertex ¬ vertices[polygon[n]]; v.normal ¬ G3dVector.Add[ v.normal, G3dVector.Mul[normal, angles[n]*sum]]; IF NOT CheckToProceedNextVertex[v, cube, cubeProc] THEN RETURN; ENDLOOP; }; FOR n: NAT IN [0..vertices.length) DO vertices[n].normal ¬ origin; ENDLOOP; ImplicitPolygons.ApplyToSurfacePolygons[surface, polygonProc]; FOR n: NAT IN [0..vertices.length) DO v: Vertex ¬ vertices[n]; v.normal ¬ G3dVector.Unit[v.normal]; ENDLOOP; surface.vertexValidities[normal] ¬ TRUE; }; }; SetVertexTextures: PUBLIC PROC [ surface: Surface, textureProc: TextureProc, cubeProc: CubeProc ¬ NIL, clientData: REF ANY ¬ NIL] ~ { cube: Cube ¬ NEW[G3dOctree.CubeRep]; IF surface # NIL AND surface.vertices # NIL AND textureProc # NIL THEN { FOR n: NAT IN [0..surface.vertices.length) DO v: Vertex ~ surface.vertices[n]; v.texture ¬ textureProc[v, clientData]; IF NOT CheckToProceedNextVertex[v, cube, cubeProc] THEN RETURN; ENDLOOP; surface.vertexValidities[texture] ¬ TRUE; }; }; SetVertexColors: PUBLIC PROC [ surface: Surface, colorProc: ColorProc, cubeProc: CubeProc ¬ NIL, clientData: REF ANY ¬ NIL] ~ { cube: Cube ¬ NEW[G3dOctree.CubeRep]; IF surface # NIL AND surface.vertices # NIL AND colorProc # NIL THEN { FOR n: NAT IN [0..surface.vertices.length) DO v: Vertex ~ surface.vertices[n]; v.color ¬ colorProc[v, clientData]; IF NOT CheckToProceedNextVertex[v, cube, cubeProc] THEN RETURN; ENDLOOP; surface.vertexValidities[color] ¬ TRUE; }; }; SetVertexScreenCoords: PUBLIC PROC [s: Surface, v: Matrix, vp: Viewport] ~ { hasPersp: BOOL ¬ G3dMatrix.HasPerspective[v]; IF s = NIL OR s.vertices = NIL THEN RETURN; IF s.screens = NIL THEN s.screens ¬ NEW[G3dShape.ScreenSequenceRep[s.vertices.length]]; IF s.screens.screensValid THEN RETURN; FOR n: NAT IN [0..s.vertices.length) DO s.screens[n] ¬ G3dMatrix.GetScreen[s.vertices[n].point, v, hasPersp, vp]; ENDLOOP; s.screens.screensValid ¬ TRUE; }; VertexScreenCoordsValid: PUBLIC PROC [surface: Surface] RETURNS [BOOL] ~ { RETURN[surface # NIL AND surface.screens # NIL AND surface.screens.screensValid]; }; SetVertexScreenCoordsInvalid: PUBLIC PROC [surface: Surface] ~ { IF surface # NIL AND surface.screens # NIL THEN surface.screens.screensValid ¬ FALSE; }; GetPointNormal: PUBLIC PROC [ point: Triple, valueProc: ValueProc, value, delta: REAL, clientData: REF ANY ¬ NIL] RETURNS [Triple] ~ { RETURN[G3dVector.Unit[[ -- opp. usual gradient so surface normals point outwards value-valueProc[[point.x+delta, point.y, point.z], clientData], value-valueProc[[point.x, point.y+delta, point.z], clientData], value-valueProc[[point.x, point.y, point.z+delta], clientData]]]]; }; <> DecodePoints: PUBLIC PROC [surface: Surface, points: TripleSequence ¬ NIL] RETURNS [TripleSequence] ~ { IF points = NIL OR points.maxLength < surface.vertices.length THEN points ¬ NEW[TripleSequenceRep[surface.vertices.length]]; points.length ¬ surface.vertices.length; FOR n: NAT IN [0..surface.vertices.length) DO points[n] ¬ surface.vertices[n].point; ENDLOOP; RETURN[points]; }; DecodeNormals: PUBLIC PROC [surface: Surface, normals: TripleSequence ¬ NIL] RETURNS [TripleSequence] ~ { IF normals = NIL OR normals.maxLength < surface.vertices.length THEN normals ¬ NEW[TripleSequenceRep[surface.vertices.length]]; normals.length ¬ surface.vertices.length; FOR n: NAT IN [0..surface.vertices.length) DO normals[n] ¬ surface.vertices[n].normal; ENDLOOP; RETURN[normals]; }; DecodeTextures: PUBLIC PROC [surface: Surface, textures: PairSequence ¬ NIL] RETURNS [PairSequence] ~ { IF textures = NIL OR textures.maxLength < surface.vertices.length THEN textures ¬ NEW[PairSequenceRep[surface.vertices.length]]; textures.length ¬ surface.vertices.length; FOR n: NAT IN [0..surface.vertices.length) DO textures[n] ¬ surface.vertices[n].texture; ENDLOOP; RETURN[textures]; }; DecodeColors: PUBLIC PROC [surface: Surface, colors: TripleSequence ¬ NIL] RETURNS [TripleSequence] ~ { IF colors = NIL OR colors.maxLength < surface.vertices.length THEN colors ¬ NEW[TripleSequenceRep[surface.vertices.length]]; colors.length ¬ surface.vertices.length; FOR n: NAT IN [0..surface.vertices.length) DO colors[n] ¬ surface.vertices[n].color; ENDLOOP; RETURN[colors]; }; END. .. <> <> <> <> <>