[_CDCSL_93-16_]<1>Cedar>release>G3dVolume>G3dOctree.mesa

Imported Types

ROPE: TYPE ~ Rope.ROPE;

STREAM: TYPE ~ IO.STREAM;

Box: TYPE ~ G3dBasic.Box;

Pair: TYPE ~ G3dBasic.Pair;

Triple: TYPE ~ G3dBasic.Triple;

Plane: TYPE ~ G3dPlane.Plane;

Errors

NoSuchOctant: ERROR [msg: ROPE];

NoSuchFace: ERROR [msg: ROPE];

StackOverflow: ERROR;

StackUnderflow: ERROR;

Directions, Edges, Faces, Octants

There are six basic directions:

l: left (lesser in x), r: right (greater in x),

b: bottom (lesser in y), t: top (greater in y),

n: near (lesser in z), f: far (greater in z)

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

Corners

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;

Cubes, Cube Sequences, and CubeStacks

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

Octrees

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

Cube Crossing a Surface

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.

Ray-Cube Intersections

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;

CallBack Procs

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.

Cube Operations

Allocation

NewCube: PROC [size: REAL, center: Triple ¬ [], cornerDataProc: CornerDataProc ¬ NIL]

RETURNS [Cube];

Create a new cube; its octant defaults to lbn and its level is 0.

Attributes

Root: PROC [cube: Cube] RETURNS [Cube];

Return the root of cube.

CubeOk: PROC [cube: Cube] RETURNS [BOOL];

Verify the integrity of the cube.

FullyPointed: PROC [cube: Cube] RETURNS [BOOL];

Return true if all kids are defined for non-terminal cubes.

NCubes: PROC [cube: Cube] RETURNS [INT];

Return 1+number of cubes descended from cube.

NTerminalCubes: PROC [cube: Cube] RETURNS [INT];

Return the number of terminal cubes descended from cube.

Center: PROC [cube: Cube] RETURNS [Triple];

Return the center of the cube.

Size: PROC [cube: Cube] RETURNS [REAL];

Return the size (width, height, depth) of the cube.

MinSize: PROC [cube: Cube] RETURNS [REAL];

Return the size of the smallest cube descended from cube.

BoxOfCube: PROC [cube: Cube] RETURNS [Box];

Return the bounding box of the cube.

AnyKids: PROC [cube: Cube] RETURNS [BOOL];

Return true if any of cube.kids is non-NIL.

DepthOf: PROC [cube: Cube] RETURNS [INT];

Return the level of the most deeply recursed terminal cube descended from cube.

Subdivision

Subdivide: PROC [cube: Cube];

Subdivide the cube into eight octants.

SubdivideTerminal: PROC [cube: Cube];

Subdivide all terminal cubes descended from cube.

RecursivelySubdivide: PROC [cube: Cube, nLevels: INT];

Recursively subdivide the terminal nodes of cube to a depth of nLevels.

Searching

PointInCube: PROC [point: Triple, cube: Cube, fudge: REAL ¬ 0.0] RETURNS [BOOL];

Return true if point is inside the cube. fudge is the percent deviation from cube size.

WhichCube: PROC [point: Triple, root: Cube] RETURNS [Cube];

Return the cube descended from root that contains point; return NIL if no such cube.

FirstKid: PROC [cube: Cube] RETURNS [Cube];

Return the first non-nil kid of cube.

FirstTerminalKid: PROC [cube: Cube] RETURNS [Cube];

Return the first terminal cube found descended from cube.

Callback

Apply: PROC [cube: Cube, cubeProc: CubeProc];

Apply cubeProc to cube and all its descendents.

ApplyToKids: PROC [cube: Cube, cubeProc: CubeProc];

Apply cubeProc to cube's descendents.

ApplyToLevel: PROC [cube: Cube, cubeProc: CubeProc, level: INT];

Apply cubeProc to all cubes descended from cube with specified level.

