DIRECTORY Basics, G3dBasic, G3dBox, G3dIO, G3dOctree, G3dPlane, FS, FileNames, IO, Real, RefText, Rope;

G3dOctreeImpl: CEDAR MONITOR
IMPORTS Basics, G3dBox, G3dIO, G3dOctree, G3dPlane, FS, FileNames, IO, Real, RefText, Rope
EXPORTS G3dOctree

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

ActiveFaces:				TYPE ~ G3dOctree.ActiveFaces;
Axis:						TYPE ~ G3dOctree.Axis;
Corner:					TYPE ~ G3dOctree.Corner;
CornerDataProc:			TYPE ~ G3dOctree.CornerDataProc;
CornerProc:				TYPE ~ G3dOctree.CornerProc;
CornerRep:				TYPE ~ G3dOctree.CornerRep;
Corners:					TYPE ~ G3dOctree.Corners;
Cross:						TYPE ~ G3dOctree.Cross;
CrossArray:				TYPE ~ G3dOctree.CrossArray;
CrossPolygonProc:		TYPE ~ G3dOctree.CrossPolygonProc;
CrossRep:					TYPE ~ G3dOctree.CrossRep;
CrossSequence:			TYPE ~ G3dOctree.CrossSequence;
CrossSequenceRep:		TYPE ~ G3dOctree.CrossSequenceRep;
CrossedEdge:				TYPE ~ G3dOctree.CrossedEdge;
CrossedEdges:			TYPE ~ G3dOctree.CrossedEdges;
Cube:						TYPE ~ G3dOctree.Cube;
CubeObject:				TYPE ~ G3dOctree.CubeObject;
CubeProc:				TYPE ~ G3dOctree.CubeProc;
CubeRep:					TYPE ~ G3dOctree.CubeRep;
CubeStack:				TYPE ~ G3dOctree.CubeStack;
CubeStackRep:			TYPE ~ G3dOctree.CubeStackRep;
CubeSequence:			TYPE ~ G3dOctree.CubeSequence;
CubeSequenceRep:		TYPE ~ G3dOctree.CubeSequenceRep;
Direction:					TYPE ~ G3dOctree.Direction;
DirectionCorners:		TYPE ~ G3dOctree.DirectionCorners;
DirectionPairs:			TYPE ~ G3dOctree.DirectionPairs;
DirectionSelect:			TYPE ~ G3dOctree.DirectionSelect;
DirectionType:			TYPE ~ G3dOctree.DirectionType;
Edge:						TYPE ~ G3dOctree.Edge;
Face:						TYPE ~ G3dOctree.Face;
FaceNeighborInfo:		TYPE ~ G3dOctree.FaceNeighborInfo;
Intersection:				TYPE ~ G3dOctree.Intersection;
IntersectionList:			TYPE ~ G3dOctree.IntersectionList;
IntersectionType:		TYPE ~ G3dOctree.IntersectionType;
Kids:						TYPE ~ G3dOctree.Kids;
Neighborhood:			TYPE ~ G3dOctree.Neighborhood;
Octant:					TYPE ~ G3dOctree.Octant;
OctantPairs:				TYPE ~ G3dOctree.OctantPairs;
Octree:					TYPE ~ G3dOctree.Octree;
OctreeMode:				TYPE ~ G3dOctree.OctreeMode;
OctreeRep:				TYPE ~ G3dOctree.OctreeRep;
OctreeType:				TYPE ~ G3dOctree.OctreeType;
FourDirections:			TYPE ~ G3dOctree.FourDirections;
FourOctants:				TYPE ~ G3dOctree.FourOctants;
FourCorners:				TYPE ~ G3dOctree.FourCorners;
ThreeCubes:				TYPE ~ G3dOctree.ThreeCubes;
ThreeDirections:			TYPE ~ G3dOctree.ThreeDirections;
ThreeEdges:				TYPE ~ G3dOctree.ThreeEdges;
TwoCorners:				TYPE ~ G3dOctree.TwoCorners;
TwoCubes:				TYPE ~ G3dOctree.TwoCubes;
TwoDirections:			TYPE ~ G3dOctree.TwoDirections;
TwoFaces:				TYPE ~ G3dOctree.TwoFaces;
TwoOctants:				TYPE ~ G3dOctree.TwoOctants;
NewCube: PUBLIC PROC [
size: REAL,
center: Triple ¬ [],
cornerDataProc: CornerDataProc ¬ NIL]
RETURNS [Cube]
~ {
RETURN[NewKid[NIL, size, lbn, 0, NewCorners[size, center, cornerDataProc]]];
};

NewKid: PROC [
parent: Cube,
size: REAL,
octant: Octant,
level: INT,
corners: Corners]
RETURNS [cube: Cube]
~ {
cube ¬ NEW[CubeRep];
cube.parent ¬ parent;
cube.size ¬ size;
cube.octant ¬ octant;
cube.level ¬ level;
cube.terminal ¬ TRUE;
cube.corners ¬ corners;
};

NewCorner: PROC [
point: Triple,
cornerDataProc: CornerDataProc ¬ NIL]
RETURNS [corner: Corner]
~ {
corner ¬ NEW[CornerRep ¬ [point: point]];
};

NewCorners: PUBLIC PROC [
size: REAL,
center: Triple,
cornerDataProc: CornerDataProc ¬ NIL]
RETURNS [corners: Corners]
~ {
d: REAL ~ 0.5*size;
l: REAL ~ center.x-d;
r: REAL ~ center.x+d;
b: REAL ~ center.y-d;
t: REAL ~ center.y+d;
n: REAL ~ center.z-d;
f: REAL ~ center.z+d;
corners ¬ [
NewCorner[[l, b, n], cornerDataProc],
NewCorner[[l, b, f], cornerDataProc],
NewCorner[[l, t, n], cornerDataProc],
NewCorner[[l, t, f], cornerDataProc],
NewCorner[[r, b, n], cornerDataProc],
NewCorner[[r, b, f], cornerDataProc],
NewCorner[[r, t, n], cornerDataProc],
NewCorner[[r, t, f], cornerDataProc]
];
};
Root: PUBLIC PROC [cube: Cube] RETURNS [root: Cube] ~ {
root ¬ cube;
IF cube # NIL THEN WHILE root.parent # NIL DO root ¬ root.parent; ENDLOOP;
};
CubeOk: PUBLIC PROC [cube: Cube] RETURNS [BOOL] ~ {
k: BOOL ¬ FALSE;
IF cube = NIL THEN RETURN[FALSE];
FOR o: Octant IN Octant DO IF cube.kids[o] # NIL THEN {k ¬ TRUE; EXIT}; ENDLOOP;
IF k = cube.terminal THEN RETURN[FALSE];
FOR o: Octant IN Octant DO
k: Cube ¬ cube.kids[o];
IF k # NIL THEN {
IF k.parent # cube THEN RETURN[FALSE];
IF NOT CubeOk[k] THEN RETURN[FALSE];
};
ENDLOOP;
RETURN[TRUE];
};

FullyPointed: PUBLIC PROC [root: Cube] RETURNS [b: BOOL ¬ TRUE] ~ {
bad: ERROR = CODE;
Inner: PROC [cube: Cube] ~ {
terminal: BOOL;
FOR o: Octant IN Octant DO
k: Cube ¬ cube.kids[o];
IF o = Octant.FIRST
THEN terminal ¬ k = NIL
ELSE IF (k # NIL) AND terminal THEN ERROR bad;
IF k # NIL THEN Inner[k];
ENDLOOP;
};
Inner[root ! bad => {b ¬ FALSE; CONTINUE}];
};

NCubes: PUBLIC PROC [root: Cube] RETURNS [nCubes: INT ¬ 0] ~ {
cubeProc: CubeProc ~ {nCubes ¬ nCubes+1};
Apply[root, cubeProc];
};

NTerminalCubes: PUBLIC PROC [root: Cube] RETURNS [nCubes: INT ¬ 0] ~ {
cubeProc: CubeProc ~ {nCubes ¬ nCubes+1};
ApplyToTerminal[root, cubeProc];
};

Center: PUBLIC PROC [cube: Cube] RETURNS [Triple] ~ {
IF cube # NIL THEN {
p0: Triple ~ cube.corners[lbn].point;
p1: Triple ~ cube.corners[rtf].point;
RETURN[[0.5*(p0.x+p1.x), 0.5*(p0.y+p1.y), 0.5*(p0.z+p1.z)]];
};
RETURN[[0.0, 0.0, 0.0]];
};

Size: PUBLIC PROC [cube: Cube] RETURNS [REAL] ~ {
RETURN[IF cube = NIL THEN 0.0 ELSE cube.size];
};

MinSize: PUBLIC PROC [root: Cube] RETURNS [min: REAL] ~ {
MinProc: CubeProc ~ {IF cube.size < min THEN min ¬ cube.size};
min ¬ 100000000.0;
ApplyToTerminal[root, MinProc];
};

BoxOfCube: PUBLIC PROC [cube: Cube] RETURNS [Box] ~ {
RETURN[[cube.corners[lbn].point, cube.corners[rtf].point]];
};

AnyKids: PUBLIC PROC [cube: Cube] RETURNS [BOOL] ~ {
FOR o: Octant IN Octant DO IF cube.kids[o] # NIL THEN RETURN[TRUE]; ENDLOOP;
RETURN[FALSE];
};

DepthOf: PUBLIC PROC [cube: Cube] RETURNS [d: INT ¬ 0] ~ {
Inner: PROC [cube: Cube, level: INT] ~ {
ll: INT ¬ level+1;
FOR o: Octant IN Octant DO
k: Cube ¬ cube.kids[o];
IF k # NIL THEN Inner[k, ll];
REPEAT
FINISHED => IF level > d THEN d ¬ level;
ENDLOOP;
};
Inner[cube, 0];
};
Subdivide: PUBLIC PROC [cube: Cube] ~ {
IF cube # NIL AND cube.terminal THEN {
FaceTry: PROC [d: Direction] RETURNS [corner: Corner ¬ NIL] ~ {
KidsTry: PROC [o0a, o0b, o1a, o1b: Octant] RETURNS [corner: Corner ¬ NIL] ~ {
IF c.kids[o0a] # NIL THEN RETURN[c.kids[o0a].corners[o0b]];
IF c.kids[o0b] # NIL THEN RETURN[c.kids[o0b].corners[o0a]];
IF c.kids[o1a] # NIL THEN RETURN[c.kids[o1a].corners[o1b]];
IF c.kids[o1b] # NIL THEN RETURN[c.kids[o1b].corners[o1a]];
};
c: Cube ~ neighbors[d];
IF c # NIL AND NOT c.terminal
THEN corner ¬ SELECT d FROM
l	=> KidsTry[rbn, rtf, rbf, rtn],
r	=> KidsTry[lbn, ltf, lbf, ltn],
b	=> KidsTry[ltn, rtf, ltf, rtn],
t	=> KidsTry[lbn, rbf, lbf, rbn],
n	=> KidsTry[lbf, rtf, ltf, rbf],
f	=> KidsTry[lbn, rtn, ltn, rbn]
ENDCASE => NIL;
};
EdgeTry: PROC [d0, d1, d2: Direction, e0, e1, e2: Edge] RETURNS [corner: Corner] ~ {
NeighborTry: PROC [d: Direction, e: Edge] RETURNS [corner: Corner ¬ NIL] ~ {
KidsTry: PROC [o0, o1: Octant] RETURNS [corner: Corner ¬ NIL] ~ {
IF c.kids[o0] # NIL THEN RETURN[c.kids[o0].corners[o1]];
IF c.kids[o1] # NIL THEN RETURN[c.kids[o1].corners[o0]];
};
c: Cube ~ neighbors[d];
IF c # NIL AND NOT c.terminal
THEN corner ¬ SELECT e FROM
lb	=> KidsTry[lbn, lbf],
lt	=> KidsTry[ltn, ltf],
ln	=> KidsTry[lbn, ltn],
lf	=> KidsTry[lbf, ltf],
rb	=> KidsTry[rbn, rbf],
rt	=> KidsTry[rtn, rtf],
rn	=> KidsTry[rbn, rtn],
rf	=> KidsTry[rbf, rtf],
bn	=> KidsTry[lbn, rbn],
bf	=> KidsTry[lbf, rbf],
tn	=> KidsTry[ltn, rtn],
tf	=> KidsTry[ltf, rtf],
ENDCASE => NIL;
};
corner ¬ NeighborTry[d0, e0];
IF corner = NIL THEN corner ¬ NeighborTry[d1, e1];
IF corner = NIL THEN corner ¬ NeighborTry[d2, e2];
};
SubCube: PROC [octant: Octant, corners: Corners] ~ {
kid: Cube ~ cube.kids[octant] ¬ NewKid[cube, kSize, octant, kidLevel, corners];
kid.terminal ¬ TRUE;
kid.size ¬ kSize;
};
kSize: REAL ~ 0.5*Size[cube];
kidLevel: INT ~ cube.level+1;
c: Triple ~ Center[cube];
neighbors: Neighborhood ~ Neighbors[cube];
cornerDataProc: CornerDataProc ¬ NIL;
ccc:	Corner ~ NewCorner[c, cornerDataProc];
lbn:	Corner ~ cube.corners[lbn];
lbf:	Corner ~ cube.corners[lbf];
ltn:	Corner ~ cube.corners[ltn];
ltf:	Corner ~ cube.corners[ltf];
rbn:	Corner ~ cube.corners[rbn];
rbf:	Corner ~ cube.corners[rbf];
rtn:	Corner ~ cube.corners[rtn];
rtf:	Corner ~ cube.corners[rtf];
lb:		Corner ¬ EdgeTry[l, lb, b,		rb, rt, lt];
lt:		Corner ¬ EdgeTry[l, lt, t,		rt, rb, lb];
ln:		Corner ¬ EdgeTry[l, ln, n,	rn, rf, lf];
lf:		Corner ¬ EdgeTry[l, lf, f,		rf, rn, ln];
rb:		Corner ¬ EdgeTry[r, rb, b,	lb, lt, rt];
rt:		Corner ¬ EdgeTry[r, rt, t,		lt, lb, rb];
rn:	Corner ¬ EdgeTry[r, rn, n,	ln, lf, rf];
rf:		Corner ¬ EdgeTry[r, rf, f,		lf, ln, rn];
bn:	Corner ¬ EdgeTry[b, bn, n,	tn, tf, bf];
bf:		Corner ¬ EdgeTry[b, bf, f,	tf, tn, bn];
tn:		Corner ¬ EdgeTry[t, tn, n,	bn, bf, tf];
tf:		Corner ¬ EdgeTry[t, tf, f,		bf, bn, tn];
l:		Corner ¬ FaceTry[l];
r:		Corner ¬ FaceTry[r];
b:		Corner ¬ FaceTry[b];
t:		Corner ¬ FaceTry[t];
n:		Corner ¬ FaceTry[n];
f:		Corner ¬ FaceTry[f];
IF lb = NIL THEN lb ¬	NewCorner[[c.x-kSize,	c.y-kSize,	c.z], cornerDataProc];
IF lt = NIL THEN lt ¬	NewCorner[[c.x-kSize,	c.y+kSize,	c.z], cornerDataProc];
IF ln = NIL THEN ln ¬	NewCorner[[c.x-kSize,	c.y,			c.z-kSize], cornerDataProc];
IF lf = NIL THEN lf ¬	NewCorner[[c.x-kSize,	c.y,			c.z+kSize], cornerDataProc];
IF rb = NIL THEN rb ¬	NewCorner[[c.x+kSize,	c.y-kSize,	c.z], cornerDataProc];
IF rt = NIL THEN rt ¬	NewCorner[[c.x+kSize,	c.y+kSize,	c.z], cornerDataProc];
IF rn = NIL THEN rn ¬	NewCorner[[c.x+kSize,	c.y,			c.z-kSize], cornerDataProc];
IF rf = NIL THEN rf ¬	NewCorner[[c.x+kSize,	c.y,			c.z+kSize], cornerDataProc];
IF bn = NIL THEN bn ¬ NewCorner[[c.x,			c.y-kSize,	c.z-kSize], cornerDataProc];
IF bf = NIL THEN bf ¬	NewCorner[[c.x,			c.y-kSize,	c.z+kSize], cornerDataProc];
IF tn = NIL THEN tn ¬	NewCorner[[c.x,			c.y+kSize,	c.z-kSize], cornerDataProc];
IF tf = NIL THEN tf ¬	NewCorner[[c.x,			c.y+kSize,	c.z+kSize], cornerDataProc];
IF l = NIL THEN	l ¬	NewCorner[[c.x-kSize,	c.y,			c.z], cornerDataProc];
IF r = NIL THEN	r ¬	NewCorner[[c.x+kSize,	c.y,			c.z], cornerDataProc];
IF b = NIL THEN b ¬	NewCorner[[c.x,			c.y-kSize,	c.z], cornerDataProc];
IF t = NIL THEN t ¬		NewCorner[[c.x,			c.y+kSize,	c.z], cornerDataProc];
IF n = NIL THEN n ¬	NewCorner[[c.x,			c.y,			c.z-kSize], cornerDataProc];
IF f = NIL THEN f ¬	NewCorner[[c.x,			c.y,			c.z+kSize], cornerDataProc];
cube.terminal ¬ FALSE;
SubCube[lbn, [lbn, lb, ln, l, bn, b, n, ccc]];
SubCube[lbf, [lb, lbf, l, lf, b, bf, ccc, f]];
SubCube[ltn, [ln, l, ltn, lt, n, ccc, tn, t]];
SubCube[ltf, [l, lf, lt, ltf, ccc, f, t, tf]];
SubCube[rbn, [bn, b, n, ccc, rbn, rb, rn, r]];
SubCube[rbf, [b, bf, ccc, f, rb, rbf, r, rf]];
SubCube[rtn, [n, ccc, tn, t, rn, r, rtn, rt]];
SubCube[rtf, [ccc, f, t, tf, r, rf, rt, rtf]];
};
};

