IntersectRayWithCube:
PUBLIC
PROC [ray: Ray, cube: Cube]
RETURNS [Intersection] ~ {
RETURN[
IF G3dOctree.PointInCube[ray.base, cube]
THEN IntersectRayInsideCube[ray, cube]
ELSE IntersectRayOutsideCube[ray, cube]];
};
IntersectRayInsideCube:
PUBLIC
PROC [ray: Ray, cube: Cube]
RETURNS [i: Intersection] ~ {
mm: Box ¬ G3dOctree.BoxOfCube[cube];
i ¬ Intersect[ray, mm, mm.min, mm.max, leaving];
i.cube ¬ cube;
};
IntersectRayOutsideCube:
PUBLIC
PROC [ray: Ray, cube: Cube]
RETURNS [i: Intersection]~ {
mm: Box ¬ G3dOctree.BoxOfCube[cube];
i ¬ Intersect[ray, mm, mm.max, mm.min, entering];
i.cube ¬ cube;
};
Intersect:
PROC [ray: Ray, mm: Box, p1, p2: Triple, hopefully: IntersectionType]
RETURNS [i: Intersection]
~ {
tests: RECORD[x, y, z: BOOL] ¬ [FALSE, FALSE, FALSE];
TestX: PROC RETURNS [BOOL] ~ {RETURN[i.point.x = mm.min.x OR i.point.x = mm.max.x]};
TestY: PROC RETURNS [BOOL] ~ {RETURN[i.point.y = mm.min.y OR i.point.y = mm.max.y]};
TestZ: PROC RETURNS [BOOL] ~ {RETURN[i.point.z = mm.min.z OR i.point.z = mm.max.z]};
GetDirectionSelect:
PROC
RETURNS [ds: DirectionSelect] ~ {
ds ¬
SELECT
TRUE
FROM
tests.x =>
SELECT
TRUE
FROM
tests.y => IF tests.z THEN xyz ELSE xy,
tests.z => xz,
ENDCASE => x,
tests.y =>
SELECT
TRUE
FROM
tests.z => yz,
ENDCASE => y,
tests.z => z,
ENDCASE => ERROR;
};
XGood:
PROC
RETURNS [good:
BOOL ¬
TRUE] ~ {
i.point.x ¬ IF ray.axis.x < 0.0 THEN p1.x ELSE p2.x;
IF (i.t ¬ (i.point.x-ray.base.x)/ray.axis.x) < 0.0 THEN RETURN[FALSE];
i.point.y ¬ ray.base.y+i.t*ray.axis.y;
IF i.point.y NOT IN [mm.min.y..mm.max.y] THEN RETURN[FALSE];
i.point.z ¬ ray.base.z+i.t*ray.axis.z;
IF i.point.z NOT IN [mm.min.z..mm.max.z] THEN RETURN[FALSE];
tests ¬ [TRUE, TestY[], TestZ[]];
};
YGood:
PROC
RETURNS [good:
BOOL ¬
TRUE] ~ {
i.point.y ¬ IF ray.axis.y < 0.0 THEN p1.y ELSE p2.y;
IF (i.t ¬ (i.point.y-ray.base.y)/ray.axis.y) < 0.0 THEN RETURN[FALSE];
i.point.x ¬ ray.base.x+i.t*ray.axis.x;
IF i.point.x NOT IN [mm.min.x..mm.max.x] THEN RETURN[FALSE];
i.point.z ¬ ray.base.z+i.t*ray.axis.z;
IF i.point.z NOT IN [mm.min.z..mm.max.z] THEN RETURN[FALSE];
tests ¬ [TestX[], TRUE, TestZ[]];
};
ZGood:
PROC
RETURNS [good:
BOOL ¬
TRUE] ~ {
i.point.z ¬ IF ray.axis.z < 0.0 THEN p1.z ELSE p2.z;
IF (i.t ¬ (i.point.z-ray.base.z)/ray.axis.z) < 0.0 THEN RETURN[FALSE];
i.point.x ¬ ray.base.x+i.t*ray.axis.x;
IF i.point.x NOT IN [mm.min.x..mm.max.x] THEN RETURN[FALSE];
i.point.y ¬ ray.base.y+i.t*ray.axis.y;
IF i.point.y NOT IN [mm.min.y..mm.max.y] THEN RETURN[FALSE];
tests ¬ [TestX[], TestY[], TRUE];
};
i.type ¬ hopefully;
IF ray.axis.x # 0.0
AND XGood[]
OR
ray.axis.y # 0.0 AND YGood[] OR
ray.axis.z # 0.0
AND ZGood[]
THEN i.directionSelect ¬ GetDirectionSelect[]
ELSE i.type ¬ empty;
};
IntersectTerminalCube:
PROC [root: Cube, ray: Ray, delta: Triple, i: Intersection]
RETURNS [Intersection]
~ {
This assumes i is an entering intersection and i.cube is not terminal.
First, test if a terminal cube exists immediately within i.cube:
Inner:
PROC [i: Intersection]
RETURNS [Intersection] ~ {
testCube: Cube ¬ NextCube[i, delta, root];
IF testCube.terminal
THEN {
i.cube ¬ testCube;
i.type ¬ entering;
RETURN[i];
};
IF testCube # i.cube
THEN {
testCube is nested within cube; it may contain a terminal cube hit by ray:
i.cube ¬ testCube;
RETURN[Inner[i]];
}
ELSE {
Nothing important in this octant of i.cube; but before leaving i.cube, test its kids:
ii: Intersection ¬ [empty, none, 1000000.0,,,];
subCubeIntersected: BOOL ¬ FALSE;
FOR o: Octant
IN Octant
DO
kid: Cube ¬ i.cube.kids[o];
IF kid #
NIL
THEN {
iii: Intersection ¬ IntersectRayOutsideCube[ray, kid];
IF iii.type = entering
AND iii.t > i.t
AND iii.t < ii.t
THEN {
ii ¬ iii;
subCubeIntersected ¬ TRUE;
};
};
ENDLOOP;
IF subCubeIntersected
THEN {
IF ii.cube.terminal
THEN RETURN[ii]
ELSE RETURN[Inner[ii]];
}
ELSE {
No subcubes intersected, so try i.cube's neighbor:
i ¬ IntersectRayInsideCube[ray, i.cube];
i.cube ¬ NextCube[i, delta, root];
IF i.cube = NIL THEN RETURN[[empty]];
RETURN[Inner[i]];
};
};
};
IF i.cube.terminal THEN RETURN[i];
RETURN[Inner[i]];
};
FirstIntersectionWithOctree:
PUBLIC
PROC [ray: Ray, octree: Octree]
RETURNS [i: Intersection]
~ {
i ¬
IF G3dOctree.PointInCube[ray.base, octree.root]
THEN [entering, none, 0.0, ray.base, , G3dOctree.WhichCube[ray.base, octree.root]]
ELSE IntersectRayOutsideCube[ray, octree.root];
IF
NOT i.cube.terminal
THEN {
delta: Triple ¬ G3dVector.Mul[ray.axis, octree.terminalRadius];
i ¬ IntersectTerminalCube[octree.root, ray, delta, i];
}
ELSE i.type ¬ entering;
};
NextCube:
PROC [i: Intersection, delta: Triple, root: Cube]
RETURNS [Cube] ~ {
This procedure per Andrew's suggestion, Oct., 1984 CG&A
(a more efficient but complex approach is by Fujimoto et. al., Apr., 1986 CG&A).
p: Triple ¬
SELECT i.directionSelect
FROM
xyz => [i.point.x+delta.x, i.point.y+delta.y, i.point.z+delta.z],
xy => [i.point.x+delta.x, i.point.y+delta.y, i.point.z],
xz => [i.point.x+delta.x, i.point.y, i.point.z+delta.z],
yz => [i.point.x, i.point.y+delta.y, i.point.z+delta.z],
x => [i.point.x+delta.x, i.point.y, i.point.z],
y => [i.point.x, i.point.y+delta.y, i.point.z],
z => [i.point.x, i.point.y, i.point.z+delta.z],
ENDCASE => i.point; -- assume i.point was actually inside a cube
RETURN[G3dOctree.WhichCube[p, root]];
};
IntersectRayWithOctree:
PUBLIC
PROC [ray: Ray, octree: Octree]
RETURNS [list: IntersectionList]
~ {
ReverseList:
PROC [in: IntersectionList]
RETURNS [out: IntersectionList] ~ {
FOR l: IntersectionList ¬ in, l.rest WHILE l # NIL DO out ¬ CONS[l.first, out]; ENDLOOP;
};
delta: Triple ¬ G3dVector.Mul[ray.axis, octree.terminalRadius];
i: Intersection ¬
IF G3dOctree.PointInCube[ray.base, octree.root]
THEN [entering, none, 0.0, ray.base, , G3dOctree.WhichCube[ray.base, octree.root]]
ELSE IntersectRayOutsideCube[ray, octree.root];
DO
IF
NOT i.cube.terminal
THEN i ¬ IntersectTerminalCube[octree.root, ray, delta, i]
ELSE i.type ¬ entering;
IF i.type = empty THEN RETURN[ReverseList[list]];
list ¬ CONS[i, list];
i ¬ IntersectRayInsideCube[ray, i.cube];
list ¬ CONS[i, list];
IF (i.cube ¬ NextCube[i, delta, octree.root]) =
NIL THEN
Ray has exited the Volume:
RETURN[ReverseList[list]]
ENDLOOP;
};