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]

];

k: Cube ¬ cube.kids[o];

IF k # NIL THEN {

ENDLOOP;

terminal: BOOL;

FOR o: Octant IN Octant DO

};

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

};

ll: INT ¬ level+1;

FOR o: Octant IN Octant DO

};

FaceTry: PROC [d: Direction] RETURNS [corner: Corner ¬ NIL] ~ {

EdgeTry: PROC [d0, d1, d2: Direction, e0, e1, e2: Edge] RETURNS [corner: Corner] ~ {

SubCube: PROC [octant: Octant, corners: Corners] ~ {

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

};

Test: PROC [o0, o1: Octant, s: {x, y, z}] ~ {

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

};

Create cube's parent, using cube's corner[o] as the center of parent:

cubeProc: CubeProc ~ {cube.level ¬ cube.level+1};

NewParent: PUBLIC PROC [cube: Cube, o: Octant] RETURNS [root: Cube] ~ {

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

Notice that the root has a kid, but is not itself truly subdivided:

root.kids[opp] ¬ cube;

Apply[root, cubeProc];

root.level ¬ 0;

TestCube[root];

};

AddCubeToParent: PROC [parent: Cube, octant: Octant, size: REAL, level: INT] ~ {

parent: Cube ¬ cube.parent;

info: FaceNeighborInfo ~ GetFaceNeighborInfo[cube, face];

IF info.recurse THEN {

parent.terminal ¬ FALSE;

AddCubeToParent[parent, info.nOctant, cube.size, cube.level];

IF fullyPointed THEN FOR o: Octant IN Octant DO

};

Test: PROC [c: Cube] RETURNS [b: BOOL] ~ {b ¬ c # NIL AND NOT c.terminal};

IF cube # NIL THEN {

EXITS

};

THEN RETURN[FALSE]

ELSE {

FOR octant: Octant IN Octant DO

RETURN[cube];

};

IF cube # NIL AND cubeProc[cube]

};

IF cube # NIL AND cubeProc[cube]

};

IF cube = NIL THEN RETURN;

IF cube.terminal

};

IF cube = NIL OR cube.level > level THEN RETURN;

IF cube.level = level

};

Test: PROC [d: Direction, o: Octant] ~ {

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

};

dir: Dir ~ decode[d];

IF NOT dir.none AND dir.x = x AND dir.y = y AND dir.z = z THEN RETURN [d]

ENDLOOP;

a: Dir ~ decode[d];

RETURN [Encode[x: -a.x, y: -a.y, z: -a.z]]

};

a[d] ¬ Opposite[d];

ENDLOOP;

d0Dir: Dir ~ decode[d0];

d1Dir: Dir ~ decode[d1];

RETURN[SELECT TRUE FROM

};

FOR d1: Direction IN Direction DO

ENDLOOP;

Dif: PROC [b0, b1: [-1..1]] RETURNS [[-1..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 o1: Octant IN Octant DO a[o0][o1] ¬ FromOctants[o0, o1]; ENDLOOP;

ENDLOOP;

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

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

lbn => lbn, lbf => lbf, ltn => ltn, ltf => ltf, rbn => rbn, rbf => rbf, rtn => rtn, rtf => rtf,

ENDCASE => none];

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

}

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

}

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

};

ln => ln, lf => lf, rn => rn, rf => rf, bn => bn, bf => bf, tn => tn, tf => tf,

ENDCASE => ERROR];

lbn => lbn, lbf => lbf, ltn => ltn, ltf => ltf, rbn => rbn, rbf => rbf, rtn => rtn, rtf => rtf,

ENDCASE => ERROR];

l => l, r => r, b => b, t => t, n => n, f => f,

ENDCASE => ERROR];

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

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

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

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

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

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

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

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

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

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

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

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

};

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

};

lb => rt, lt => rb, ln => rf, lf => rn, rb => lt, rt => lb, rn => lf,

rf => ln, bn => tf, bf => tn, tn => bf, ENDCASE => bn];

};

VAL[Basics.BITXOR[octantWord, faceBit]],

SELECT face FROM l, b, n => faceWord = 0, ENDCASE => faceWord # 0

]];

THEN RETURN[NIL]

ELSE {

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;

six faces:

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

twelve edges:

lb => {

lt => {

ln => {

lf => {

rb => {

rt => {

rn => {

rf => {

bn => {

bf => {

tn => {

tf => {

eight corners:

lbn => {

lbf => {

ltn => {

ltf => {

rbn => {

rbf => {

rtn => {

rtf => {

ENDCASE => x ¬ cube;

FOR direction: Direction IN Direction DO

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;

FOR o: Octant IN Octant DO

cube.terminal ¬ TRUE;

};

nextLevel: INT ~ level+1;

FOR o: Octant IN Octant DO

};

bbox ¬ G3dBox.BoxUnionBox[bbox, l.first.bbox];

ENDLOOP;

this can happen after subdividing. Set up an empty track, and fall into regular case.

track ¬ NEW[ObjectTrackRep];

track.objects ¬ NIL;

cube.refAny ¬ track;

};

THEN {

ELSE {

THEN {

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.

FOR octant: Octant IN Octant DO

RETURN [NIL];

};

RETURN [NIL];

};

THEN {

ELSE {

RETURN [NIL];

Inner: PROC [cube: Cube] ~ {

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",

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

};

InnerReadCube: PROC [parent: Cube] ~ {

in: STREAM ¬ FS.StreamOpen[FileNames.ResolveRelativePath[fileName] !

text: REF TEXT ¬ RefText.ObtainScratch[100];

id: ROPE ¬ "cube:\t";

line: G3dIO.Line ¬

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

};

THEN 2*cubeStack.maxLength-cubeStack.top-cubeStack.bottom

ELSE cubeStack.bottom-cubeStack.top];

crossSequence ¬ scratchCrossSequences[i];

IF crossSequence = NIL THEN LOOP;

crossSequence.length ¬ 0;

scratchCrossSequences[i] ¬ NIL;

RETURN;

ENDLOOP;

IF scratchCrossSequences[i] # NIL THEN LOOP;

scratchCrossSequences[i] ¬ crossSequence;

RETURN;

ENDLOOP;

x=>"x", y=>"y", z=>"z", xy=>"xy", xz=>"xz", yz=>"yz", xyz=>"xyz", ENDCASE=>"none"];

IF Equal[RopeFromFace[face], rope] THEN RETURN[face];

ENDLOOP;

IF Equal[RopeFromDirection[d], rope] THEN RETURN[d];

ENDLOOP;