SubdivideTerminal: PUBLIC PROC [cube: Cube] ~ {
cubeProc: CubeProc ~ {Subdivide[cube]};
ApplyToTerminal[cube, cubeProc];
};

RecursivelySubdivide: PUBLIC PROC [cube: Cube, nLevels: INT] ~ {
THROUGH [0..nLevels) DO SubdivideTerminal[cube]; ENDLOOP;
};
TestCube: PROC [cube: Cube] ~ {
tol: REAL ~ 0.01*Size[cube];
InnerTest: PROC [cube: Cube] ~ {
Test: PROC [o0, o1: Octant, s: {x, y, z}] ~ {
IF s # x AND ABS[c[o0].point.x-c[o1].point.x] > tol THEN ERROR;
IF s # y AND ABS[c[o0].point.y-c[o1].point.y] > tol THEN ERROR;
IF s # z AND ABS[c[o0].point.z-c[o1].point.z] > tol THEN ERROR;
};
c: Corners ¬ cube.corners;
Test[lbn, ltn, y]; Test[lbf, ltf, y]; Test[lbn, lbf, z]; Test[ltn, ltf, z];
Test[rbn, rtn, y]; Test[rbf, rtf, y]; Test[rbn, rbf, z]; Test[rtn, rtf, z];
Test[lbn, rbn, x]; Test[lbf, rbf, x]; Test[ltn, rtn, x]; Test[ltf, rtf, x];
};
InnerTest[cube];
};

AddCube: PUBLIC PROC [cube: Cube, face: Face, fullyPointed: BOOL ¬ TRUE]
RETURNS [root: Cube]
~ {
IF cube = NIL THEN RETURN[NIL];
TestCube[cube];
IF FaceNeighbor[cube, face] # NIL THEN RETURN[Root[cube]];
IF cube.parent = NIL THEN {
cubeProc: CubeProc ~ {cube.level ¬ cube.level+1};
NewParent: PUBLIC PROC [cube: Cube, o: Octant] RETURNS [root: Cube] ~ {
oo: Octant ~ G3dOctree.OppositeOctant[o];
d: REAL ~ 2.0*Size[cube];
l, r, b, t, n, f: REAL;
c: Triple ~ cube.corners[o].point;
pp: Triple ~ cube.corners[oo].point;
SELECT oo FROM
lbn		=> {l ¬ pp.x;	b ¬ pp.y;	n ¬ pp.z;	r ¬ pp.x+d;	t ¬ pp.y+d;	f ¬ pp.z+d};
lbf		=> {l ¬ pp.x;	b ¬ pp.y;	f ¬ pp.z;	r ¬ pp.x+d;	t ¬ pp.y+d;	n ¬ pp.z-d};
ltn		=> {l ¬ pp.x;	t ¬ pp.y;	n ¬ pp.z;	r ¬ pp.x+d;	b ¬ pp.y-d;	f ¬ pp.z+d};
ltf			=> {l ¬ pp.x;	t ¬ pp.y;	f ¬ pp.z;	r ¬ pp.x+d;	b ¬ pp.y-d;	n ¬ pp.z-d};
rbn		=> {r ¬ pp.x;	b ¬ pp.y;	n ¬ pp.z;	l ¬ pp.x-d;	t ¬ pp.y+d;	f ¬ pp.z+d}; 
rbf		=> {r ¬ pp.x;	b ¬ pp.y;	f ¬ pp.z;	l ¬ pp.x-d;	t ¬ pp.y+d;	n ¬ pp.z-d};
rtn		=> {r ¬ pp.x;	t ¬ pp.y;	n ¬ pp.z;	l ¬ pp.x-d;	b ¬ pp.y-d;	f ¬ pp.z+d};
ENDCASE	=> {r ¬ pp.x;	t ¬ pp.y;	f ¬ pp.z;	l ¬ pp.x-d;	b ¬ pp.y-d;	n ¬ pp.z-d};
root ¬ NEW[CubeRep ¬ [size: d]];
root.corners[oo] ¬ cube.corners[oo];
IF oo # lbn THEN root.corners[lbn] ¬ NewCorner[[l, b, n]];
IF oo # lbf THEN root.corners[lbf] ¬ NewCorner[[l, b, f]];
IF oo # ltn THEN root.corners[ltn] ¬ NewCorner[[l, t, n]];
IF oo # ltf THEN root.corners[ltf] ¬ NewCorner[[l, t, f]];
IF oo # rbn THEN root.corners[rbn] ¬ NewCorner[[r, b, n]];
IF oo # rbf THEN root.corners[rbf] ¬ NewCorner[[r, b, f]];
IF oo # rtn THEN root.corners[rtn] ¬ NewCorner[[r, t, n]];
IF oo # rtf THEN root.corners[rtf] ¬ NewCorner[[r, t, f]];
};
o: Octant ~ SELECT face FROM l=> lbn, r=> rtf, b=> rbn, t=> ltf, n=> ltn, ENDCASE=> rbf;
opp: Octant ~ G3dOctree.OppositeOctant[o];
cube.parent ¬ root ¬ NewParent[cube, o];
cube.octant ¬ opp;
root.corners[opp] ¬ cube.corners[opp];
root.kids[opp] ¬ cube;
Apply[root, cubeProc];
root.level ¬ 0;
TestCube[root];
};
{
AddCubeToParent: PROC [parent: Cube, octant: Octant, size: REAL, level: INT] ~ {
new: Cube¬ NEW[CubeRep ¬ [size: size, octant: octant, terminal: TRUE, parent: parent]];
c: Corner ¬ parent.corners[octant];
l, r: REAL ¬ parent.corners[octant].point.x;
b, t: REAL ¬ parent.corners[octant].point.y;
n, f: REAL ¬ parent.corners[octant].point.z;
SELECT octant FROM
lbn	=> {r ¬ l+size;	t ¬ b+size;	f ¬ n+size};
lbf	=> {r ¬ l+size;	t ¬ b+size;	n ¬ f-size};
ltn	=> {r ¬ l+size;	b ¬ t-size;	f ¬ n+size};
ltf		=> {r ¬ l+size;	b ¬ t-size;	n ¬ f-size};
rbn	=> {l ¬ r-size;	t ¬ b+size;	f ¬ n+size};
rbf	=> {l ¬ r-size;	t ¬ b+size;	n ¬ f-size};
rtn	=> {l ¬ r-size;	b ¬ t-size;	f ¬ n+size};
rtf		=> {l ¬ r-size;	b ¬ t-size;	n ¬ f-size};
ENDCASE;
parent.kids[octant] ¬ new;
new.level ¬ level;
FOR face: Face IN Face DO
neighbor: Cube ~ FaceNeighbor[new, face];
IF neighbor # NIL THEN {
n: Corners ~ neighbor.corners;
SELECT face FROM
l => {
new.corners[lbn] ¬ n[rbn]; new.corners[lbf] ¬ n[rbf];
new.corners[ltn] ¬ n[rtn];	new.corners[ltf] ¬ n[rtf];
};
r => {
new.corners[rbn] ¬ n[lbn]; new.corners[rbf] ¬ n[lbf];
new.corners[rtn] ¬ n[ltn];	new.corners[rtf] ¬ n[ltf];
};
b => {
new.corners[lbn] ¬ n[ltn];	new.corners[lbf] ¬ n[ltf];
new.corners[rbn] ¬ n[rtn];	new.corners[rbf] ¬ n[rtf];
};
t => {
new.corners[ltn] ¬ n[lbn];	new.corners[ltf] ¬ n[lbf];
new.corners[rtn] ¬ n[rbn];	new.corners[rtf] ¬ n[rbf];
};
n => {
new.corners[lbn] ¬ n[lbf];	new.corners[ltn] ¬ n[ltf];
new.corners[rbn] ¬ n[rbf];	new.corners[rtn] ¬ n[rtf];
};
ENDCASE => {
new.corners[lbf] ¬ n[lbn];	new.corners[ltf] ¬ n[ltn];
new.corners[rbf] ¬ n[rbn];	new.corners[rtf] ¬ n[rtn];
};
};
ENDLOOP;
new.corners[octant] ¬ parent.corners[octant];
FOR o: Octant IN Octant DO
IF new.corners[o] = NIL THEN {
new.corners[o] ¬ NEW[CornerRep];
new.corners[o].point ¬ SELECT o FROM
lbn		=> [l, b, n],
lbf		=> [l, b, f],
ltn		=> [l, t, n],
ltf			=> [l, t, f],
rbn		=> [r, b, n],
rbf		=> [r, b, f],
rtn		=> [r, t, n],
ENDCASE	=> [r, t, f];
};
ENDLOOP;
TestCube[new];
};
parent: Cube ¬ cube.parent;
info: FaceNeighborInfo ~ GetFaceNeighborInfo[cube, face];
IF info.recurse THEN {
neighborOfParent: Cube ¬ FaceNeighbor[cube.parent, face];
IF neighborOfParent = NIL THEN root ¬ AddCube[cube.parent, face, fullyPointed];
IF (neighborOfParent ¬ FaceNeighbor[cube.parent, face]) = NIL THEN ERROR;
parent ¬ neighborOfParent;
};
parent.terminal ¬ FALSE;
AddCubeToParent[parent, info.nOctant, cube.size, cube.level];
IF fullyPointed THEN FOR o: Octant IN Octant DO
IF parent.kids[o] = NIL THEN AddCubeToParent[parent, o, cube.size, cube.level];
ENDLOOP;
};
RETURN[Root[cube]];
};

DeleteCube: PUBLIC PROC [cube: Cube] ~ {
IF cube # NIL AND cube.parent # NIL THEN cube.parent.kids[cube.octant] ¬ NIL;
};

MakeRestrictedOctree: PUBLIC PROC [root: Cube] ~ {
Inner: CubeProc ~ {
Test: PROC [c: Cube] RETURNS [b: BOOL] ~ {b ¬ c # NIL AND NOT c.terminal};
IF cube # NIL THEN {
neighbors: Neighborhood ¬ Neighbors[cube];
FOR face: Face IN Face DO
neighbor: Cube ¬ neighbors[DirectionFromFace[face]];
IF neighbor # NIL AND NOT neighbor.terminal THEN {
fourOcts: FourOctants ¬ FaceOctants[G3dOctree.OppositeFace[face]];
IF Test[neighbor.kids[fourOcts.o0]] THEN GOTO subdivide;
IF Test[neighbor.kids[fourOcts.o1]] THEN GOTO subdivide;
IF Test[neighbor.kids[fourOcts.o2]] THEN GOTO subdivide;
IF Test[neighbor.kids[fourOcts.o3]] THEN GOTO subdivide;
};
ENDLOOP;
FOR edge: Edge IN Edge DO
neighbor: Cube ¬ neighbors[DirectionFromEdge[edge]];
IF neighbor # NIL AND NOT neighbor.terminal THEN {
twoOcts: TwoOctants ¬ EdgeOctants[DiagonalEdge[edge]];
IF Test[neighbor.kids[twoOcts.o0]] THEN GOTO subdivide;
IF Test[neighbor.kids[twoOcts.o1]] THEN GOTO subdivide;
};
ENDLOOP;
FOR octant: Octant IN Octant DO
neighbor: Cube ¬ neighbors[DirectionFromOctant[octant]];
IF neighbor # NIL AND NOT neighbor.terminal
AND Test[neighbor.kids[G3dOctree.OppositeOctant[octant]]] THEN GOTO subdivide;
ENDLOOP;
};
EXITS
subdivide => {
Subdivide[cube];
IF cube.parent # NIL THEN {
grandNeighbors: Neighborhood ¬ Neighbors[cube.parent];
threeEdges: ThreeEdges ¬ EdgesFromOctant[cube.octant];
threeDirections: ThreeDirections ¬ DirectionsFromOctant[cube.octant];
[] ¬ Inner[grandNeighbors[DirectionFromOctant[cube.octant]]];
[] ¬ Inner[grandNeighbors[DirectionFromEdge[threeEdges.e0]]];
[] ¬ Inner[grandNeighbors[DirectionFromEdge[threeEdges.e1]]];
[] ¬ Inner[grandNeighbors[DirectionFromEdge[threeEdges.e2]]];
[] ¬ Inner[grandNeighbors[threeDirections.d0]];
[] ¬ Inner[grandNeighbors[threeDirections.d1]];
[] ¬ Inner[grandNeighbors[threeDirections.d2]];
};
};
};
ApplyToTerminal[root, Inner];
};
PointInCube: PUBLIC PROC [point: Triple, cube: Cube, fudge: REAL ¬ 0.] RETURNS [BOOL] ~ {
IF cube = NIL
THEN RETURN[FALSE]
ELSE {
extra: REAL ~ fudge*Size[cube];
RETURN[
point.x >= cube.corners[lbn].point.x-extra AND
point.x <= cube.corners[rbn].point.x+extra AND
point.y >= cube.corners[lbn].point.y-extra AND
point.y <= cube.corners[ltn].point.y+extra AND
point.z >= cube.corners[lbn].point.z-extra AND
point.z <= cube.corners[lbf].point.z+extra];
};
};

