<<>> <> <> <> DIRECTORY G3dBasic, G3dPlane, IO, Rope; G3dOctree: CEDAR DEFINITIONS ~ BEGIN <> ROPE: TYPE ~ Rope.ROPE; STREAM: TYPE ~ IO.STREAM; Box: TYPE ~ G3dBasic.Box; Pair: TYPE ~ G3dBasic.Pair; Triple: TYPE ~ G3dBasic.Triple; Plane: TYPE ~ G3dPlane.Plane; <> NoSuchOctant: ERROR [msg: ROPE]; NoSuchFace: ERROR [msg: ROPE]; StackOverflow: ERROR; StackUnderflow: ERROR; <> <> <> <> <> <<>> Axis: TYPE ~ {x, y, z}; -- edge alignment Face: TYPE ~ {l, r, b, t, n, f}; TwoFaces: TYPE ~ RECORD [f0, f1: Face]; ActiveFaces: TYPE ~ ARRAY Face OF BOOL ¬ ALL[FALSE]; Edge: TYPE ~ {lb, lt, ln, lf, rb, rt, rn, rf, bn, bf, tn, tf}; ThreeEdges: TYPE ~ RECORD [e0, e1, e2: Edge]; Direction: TYPE ~ { l, r, b, t, n, f, -- faces lb, lt, ln, lf, rb, rt, rn, rf, bn, bf, tn, tf, -- edges lbn, lbf, ltn, ltf, rbn, rbf, rtn, rtf, -- corners c, none -- center, none }; DirectionType: TYPE ~ {none, face, edge, corner}; DirectionSelect: TYPE ~ {x, y, z, xy, xz, yz, xyz, none}; DirectionPairs: TYPE ~ ARRAY Direction OF Pair; TwoDirections: TYPE ~ RECORD [d0, d1: Direction]; ThreeDirections: TYPE ~ RECORD [d0, d1, d2: Direction]; FourDirections: TYPE ~ RECORD [d0, d1, d2, g3d: Direction]; Octant: TYPE ~ MACHINE DEPENDENT { lbn(0), lbf(1), ltn(2), ltf(3), -- left corners rbn(4), rbf(5), rtn(6), rtf(7) -- right corners }; OctantPairs: TYPE ~ ARRAY Octant OF Pair; TwoOctants: TYPE ~ RECORD [o0, o1: Octant]; FourOctants: TYPE ~ RECORD [o0, o1, o2, o3: Octant]; FaceNeighborInfo: TYPE ~ RECORD [nOctant: Octant, recurse: BOOL]; <> Corner: TYPE ~ REF CornerRep; CornerRep: TYPE ~ RECORD [ point: Triple ¬ [], -- location of corner outOfRange: BOOL ¬ FALSE, -- corner not in function domain valueSet: BOOL ¬ FALSE, -- true if value computed value: REAL ¬ 0.0, -- surface value at corner inside: BOOL ¬ FALSE, -- if valueSet & value > 0 nearestSet: BOOL ¬ FALSE, -- true iff nearest computed nearest: Triple ¬ [], -- surface point nearest to corner squareDistance: REAL ¬ 0.0, -- square-distance to nearest lCross: Cross ¬ NIL, -- leftward surface intersection bCross: Cross ¬ NIL, -- bottomward surface intersection nCross: Cross ¬ NIL -- nearward surface intersection ]; TwoCorners: TYPE ~ RECORD [c0, c1: Corner]; FourCorners: TYPE ~ RECORD [c0, c1, c2, c3: Corner]; Corners: TYPE ~ ARRAY Octant OF Corner; DirectionCorners: TYPE ~ ARRAY Direction OF Corner; <> Cube: TYPE ~ REF CubeRep; CubeRep: TYPE ~ RECORD [ parent: Cube ¬ NIL, -- parent cube size: REAL ¬ 1.0, -- length of an edge octant: Octant ¬ lbn, -- relation to parent cube level: INT ¬ 0, -- recursion depth terminal: BOOL ¬ FALSE, -- if true, leaf node corners: Corners ¬ ALL[NIL], -- corner locations and info kids: Kids ¬ ALL[NIL], -- subdivided cube crossesComputed: BOOL ¬ FALSE, -- true if surfaceCrossed: BOOL ¬ FALSE, -- true iff surface crosses cube refAny: REF ANY ¬ NIL]; -- a potentially useful pointer Kids: TYPE ~ ARRAY Octant OF Cube; Neighborhood: TYPE ~ ARRAY Direction OF Cube ¬ ALL[NIL]; -- neighbors of a cube TwoCubes: TYPE ~ RECORD [c0, c1: Cube]; ThreeCubes: TYPE ~ RECORD [c0, c1, c2: Cube]; CubeStack: TYPE ~ REF CubeStackRep; CubeStackRep: TYPE ~ RECORD [ top: INT ¬ 0, bottom: INT ¬ 0, size: INT ¬ 0, maxSize: INT ¬ 0, element: SEQUENCE maxLength: INT OF Cube]; CubeSequence: TYPE ~ REF CubeSequenceRep; CubeSequenceRep: TYPE ~ RECORD [ length: INT ¬ 0, element: SEQUENCE maxLength: INT OF Cube]; <> OctreeMode: TYPE ~ RECORD [ postAdaptMax: INT ¬ 0, -- max subdivs beyond terminal, given octree flatness: REAL ¬ 30.0, -- criterion in degrees for adaptive subdivision tolerance: REAL ¬ 0.0001, -- tolerance for edge convergence type: SELECT OctreeType: OctreeType FROM converge => [ rootSize: REAL, -- size of octree recurseMin: INT ¬ 1, -- min # of subdivisions of octree recurseMax: INT ¬ 5], -- max # of subdivisions of octree track => [ cubeSize: REAL ¬ 0.05, -- size of initial cube surfacePoint: Triple ¬ [], -- a point on the surface duringAdaptMax: INT ¬ 0], -- max # subdivisions during tracking ENDCASE]; OctreeType: TYPE ~ {track, converge}; Octree: TYPE ~ REF OctreeRep; OctreeRep: TYPE ~ RECORD [ root: Cube ¬ NIL, -- the octree root mode: OctreeMode ¬ [,,, track[]], -- way octree was constructed depth: INT ¬ 0, -- level of most deeply recursed name: ROPE ¬ NIL, -- name of octree errorMsg: ROPE ¬ NIL, -- error message during creation radius, terminalRadius: REAL ¬ 0.0, -- half edge length of root, leaf diameter, terminalDiameter: REAL ¬ 0.0, -- edge length of root, leaf nCubes, nTerminalCubes: CARD ¬ 0, -- # of cubes and terminal cubes truncated: BOOL ¬ FALSE, -- if octree truncates a surface completed: BOOL ¬ FALSE, -- if octree creation not aborted nFaceDepthChanges: INT ¬ 0, -- # terminal faces/non-terminal nRecursiveTrackFailures: INT ¬ 0, -- # anomalies: facedepth changes refAny: REF ANY ¬ NIL] ; -- a potentially useful pointer <> Cross: TYPE ~ REF CrossRep; CrossRep: TYPE ~ RECORD [ id: INT ¬ -1, -- vertex id value: REAL ¬ 0.0, -- spatial value point: Triple ¬ [], -- location of surface vertex normal: Triple ¬ [], -- if not origin, normal at point ok: BOOL ¬ TRUE]; -- FALSE if subsequently rejected CrossArray: TYPE ~ ARRAY Edge OF Cross; CrossSequence: TYPE ~ REF CrossSequenceRep; CrossSequenceRep: TYPE ~ RECORD [ length: INT ¬ 0, element: SEQUENCE maxLength: INT OF Cross]; CrossedEdge: TYPE ~ RECORD [ -- a surface-crossedEdge edge cIn, cOut: Corner ¬ NIL, -- inside and outside corners oIn, oOut: Octant]; -- and their octants CrossedEdges: TYPE ~ ARRAY Edge OF CrossedEdge; -- possible edge-surface inter. <> IntersectionType: TYPE ~ {empty, entering, leaving}; Intersection: TYPE ~ RECORD [ type: IntersectionType ¬ empty, -- entered, left, or missed the cube directionSelect: DirectionSelect ¬ none, -- intersect at face, edge, or corner t: REAL ¬ 0.0, -- parametric point of intersection point: Triple ¬ [], -- point of intersection value: REAL ¬ 0.0, -- value at intersection point cube: Cube ¬ NIL]; -- which cube intersected IntersectionList: TYPE ~ LIST OF Intersection; <> CubeProc: TYPE ~ PROC [cube: Cube] RETURNS [continue: BOOL ¬ TRUE]; << Procedure for operating on a cube and its descendents.>> <<>> CornerProc: TYPE ~ PROC [corner: Corner] RETURNS [continue: BOOL ¬ TRUE]; << Perform operation on a cube corner.>> <<>> CornerDataProc: TYPE ~ PROC [corner: Corner] RETURNS [REF ANY]; << Called when a corner is allocated.>> <<>> CrossPolygonProc: TYPE ~ PROC [nPolygon: INT, polygon: CrossSequence] RETURNS [continue: BOOL ¬ TRUE]; << nPolygon is polygon id; polygon is sequence of crosses.>> <> <> NewCube: PROC [size: REAL, center: Triple ¬ [], cornerDataProc: CornerDataProc ¬ NIL] RETURNS [Cube]; <> <> Root: PROC [cube: Cube] RETURNS [Cube]; <> <<>> CubeOk: PROC [cube: Cube] RETURNS [BOOL]; <> <<>> FullyPointed: PROC [cube: Cube] RETURNS [BOOL]; <> <<>> NCubes: PROC [cube: Cube] RETURNS [INT]; <> <<>> NTerminalCubes: PROC [cube: Cube] RETURNS [INT]; <> <<>> Center: PROC [cube: Cube] RETURNS [Triple]; <> <<>> Size: PROC [cube: Cube] RETURNS [REAL]; <> <<>> MinSize: PROC [cube: Cube] RETURNS [REAL]; <> <<>> BoxOfCube: PROC [cube: Cube] RETURNS [Box]; <> <<>> AnyKids: PROC [cube: Cube] RETURNS [BOOL]; <> <<>> DepthOf: PROC [cube: Cube] RETURNS [INT]; <> <> Subdivide: PROC [cube: Cube]; <> <<>> SubdivideTerminal: PROC [cube: Cube]; <> <<>> RecursivelySubdivide: PROC [cube: Cube, nLevels: INT]; <> <> PointInCube: PROC [point: Triple, cube: Cube, fudge: REAL ¬ 0.0] RETURNS [BOOL]; <> WhichCube: PROC [point: Triple, root: Cube] RETURNS [Cube]; <> <<>> FirstKid: PROC [cube: Cube] RETURNS [Cube]; <> <<>> FirstTerminalKid: PROC [cube: Cube] RETURNS [Cube]; <> <> Apply: PROC [cube: Cube, cubeProc: CubeProc]; <> <<>> ApplyToKids: PROC [cube: Cube, cubeProc: CubeProc]; <> <<>> ApplyToLevel: PROC [cube: Cube, cubeProc: CubeProc, level: INT]; <> ApplyToTerminal: PROC [cube: Cube, cubeProc: CubeProc]; <> <<>> ApplyToTerminalCorners: PROC [cube: Cube, cornerProc: CornerProc]; <> <<>> ApplyToNonParentKidCorners: PROC [cube: Cube, cornerProc: CornerProc]; <> <> <> <> FaceNeighbor: PROC [cube: Cube, face: Face] RETURNS [Cube]; <> <<>> EdgeNeighbors: PROC [cube: Cube, edge: Edge] RETURNS [ThreeCubes]; <> <<>> Neighbor: PROC [cube: Cube, direction: Direction] RETURNS [Cube]; <> <<>> Neighbors: PROC [cube: Cube] RETURNS [Neighborhood]; <> <<>> Move: PROC [cube: Cube, direction: Direction] RETURNS [Neighborhood]; <> <> AddCube: PROC [cube: Cube, face: Face, fullyPointed: BOOL ¬ TRUE] RETURNS [root: Cube]; <> <> <> <<>> DeleteCube: PROC [cube: Cube]; <> <<>> MakeRestrictedOctree: PROC [root: Cube]; <> <<>> SetOctreeFields: PROC [octree: Octree]; <> <> <<>> SetTerminalField: PROC [root: Cube]; <> SetLevels: PROC [root: Cube]; <> <> PlaneFromCubeFace: PROC [cube: Cube, face: Face] RETURNS [Plane]; <> GetClientData: PROC [Cube] RETURNS [REF ANY]; <> <<>> SetClientData: PROC [Cube, REF ANY]; <> <> CubeObject: TYPE ~ REF CubeObjectRep; CubeObjectQueryProc: TYPE ~ PROC [val: REF, pt: Triple] RETURNS [BOOL]; CubeObjectRep: TYPE ~ RECORD [val: REF _ NIL, bbox: Box, query: CubeObjectQueryProc]; FromObjects: PROC [objs: LIST OF CubeObject] RETURNS [Cube]; <> AddObject: PROC [Cube, CubeObject]; <> <> SubdivideGivenObjects: PROC [cube: Cube, maxPerCube: INT, maxDepth: INT]; <> <> QueryObjects: PROC [Cube, Triple] RETURNS [obj: REF ANY]; <> <> <> EdgeCorners: PROC [cube: Cube, edge: Edge] RETURNS [TwoCorners]; <> <> FaceCorners: PROC [cube: Cube, face: Face] RETURNS [FourCorners]; <> <<>> NewCorners: PROC [size: REAL, center: Triple, cornerDataProc: CornerDataProc ¬ NIL] RETURNS [Corners]; <> <<>> GetDirectionCorner: PROC [cube: Cube, d: Direction] RETURNS [c: Corner]; <> <<>> GetDirectionCorners: PROC [cube: Cube] RETURNS [DirectionCorners]; <> <> <> EdgesFromOctant: PROC [octant: Octant] RETURNS [ThreeEdges]; <> <<>> DirectionsFromOctant: PROC [octant: Octant] RETURNS [ThreeDirections]; <> <<>> FaceFromEdgeOctant: PROC [edge: Edge, octant: Octant] RETURNS [Face]; <> NextCWEdge: PROC [edge: Edge, face: Face] RETURNS [Edge]; <> NextCCWEdge: PROC [edge: Edge, face: Face] RETURNS [Edge]; <> EdgeDirections: PROC [edge: Edge] RETURNS [ThreeDirections]; <> <<>> EdgeFaces: PROC [edge: Edge] RETURNS [TwoFaces]; <> <<>> EdgeOctants: PROC [edge: Edge] RETURNS [TwoOctants]; <> <> <<>> FaceOctants: PROC [face: Face] RETURNS [FourOctants]; <> <<>> OppositeEdge: PROC [edge: Edge, face: Face] RETURNS [Edge]; <> <<>> InverseEdge: PROC [edge: Edge, face: Face] RETURNS [Edge]; <> <<>> DiagonalEdge: PROC [edge: Edge] RETURNS [Edge]; <> <<>> OtherFace: PROC [edge: Edge, face: Face] RETURNS [Face]; <> <<>> AxisFromEdge: PROC [edge: Edge] RETURNS [Axis]; <> <<>> DirectionTypeFromDirection: PROC [direction: Direction] RETURNS [DirectionType]; <> <<>> DirectionFromFace: PROC [face: Face] RETURNS [Direction]; <> <<>> DirectionFromEdge: PROC [edge: Edge] RETURNS [Direction]; <> <<>> DirectionFromOctant: PROC [octant: Octant] RETURNS [Direction]; <> <<>> DirectionFromOctants: PROC [octant0, octant1: Octant] RETURNS [Direction]; <> <<>> DirectionFromPoints: PROC [point0, point1: Triple] RETURNS [Direction]; <> <<>> OppositeOctant: PROC [octant: Octant] RETURNS [Octant] ~ INLINE { RETURN[VAL[ORD[LAST[Octant]]-ORD[octant]]]}; <> <<>> OppositeFace: PROC [face: Face] RETURNS [Face]; <> OppositeDirection: PROC [direction: Direction] RETURNS [Direction]; <> <<>> AddDirection: PROC [d0, d1: Direction] RETURNS [Direction]; <> <<(eg., return none if d0 = l and d1 = r; return lb if d0 = l and d1 = b).>> <<>> EdgeFromDirection: PROC [d: Direction] RETURNS [Edge]; <> <<>> OctantFromDirection: PROC [d: Direction] RETURNS [Octant]; <> <<>> OctantFromThreeDirections: PROC [d0, d1, d2: Direction] RETURNS [Octant]; <> FaceFromDirection: PROC [d: Direction] RETURNS [Face]; <> <<>> FaceDirections: PROC [face: Face] RETURNS [FourDirections]; <> <<>> NormalFromFace: PROC [face: Face] RETURNS [Triple]; <> <> <> <> <> <<>> WriteCubesToFile: PROC [fileName: ROPE, cube: Cube, miscInfo: ROPE ¬ NIL]; <> ReadCubesFromFile: PROC [fileName: ROPE] RETURNS [Cube]; <> <> AddToCubeSequence: PROC [cube: Cube, cubes: CubeSequence ¬ NIL] RETURNS [CubeSequence]; <> LengthenCubeSequence: PROC [cubes: CubeSequence, amount: REAL ¬ 1.3] RETURNS [CubeSequence]; <> <> NewCubeStack: PROC [length: INT] RETURNS [CubeStack]; <> WriteBottomOfCubeStack: PROC [cube: Cube, cubeStack: CubeStack]; <> ReadTopOfCubeStack: PROC [cubeStack: CubeStack] RETURNS [cube: Cube]; <> CubeStackSize: PROC [cubeStack: CubeStack] RETURNS [INT]; <> MaxCubeStackSize: PROC [cubeStack: CubeStack] RETURNS [INT]; <> CubeStackEmpty: PROC [cubeStack: CubeStack] RETURNS [BOOL]; <> <<>> LengthenCubeStack: PROC [cubeStack: CubeStack, amount: REAL ¬ 1.3] RETURNS [CubeStack]; <> <> ObtainCrossSequence: PROC RETURNS [crossSequence: CrossSequence]; <> ReleaseCrossSequence: PROC [crossSequence: CrossSequence]; <> <> RopeFromOctant: PROC [octant: Octant] RETURNS [ROPE]; <> <<>> RopeFromFace: PROC [face: Face] RETURNS [ROPE]; <> <<>> RopeFromDirection: PROC [direction: Direction] RETURNS [ROPE]; <> <<>> RopeFromDirectionSelect: PROC [directionSelect: DirectionSelect] RETURNS [ROPE]; <> <<>> OctantFromRope: PROC [rope: ROPE] RETURNS [Octant]; <> <<>> FaceFromRope: PROC [rope: ROPE] RETURNS [Face]; <> <<>> DirectionFromRope: PROC [rope: ROPE] RETURNS [Direction]; <> <<>> RopeFromRefAny: PROC [ref: REF ANY] RETURNS [rope: ROPE]; <> <<>> END.