ApplyToTerminal: PROC [cube: Cube, cubeProc: CubeProc];

Apply cubeProc to all terminal descendents of cube.

ApplyToTerminalCorners: PROC [cube: Cube, cornerProc: CornerProc];

Apply cornerProc to all corners of terminal descendents of cube.

ApplyToNonParentKidCorners: PROC [cube: Cube, cornerProc: CornerProc];

Apply cornerProc to all the kid corners of cube that are not corners of cube;

these are the midpoints of cube's edges, the center of cube's faces, and the center of cube.

An error may result if any of cubes.kids is undefined.

Neighbors

FaceNeighbor: PROC [cube: Cube, face: Face] RETURNS [Cube];

Return the neighbor next to cube's face; return NIL if no such neighbor.

EdgeNeighbors: PROC [cube: Cube, edge: Edge] RETURNS [ThreeCubes];

Return the three neighbors next to cube's edge; return NIL if no such neighbor.

Neighbor: PROC [cube: Cube, direction: Direction] RETURNS [Cube];

Return the neighbor next to cube in the given direction; return NIL if no such neighbor.

Neighbors: PROC [cube: Cube] RETURNS [Neighborhood];

Return the cube and its 26 neighbors.

Move: PROC [cube: Cube, direction: Direction] RETURNS [Neighborhood];

Return the neighborhood of cube after it has moved in the given direction.

Octree

AddCube: PROC [cube: Cube, face: Face, fullyPointed: BOOL ¬ TRUE] RETURNS [root: Cube];

If the face neighbor of cube doesn't exist, allocate it, creating any required parents.

If fullyPointed, then parent (and grandparent, etc.) of cube will be fully subdivided,

otherwise, only cube is added.

DeleteCube: PROC [cube: Cube];

Delete cube from its parent.

MakeRestrictedOctree: PROC [root: Cube];

Ensure by subdivision that no cube neighbors differ in octree depth by more than one.

SetOctreeFields: PROC [octree: Octree];

Set the depth, radius, terminalRadius, diameter, terminalDiameter, and nTerminalCubes

fields of the octree.

SetTerminalField: PROC [root: Cube];

For each cube, set terminal field true iff cube has no kids, false otherwise.

SetLevels: PROC [root: Cube];

For each cube, set level field according to its depth in the octree.

Miscellany

PlaneFromCubeFace: PROC [cube: Cube, face: Face] RETURNS [Plane];

Return the plane containing the specified face.

GetClientData: PROC [Cube] RETURNS [REF ANY];

Get any previously set client data.

SetClientData: PROC [Cube, REF ANY];

Setset client data for subsequent access.

Object Query

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

Construct a cube which contains the given objects

AddObject: PROC [Cube, CubeObject];

Adds one more object - the Cube must have been created with 'FromObjects.'

The new object must fit within the old cube.

SubdivideGivenObjects: PROC [cube: Cube, maxPerCube: INT, maxDepth: INT];

Subdivide the given cube (which must have been created with FromObjects/AddObject)

until every sub-cube has either
1) <= (maxPerCube) objects in it
2) a depth = (maxDepth)

QueryObjects: PROC [Cube, Triple] RETURNS [obj: REF ANY];

Find the object which contains the given triple. If none, returns NIL.

The cube must have been createdc by (FromObjects).

Corner Operations

EdgeCorners: PROC [cube: Cube, edge: Edge] RETURNS [TwoCorners];

Return the two corners at cube's edge.

In the TwoCorners record, l precedes r, b precedes t, and n precedes f.

FaceCorners: PROC [cube: Cube, face: Face] RETURNS [FourCorners];

Return the four corners along cube's face. Corners are clockwise if viewed from outside.

NewCorners: PROC [size: REAL, center: Triple, cornerDataProc: CornerDataProc ¬ NIL]

RETURNS [Corners];