WhichCube: PUBLIC PROC [point: Triple, root: Cube] RETURNS [Cube] ~ {
Test: PROC [cube: Cube] RETURNS [Cube] ~ {
FOR octant: Octant IN Octant DO
kid: Cube ¬ cube.kids[octant];
IF kid # NIL AND PointInCube[point, kid] THEN RETURN[Test[kid]];
ENDLOOP;
RETURN[cube];
};
RETURN[IF PointInCube[point, root] THEN Test[root] ELSE NIL];
};

FirstKid: PUBLIC PROC [cube: Cube] RETURNS [Cube] ~ {
IF cube = NIL THEN RETURN[NIL];
FOR o: Octant IN Octant DO IF cube.kids[o] # NIL THEN RETURN[cube.kids[o]]; ENDLOOP;
RETURN[NIL];
};

FirstTerminalKid: PUBLIC PROC [cube: Cube] RETURNS [Cube] ~ {
kid: Cube ¬ cube;
WHILE (kid # NIL AND NOT kid.terminal) DO kid ¬ FirstKid[kid]; ENDLOOP;
RETURN[kid];
};
Apply: PUBLIC PROC [cube: Cube, cubeProc: CubeProc] ~ {
Inner: PROC [cube: Cube] ~ {
IF cube # NIL AND cubeProc[cube]
THEN FOR o: Octant IN Octant DO Inner[cube.kids[o]]; ENDLOOP;
};
Inner[cube];
};

ApplyToKids: PUBLIC PROC [cube: Cube, cubeProc: CubeProc] ~ {
Inner: PROC [cube: Cube] ~ {
IF cube # NIL AND cubeProc[cube]
THEN FOR o: Octant IN Octant DO Inner[cube.kids[o]]; ENDLOOP;
};
IF cube # NIL THEN FOR o: Octant IN Octant DO Inner[cube.kids[o]]; ENDLOOP;
};

ApplyToTerminal: PUBLIC PROC [cube: Cube, cubeProc: CubeProc] ~ {
Inner: PROC [cube: Cube] ~ {
IF cube = NIL THEN RETURN;
IF cube.terminal
THEN {IF NOT cubeProc[cube] THEN RETURN}
ELSE FOR o: Octant IN Octant DO Inner[cube.kids[o]]; ENDLOOP;
};
Inner[cube];
};

ApplyToLevel: PUBLIC PROC [cube: Cube, cubeProc: CubeProc, level: INT] ~ {
Inner: PROC [cube: Cube] ~ {
IF cube = NIL OR cube.level > level THEN RETURN;
IF cube.level = level
THEN {IF NOT cubeProc[cube] THEN RETURN}
ELSE FOR o: Octant IN Octant DO Inner[cube.kids[o]]; ENDLOOP;
};
Inner[cube];
};

ApplyToTerminalCorners: PUBLIC PROC [cube: Cube, cornerProc: CornerProc] ~ {
abort: ERROR = CODE;
cubeProc: CubeProc ~ {
Test: PROC [d: Direction, o: Octant] ~ {
IF neighbors[d] = NIL THEN IF NOT cornerProc[cube.corners[o]] THEN ERROR abort;
};
neighbors: Neighborhood ~ Neighbors[cube];
IF NOT cornerProc[cube.corners[lbn]] THEN ERROR abort;
Test[f, lbf]; Test[rf, rbf]; Test[r, rbn]; Test[t, ltn]; Test[tf, ltf]; Test[rtf, rtf]; Test[rt, rtn];
};
ApplyToTerminal[cube, cubeProc ! abort => CONTINUE];
};

ApplyToNonParentKidCorners: PUBLIC PROC [cube: Cube, cornerProc: CornerProc] ~ {
Apply: PROC [d: Direction] RETURNS [BOOL] ~ {RETURN[cornerProc[directionCorners[d]]]};
directionCorners: DirectionCorners ~ GetDirectionCorners[cube];
IF NOT Apply[ln] THEN RETURN;			-- midpoint of ln edge
IF NOT Apply[lf] THEN RETURN;			-- midpoint of lf edge
IF NOT Apply[rn] THEN RETURN;		-- midpoint of rn edge
IF NOT Apply[rf] THEN RETURN;			-- midpoint of rf edge
IF NOT Apply[lb] THEN RETURN;			-- midpoint of lb edge
IF NOT Apply[lt] THEN RETURN;			-- midpoint of lt edge
IF NOT Apply[rb] THEN RETURN;			-- midpoint of rb edge
IF NOT Apply[rt] THEN RETURN;			-- midpoint of rt edge
IF NOT Apply[bn] THEN RETURN;		-- midpoint of bn edge
IF NOT Apply[tn] THEN RETURN;			-- midpoint of tn edge
IF NOT Apply[bf] THEN RETURN;			-- midpoint of bf edge
IF NOT Apply[tf] THEN RETURN;			-- midpoint of tf edge
IF NOT Apply[l] THEN RETURN;			-- center of l face
IF NOT Apply[r] THEN RETURN;			-- center of r face
IF NOT Apply[b] THEN RETURN;			-- center of b face
IF NOT Apply[t] THEN RETURN;			-- center of t face
IF NOT Apply[n] THEN RETURN;			-- center of n face
IF NOT Apply[f] THEN RETURN;			-- center of f face
IF NOT Apply[c] THEN RETURN;			-- center
};
Dir: TYPE ~ RECORD [x --(l-r)--, y --(b-t)--, z --(n-f)--: [-1..1], none: BOOL ¬ FALSE];

opposites:		ARRAY Direction OF Direction ~ InitOpposites[];
sums:			ARRAY Direction OF ARRAY Direction OF Direction ~ InitSums[];
fromOctants:	ARRAY Octant OF ARRAY Octant OF Direction ~ InitFromOctants[];

decode: ARRAY Direction OF Dir ~ [
none:	[0,		0,		0,	TRUE],
c:		[0,		0,		0],
l:		[-1,	0,		0],
r:		[1,		0,		0],
b:		[0,		-1,	0],
t:		[0,		1,		0],
n:		[0,		0,		-1],
f:		[0,		0,		1],
lb:		[-1,	-1,	0],
lt:		[-1,	1,		0],
ln:		[-1,	0,		-1],
lf:		[-1,	0,		1],
rb:		[1,		-1,	0],
rt:		[1,		1,		0],
rn:	[1,		0,		-1],
rf:		[1,		0,		1],
bn:	[0,		-1,	-1],
bf:		[0,		-1,	1],
tn:		[0,		1,		-1],
tf:		[0,		1,		1],
lbn:	[-1,	-1,	-1],
lbf:	[-1,	-1,	1],
ltn:	[-1,	1,		-1],
ltf:	[-1,	1,		1],
rbn:	[1,		-1,	-1],
rbf:	[1,		-1,	1],
rtn:	[1,		1,		-1],
rtf:	[1,		1,		1]
];

Encode: PROC [x, y, z: INT] RETURNS [Direction] ~ {
FOR d: Direction IN Direction DO
dir: Dir ~ decode[d];
IF NOT dir.none AND dir.x = x AND dir.y = y AND dir.z = z THEN RETURN [d]
ENDLOOP;
RETURN [none]
};

InitOpposites: PROC RETURNS [a: ARRAY Direction OF Direction] ~ INLINE {
Opposite: PROC [d: Direction] RETURNS [Direction] ~ {
a: Dir ~ decode[d];
RETURN [Encode[x: -a.x, y: -a.y, z: -a.z]]
};
FOR d: Direction IN Direction DO
a[d] ¬ Opposite[d];
ENDLOOP;
};

InitSums: PROC RETURNS [a: ARRAY Direction OF ARRAY Direction OF Direction] ~ INLINE {
Sum: PROC [d0, d1: Direction] RETURNS [Direction] ~ {
d0Dir: Dir ~ decode[d0];
d1Dir: Dir ~ decode[d1];
RETURN[SELECT TRUE FROM
d0Dir.none => d1,
d1Dir.none => d0,
ENDCASE => Encode[d0Dir.x+d1Dir.x, d0Dir.y+d1Dir.y, d0Dir.z+d1Dir.z]];
};
FOR d0: Direction IN Direction DO
FOR d1: Direction IN Direction DO
a[d0][d1] ¬ Sum[d0, d1];
ENDLOOP;
ENDLOOP;
};

InitFromOctants: PROC RETURNS [a: ARRAY Octant OF ARRAY Octant OF Direction]~INLINE {
FromOctants: PROC [octant0, octant1: Octant] RETURNS [Direction] ~ {
Dif: PROC [b0, b1: [-1..1]] RETURNS [[-1..1]] ~ {
RETURN[SELECT b1 FROM b0 => 0, > b0 => 1, ENDCASE => -1];
};
d0: Dir ~ decode[DirectionFromOctant[octant0]];
d1: Dir ~ decode[DirectionFromOctant[octant1]];
RETURN[Encode[Dif[d0.x, d1.x], Dif[d0.y, d1.y], Dif[d0.z, d1.z]]];
};
FOR o0: Octant IN Octant DO
FOR o1: Octant IN Octant DO a[o0][o1] ¬ FromOctants[o0, o1]; ENDLOOP;
ENDLOOP;
};

DirectionTypeFromDirection: PUBLIC PROC [direction: Direction]
RETURNS [DirectionType]
~ {
RETURN[SELECT direction FROM
l, r, b, t, n, f => face,
lb, lt, ln, lf, rb, rt, rn, rf, bn, bf, tn, tf => edge,
lbn, lbf, ltn, ltf, rbn, rbf, rtn, rtf => corner,
ENDCASE => none];
};

DirectionFromFace: PUBLIC PROC [face: Face] RETURNS [Direction] ~ {
RETURN[SELECT face FROM l => l, r => r, b => b, t => t, n => n, f => f, ENDCASE => none];
};

DirectionFromEdge: PUBLIC PROC [edge: Edge] RETURNS [Direction] ~ {
RETURN[SELECT edge FROM
lb=>lb, lt=>lt, rb=>rb, rt=>rt, ln=>ln, lf=>lf, rn=>rn, rf=>rf, bn=>bn, bf=>bf, tn=>tn, tf=>tf,
ENDCASE => none];
};

DirectionFromOctant: PUBLIC PROC [octant: Octant] RETURNS [Direction] ~ {
RETURN[SELECT octant FROM
lbn => lbn, lbf => lbf, ltn => ltn, ltf => ltf, rbn => rbn, rbf => rbf, rtn => rtn, rtf => rtf,
ENDCASE => none];
};

DirectionFromOctants: PUBLIC PROC [octant0, octant1: Octant] RETURNS [Direction] ~ {
RETURN[fromOctants[octant0][octant1]];
};

DirectionFromPoints: PUBLIC PROC [point0, point1: Triple] RETURNS [Direction] ~ {
xSame: BOOL ~ point0.x = point1.x;
ySame: BOOL ~ point0.y = point1.y;
zSame: BOOL ~ point0.z = point1.z;
IF xSame THEN {
IF ySame THEN RETURN[IF point1.z > point0.z THEN f ELSE n];
IF zSame THEN RETURN[IF point1.y > point0.y THEN t ELSE b];
}
ELSE IF ySame THEN {
IF xSame THEN RETURN[IF point1.z > point0.z THEN f ELSE n];
IF zSame THEN RETURN[IF point1.x > point0.x THEN r ELSE l];
}
ELSE IF zSame THEN {
IF xSame THEN RETURN[IF point1.y > point0.y THEN t ELSE b];
IF ySame THEN RETURN[IF point1.x > point0.x THEN r ELSE l];
};
RETURN[none];
};

OppositeFace: PUBLIC PROC [face: Face] RETURNS [Face] ~ {
RETURN[SELECT face FROM l => r, r => l, b => t, t => b, n => f, ENDCASE => n];
};

OppositeDirection: PUBLIC PROC [direction: Direction] RETURNS [Direction] ~ {
RETURN[opposites[direction]];
};

AddDirection: PUBLIC PROC [d0, d1: Direction] RETURNS [Direction] ~ {
RETURN[sums[d0][d1]];
};

EdgeFromDirection: PUBLIC PROC [d: Direction] RETURNS [Edge] ~ {
RETURN[SELECT d FROM
ln	=> ln, lf	=> lf, rn	=> rn, rf	=> rf, bn	=> bn, bf	=> bf, tn	=> tn, tf	=> tf,
ENDCASE => ERROR];
};
OctantFromDirection: PUBLIC PROC [d: Direction] RETURNS [Octant] ~ {
RETURN[SELECT d FROM
lbn => lbn, lbf => lbf, ltn => ltn, ltf => ltf, rbn => rbn, rbf => rbf, rtn => rtn, rtf => rtf,
ENDCASE => ERROR];
};
OctantFromThreeDirections: PUBLIC PROC [d0, d1, d2: Direction] RETURNS [o: Octant] ~ {
o ¬ OctantFromDirection[AddDirection[AddDirection[d0, d1], d2]];
};

FaceFromDirection: PUBLIC PROC [d: Direction] RETURNS [Face] ~ {
RETURN[SELECT d FROM
l => l, r => r, b => b, t => t, n => n, f => f,
ENDCASE => ERROR];
};

FaceDirections: PUBLIC PROC [face: Face] RETURNS [fd: FourDirections] ~ {
fd ¬ SELECT face FROM
l => [lb, lt, ln, lf], r => [rb, rt, rn, rf], b => [lb, rb, bn, bf],
t => [lt, rt, tn, tf], n => [ln, rn, bn, tn], ENDCASE => [lf, rf, bf, tf];
};

NormalFromFace: PUBLIC PROC [face: Face] RETURNS [Triple] ~ {
RETURN[SELECT face FROM
l => [-1.0, 0.0, 0.0], r => [1.0, 0.0, 0.0], b => [0.0, -1.0, 0.0],
t => [0.0, 1.0, 0.0], n => [0.0, 0.0, -1.0], ENDCASE => [0.0, 0.0, 1.0]];
};
PlaneFromCubeFace: PUBLIC PROC [cube: Cube, face: Face] RETURNS [p: Plane] ~ {
o: Octant ¬ SELECT face FROM l=>lbn, r=>rbn, b=>lbn, t=>ltn, n=>lbn, ENDCASE=>lbf;
p ¬ G3dPlane.FromPointAndNormal[cube.corners[o].point, NormalFromFace[face]];
};

EdgesFromOctant: PUBLIC PROC [octant: Octant] RETURNS [ThreeEdges] ~ {
RETURN[SELECT octant FROM
lbn => [lb, ln, bn], lbf => [lb, lf, bf], ltn => [lt, ln, tn], ltf => [lt, lf, tf],
rbn => [rb, rn, bn], rbf => [rb, rf, bf], rtn => [rt, rn, tn], ENDCASE => [rt, rf, tf]];
};
DirectionsFromOctant: PUBLIC PROC [octant: Octant] RETURNS [ThreeDirections] ~ {
RETURN[SELECT octant FROM
lbn => [l, b, n], lbf => [l, b, f], ltn => [l, t, n], ltf => [l, t, f],
rbn => [r, b, n], rbf => [r, b, f], rtn => [r, t, n], ENDCASE => [r, t, f]];
};

FaceFromEdgeOctant: PUBLIC PROC [edge: Edge, octant: Octant] RETURNS [Face] ~ {
RETURN[SELECT edge FROM
lb =>			IF octant = lbn	THEN l	ELSE b,
lt =>			IF octant = ltn	THEN t	ELSE l,
ln =>			IF octant = lbn	THEN n	ELSE l,
lf =>			IF octant = lbf	THEN l	ELSE f,
rb =>			IF octant = rbn	THEN b	ELSE r,
rt =>			IF octant = rtn	THEN r	ELSE t,
rn =>			IF octant = rbn	THEN r	ELSE n,
rf =>			IF octant = rbf	THEN f	ELSE r,
bn =>			IF octant = lbn	THEN b	ELSE n,
bf =>			IF octant = lbf	THEN f	ELSE b,
tn =>			IF octant = ltn	THEN n	ELSE t,
ENDCASE =>	IF octant = ltf	THEN t	ELSE f];
};

NextCWEdge: PUBLIC PROC [edge: Edge, face: Face] RETURNS [Edge] ~ {
RETURN[SELECT edge FROM
lb =>			IF face = l	THEN lf	ELSE bn,
lt =>			IF face = l	THEN ln	ELSE tf,
ln =>			IF face = l	THEN lb	ELSE tn,
lf =>			IF face = l	THEN lt	ELSE bf,
rb =>			IF face = r	THEN rn	ELSE bf,
rt =>			IF face = r	THEN rf	ELSE tn,
rn =>			IF face = r	THEN rt	ELSE bn,
rf =>			IF face = r	THEN rb	ELSE tf,
bn =>			IF face = b	THEN rb	ELSE ln,
bf =>			IF face = b	THEN lb	ELSE rf,
tn =>			IF face = t	THEN lt	ELSE rn,
ENDCASE =>	IF face = t	THEN rt	ELSE lf];
};

NextCCWEdge: PUBLIC PROC [edge: Edge, face: Face] RETURNS [Edge] ~ {
RETURN[SELECT edge FROM
lb =>			IF face = l	THEN ln	ELSE bf,
lt =>			IF face = l	THEN lf	ELSE tn,
ln =>			IF face = l	THEN lt	ELSE bn,
lf =>			IF face = l	THEN lb	ELSE tf,
rb =>			IF face = r	THEN rf	ELSE bn,
rt =>			IF face = r	THEN rn	ELSE tf,
rn =>			IF face = r	THEN rb	ELSE tn,
rf =>			IF face = r	THEN rt	ELSE bf,
bn =>			IF face = b	THEN lb	ELSE rn,
bf =>			IF face = b	THEN rb	ELSE lf,
tn =>			IF face = t	THEN rt	ELSE ln,
ENDCASE =>	IF face = t	THEN lt	ELSE rf];
};

EdgeDirections: PUBLIC PROC [edge: Edge] RETURNS [ThreeDirections] ~ {
RETURN[SELECT edge FROM
lb => [l, b, lb], lt => [l, t, lt], ln => [l, n, ln], lf => [l, f, lf], rb => [r, b, rb],
rt => [r, t, rt], rn => [r, n, rn], rf => [r, f, rf], bn => [b, n, bn],
bf => [b, f, bf], tn => [t, n, tn], tf => [t, f, tf], ENDCASE => [none, none, none]];
};

EdgeFaces: PUBLIC PROC [edge: Edge] RETURNS [TwoFaces] ~ {
RETURN[SELECT edge FROM
lb => [l, b], lt => [l, t], ln => [l, n], lf => [l, f], rb => [r, b], rt => [r, t],
rn => [r, n], rf => [r, f], bn => [b, n], bf => [b, f], tn => [t, n], ENDCASE => [t, f]];
};

EdgeOctants: PUBLIC PROC [edge: Edge] RETURNS [TwoOctants] ~ {
RETURN[SELECT edge FROM
lb => [lbn, lbf], lt => [ltn, ltf], ln => [lbn, ltn], lf => [lbf, ltf],
rb => [rbn, rbf], rt => [rtn, rtf], rn => [rbn, rtn], rf => [rbf, rtf],
bn => [lbn, rbn], bf => [lbf, rbf], tn => [ltn, rtn], ENDCASE	=>	[ltf, rtf]];
};

FaceOctants: PUBLIC PROC [face: Face] RETURNS [FourOctants] ~ {
RETURN[SELECT face FROM
l			=> [lbf, ltf, ltn, lbn],
r			=> [rbn, rtn, rtf, rbf],
b			=> [lbf, lbn, rbn, rbf],
t			=> [ltn, ltf, rtf, rtn],
n			=> [lbn, ltn, rtn, rbn],
ENDCASE	=> [rbf, rtf, ltf, lbf]];
};

EdgeCorners: PUBLIC PROC [cube: Cube, edge: Edge] RETURNS [TwoCorners] ~ {
octants: TwoOctants ~ EdgeOctants[edge];
RETURN[[cube.corners[octants.o0], cube.corners[octants.o1]]];
};

FaceCorners: PUBLIC PROC [cube: Cube, face: Face] RETURNS [FourCorners] ~ {
o: FourOctants ~ FaceOctants[face];
RETURN[[cube.corners[o.o0], cube.corners[o.o1], cube.corners[o.o2], cube.corners[o.o3]]];
};

OppositeEdge: PUBLIC PROC [edge: Edge, face: Face] RETURNS [Edge] ~ {
RETURN[SELECT edge FROM
lb =>			IF face = l	THEN lt	ELSE rb,
lt =>			IF face = l	THEN lb	ELSE rt,
ln =>			IF face = l	THEN lf	ELSE rn,
lf =>			IF face = l	THEN ln	ELSE rf,
rb =>			IF face = r	THEN rt	ELSE lb,
rt =>			IF face = r	THEN rb	ELSE lt,
rn =>			IF face = r	THEN rf	ELSE ln,
rf =>			IF face = r	THEN rn	ELSE lf,
bn =>			IF face = b	THEN bf	ELSE tn,
bf =>			IF face = b	THEN bn	ELSE tf,
tn =>			IF face = t	THEN tf	ELSE bn,
ENDCASE =>	IF face = t	THEN tn	ELSE bf];
};

InverseEdge: PUBLIC PROC [edge: Edge, face: Face] RETURNS [Edge] ~ {
RETURN[SELECT edge FROM
lb =>			IF face = l	THEN rb	ELSE lt,
lt =>			IF face = l	THEN rt	ELSE lb,
ln =>			IF face = l	THEN rn	ELSE lf,
lf =>			IF face = l	THEN rf	ELSE ln,
rb =>			IF face = r	THEN lb	ELSE rt,
rt =>			IF face = r	THEN lt	ELSE rb,
rn =>			IF face = r	THEN ln	ELSE rf,
rf =>			IF face = r	THEN lf	ELSE rn,
bn =>			IF face = b	THEN tn	ELSE bf,
bf =>			IF face = b	THEN tf	ELSE bn,
tn =>			IF face = t	THEN bn	ELSE tf,
ENDCASE =>	IF face = t	THEN bf	ELSE tn];
};

DiagonalEdge: PUBLIC PROC [edge: Edge] RETURNS [Edge] ~ {
RETURN[SELECT edge FROM
lb => rt, lt => rb, ln => rf, lf => rn, rb => lt, rt => lb, rn => lf,
rf => ln, bn => tf, bf => tn, tn => bf, ENDCASE => bn];
};

OtherFace: PUBLIC PROC [edge: Edge, face: Face] RETURNS [Face] ~ {
twoFaces: TwoFaces ¬ EdgeFaces[edge];
RETURN[IF face = twoFaces.f0 THEN twoFaces.f1 ELSE twoFaces.f1];
};

AxisFromEdge: PUBLIC PROC [edge: Edge] RETURNS [Axis] ~ {
RETURN[SELECT edge FROM bn, tn, bf, tf => x, ln, lf, rn, rf => y, ENDCASE => z];
};
GetFaceNeighborInfo: PROC [cube: Cube, face: Face] RETURNS [FaceNeighborInfo] ~ {
octantWord: WORD ~ ORD[cube.octant];
faceBit: WORD ~ SELECT face FROM l, r => 4, b, t => 2, ENDCASE => 1;
faceWord: WORD ~ Basics.BITAND[octantWord, faceBit];
RETURN[[
VAL[Basics.BITXOR[octantWord, faceBit]],
SELECT face FROM l, b, n => faceWord = 0, ENDCASE => faceWord # 0
]];
};

FaceNeighbor: PUBLIC PROC [cube: Cube, face: Face] RETURNS [Cube] ~ {
IF cube = NIL OR cube.parent = NIL
THEN RETURN[NIL]
ELSE {
faceNeighborInfo: FaceNeighborInfo ~ GetFaceNeighborInfo[cube, face];
IF faceNeighborInfo.recurse
THEN {
parentNeighbor: Cube ¬ FaceNeighbor[cube.parent, face];
IF parentNeighbor = NIL
THEN RETURN[NIL]
ELSE RETURN[parentNeighbor.kids[faceNeighborInfo.nOctant]];
}
ELSE RETURN[cube.parent.kids[faceNeighborInfo.nOctant]];
};
};

EdgeNeighbors: PUBLIC PROC [cube: Cube, edge: Edge] RETURNS [cubes: ThreeCubes] ~ {
f1, f2: Face;
SELECT edge FROM
lb	=> {f1 ¬ l;	f2 ¬ b};
lt	=> {f1 ¬ l;	f2 ¬ t};
rb	=> {f1 ¬ r;	f2 ¬ b};
rt	=> {f1 ¬ r;	f2 ¬ t};
ln	=> {f1 ¬ l;	f2 ¬ n};
lf	=> {f1 ¬ l;	f2 ¬ f};
rn	=> {f1 ¬ r;	f2 ¬ n};
rf	=> {f1 ¬ r;	f2 ¬ f};
bn	=> {f1 ¬ b;	f2 ¬ n};
bf	=> {f1 ¬ b;	f2 ¬ f};
tn	=> {f1 ¬ t;	f2 ¬ n};
tf	=> {f1 ¬ t;	f2 ¬ f};
ENDCASE;
cubes.c0 ¬ FaceNeighbor[cube, f1];
cubes.c1 ¬ FaceNeighbor[cube, f2];
cubes.c2 ¬ FaceNeighbor[cubes.c0, f2];
};

Neighbor: PUBLIC PROC [cube: Cube, direction: Direction] RETURNS [x: Cube] ~ {
IF cube = NIL THEN RETURN[NIL];
SELECT direction FROM
l => x ¬ FaceNeighbor[cube, l];
r => x ¬ FaceNeighbor[cube, r];
b => x ¬ FaceNeighbor[cube, b];
t => x ¬ FaceNeighbor[cube, t];
n => x ¬ FaceNeighbor[cube, n];
f => x ¬ FaceNeighbor[cube, f];
lb => {
l: Cube ¬ FaceNeighbor[cube, l];
x ¬ IF l # NIL THEN FaceNeighbor[l, b] ELSE FaceNeighbor[FaceNeighbor[cube, b], l];
};
lt => {
l: Cube ¬ FaceNeighbor[cube, l];
x ¬ IF l # NIL THEN FaceNeighbor[l, t] ELSE FaceNeighbor[FaceNeighbor[cube, t], l];
};
ln => {
l: Cube ¬ FaceNeighbor[cube, l];
x ¬ IF l # NIL THEN FaceNeighbor[l, n] ELSE FaceNeighbor[FaceNeighbor[cube, n], l];
};
lf => {
l: Cube ¬ FaceNeighbor[cube, l];
x ¬ IF l # NIL THEN FaceNeighbor[l, f] ELSE FaceNeighbor[FaceNeighbor[cube, f], l];
};
rb => {
r: Cube ¬ FaceNeighbor[cube, r];
x ¬ IF r # NIL THEN FaceNeighbor[r, b] ELSE FaceNeighbor[FaceNeighbor[cube, b], r];
};
rt => {
r: Cube ¬ FaceNeighbor[cube, r];
x ¬ IF r # NIL THEN FaceNeighbor[r, t] ELSE FaceNeighbor[FaceNeighbor[cube, t], r];
};
rn => {
r: Cube ¬ FaceNeighbor[cube, r];
x ¬ IF r # NIL THEN FaceNeighbor[r, n] ELSE FaceNeighbor[FaceNeighbor[cube, n], r];
};
rf => {
r: Cube ¬ FaceNeighbor[cube, r];
x ¬ IF r # NIL THEN FaceNeighbor[r, f] ELSE FaceNeighbor[FaceNeighbor[cube, f], r];
};
bn => {
b: Cube ¬ FaceNeighbor[cube, b];
x ¬ IF b # NIL THEN FaceNeighbor[b, n] ELSE FaceNeighbor[FaceNeighbor[cube, n],b];
};
bf => {
b: Cube ¬ FaceNeighbor[cube, b];
x ¬ IF b # NIL THEN FaceNeighbor[b, f] ELSE FaceNeighbor[FaceNeighbor[cube, f],b ];
};
tn => {
t: Cube ¬ FaceNeighbor[cube, t];
x ¬ IF t # NIL THEN FaceNeighbor[t, n] ELSE FaceNeighbor[FaceNeighbor[cube, n], t];
};
tf => {
t: Cube ¬ FaceNeighbor[cube, t];
x ¬ IF t # NIL THEN FaceNeighbor[t, f] ELSE FaceNeighbor[FaceNeighbor[cube, f], t];
};
lbn => {
temp: Cube ¬ Neighbor[cube, lb];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, n]];
temp ¬ Neighbor[cube, ln];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, b]];
RETURN[FaceNeighbor[Neighbor[cube, bn], l]];
};
lbf => {
temp: Cube ¬ Neighbor[cube, lb];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, f]];
temp ¬ Neighbor[cube, lf];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, b]];
RETURN[FaceNeighbor[Neighbor[cube, bf], l]];
};
ltn => {
temp: Cube ¬ Neighbor[cube, lt];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, n]];
temp ¬ Neighbor[cube, ln];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, t]];
RETURN[FaceNeighbor[Neighbor[cube, tn], l]];
};
ltf => {
temp: Cube ¬ Neighbor[cube, lt];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, f]];
temp ¬ Neighbor[cube, lf];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, t]];
RETURN[FaceNeighbor[Neighbor[cube, tf], l]];
};
rbn => {
temp: Cube ¬ Neighbor[cube, rb];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, n]];
temp ¬ Neighbor[cube, rn];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, b]];
RETURN[FaceNeighbor[Neighbor[cube, bn], r]];
};
rbf => {
temp: Cube ¬ Neighbor[cube, rb];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, f]];
temp ¬ Neighbor[cube, rf];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, b]];
RETURN[FaceNeighbor[Neighbor[cube, bf], r]];
};
rtn => {
temp: Cube ¬ Neighbor[cube, rt];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, n]];
temp ¬ Neighbor[cube, rn];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, t]];
RETURN[FaceNeighbor[Neighbor[cube, tn], r]];
};
rtf => {
temp: Cube ¬ Neighbor[cube, rt];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, f]];
temp ¬ Neighbor[cube, rf];
IF temp # NIL THEN RETURN[FaceNeighbor[temp, t]];
RETURN[FaceNeighbor[Neighbor[cube, tf], r]];
};
ENDCASE	=> x ¬ cube;
};

