
DIRECTORY G3dBasic, G3dOctree, G3dRayCube, G3dVector;

G3dRayCubeImpl: CEDAR PROGRAM
IMPORTS G3dOctree, G3dVector
EXPORTS G3dRayCube

~ BEGIN
Ray:					TYPE ~ G3dBasic.Ray;
Box:					TYPE ~ G3dBasic.Box;
Triple:				TYPE ~ G3dBasic.Triple;
DirectionSelect:		TYPE ~ G3dOctree.DirectionSelect;
Octant:				TYPE ~ G3dOctree.Octant;
Cube:					TYPE ~ G3dOctree.Cube;
Intersection:			TYPE ~ G3dOctree.Intersection;
IntersectionList:		TYPE ~ G3dOctree.IntersectionList;
IntersectionType:	TYPE ~ G3dOctree.IntersectionType;
Octree:				TYPE ~ G3dOctree.Octree;
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]
~ {
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 {
i.cube м testCube;
RETURN[Inner[i]];
}
ELSE {
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 {
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] ~ {
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
RETURN[ReverseList[list]]
ENDLOOP;
};

END.

  д  
G3dRayCubeImpl.mesa
Copyright ╙ 1985, 1992 by Xerox Corporation.  All rights reserved.
Bloomenthal, November 21, 1992 2:54 pm PST
Types
Ray-Cube Operations
This assumes i is an entering intersection and i.cube is not terminal.
First, test if a terminal cube exists immediately within i.cube:
testCube is nested within cube; it may contain a terminal cube hit by ray:
Nothing important in this octant of i.cube; but before leaving i.cube, test its kids:
No subcubes intersected, so try i.cube's neighbor:
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).
Ray has exited the Volume:
 Э╩ї  Ц"cedarcode" styleХNewlineDelimiter
Щ ЩJЪЬ	╧eЬ6ЩBJЩ*JШ JЪ╧k	Ь,Ш5JШ ЧЪ╤blnЬЮЬЮШJЪЮЬШJЪЮЬШJШ ЧJЪЬЮШheadЪ╧lЩJЪЬЮЬШJЪЬЮЬШJЪЬЮЬШ"JЪЬЮЬШ3JЪЬ
ЮЬШ#JЪЬЮЬШ JЪЬЮЬШ.JЪЬЮЬШ5JЪЬЮЬШ4JЪЬЮЬШ#ЧЪаЩЪ╧nЬЮЬЮЬЮЬШSЪЮЬЮЬ&Ш/JЪЮЬ"Ш&JЪЮЬ%Ш)ЧJШJШ ЧЪбЬЮЬЮЬЮЬШXJШ$JШ0JШJШJШ ЧЪбЬЮЬЮЬЮЬШXJШ$JШ1JШJШJШ ЧЪб	ЬЮЬAШPJЪЮЬШJШJЪЬЮЬ
ЮЬЮЬЮЬЮЬШ5JЪбЬЮЬЮЬЮЬЮЬЮЬШTJЪбЬЮЬЮЬЮЬЮЬЮЬШTJЪбЬЮЬЮЬЮЬЮЬЮЬШTЪбЬЮЬЮЬШ:ЪЬЮЬЮЬЮШЪЬЮЬЮЬЮШJЪЬЮЬ	ЮЬЮЬШ'JШJЪЮЬШЧЪЬЮЬЮЬЮШJШJЪЮЬШЧJШJЪЮЬЮЬШЧJШЧЪ
бЬЮЬЮЬЮЬЮЬШ+JЪЬЮЬЮЬЮЬШ4JЪЮЬ1ЮЬЮЬЮЬШFJШ&JЪЮЬЮЬЮЬЮЬЮЬЮЬШ<JШ&JЪЮЬЮЬЮЬЮЬЮЬЮЬШ<JЪЬ	ЮЬШ!JШЧЪ
бЬЮЬЮЬЮЬЮЬШ+JЪЬЮЬЮЬЮЬШ4JЪЮЬ1ЮЬЮЬЮЬШFJШ&JЪЮЬЮЬЮЬЮЬЮЬЮЬШ<JШ&JЪЮЬЮЬЮЬЮЬЮЬЮЬШ<JЪЬЮЬШ!JШЧЪ
бЬЮЬЮЬЮЬЮЬШ+JЪЬЮЬЮЬЮЬШ4JЪЮЬ1ЮЬЮЬЮЬШFJШ&JЪЮЬЮЬЮЬЮЬЮЬЮЬШ<JШ&JЪЮЬЮЬЮЬЮЬЮЬЮЬШ<JЪЬЮЬШ!JШЧJШЪЮЬЮЬ	ЮШ"JЪЬЮЬ	ЮШЪЬЮЬШJЪЮЬ)Ш-JЪЮЬШЧЧJШJШ ЧЪбЬЮЬ7ШRJЪЮЬШJШJЩFJЩ@ЪбЬЮЬЮЬШ8JШ*ЪЮЬЮЬШJШJШJЪЮЬШ
JШЧЪЮЬШЪЮЬШJЩJJШJЪЮЬ╧bЬШJШЧЪЮЬШJЩUJШ/JЪЬЮЬЮЬШ!ЪЮЬЮЬЮШJШЪЮЬЮЬЮЬШJШ6ЪЮЬЮЬЮЬЮЬШ>JШ	JЪЬЮЬШJШЧJШЧJЪЮЬШЧЪЮЬШЪЮЬШЪЮЬШJЪЮЬЮЬШJЪЮЬЮЬвЬШJШЧЧЪЮЬШJЩ2JШ(JШ"JЪЮЬ
ЮЬЮЬЮЬ
Ш%JЪЮЬвЬШJШЧЧJШЧЧJШЧJЪЮЬЮЬЮЬШ"JЪЮЬШJШJШ ЧЪбЬЮЬЮЬШCJЪЮЬШJШЪЬЮЬ-Ш3JЪЮЬNШRJЪЮЬ+Ш/ЧЪЮЬЮЬШЪЮЬШJШ?JШ6JШЧJЪЮЬШЧJШJШ ЧЪбЬЮЬ.ЮЬШNJЩ7JЩPЪЬЮЬЮШ)JШAJШ9JШ9JШ9JШ0JШ0JШ0JЪЮЬ╧c,ШAЧJЪЮЬШ%JШJШ ЧЪбЬЮЬЮЬШ>JЪЮЬШ JШЪбЬЮЬЮЬШLJЪЮЬ"ЮЬЮЬЮЬЮЬЮЬШXJШЧJШ?ЪЬЮЬ-ШAJЪЮЬNШRJЪЮЬ+Ш/ЧЪЮШЪЮЬЮЬШJЪЮЬ6Ш:JЪЮЬШЧJЪЮЬЮЬЮЬШ1JЪЬЮЬ
ШJШ(JЪЬЮЬ
ШЪЮЬ.ЮШ8JЩJЪЮЬШЧJЪЮЬШЧJШЧJШ ЧJЪЮЬШJШ Ч ЕЧ    *  "├  