Compute the corners of a cube given its center and size.

GetDirectionCorner: PROC [cube: Cube, d: Direction] RETURNS [c: Corner];

Return the corner lying in the given direction.

GetDirectionCorners: PROC [cube: Cube] RETURNS [DirectionCorners];

Return the 27 corners of cube's children.

An error may occur if any of cube.kids is undefined.

Axis, Edge, Face, Octant, Direction Operations

EdgesFromOctant: PROC [octant: Octant] RETURNS [ThreeEdges];

Return the three edges that emanate from octant.

DirectionsFromOctant: PROC [octant: Octant] RETURNS [ThreeDirections];

Return the three Directions that create octant.

FaceFromEdgeOctant: PROC [edge: Edge, octant: Octant] RETURNS [Face];

face traversed cw by edge starting at octant; no checking that octant agrees with edge.

NextCWEdge: PROC [edge: Edge, face: Face] RETURNS [Edge];

Return the next edge clockwise around face; no checking that edge and face agree.

NextCCWEdge: PROC [edge: Edge, face: Face] RETURNS [Edge];

Return the next edge counter-clockwise around face; no checking that edge and face agree.

EdgeDirections: PROC [edge: Edge] RETURNS [ThreeDirections];

Return the three directions that cubes can lie around an edge.

EdgeFaces: PROC [edge: Edge] RETURNS [TwoFaces];

Return the two faces around a cube's edge.

EdgeOctants: PROC [edge: Edge] RETURNS [TwoOctants];

Return the two octants at a cube's edge.

In the TwoOctants record, l precedes r, b precedes t, and n precedes f.

FaceOctants: PROC [face: Face] RETURNS [FourOctants];

Return the four octants along face. Octants are clockwise if viewed from outside.

OppositeEdge: PROC [edge: Edge, face: Face] RETURNS [Edge];

Return the edge on the opposite side of face.

InverseEdge: PROC [edge: Edge, face: Face] RETURNS [Edge];

Return the edge as shared by a cube with face adjacency.

DiagonalEdge: PROC [edge: Edge] RETURNS [Edge];

Return the edge diagonally across the cube.

OtherFace: PROC [edge: Edge, face: Face] RETURNS [Face];

Return the face on the other side of edge from face.

AxisFromEdge: PROC [edge: Edge] RETURNS [Axis];

Return the axis aligned with the edge.

DirectionTypeFromDirection: PROC [direction: Direction] RETURNS [DirectionType];

Return the direction type given the direction.

DirectionFromFace: PROC [face: Face] RETURNS [Direction];

Return the direction that is the face.

DirectionFromEdge: PROC [edge: Edge] RETURNS [Direction];

Return the direction that is the edge.

DirectionFromOctant: PROC [octant: Octant] RETURNS [Direction];

Return the direction that is the octant.

DirectionFromOctants: PROC [octant0, octant1: Octant] RETURNS [Direction];

Return the direction which takes octant0 to octant1.

DirectionFromPoints: PROC [point0, point1: Triple] RETURNS [Direction];