Neighbors: PUBLIC PROC [cube: Cube] RETURNS [neighbors: Neighborhood] ~ {
IF cube # NIL THEN
FOR direction: Direction IN Direction DO
neighbors[direction] ¬ Neighbor[cube, direction];
ENDLOOP;
};

Move: PUBLIC PROC [cube: Cube, direction: Direction] RETURNS [Neighborhood] ~ {
RETURN[Neighbors[Neighbor[cube, direction]]];
};
GetDirectionCorner: PUBLIC PROC [cube: Cube, d: Direction] RETURNS [c: Corner] ~ {
c ¬ SELECT d FROM
lbn	=> cube.corners[lbn],					-- lbn corner
lbf	=> cube.corners[lbf],					-- lbf corner
ltn	=> cube.corners[ltn],					-- ltn corner
ltf		=> cube.corners[ltf],						-- ltf corner
rbn	=> cube.corners[rbn],					-- rbn corner
rbf	=> cube.corners[rbf],					-- rbf corner
rtn	=> cube.corners[rtn],					-- rtn corner
rtf		=> cube.corners[rtf],					-- rtf corner
ln		=> cube.kids[ltn].corners[lbn],			-- midpoint of ln edge
lf		=> cube.kids[ltf].corners[lbf],			-- midpoint of lf edge
rn		=> cube.kids[rtn].corners[rbn],			-- midpoint of rn edge
rf		=> cube.kids[rtf].corners[rbf],			-- midpoint of rf edge
lt		=> cube.kids[ltn].corners[ltf],			-- midpoint of lt edge
lb		=> cube.kids[lbn].corners[lbf],			-- midpoint of lb edge
rt		=> cube.kids[rtn].corners[rtf],			-- midpoint of rt edge
rb		=> cube.kids[rbn].corners[rbf],			-- midpoint of rb edge
tn		=> cube.kids[ltn].corners[rtn],			-- midpoint of tn edge
bn		=> cube.kids[lbn].corners[rbn],		-- midpoint of bn edge
tf		=> cube.kids[ltf].corners[rtf],			-- midpoint of tf edge
bf		=> cube.kids[lbf].corners[rbf],			-- midpoint of bf edge
l		=> cube.kids[lbn].corners[ltf],			-- center of l face
r		=> cube.kids[rbn].corners[rtf],			-- center of r face
b		=> cube.kids[lbn].corners[rbf],			-- center of b face
t		=> cube.kids[ltn].corners[rtf],			-- center of t face
n		=> cube.kids[lbn].corners[rtn],			-- center of n face
f		=> cube.kids[lbf].corners[rtf],			-- center of f face
c		=> cube.kids[lbn].corners[rtf],			-- center of cube
ENDCASE => NIL;
};

GetDirectionCorners: PUBLIC PROC [cube: Cube]
RETURNS [directionCorners: DirectionCorners]
~ {
directionCorners[lbn]	¬ cube.corners[lbn];					-- lbn corner
directionCorners[lbf]	¬ cube.corners[lbf];						-- lbf corner
directionCorners[ltn]	¬ cube.corners[ltn];						-- ltn corner
directionCorners[ltf]	¬ cube.corners[ltf];						-- ltf corner
directionCorners[rbn]	¬ cube.corners[rbn];					-- rbn corner
directionCorners[rbf]	¬ cube.corners[rbf];						-- rbf corner
directionCorners[rtn]	¬ cube.corners[rtn];						-- rtn corner
directionCorners[rtf]	¬ cube.corners[rtf];						-- rtf corner
directionCorners[ln]		¬ cube.kids[ltn].corners[lbn];			-- midpoint of ln edge
directionCorners[lf]		¬ cube.kids[ltf].corners[lbf];			-- midpoint of lf edge
directionCorners[rn]	¬ cube.kids[rtn].corners[rbn];			-- midpoint of rn edge
directionCorners[rf]		¬ cube.kids[rtf].corners[rbf];			-- midpoint of rf edge
directionCorners[lt]		¬ cube.kids[ltn].corners[ltf];			-- midpoint of lt edge
directionCorners[lb]		¬ cube.kids[lbn].corners[lbf];			-- midpoint of lb edge
directionCorners[rt]		¬ cube.kids[rtn].corners[rtf];			-- midpoint of rt edge
directionCorners[rb]		¬ cube.kids[rbn].corners[rbf];			-- midpoint of rb edge
directionCorners[tn]		¬ cube.kids[ltn].corners[rtn];			-- midpoint of tn edge
directionCorners[bn]	¬ cube.kids[lbn].corners[rbn];			-- midpoint of bn edge
directionCorners[tf]		¬ cube.kids[ltf].corners[rtf];			-- midpoint of tf edge
directionCorners[bf]		¬ cube.kids[lbf].corners[rbf];			-- midpoint of bf edge
directionCorners[l]		¬ cube.kids[lbn].corners[ltf];			-- center of l face
directionCorners[r]		¬ cube.kids[rbn].corners[rtf];			-- center of r face
directionCorners[b]		¬ cube.kids[lbn].corners[rbf];			-- center of b face
directionCorners[t]		¬ cube.kids[ltn].corners[rtf];			-- center of t face
directionCorners[n]		¬ cube.kids[lbn].corners[rtn];			-- center of n face
directionCorners[f]		¬ cube.kids[lbf].corners[rtf];			-- center of f face
directionCorners[c]		¬ cube.kids[lbn].corners[rtf];			-- center of cube
};
SetTerminalField: PUBLIC PROC [root: Cube] ~ {
cubeProc: CubeProc ~ {
FOR o: Octant IN Octant DO
IF cube.kids[o] # NIL THEN {
cube.terminal ¬ FALSE;
RETURN;
};
ENDLOOP;
cube.terminal ¬ TRUE;
};
Apply[root, cubeProc];
};

SetLevels: PUBLIC PROC [root: Cube] ~ {
SetKidsLevel: PROC [cube: Cube, level: INT] ~ {
nextLevel: INT ~ level+1;
FOR o: Octant IN Octant DO
kid: Cube ¬ cube.kids[o];
IF kid = NIL THEN LOOP;
kid.level ¬ level;
SetKidsLevel[kid, nextLevel];
ENDLOOP;
};
root.level ¬ 0;
SetKidsLevel[root, 1];
};
GetClientData: PUBLIC PROC [cube: Cube] RETURNS [REF ANY] ~ {
RETURN [cube.refAny];
};
SetClientData: PUBLIC PROC [cube: Cube, r: REF ANY]  ~ {
IF cube # NIL THEN cube.refAny ¬ r;
};

ObjectTrack:		TYPE ~ REF ObjectTrackRep;
ObjectTrackRep:	TYPE ~ RECORD [objects: LIST OF CubeObject  _ NIL];


FromObjects: PUBLIC PROC [objs: LIST OF CubeObject] RETURNS [Cube] ~ {
bbox: Box ¬ objs.first.bbox;
size: REAL;
ans: Cube ¬ NIL;
track: ObjectTrack ¬ NEW[ObjectTrackRep];

FOR l: LIST OF CubeObject _ objs, l.rest WHILE l # NIL DO
bbox ¬ G3dBox.BoxUnionBox[bbox, l.first.bbox];
ENDLOOP;
size ¬ MAX[bbox.max.x - bbox.min.x, bbox.max.y - bbox.min.y];
size ¬ MAX[size, bbox.max.z - bbox.min.z];
ans ¬ NewCube[size, G3dBox.BoxCenter[bbox]];
track.objects ¬ objs;
SetClientData[ans, track];
RETURN[ans];
};

AddObject: PUBLIC PROC [cube: Cube, obj: CubeObject] ~ {
track: ObjectTrack ¬ NIL;
intersection: Box;
hasIntersection: BOOL;
IF cube = NIL OR obj = NIL THEN RETURN;

IF cube.refAny = NIL AND cube.terminal THEN {
track ¬ NEW[ObjectTrackRep];
track.objects ¬ NIL;
cube.refAny ¬ track;
};
IF NOT ISTYPE[cube.refAny,ObjectTrack] THEN RETURN;
track ¬ NARROW[cube.refAny];
[hasIntersection, intersection] ¬ G3dBox.Intersect[BoxOfCube[cube], obj.bbox];
IF NOT hasIntersection THEN RETURN;
IF cube.terminal 
THEN {
myCo: CubeObject ¬ NEW[G3dOctree.CubeObjectRep ¬
[val: obj.val, bbox: intersection, query: obj.query]];
track.objects ¬ CONS[myCo, track.objects];
}
ELSE {
FOR octant: Octant IN Octant DO
AddObject[cube.kids[octant], obj];
ENDLOOP;
};
};

SubdivideGivenObjects: PUBLIC PROC [cube: Cube, maxPerCube: INT, maxDepth: INT]  ~ {
track: ObjectTrack;

IF cube = NIL OR cube.refAny = NIL OR NOT ISTYPE[cube.refAny,ObjectTrack] THEN RETURN;
track ¬ NARROW[cube.refAny];
IF cube.level >= maxDepth THEN RETURN;
IF cube.terminal 
THEN {
nObjs: INT ¬ 0;
FOR l: LIST OF CubeObject _ track.objects, l.rest WHILE l # NIL DO
nObjs ¬ nObjs + 1;
ENDLOOP;
IF nObjs <= maxPerCube THEN {
RETURN;
};
Subdivide[cube];
FOR l: LIST OF CubeObject _ track.objects, l.rest WHILE l # NIL DO
FOR octant: Octant IN Octant DO
AddObject[cube.kids[octant], l.first];
ENDLOOP;
ENDLOOP;
track.objects ¬ NIL;
};
FOR octant: Octant IN Octant DO
SubdivideGivenObjects[cube.kids[octant], maxPerCube, maxDepth];
ENDLOOP;

};

QueryObjects: PUBLIC PROC [cube: Cube, pt: Triple] RETURNS [obj: REF ANY] ~ {
track: ObjectTrack;
IF cube = NIL THEN RETURN [NIL];
IF cube.refAny = NIL THEN RETURN [NIL];
IF NOT ISTYPE[cube.refAny,ObjectTrack] THEN {
RETURN [NIL];
};
track ¬ NARROW[cube.refAny];
IF NOT G3dBox.PointInBox[BoxOfCube[cube], pt] THEN {
RETURN [NIL];
};
IF cube.terminal 
THEN {
FOR l: LIST OF CubeObject _ track.objects, l.rest WHILE l # NIL DO
co: CubeObject ¬ l.first;
IF G3dBox.PointInBox[co.bbox,pt] THEN {
IF co.query[co.val, pt] THEN RETURN [co.val];
};
ENDLOOP;
}
ELSE {
d0, d1, d2: Direction;
centerPt: Triple ¬ Center[cube];
octant: Octant;
val: REF ANY;

d0 ¬ IF pt.x > centerPt.x THEN r ELSE l;
d1 ¬ IF pt.y > centerPt.y THEN t ELSE b;
d2 ¬ IF pt.z > centerPt.z THEN f ELSE n;
octant ¬ OctantFromThreeDirections[d0,d1,d2];
val ¬ QueryObjects[cube.kids[octant], pt];
IF val # NIL THEN RETURN [val];
};
RETURN [NIL];
};
SetOctreeFields: PUBLIC PROC [octree: Octree] ~ {
IF octree = NIL OR octree.root = NIL THEN RETURN;
octree.depth ¬ DepthOf[octree.root];
octree.radius ¬ 0.5*(octree.diameter ¬ Size[octree.root]);
octree.terminalRadius ¬ 0.5*(octree.terminalDiameter ¬ MinSize[octree.root]);
octree.nTerminalCubes ¬ NTerminalCubes[octree.root];
octree.nCubes ¬ NCubes[octree.root];
};
WriteCubesToFile: PUBLIC PROC [fileName: ROPE, cube: Cube, miscInfo: ROPE ¬ NIL] ~ {
IF cube # NIL AND fileName # NIL THEN {
Inner: PROC [cube: Cube] ~ {
AddChar: PROC [c: CHAR] ~ INLINE {
text[text.length] ¬ c;
text.length ¬ text.length+1;
};
text.length ¬ 6;
FOR n: INT IN [0..cube.level) DO
AddChar['\t];
ENDLOOP;
FOR o: Octant IN Octant DO
AddChar[IF cube.kids[o] = NIL THEN '0 ELSE '1];
ENDLOOP;
AddChar['\n];
IO.PutText[out, text];
FOR o: Octant IN Octant DO
IF cube.kids[o] # NIL THEN Inner[cube.kids[o]];
ENDLOOP;
};
text: REF TEXT ¬ RefText.ObtainScratch[100];
out: STREAM ¬ FS.StreamOpen[fileName, $create];
center: Triple ¬ Center[cube];
IO.PutFL[out, "Volume~ size: %g\tcenter: %g\t%g\t%g\n\n",
LIST[IO.real[cube.size], IO.real[center.x], IO.real[center.y], IO.real[center.z]]];
IF miscInfo # NIL THEN IO.PutF1[out, "MiscInfo~ %g\n\n", IO.rope[miscInfo]];
text ¬ RefText.AppendRope[text, "cube:\t"];
Inner[cube];
IO.Close[out];
RefText.ReleaseScratch[text];
};
};

ReadCubesFromFile: PUBLIC PROC [fileName: ROPE] RETURNS [root: Cube] ~ {
IF fileName # NIL THEN {
InnerReadCube: PROC [parent: Cube] ~ {
CubeLineOK: PROC RETURNS [ok: BOOL ¬ TRUE] ~ {
DO
text ¬ IO.GetLine[in, text ! IO.EndOfStream => GOTO eof];
IF Rope.Run[id, 0, RefText.TrustTextAsRope[text], 0, TRUE] = 6 THEN RETURN;
REPEAT
eof => ok ¬ FALSE;
ENDLOOP;
};
IF CubeLineOK[] THEN {
n: INT ¬ 6;
WHILE text[n] = '\t DO n ¬ n+1; ENDLOOP;
FOR nn: INT IN [n..n+8) DO
IF text[nn] = '1 THEN EXIT;
REPEAT
FINISHED => RETURN;
ENDLOOP;
Subdivide[parent];
FOR o: Octant IN Octant DO
IF text[n] = '0 THEN parent.kids[o] ¬ NIL;
n ¬ n+1;
ENDLOOP;
FOR o: Octant IN Octant DO
kid: Cube ¬ parent.kids[o];
IF kid # NIL THEN InnerReadCube[kid];
ENDLOOP;
};
};
in: STREAM ¬ FS.StreamOpen[FileNames.ResolveRelativePath[fileName] !
FS.Error => GOTO noOpen];
text: REF TEXT ¬ RefText.ObtainScratch[100];
id: ROPE ¬ "cube:\t";
line: G3dIO.Line ¬
G3dIO.FindKeyWord[in, "Octree",,, G3dIO.ObtainLine[]];
skip1: ROPE ¬ G3dIO.GetWord[line];
size: REAL ¬ G3dIO.GetReal[line];
skip2: ROPE ¬ G3dIO.GetWord[line];
center: Triple ¬ G3dIO.GetTriple[line];
root ¬ NewCube[size, center];
InnerReadCube[root];
G3dIO.ReleaseLine[line];
RefText.ReleaseScratch[text];
IO.Close[in];
EXITS
noOpen => RETURN;
};
};
AddToCubeSequence: PUBLIC PROC [cube: Cube, cubes: CubeSequence ¬ NIL]
RETURNS [CubeSequence]
~ {
IF cubes = NIL THEN cubes ¬ NEW[CubeSequenceRep[10]];
IF cubes.length = cubes.maxLength THEN cubes ¬ LengthenCubeSequence[cubes];
cubes[cubes.length] ¬ cube;
cubes.length ¬ cubes.length+1;
RETURN[cubes];
};