Return direction taking point0 to point1 (none if the points aren't aligned on the grid).

OppositeOctant: PROC [octant: Octant] RETURNS [Octant] ~ INLINE {

RETURN[VAL[ORD[LAST[Octant]]-ORD[octant]]]};

Return the opposite octant.

OppositeFace: PROC [face: Face] RETURNS [Face];

Return the face opposite face.

OppositeDirection: PROC [direction: Direction] RETURNS [Direction];

Return the opposite direction of direction.

AddDirection: PROC [d0, d1: Direction] RETURNS [Direction];

Return the result of applying d1 to d0

(eg., return none if d0 = l and d1 = r; return lb if d0 = l and d1 = b).

EdgeFromDirection: PROC [d: Direction] RETURNS [Edge];

Return the edge that is the direction d; ERROR raised if d is not an edge direction.

OctantFromDirection: PROC [d: Direction] RETURNS [Octant];

Return the octant that is the direction d; ERROR raised if d is not an octant direction.

OctantFromThreeDirections: PROC [d0, d1, d2: Direction] RETURNS [Octant];

Return the octant that is in the direction given by the sum of d0, d1, and d2.

FaceFromDirection: PROC [d: Direction] RETURNS [Face];

Return the face that is the direction d; ERROR raised if d is not an face direction.

FaceDirections: PROC [face: Face] RETURNS [FourDirections];

Return the directions associated with the four corners of face.

NormalFromFace: PROC [face: Face] RETURNS [Triple];

Return the face normal.

IO

File Format:

The first line gives the center and size of the root cube.

Following lines each represent a cube, specifying, by "0" or "1", which octants exist.

WriteCubesToFile: PROC [fileName: ROPE, cube: Cube, miscInfo: ROPE ¬ NIL];

Write the Volume to the named file.

ReadCubesFromFile: PROC [fileName: ROPE] RETURNS [Cube];

Read the Volume from the named file.

Cube Sequence Procedures

AddToCubeSequence: PROC [cube: Cube, cubes: CubeSequence ¬ NIL]

RETURNS [CubeSequence];

Add cube to cubes, lengthening cubes if necessary.

LengthenCubeSequence: PROC [cubes: CubeSequence, amount: REAL ¬ 1.3]

RETURNS [CubeSequence];

Return a copy of the input sequence whose maxLength is amount*input.maxLength.

Cube Stack Support Procedures

NewCubeStack: PROC [length: INT] RETURNS [CubeStack];

Create a new stack of cubes capable of storing length cubes

WriteBottomOfCubeStack: PROC [cube: Cube, cubeStack: CubeStack];

Add cube to the bottom of the stack; may raise ERROR StackOverflow.

ReadTopOfCubeStack: PROC [cubeStack: CubeStack] RETURNS [cube: Cube];

Read a cube from the top of the stack; may raise ERROR StackUnderflow.

CubeStackSize: PROC [cubeStack: CubeStack] RETURNS [INT];

Return the current number of cubes in the stack.

MaxCubeStackSize: PROC [cubeStack: CubeStack] RETURNS [INT];

Return the maximum size obtained by cubeStack.

CubeStackEmpty: PROC [cubeStack: CubeStack] RETURNS [BOOL];

Return true iff there are no cubes in the stack.

LengthenCubeStack: PROC [cubeStack: CubeStack, amount: REAL ¬ 1.3]

RETURNS [CubeStack];

Return a copy of the input CubeStack whose maxLength is amount*input.maxLength.

Cross Support Procedures

ObtainCrossSequence: PROC RETURNS [crossSequence: CrossSequence];

From the pool, obtain a cross sequence with maxLength of 12.

ReleaseCrossSequence: PROC [crossSequence: CrossSequence];

Return the crossSequence to the pool.

Ropes

RopeFromOctant: PROC [octant: Octant] RETURNS [ROPE];

Return the rope describing the octant.

RopeFromFace: PROC [face: Face] RETURNS [ROPE];

Return the rope describing the face.

RopeFromDirection: PROC [direction: Direction] RETURNS [ROPE];

Return the rope describing the direction.

RopeFromDirectionSelect: PROC [directionSelect: DirectionSelect] RETURNS [ROPE];

Return the rope describing the directionSelect.

OctantFromRope: PROC [rope: ROPE] RETURNS [Octant];

Return the octant given the rope; can raise $NoSuchOctant.

FaceFromRope: PROC [rope: ROPE] RETURNS [Face];

Return the face given the rope; can raise $NoSuchDirection.

DirectionFromRope: PROC [rope: ROPE] RETURNS [Direction];

Return the direction given the rope.

RopeFromRefAny: PROC [ref: REF ANY] RETURNS [rope: ROPE];

Return a capitalized rope.