LengthenCubeSequence: PUBLIC PROC [cubes: CubeSequence, amount: REAL ¬ 1.3]
RETURNS [new: CubeSequence]
~ {
new ¬ NEW[CubeSequenceRep[Real.Round[1.3*cubes.length]]];
FOR i: INT IN [0..cubes.length) DO new[i] ¬ cubes[i]; ENDLOOP;
new.length ¬ cubes.length;
};
StackOverflow:	PUBLIC ERROR = CODE;
StackUnderflow:	PUBLIC ERROR = CODE;

NewCubeStack: PUBLIC PROC [length: INT] RETURNS [CubeStack] ~ {
RETURN[NEW[CubeStackRep[length]]];
};

WriteBottomOfCubeStack: PUBLIC PROC [cube: Cube, cubeStack: CubeStack] ~ {
newBottom: INT ~ (cubeStack.bottom+1) MOD cubeStack.maxLength;
cubeStack[cubeStack.bottom] ¬ cube;
IF newBottom = cubeStack.top THEN ERROR StackOverflow;
cubeStack.bottom ¬ newBottom;
cubeStack.size ¬ cubeStack.size+1;
cubeStack.maxSize ¬ MAX[cubeStack.maxSize, cubeStack.size];
};

ReadTopOfCubeStack: PUBLIC PROC [cubeStack: CubeStack] RETURNS [cube: Cube] ~ {
IF cubeStack.bottom = cubeStack.top THEN ERROR StackUnderflow;
cube ¬ cubeStack[cubeStack.top];
cubeStack.top ¬ (cubeStack.top+1) MOD cubeStack.maxLength;
cubeStack.size ¬ cubeStack.size-1;
};

CubeStackSize: PUBLIC PROC [cubeStack: CubeStack] RETURNS [INT] ~ {
RETURN[cubeStack.size];
};

MaxCubeStackSize: PUBLIC PROC [cubeStack: CubeStack] RETURNS [INT] ~ {
RETURN[cubeStack.maxSize];
};

CubeStackEmpty: PUBLIC PROC [cubeStack: CubeStack] RETURNS [BOOL] ~ {
RETURN[cubeStack.bottom = cubeStack.top];
};

LengthenCubeStack: PUBLIC PROC [cubeStack: CubeStack, amount: REAL ¬ 1.3]
RETURNS [newStack: CubeStack]
~ {
newStack ¬ NEW[CubeStackRep[Real.Round[amount*cubeStack.maxLength]]];
FOR i: INT IN [0..cubeStack.maxLength) DO newStack[i] ¬ cubeStack[i]; ENDLOOP;
newStack.top ¬ cubeStack.top;
newStack.bottom ¬ cubeStack.bottom;
newStack.size ¬ cubeStack.size;
};
nScratchCrossSequences: INT ~ 6;
scratchCrossSequences: ARRAY [0..nScratchCrossSequences) OF CrossSequence ¬ ALL[NIL];

ObtainCrossSequence: PUBLIC ENTRY PROC RETURNS [crossSequence: CrossSequence] ~ {
FOR i: INT IN [0..nScratchCrossSequences) DO
crossSequence ¬ scratchCrossSequences[i];
IF crossSequence = NIL THEN LOOP;
crossSequence.length ¬ 0;
scratchCrossSequences[i] ¬ NIL;
RETURN;
ENDLOOP;
crossSequence ¬ NEW[CrossSequenceRep[100]];
};

ReleaseCrossSequence: PUBLIC ENTRY PROC [crossSequence: CrossSequence] ~ {
FOR i: INT IN [0..nScratchCrossSequences) DO
IF scratchCrossSequences[i] # NIL THEN LOOP;
scratchCrossSequences[i] ¬ crossSequence;
RETURN;
ENDLOOP;
};
NoSuchOctant:	PUBLIC ERROR [msg: ROPE] ~ CODE;
NoSuchFace:		PUBLIC ERROR [msg: ROPE] ~ CODE;

RopeFromOctant: PUBLIC PROC [octant: Octant] RETURNS [ROPE] ~ {
RETURN[Rope.Substr[IO.PutFR1["%g", IO.refAny[NEW[Octant ¬ octant]]], 1]];
};

RopeFromFace: PUBLIC PROC [face: Face] RETURNS [ROPE] ~ {
RETURN[Rope.Substr[IO.PutFR1["%g", IO.refAny[NEW[Face ¬ face]]], 1]];
};
RopeFromDirection: PUBLIC PROC [direction: Direction] RETURNS [ROPE] ~ {
RETURN[Rope.Substr[IO.PutFR1["%g", IO.refAny[NEW[Direction ¬ direction]]], 1]];
};

RopeFromDirectionSelect: PUBLIC PROC [directionSelect: DirectionSelect] RETURNS [ROPE] ~ {
RETURN[SELECT directionSelect FROM
x=>"x", y=>"y", z=>"z", xy=>"xy", xz=>"xz", yz=>"yz", xyz=>"xyz", ENDCASE=>"none"];
};

OctantFromRope: PUBLIC PROC [rope: ROPE] RETURNS [Octant] ~ {
FOR o: Octant IN Octant DO IF Equal[RopeFromOctant[o], rope] THEN RETURN[o]; ENDLOOP;
ERROR NoSuchOctant[rope];
};

FaceFromRope: PUBLIC PROC [rope: ROPE] RETURNS [Face] ~ {
FOR face: Face IN Face DO
IF Equal[RopeFromFace[face], rope] THEN RETURN[face];
ENDLOOP;
ERROR NoSuchFace[rope];
};

DirectionFromRope: PUBLIC PROC [rope: ROPE] RETURNS [Direction] ~ {
FOR d: Direction IN Direction DO
IF Equal[RopeFromDirection[d], rope] THEN RETURN[d];
ENDLOOP;
RETURN[none];
};

RopeFromRefAny: PUBLIC PROC [ref: REF ANY] RETURNS [rope: ROPE] ~ {
ioRope: ROPE ~ IO.PutFR1["%g", IO.refAny[ref]];
text: REF TEXT ~ RefText.AppendRope[RefText.ObtainScratch[90], ioRope, 1];
IF text[0] IN ['a..'z] THEN text[0] ¬ text[0]-('a-'A);
rope ¬ Rope.FromRefText[text];
RefText.ReleaseScratch[text];
};

Equal: PROC [r1, r2: ROPE] RETURNS [BOOL] ~ {RETURN[Rope.Equal[r1, r2, FALSE]]};

END.
	δ
G3dOctreeImpl.mesa
Copyright Σ 1985, 1992 by Xerox Corporation.  All rights reserved.
Bloomenthal, November 21, 1992 2:30 pm PST
Types
Allocation
Attributes

Subdivision
Modification
Create cube's parent, using cube's corner[o] as the center of parent:
Notice that the root has a kid, but is not itself truly subdivided:
This may change cube's level:
Searching
Callback
Directions


Edge-Face-Octant

Neighbors
six faces:
twelve edges:
eight corners:
Children
Miscellany
Object Query
By Ken Fishkin.
These operations are performed using the refAny field of the cube to store a pointer
to a record containing a list of all objects which (at least partially) are within this cube.
This is NIL for non-terminal cubes.
PrintBox: PROC [b: Box, s: IO.STREAM, hdr: ROPE ¬ NIL]  ~ {
IF hdr # NIL THEN IO.PutRope[s,hdr];
G3dIO.PrintTriple[s,b.min,"min:"];
G3dIO.PrintTriple[s,b.max,"max:"];
};
first, go through and find the bounding box of all the objects: needed to create the Cube.
cube size is the max side length of the bbox:
sanity checks....
this can happen after subdividing. Set up an empty track, and fall into regular case.
does this object belong within me?
I am a terminal: add to me directly.
add to the kids. Since this guy can cross cube boundaries, might be added to more
than one child: go through all of them.
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)

can't weasel out of it anymore: have to split myself up, and hand off the objects to my kids. Since my objects may cross more than one of my kids, will do this by adding each object to each kid: the kid will check and see if it lies outside his boundaries.
PrintBox[BoxOfCube[cube],TerminalIO.TOS[], IO.PutFR["%g: %g objs: Subdividing:", IO.int[cube.level], IO.int[nObjs]]];
and now fall down to non-terminal case (I'm not a terminal anymore):
need to make sure the kids aren't overloaded. Note that I don't have to change my bounding box, as the objects are unchanged and hence have the same bounding boxes.
G3dIO.PrintTriple[TerminalIO.TOS[], pt, "QueryObjects:pt:"];
PrintBox[BoxOfCube[cube], TerminalIO.TOS[], "checking against cube:"];
Figure out which octant could contain this point:
Miscellany
IO
Cube Sequence Procedures
Cube Stack Support Procedures
RETURN[IF cubeStack.top > cubeStack.bottom
THEN 2*cubeStack.maxLength-cubeStack.top-cubeStack.bottom
ELSE cubeStack.bottom-cubeStack.top];
Cross Support Procedures
Ropes

ΚAΛ–
"cedarcode" style•NewlineDelimiter

™™Jšœ	Οeœ6™BJ™*J˜JšΟk	œ^˜gJ˜—šΠbl
œžœ
ž˜JšžœS˜ZJšžœ
˜J˜—Jšœž˜
head–16.0 24 .div 1 1 textColorš
Οl™Jšžœ
ž
œžœ
˜Jš	žœžžœžœ
žœ
˜Jšœžœ˜Jšœž
œ˜ Jšœ	žœ˜$šœžœ˜"J˜—Jšœžœœœ
˜-Jšœžœœœ
˜!Jšœžœœœ
˜$Jšœžœœœ
˜2Jšœžœœœ
˜+Jšœžœœœ
˜)Jšœ
žœœœ
˜&Jšœžœœœ
˜#Jšœžœœœ
˜+Jšœžœœœ
˜5Jšœžœœœ
˜(Jšœžœœœ
˜0Jšœžœœœ
˜5Jšœžœœœ
˜-Jšœžœœœ
˜.Jšœžœœœ
˜!Jšœ
žœ˜+Jšœ
žœœœ
˜'Jšœ
žœœœ
˜&Jšœžœœœ
˜)Jšœžœœœ
˜.Jšœžœœœ
˜.Jšœžœœœ
˜3Jšœžœœœ
˜*Jšœžœœœ
˜5Jšœžœœœ
˜2Jšœžœœœ
˜4Jšœžœœœ
˜0Jšœžœœœ
˜!Jšœžœœœ
˜!Jšœžœ˜5Jšœžœœœ
˜/Jšœžœœœ
˜6Jšœžœœœ
˜5Jšœžœœœ
˜!Jšœžœœœ
˜.Jšœžœœœ
˜$Jšœžœœœ
˜-Jšœžœœœ
˜$Jšœžœœœ
˜+Jšœžœœœ
˜)Jšœžœœœ
˜+Jšœžœœœ
˜2Jšœžœœœ
˜-Jšœžœœœ
˜-Jšœžœœœ
˜+Jšœžœœœ
˜4Jšœžœœœ
˜+Jšœžœœœ
˜+Jšœ
žœœœ
˜'Jšœžœœœ
˜0Jšœ
žœœœ
˜'Jšœžœœœ
˜+—š
 
™
šΟnœžœ
žœ˜Jšœžœ
˜J˜Jšœ!žœ
˜%Jšžœ˜J˜Jšžœžœ;˜LJ˜J˜—š‘œžœ˜J˜
Jšœžœ
˜J˜Jšœžœ
˜J˜Jšžœ
˜J˜Jšœžœ
˜J˜J˜J˜J˜Jšœžœ
˜J˜J˜J˜—š‘	œžœ˜J˜Jšœ!žœ
˜%Jšžœ˜J˜Jšœ	žœ˜)J˜J˜—šΠbn
œžœ
žœ˜Jšœžœ
˜J˜Jšœ!žœ
˜%Jšžœ˜J˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜Jšœžœ˜˜J˜%J˜%J˜%J˜%J˜%J˜%J˜%J˜$J˜—J˜——š
 
™
š‘œžœ
žœžœ˜7J˜Jšžœžœ
žœ
žœžœ
žœžœ
˜JJ˜J™—š
‘œžœ
žœžœžœ˜3Jšœžœžœ
˜Jš
žœžœ
žœ
žœ
žœ˜!Jšžœžœžœ
žœžœ
žœžœžœžœ
˜PJšžœžœ
žœ
žœ˜(šžœžœž˜J˜šžœžœ
žœ˜Jšžœžœ
žœ
žœ˜&Jšžœ
žœ
Οbœžœ
žœ
žœ˜$J˜—Jšžœ
˜—Jšžœ
žœ˜
J˜J˜—š‘œžœ
žœžœžœžœ˜CJšœžœžœ
˜š‘œžœ˜Jšœ
žœ
˜šžœžœž˜J˜šžœž˜Jšžœž˜Jšžœ
žœžœžœ
žœ
žœ˜.—Jšžœžœ
žœ
£œ˜Jšžœ
˜—J˜—Jšœžœžœ˜+J˜J˜—š
‘œžœ
žœžœ
žœ	˜>J˜)J˜J˜J˜—š
‘œžœ
žœžœ
žœ	˜FJ˜)J˜ J˜J˜—š‘œžœ
žœžœ
˜5šžœžœ
žœ˜J˜%J˜%Jšžœ6˜<J˜—Jšžœ˜J˜J˜—š
‘œžœ
žœžœžœ˜1Jš
žœ
žœžœ
žœžœ˜.J˜J˜—š
‘œžœ
žœžœžœ˜9Jš‘œžœžœ˜>J˜J˜J˜J˜—š‘	œžœ
žœžœ
˜5Jšžœ5˜;J˜J˜—š
‘œžœ
žœžœžœ˜4Jšžœžœžœ
žœžœ
žœ
žœ
žœžœ
˜LJšžœ
žœ˜J˜J˜—š
‘œžœ
žœžœžœ	˜:š‘œžœžœ˜(Jšœžœ˜šžœžœž˜J˜Jšžœžœ
žœ
£œ˜š
ž˜Jšžœžœžœ˜(—Jšžœ
˜—J˜—J˜J˜——š
 ™š‘	œžœ
žœ˜'šžœžœ
žœžœ˜&š‘œžœžœžœ˜?š‘œžœžœžœ˜MJšžœžœ
žœ
žœ˜;Jšžœžœ
žœ
žœ˜;Jšžœžœ
žœ
žœ˜;Jšžœžœ
žœ
žœ˜;J˜—J˜šžœžœ
žœ
žœ˜šžœ
žœž˜J˜!J˜!J˜!J˜!J˜!J˜ Jšžœžœ
˜——J˜—š‘œžœ+žœ˜Tš‘œžœžœžœ˜Lš‘œžœžœžœ˜AJšžœžœ
žœ
žœ˜8Jšžœžœ
žœ
žœ˜8J˜—J˜šžœžœ
žœ
žœ˜šžœ
žœž˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜Jšžœžœ
˜——J˜—J˜Jšžœ
žœ
žœ˜2Jšžœ
žœ
žœ˜2J˜—š‘œžœ'˜4J˜OJšœžœ
˜J˜J˜—Jšœžœ˜Jšœ
žœ˜J˜J˜*Jšœ!žœ
˜%J˜+J˜ J˜ J˜ J˜ J˜ J˜ J˜ J˜ J˜-J˜-J˜,J˜-J˜,J˜-J˜+J˜-J˜+J˜,J˜,J˜-J˜J˜J˜J˜J˜J˜Jšžœžœ
žœ=˜MJšžœžœ
žœ=˜MJšžœžœ
žœ?˜OJšžœžœ
žœ?˜OJšžœžœ
žœ=˜MJšžœžœ
žœ=˜MJšžœžœ
žœ?˜OJšžœžœ
žœ?˜OJšžœžœ
žœ?˜OJšžœžœ
žœ?˜OJšžœžœ
žœ?˜OJšžœžœ
žœ?˜OJšžœžœ
žœ8˜GJšžœžœ
žœ8˜GJšžœžœ
žœ8˜GJšžœžœ
žœ9˜HJšžœžœ
žœ:˜IJšžœžœ
žœ:˜IJšœžœ
˜J˜.J˜.J˜.J˜.J˜.J˜.J˜.J˜.J˜—J˜J˜—š‘œžœ
žœ˜/J˜'J˜ J˜J˜—š‘œžœ
žœžœ˜@Jšžœžœžœ
˜9J˜——š
 ™š‘œžœ˜Jšœžœ˜š‘	œžœ˜ š‘œžœ#˜-Jš
žœžœ
žœ$žœ
žœ
˜?Jš
žœžœ
žœ$žœ
žœ
˜?Jš
žœžœ
žœ$žœ
žœ
˜?J˜—J˜J˜KJ˜KJ˜KJ˜—J˜J˜J˜—š
‘œžœ
žœ(žœžœ
˜HJšžœ
˜J˜Jš
žœžœ
žœ
žœ
žœ˜J˜Jšžœžœ
žœ
žœ
˜:šžœžœ
žœ˜J™EJ˜1š‘	œžœ
žœžœ˜GJ˜)Jšœžœ˜Jšœžœ
˜J˜"J˜$šžœž˜J˜KJ˜KJ˜KJ˜LJ˜LJ˜KJ˜KJšžœG˜N—Jšœžœ˜ J˜$Jšžœ
žœ*˜:Jšžœ
žœ*˜:Jšžœ
žœ*˜:Jšžœ
žœ*˜:Jšžœ
žœ*˜:Jšžœ
žœ*˜:Jšžœ
žœ*˜:Jšžœ
žœ*˜:J˜—Jšœžœžœ.žœ˜XJ˜*J˜(J˜J˜&J™CJ˜J˜J˜J˜J˜—˜
š‘œžœ&žœ	žœ˜PJšœžœ2žœ˜WJ˜#Jšœžœ"˜,Jšœžœ"˜,Jšœžœ"˜,šžœž˜J˜,J˜,J˜,J˜-J˜,J˜,J˜,J˜-Jšžœ
˜—J˜J˜šžœžœž˜J˜)šžœžœ
žœ˜J˜šžœž˜˜J˜5J˜5J˜—˜J˜5J˜5J˜—˜J˜5J˜5J˜—˜J˜5J˜5J˜—˜J˜5J˜5J˜—šžœ˜J˜5J˜5J˜——J˜—Jšžœ
˜—J˜-šžœžœž˜šžœžœ
žœ˜Jšœžœ˜ šœžœž˜$J˜J˜J˜J˜J˜J˜J˜Jšžœ˜—J˜—Jšžœ
˜—J˜J˜—J˜J˜9šžœžœ˜J™J˜9Jšžœžœ
žœ£œ"˜OJšžœ8žœ
žœ
žœ
˜IJ˜J˜—Jšœžœ
˜J˜=š	žœžœ
žœžœž˜/Jšžœžœ
žœ3˜OJšžœ
˜—J˜—Jšžœ
˜J˜J˜—š‘
œžœ
žœ˜(Jšžœžœ
žœžœ
žœ!žœ
˜MJ˜J˜—š‘œžœ
žœ˜2š‘œ˜Jš‘œžœžœžœ
žœ
žœ
žœ
˜Jšžœžœ
žœ˜J˜*šžœžœž˜J˜4š
žœžœ
žœ
žœžœ˜2J˜BJšžœ"žœ
žœ˜8Jšžœ"žœ
žœ˜8Jšžœ"žœ
žœ˜8Jšžœ"žœ
žœ˜8J˜—Jšžœ
˜—šžœžœž˜J˜4š
žœžœ
žœ
žœžœ˜2J˜6Jšžœ!žœ
žœ˜7Jšžœ!žœ
žœ˜7J˜—Jšžœ
˜—šžœžœž˜J˜8šžœžœ
žœ
žœ˜+Jšžœ7žœ
žœ˜N—Jšžœ
˜—J˜—š
ž˜˜J˜šžœžœ
žœ˜J˜6J˜6J˜EJšœ£œ3˜=Jšœ£œ3˜=Jšœ£œ3˜=Jšœ£œ3˜=Jšœ£œ%˜/Jšœ£œ%˜/Jšœ£œ%˜/J˜—J˜——J˜—J˜J˜——š
 	™	š‘œžœ
žœ$žœžœžœ˜Yšžœž˜
Jšžœ
žœ
žœ
˜šžœ˜Jšœžœ˜šžœ
˜Jšœ+ž˜.Jšœ+ž˜.Jšœ+ž˜.Jšœ+ž˜.Jšœ+ž˜.J˜,—J˜——J˜J˜—š‘	œžœ
žœžœ˜Eš’œžœžœ˜*šžœžœž˜J˜Jšžœžœ
žœžœ
žœ
£œ˜@Jšžœ
˜—Jšžœ˜
J˜—Jš
žœ
žœžœžœ
žœ˜=J˜J˜—š‘œžœ
žœžœ˜5Jš
žœžœ
žœ
žœ
žœ˜Jšžœžœžœ
žœžœ
žœ
žœžœ
˜TJšžœ
žœ˜J˜J˜—š‘œžœ
žœžœ˜=J˜Jšžœžœ
žœ
žœžœžœ
˜GJšžœ˜J˜——š
 ™š‘œžœ
žœ%˜7š‘œžœ˜šžœžœ
žœ˜ Jšžœ
žœžœžœ
£œžœ
˜=—J˜—J˜J˜J˜—š‘œžœ
žœ%˜=š‘œžœ˜šžœžœ
žœ˜ Jšžœ
žœžœžœ
£œžœ
˜=—J˜—Jšžœžœ
žœ
žœžœžœžœ
˜KJ˜J˜—š‘œžœ
žœ%˜Aš‘œžœ˜Jšžœžœ
žœ
žœ
˜šžœ˜Jš
žœžœ
žœžœ
žœ
˜(Jšžœ
žœžœžœ
£œžœ
˜=—J˜—J˜J˜J˜—š‘œžœ
žœ)žœ˜Jš‘œžœ˜Jš
žœžœ
žœžœ
žœ
˜0šžœ˜Jš
žœžœ
žœžœ
žœ
˜(Jšžœ
žœžœžœ
£œžœ
˜=—J˜—J˜J˜J˜—š‘œžœ
žœ)˜LJšœžœžœ
˜˜š‘œžœ˜(Jšžœžœ
žœ
žœ
žœžœ
žœ˜OJ˜—J˜*Jšžœ
žœžœ
žœ˜6J˜fJ˜—Jšœ*žœ˜4J˜J˜—š‘œžœ
žœ)˜PJš
‘œžœžœžœžœ#˜VJ˜?Jš
žœ
žœžž
ž
žœΟc˜6Jšžœ
žœžœ€˜6Jšžœ
žœžœ€˜5Jšžœ
žœžœ€˜6Jšžœ
žœžœ€˜6Jšžœ
žœžœ€˜6Jšžœ
žœžœ€˜6Jšžœ
žœžœ€˜6Jšžœ
žœžœ€˜5Jšžœ
žœžœ€˜6Jšžœ
žœžœ€˜6Jšžœ
žœžœ€˜6Jš	žœ
žœ
žœ
žœ€˜2Jš	žœ
žœ
žœ
žœ€˜2Jš	žœ
žœ
žœ
žœ€˜2Jš	žœ
žœ
žœ
žœ€˜2Jš	žœ
žœ
žœ
žœ€˜2Jš	žœ
žœ
žœ
žœ€˜2Jš	žœ
žœ
žœ
žœ€	˜(J˜——š
 
™
Jšœžœžœ€	œ€	œ€	œžœžœ˜XJ˜Jšœžœžœ˜;Jš	œžœžœ
žœžœ˜Eš	œ
žœžœ
žœžœ˜KJ˜—šœžœžœ˜"Jšœžœ˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜—š‘œžœžœžœ˜3šžœžœž˜ J˜Jšžœ
žœ
žœžœžœžœ
žœ˜IJšžœ
˜—Jšžœ˜
J˜J˜—š‘
œžœ
žœžœžœžœ˜Hš‘œžœžœ˜5J˜Jšžœ$˜*J˜—šžœžœž˜ J˜Jšžœ
˜—J˜J˜—š‘œžœ
žœžœžœ
žœžœžœ˜Vš‘œžœžœ˜5J˜J˜šžœ
žœ
žœ
ž˜J˜J˜Jšžœ?˜F—J˜—šžœžœž˜!šžœžœž˜!J˜Jšžœ
˜—Jšžœ
˜—J˜J˜—š‘œžœ
žœžœžœ
žœžœžœ˜Uš‘œžœžœ˜Dš‘œžœžœ˜1Jšžœ
žœžœžœ˜9J˜—J˜/J˜/Jšžœ<˜BJ˜—šžœžœž˜Jšžœžœžœ"žœ
˜EJšžœ
˜—J˜J˜—š‘œžœ
žœ˜>Jšžœ˜J˜šžœ
žœž˜J˜J˜7J˜1Jšžœ
˜—J˜J˜—š‘œžœ
žœžœ˜CJšžœ
žœžœ1žœ
˜YJ˜J˜—š‘œžœ
žœžœ˜Cšžœ
žœž˜J˜_Jšžœ
˜—J˜J˜—š‘œžœ
žœžœ˜Išžœ
žœž˜J˜_Jšžœ
˜—J˜J˜—š‘œžœ
žœžœ˜TJšžœ ˜&J˜J˜—š‘œžœ
žœžœ˜QJšœžœ˜"Jšœžœ˜"Jšœžœ˜"šžœžœ˜Jšžœžœ
žœ
žœžœžœ˜;Jšžœžœ
žœ
žœžœžœ˜;J˜
—šžœ
žœžœ˜Jšžœžœ
žœ
žœžœžœ˜;Jšžœžœ
žœ
žœžœžœ˜;J˜
—šžœ
žœžœ˜Jšžœžœ
žœ
žœžœžœ˜;Jšžœžœ
žœ
žœžœžœ˜;J˜—Jšžœ˜
J˜J˜—š‘œžœ
žœžœ˜9Jšžœ
žœžœ)žœ˜NJ˜J˜—š‘œžœ
žœžœ˜MJšžœ˜J˜J˜—š‘œžœ
žœžœ˜EJšžœ˜J˜J˜—š‘œžœ
žœžœ˜@šžœ
žœž˜J˜OJšžœžœ˜—J˜J™—š‘œžœ
žœžœ
˜Dšžœ
žœž˜J˜_Jšžœžœ˜—J˜J™—š‘œžœ
žœžœ˜VJ˜@J˜J˜—š‘œžœ
žœžœ˜@šžœ
žœž˜J˜/Jšžœžœ˜—J˜J˜—š‘œžœ
žœžœ˜Išœžœž˜J˜DJšœ-žœ˜J—˜J˜——š‘œžœ
žœžœ
˜=šžœ
žœž˜J˜CJšœ,žœ˜I—J˜——š
 ™š‘œžœ
žœžœ˜NJšœžœžœ)žœ˜RJ˜MJ˜J˜—š‘œžœ
žœžœ˜Fšžœ
žœž˜J˜SJšœ>žœ˜X—J˜J™—š‘œžœ
žœžœ˜Pšžœ
žœž˜J˜GJšœ5žœ˜L—J˜J˜—š‘œžœ
žœžœ˜Ošžœ
žœž˜Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšœžœžœžœ˜&Jšžœžœžœžœ˜*—J˜J˜—š‘
œžœ
žœžœ˜Cšžœ
žœž˜Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšžœžœ
žœžœ˜(—J˜J˜—š‘œžœ
žœžœ˜Dšžœ
žœž˜Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšžœžœ
žœžœ˜(—J˜J˜—š‘œžœ
žœžœ˜Fšžœ
žœž˜J˜YJ˜GJšœ5žœ˜U—J˜J˜—š‘	œžœ
žœžœ˜:šžœ
žœž˜J˜SJšœEžœ˜Y—J˜J˜—š‘œžœ
žœžœ˜>šžœ
žœž˜J˜GJ˜GJšœ5ž
žœ˜M—J˜J˜—š‘œžœ
žœžœ˜?šžœ
žœž˜J˜J˜J˜J˜J˜Jšžœ˜!—J˜J˜—š‘œžœ
žœžœ˜JJ˜(Jšžœ7˜=J˜J˜—š‘œžœ
žœžœ˜KJ˜#JšžœS˜YJ˜J˜—š‘œžœ
žœžœ˜Ešžœ
žœž˜Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšžœžœ
žœžœ˜(J˜J˜——š‘œžœ
žœžœ˜Dšžœ
žœž˜Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšœžœ
žœžœ˜$Jšžœžœ
žœžœ˜(J˜J˜——š‘œžœ
žœžœ˜9šžœ
žœž˜J˜EJšœ'ž
žœ˜7J˜J˜——š‘	œžœ
žœžœ˜BJ˜%Jšžœ
žœžœ
žœ˜@J˜J˜—š‘œžœ
žœžœ˜9Jš	žœ
žœžœœžœ˜PJ˜——š
 	™	š‘œžœžœ˜QJšœžœžœ˜$Jš	œ	žœžœžœžœ˜DJšœ
žœ
žœ˜4šžœ˜Jšžœžœ˜(Jšžœžœžœ˜AJ˜—J˜J˜—š‘œžœ
žœžœ˜Ešžœžœ
žœž˜"Jšžœ
žœ
žœ
˜šžœ˜J˜Ešžœ˜šžœ˜J˜7šžœž˜Jšžœ
žœ
žœ
˜Jšžœ
žœ0˜;—J˜
—Jšžœ
žœ-˜8—J˜——J˜J˜—š‘
œžœ
žœžœ˜SJ˜
šžœž˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜J˜Jšžœ
˜—J˜"J˜"J˜&J˜J˜—š‘œžœ
žœ$žœ˜NJš
žœžœ
žœ
žœ
žœ˜šžœž˜J™
J˜J˜J˜J˜J˜J˜J™
˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ'˜RJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—˜J˜ Jš	œžœžœ
žœžœ(˜SJ˜—J™˜J˜ Jšžœžœ
žœ
žœ˜1J˜Jšžœžœ
žœ
žœ˜1Jšžœ&˜,J˜—˜J˜ Jšžœžœ
žœ
žœ˜1J˜Jšžœžœ
žœ
žœ˜1Jšžœ&˜,J˜—˜J˜ Jšžœžœ
žœ
žœ˜1J˜Jšžœžœ
žœ
žœ˜1Jšžœ&˜,J˜—˜J˜ Jšžœžœ
žœ
žœ˜1J˜Jšžœžœ
žœ
žœ˜1Jšžœ&˜,J˜—˜J˜ Jšžœžœ
žœ
žœ˜1J˜Jšžœžœ
žœ
žœ˜1Jšžœ&˜,J˜—˜J˜ Jšžœžœ
žœ
žœ˜1J˜Jšžœžœ
žœ
žœ˜1Jšžœ&˜,J˜—˜J˜ Jšžœžœ
žœ
žœ˜1J˜Jšžœžœ
žœ
žœ˜1Jšžœ&˜,J˜—˜J˜ Jšžœžœ
žœ
žœ˜1J˜Jšžœžœ
žœ
žœ˜1Jšžœ&˜,J˜—Jšžœ
˜—J˜J˜—š‘	œžœ
žœžœ˜Išžœžœ
ž˜šžœžœž˜(J˜1Jšžœ
˜——J˜J˜—š‘œžœ
žœ$žœ˜OJšžœ'˜-J˜——š
 ™š‘œžœ
žœžœ˜Ršœžœž˜Jšœ€
˜+Jšœ€
˜+Jšœ€
˜+Jšœ €
˜-Jšœ€
˜+Jšœ€
˜+Jšœ€
˜+Jšœ€
˜,Jšœ&€˜<Jšœ&€˜<Jšœ&€˜<Jšœ&€˜<Jšœ&€˜<Jšœ&€˜<Jšœ&€˜<Jšœ&€˜<Jšœ&€˜<Jšœ%€˜;Jšœ&€˜<Jšœ&€˜<Jšœ%€˜8Jšœ%€˜8Jšœ%€˜8Jšœ%€˜8Jšœ%€˜8Jšœ%€˜8Jšœ%€˜6Jšžœžœ
˜—J˜J˜—š‘œžœ
žœ
˜-Jšžœ%˜,J˜Jšœ/€
˜<Jšœ0€
˜=Jšœ0€
˜=Jšœ0€
˜=Jšœ/€
˜<Jšœ0€
˜=Jšœ0€
˜=Jšœ0€
˜=Jšœ7€˜MJšœ7€˜MJšœ6€˜LJšœ7€˜MJšœ7€˜MJšœ7€˜MJšœ7€˜MJšœ7€˜MJšœ7€˜MJšœ6€˜LJšœ7€˜MJšœ7€˜MJšœ6€˜IJšœ6€˜IJšœ6€˜IJšœ6€˜IJšœ6€˜IJšœ6€˜IJšœ6€˜GJ˜——š
 
™
š‘œžœ
žœ˜.˜šžœžœž˜šžœžœ
žœ˜Jšœžœ
˜Jšžœ
˜J˜—Jšžœ
˜—Jšœžœ
˜J˜—J˜J˜J˜—š‘	œžœ
žœ˜'š‘œžœžœ˜/Jšœžœ˜šžœžœž˜J˜Jšžœžœ
žœ
žœ
˜J˜J˜Jšžœ
˜—J˜—J˜J˜J˜—
codeš‘
œžœ
žœžœžœ
žœ˜=Lšžœ˜L˜—š
‘
œžœ
žœžœ
žœ˜8Lšžœžœ
žœ˜#L˜J˜——š
 ™J™J™TJ™]JšœΟsœ™#Jšœžœžœ˜(šœž
žœžœœž
žœ
žœžœ˜CL˜—š‘œžœ
žœ
žœžœžœ™;Lšžœžœ
žœ
žœ™$L™"L™"L™—L˜š‘œžœ
žœžœ
žœ
žœ˜FL˜Lšœžœ
˜Lšœžœ
˜Lšœžœ˜)L˜L™Zšžœžœ
žœžœžœ
ž˜9L˜.Lšžœ
˜—L™-Lšœžœ3˜=Lšœžœ ˜*L˜,L˜L˜Lšžœ˜L˜L˜—š‘	œžœ
žœ"˜8Lšœžœ
˜L˜Lšœžœ
˜L™Lšžœžœ
žœžœ
žœ
žœ
˜'L˜šžœžœ
žœžœ˜-L™ULšœžœ˜Lšœžœ
˜L˜Lš
œ˜—Lš
žœ
žœ
žœžœ
žœ
˜3Lšœžœ˜L™"L˜NLšžœ
žœžœ
žœ
˜#šžœ˜šžœ˜L™$šœžœ˜0L˜6—Lšœžœ˜*L˜
—šžœ˜L™QL™'šžœžœž˜L˜"Lšžœ
˜—Lš
œ˜——L˜L˜—š
‘œžœ
žœžœžœ˜TL™«
L™L˜L˜Lšžœžœ
žœžœ
žœ
žœ
žœžœ
žœ
˜VLšœžœ˜Lšžœžœ
žœ
˜&šžœ˜šžœ˜Lšœžœ˜šžœžœ
žœ$žœžœ
ž˜BL˜Lšžœ
˜—šžœžœ˜Lšžœ
˜Lš
œ˜—L™€Lšœ$žœžœ$žœ"™uL˜šžœžœ
žœ$žœžœ
ž˜Bšžœžœž˜L˜&Lšžœ
˜—Lšžœ
˜—Lšœžœ
˜L™DL˜—L™€
šžœžœž˜L˜?Lšžœ
˜——L˜L˜—L˜š‘œžœ
žœžœžœ
žœ˜ML˜Lš
žœžœ
žœ
žœžœ˜ Lšœžœ™<Lšœ%žœ™FLš
žœžœ
žœ
žœžœ˜'šžœ
žœ
žœžœ˜-Lšžœžœ˜
Lš
œ˜—Lšœžœ˜šžœ
žœ(žœ˜4Lšžœžœ˜
Lš
œ˜—šžœ˜šžœ˜šžœžœ
žœ$žœžœ
ž˜BL˜šžœžœ˜'Lšžœžœ
žœ
˜-Lš
œ˜—Lšžœ
˜—L˜
—šžœ˜L™1L˜L˜ L˜Lšœžœ
žœ
˜
L˜Lšœžœžœžœ˜(Lšœžœžœžœ˜(Lšœžœžœžœ˜(L˜-L˜*Lšžœžœ
žœ
žœ˜Lš
œ˜—Lšžœžœ˜
—L˜——š
 
™
š‘œžœ
žœ˜1Jšžœ
žœ
žœžœ
žœ
žœ
˜1J˜$J˜:J˜MJ˜4J˜$J˜——š
 ™š‘œžœ
žœžœžœžœ˜Tš
žœžœ
žœžœ
žœ˜'š‘œžœ˜š‘œžœžœžœ˜"J˜J˜J˜—J˜šžœžœ
žœž˜ J˜
Jšžœ
˜—šžœžœž˜Jš	œžœžœ
žœžœ˜/Jšžœ
˜—J˜
Jšžœ˜šžœžœž˜Jšžœžœ
žœ
‘œ˜/Jšžœ
˜—J˜—Jšœžœ
žœ˜,Jšœžœžœ˜/J˜šžœ7˜9Jš
žœ
žœžœžœžœ˜S—Jš
žœžœ
žœ
žœ žœ˜LJ˜+J˜Jšžœ˜J˜J˜—J˜J˜—š
‘œžœ
žœžœžœ˜Hšžœžœ
žœ˜š‘
œžœ˜&š
‘
œžœ
žœžœžœ˜.š
ž˜Jšœžœžœžœ˜9Jšžœ3žœžœ
žœ
˜Kš
ž˜Jšœžœ
˜—Jšžœ
˜—J˜—šžœžœ˜Jšœžœ˜Jšžœžœ
žœ
˜(šžœžœ
žœ
ž˜Jšžœžœ
žœ
˜š
ž˜Jšžœžœ
˜—Jšžœ
˜—J˜šžœžœž˜Jšžœžœžœ
˜*J˜Jšžœ
˜—šžœžœž˜J˜Jšžœžœ
žœ˜%Jšžœ
˜—J˜—J˜—šœžœžœ5˜DJšžœ
žœ	˜—Jšœžœ
žœ˜,Jšœžœ
˜˜J˜6—Jšœžœ˜"Jšœžœ˜!Jšœžœ˜"J˜'J˜J˜J˜J˜Jšžœ˜
š
ž˜Jšœ
žœ
˜—J˜—J˜——š
 ™š‘œžœ
žœ$žœ
˜FJšžœ˜J˜Jšžœ	žœ
žœ	žœ˜5Jšžœ žœ%˜KJ˜J˜Jšžœ˜J˜J˜—š‘œžœžœ˜KJšžœ˜J˜Jšœžœ0˜9Jš
žœžœ
žœžœžœ
˜>J˜J˜——š
 ™Jšœžœžœ
˜#Jšœžœžœ
˜$J˜š‘œžœ
žœžœ˜?Jšžœ
žœ˜"J˜J˜—š‘œžœ'˜JJšœžœžœ˜>J˜#Jšžœžœ
žœ˜6J˜J˜"Jšœžœ$˜;J˜J˜—š‘œžœžœ˜OJšžœ"žœ
žœ˜>J˜ Jšœ"žœ˜:J˜"J˜J˜—š
‘
œžœ
žœžœžœ˜CJšžœ˜šžœ
žœ!™*Jšžœ5™9Jšžœ!™%—J˜J˜—š
‘œžœ
žœžœžœ˜FJšžœ˜J˜J˜—š‘œžœžœžœ˜EJšžœ#˜)J˜J˜—š‘œžœ žœ˜IJšžœ˜J˜Jšœžœ7˜EJš
žœžœ
žœžœžœ
˜NJ˜J˜#J˜J˜——š
 ™Jšœžœ˜ Jš	œžœžœžœ
žœ˜UJ˜š‘œžœ
žœ
žœ#˜Qšžœžœ
žœž˜,J˜)Jšžœžœ
žœ
žœ
˜!J˜Jšœžœ
˜Jšžœ
˜Jšžœ
˜—Jšœ
ž
œ
žœ˜+J˜J˜—š‘œžœ
žœ#˜Jšžœžœ
žœž˜,Jšžœžœ
žœ
žœ
˜,J˜)Jšžœ
˜Jšžœ
˜—J˜——š
 ™Jš	œžœ
žœžœžœ
˜.Jš	œžœ
žœžœžœ
˜-J˜š
‘œžœ
žœžœžœ˜?Jšžœ
žœžœžœ˜IJ˜J˜—š
‘œžœ
žœžœžœ˜9Jšžœ
žœžœžœ˜EJ˜J™—š
‘œžœ
žœžœžœ˜HJšžœ
žœžœžœ˜OJ˜J˜—š‘œžœ#žœžœ˜Zšžœ
žœž˜"JšœAžœ
˜S—J˜J˜—š
‘œžœ
žœžœžœ
˜=Jšžœžœžœ
žœ žœ
žœžœ
˜UJšžœ˜J˜J˜—š
‘œžœ
žœžœžœ˜9šžœžœž˜Jšžœ!žœ
žœ˜5Jšžœ
˜—Jšžœ˜J˜J˜—š
‘œžœ
žœžœžœ˜Cšžœžœž˜ Jšžœ#žœ
žœ˜4Jšžœ
˜—Jšžœ˜
J˜J˜—š‘œžœžœ
žœžœžœ˜CJšœžœžœžœ˜/Jšœžœ
žœ<˜JJšžœ	žœ
žœ˜6J˜J˜J˜—J˜Jš‘œžœ
žœžœžœžœžœ˜PJ˜—Jšžœ
˜—…—ΟΜ{