File: SVCastRaysImplB.mesa
Last edited by Bier on June 2, 1987 1:41:02 pm PDT
Copyright © 1984 by Xerox Corporation. All rights reserved.
Contents: The ray casting (as opposed to tree building) part of the SVRay package. SVRay.mesa builds the trees
DIRECTORY
AIS, AtomButtonsTypes, SVCastRays, CoordSys, SVRay, DisplayListToTree, IO, Matrix3d, SV2d, SV3d, SVBasicTypes, SVModelTypes, SVSceneTypes;
SVCastRaysImplB: CEDAR PROGRAM
IMPORTS SVCastRays, CoordSys, SVRay, DisplayListToTree, Matrix3d
EXPORTS SVCastRays =
BEGIN
Slice: TYPE = SVSceneTypes.Slice;
BoundSphere: TYPE = SVBasicTypes.BoundSphere;
Camera: TYPE = SVModelTypes.Camera;
Classification: TYPE = SVSceneTypes.Classification;
Composite: TYPE = SVSceneTypes.Composite;
CoordSystem: TYPE = SVModelTypes.CoordSystem;
FeedbackData: TYPE = AtomButtonsTypes.FeedbackData;
Point2d: TYPE = SV2d.Point2d;
Point3d: TYPE = SV3d.Point3d;
Primitive: TYPE = SVSceneTypes.Primitive;
Ray: TYPE = SVSceneTypes.Ray;
Vector3d: TYPE = SV3d.Vector3d;
DoesHit: PROC [class: Classification] RETURNS [BOOL] = {
RETURN[class.count > 0 OR class.classifs[1] = TRUE];
};
RayCastBoundingSpheres: PUBLIC PROC [worldRay: Ray, node: REF ANY, consolidate: BOOL ← TRUE, feedback: FeedbackData, makeStream: BOOL ← FALSE, indent: NAT ← 0] RETURNS [class: Classification] = {
The main ray casting procedure. worldRay must be in WORLD coordinates before this procedure is called.
OPEN SVCastRays;
IF node = NIL THEN {class ← EmptyClass[]; RETURN};
WITH node SELECT FROM
comp: Composite => {
leftClass, rightClass: Classification;
leftBoxHit, leftHit, rightBoxHit, rightHit: BOOL;
totalMiss: BOOL ← FALSE;
boundSphere: BoundSphere;
Before casting each ray, see if the ray will be in the bounding sphere of the son node.
For optimizing, here is the plan:
1) Check ray for left bound box. Set leftBoxHit if appropriate.
2) If leftBoxHit then cast the ray. Set leftHit if appropriate.
3) If not leftHit then if comp.operation = intersection or difference, return miss.
4) If hit, or union, then right box test. Set RightBoxMiss if appropriate.
5) If miss then return: leftclass for difference, empty for intersection, leftClass for union.
6) Else cast ray.
7) Return rightclass or combination if appropriate
1) Check ray for left bound box. Set leftBoxHit if appropriate.
WITH comp.leftSolid SELECT FROM
p: Primitive => boundSphere ← p.boundSphere;
c: Composite => boundSphere ← c.boundSphere;
ENDCASE => ERROR;
leftBoxHit ← SVRay.RayHitsBoundSphere[worldRay, boundSphere];
2) If leftBoxHit then cast the ray. Set leftHit if appropriate.
IF leftBoxHit THEN {
leftClass ← RayCastBoundingSpheres[worldRay, comp.leftSolid, consolidate, feedback, makeStream, indent];
leftHit ← DoesHit[leftClass]; }
ELSE {leftHit ← FALSE; leftClass ← EmptyClass[]};
3) If not leftHit then if comp.operation = intersection or difference, return miss.
IF NOT leftHit THEN IF comp.operation = intersection OR comp.operation = difference
THEN {
class ← leftClass; WriteStreamComp[comp, class, feedback, makeStream, indent]; RETURN};
leftClass is (or is equivalent to) EmptyClass[];
4) If hit, or union, then right sphere test. Set RightBoxMiss if appropriate. (we don't have to test for this state. It is the only one left.)
WITH comp.rightSolid SELECT FROM
p: Primitive => boundSphere ← p.boundSphere;
c: Composite => boundSphere ← c.boundSphere;
ENDCASE => ERROR;
rightBoxHit ← SVRay.RayHitsBoundSphere[worldRay, boundSphere];
5) If miss then return EmptyClass. Else cast ray.
IF NOT rightBoxHit THEN
This could be a union with or without a left miss or (intersection/difference) with an initial hit.
SELECT comp.operation FROM
union => {class ← leftClass; WriteStreamComp[comp, class, feedback, makeStream, indent]; RETURN};
intersection =>
IF NOT leftHit THEN RETURN[leftClass]
ELSE {
ReturnClassToPool[leftClass]; class ← EmptyClass[]; WriteStreamComp[comp, class, feedback, makeStream, indent]; RETURN};
difference => {class ← leftClass; WriteStreamComp[comp, class, feedback, makeStream, indent]; RETURN};
ENDCASE => ERROR;
6) Else cast ray. We have Union, or (intersection/difference) with left hit. Ray hits box.
rightClass ← RayCastBoundingSpheres[worldRay, comp.rightSolid, consolidate, feedback, makeStream, indent];
rightHit ← DoesHit[rightClass];
7) Return rightclass, combination or empty if appropriate
SELECT comp.operation FROM
union =>
IF rightHit THEN {
IF leftHit THEN class ← UnionCombine[leftClass, rightClass, consolidate]
ELSE {ReturnClassToPool[leftClass]; class ← rightClass}
}
ELSE {
ReturnClassToPool[rightClass]; class ← leftClass};
intersection =>
IF rightHit THEN {
IF leftHit THEN class ← IntersectionCombine[leftClass, rightClass, consolidate]
ELSE {ReturnClassToPool[rightClass]; class ← leftClass;}
}
ELSE IF leftHit THEN {ReturnClassToPool[leftClass]; class ← rightClass}
ELSE {ReturnClassToPool[rightClass]; class ← leftClass};
difference =>
IF rightHit THEN {
IF leftHit THEN class ← DifferenceCombine[leftClass, rightClass, consolidate]
ELSE {ReturnClassToPool[rightClass]; class ← leftClass} -- leftClass null
}
ELSE {ReturnClassToPool[rightClass]; class ← leftClass};
ENDCASE => ERROR;
WriteStreamComp[comp, class, feedback, makeStream, indent];
RETURN};
prim: Primitive => {
localRay: Ray;
IF prim.ignoreMe THEN
{class ← SVCastRays.GetClassFromPool[]; SVCastRays.MakeClassAMiss[class]; RETURN};
localRay ← SVRay.TransformRay[worldRay, prim.worldWRTPrim]; -- (takes a new ray from the pool)
class ← prim.rayCastBoundingSpheres[localRay, prim.sliceD, prim];
WriteStreamPrim[prim, class, feedback, makeStream, 0];
SVRay.ReturnRayToPool[localRay]; -- returns ray to pool
RETURN};
ENDCASE => ERROR;
}; -- end of RayCastBoundingSpheres
ClassAssign: PROC [to: Classification, i: NAT, from: Classification, j: NAT] = {
to.params[i] ← from.params[j];
to.classifs[i] ← from.classifs[j];
to.normals[i] ← from.normals[j];
to.surfaces[i] ← from.surfaces[j];
to.primitives[i] ← from.primitives[j];
};
ClassSwap: PROC [class: Classification, i, j: NAT] = {
Swap the ith and jth columns of a classification record.
paramTemp: REAL;
classifTemp: BOOL;
normalTemp: Vector3d;
surfaceTemp: Surface;
primTemp: Primitive;
paramTemp ← class.params[i];
class.params[i] ← class.params[j];
class.params[j] ← paramTemp;
classifTemp ← class.classifs[i];
class.classifs[i] ← class.classifs[j];
class.classifs[j] ← class.classifs[i];
normalTemp ← class.classifs[i]
class.normals[i] ← class.normals[j];
class.normals[j] ← class.normals[i];
surfaceTemp ← class.surfaces[i];
class.surfaces[i] ← class.surfaces[j];
class.surfaces[j] ← class.surfaces[i];
primTemp ← class.primitives[i];
class.primitives[i] ← class.primitives[j];
class.primitives[j] ← class.primitives[i];
};
SortClassByPrimitive: PUBLIC PROC [class: Classification] = {
Reorders the classification so that all of the intersections corresponding to a particular primitive are grouped together (locally in ascending t value), and primitives are ordered by t value of the first hit on that primitive. Copy from newClass to class as you go.
newClass: Classification;
used: ARRAY [1..SVSceneTypes.maxSceneDepth] OF BOOL;
thisPrim: Primitive;
newClass ← SVRay.CopyClass[class];
FOR i: NAT IN [1..SVSceneTypes.maxSceneDepth] DO used[i] ← FALSE; ENDLOOP;
thisPrim ← newClass.primitives[1];
FOR i: NAT IN [1..class.count] DO
FOR j: NAT IN [1..class.count] DO
IF NOT used[j] AND newClass.primitives[j] = thisPrim THEN {
ClassAssign[class, i, newClass, j];
used[j] ← TRUE;
GOTO Found;
};
REPEAT
Found => NULL;
FINISHED =>
FOR k: NAT IN [1..class.count] DO
IF NOT used[k] THEN {
thisPrim ← newClass.primitives[k];
ClassAssign[class, i, newClass, k];
used[k] ← TRUE;
EXIT;
};
ENDLOOP;
ENDLOOP;
ENDLOOP;
};
The SurfacePointAndNormal and AssemblyAndPrimitive procedures are distinct because Cedar can't handle a return record which both contains a pointer (assembly) and returns 6 REALS (long pointer-containing return record is unsafe)
NthSurfacePointAndNormal: PUBLIC PROC [class: Classification, rayWorld: Ray, n: NAT] RETURNS [surfacePtWorld: Point3d, normalWorld: Vector3d] = {
Find the surface point and surface normal of the nth primitive hit by the ray.
firstPrim: Primitive;
primitiveNormal: Vector3d;
t: REAL;
count: NAT ← 0;
IF n = 0 OR n > class.count THEN ERROR;
FOR i: NAT IN [1..class.count] DO
IF class.stills[i] THEN {
count ← count + 1;
IF count = n THEN GOTO Found;
};
REPEAT
Found => {
t ← class.params[i]; -- the parameter of the ray intersection
primitiveNormal ← class.normals[i];
firstPrim ← class.primitives[i];
normalWorld ← Matrix3d.UpdateVectorWithInverse[firstPrim.worldWRTPrim, primitiveNormal];
surfacePtWorld ← SVRay.EvaluateWorldRay[rayWorld, t];
};
FINISHED => {
surfacePtWorld ← [0,0,0];
normalWorld ← [0,0,1];
};
ENDLOOP;
};
LastOfFirstPointAndNormal: PUBLIC PROC [class: Classification, rayWorld: Ray] RETURNS [surfacePtWorld: Point3d, normalWorld: Vector3d] = {
Find the surface point and surface normal, belonging to the first primitive hit by the ray, when the ray last leaves that primitive.
primitiveNormal: Vector3d;
t: REAL;
lastNum: NAT ← class.count;
lastOfFirstIndex: NAT ← 1;
firstPrim: Primitive ← class.primitives[1];
IF lastNum = 0 THEN RETURN;
FOR i: NAT DECREASING IN [2..lastNum] DO
IF class.primitives[i] = firstPrim THEN GOTO Found;
REPEAT
Found => lastOfFirstIndex ← i;
ENDLOOP;
t ← class.params[lastOfFirstIndex]; -- the parameter of the last ray intersection
primitiveNormal ← class.normals[lastOfFirstIndex];
normalWorld ← Matrix3d.UpdateVectorWithInverse[firstPrim.worldWRTPrim, primitiveNormal];
surfacePtWorld ← SVRay.EvaluateWorldRay[rayWorld, t];
};
LastOfFirstHitData: PUBLIC PROC [class: Classification] RETURNS [hitData: REF ANY] = {
Find the surface point and surface normal, belonging to the first primitive hit by the ray, when the ray last leaves that primitive.
lastNum: NAT ← class.count;
lastOfFirstIndex: NAT ← 1;
firstPrim: Primitive ← class.primitives[1];
IF lastNum = 0 THEN RETURN;
FOR i: NAT DECREASING IN [2..lastNum] DO
IF class.primitives[i] = firstPrim THEN GOTO Found;
REPEAT
Found => lastOfFirstIndex ← i;
ENDLOOP;
hitData ← class.surfaces[lastOfFirstIndex];
};
LastTopLevelPointAndNormal: PUBLIC PROC [class: Classification, rayWorld: Ray, root: Slice] RETURNS [surfacePtWorld: Point3d, normalWorld: Vector3d] = {
Find the surface point and surface normal, belonging to the first top level assembly hit by the ray, when the ray last leaves that top level assembly. Note that the assembly may well be composite (composed of multiple primitives). "Top level" assemblies are direct children of "root".
primitiveNormal: Vector3d;
t: REAL;
lastNum: NAT ← class.count;
lastTopLevelIndex: NAT ← 1;
firstPrim: Primitive ← class.primitives[1];
lastPrim: Primitive;
firstAssembly, thisAssembly: Slice;
firstTopLevel: Slice;
firstAssembly ← NARROW[firstPrim.assembly];
firstTopLevel ← DisplayListToTree.AncestorAtLevel[firstAssembly, root, 1];
IF lastNum = 0 THEN RETURN;
FOR i: NAT DECREASING IN [2..lastNum] DO
thisAssembly ← NARROW[class.primitives[i].assembly];
IF DisplayListToTree.IsSuccessorOf[thisAssembly, firstTopLevel] THEN GOTO Found;
REPEAT
Found => lastTopLevelIndex ← i;
ENDLOOP;
t ← class.params[lastTopLevelIndex]; -- the parameter of the last ray intersection
primitiveNormal ← class.normals[lastTopLevelIndex];
lastPrim ← class.primitives[lastTopLevelIndex];
normalWorld ← Matrix3d.UpdateVectorWithInverse[lastPrim.worldWRTPrim, primitiveNormal];
surfacePtWorld ← SVRay.EvaluateWorldRay[rayWorld, t];
};
NthAssemblyAndPrimitive: PUBLIC PROC [class: Classification, n: NAT] RETURNS [assembly: Slice, primitive: Primitive] = {
Find the nth primitive hit by the ray and its corresponding displaylist assembly.
count: NAT ← 0;
IF n = 0 OR n > class.count THEN RETURN[NIL, NIL];
FOR i: NAT IN [1..class.count] DO
IF class.stills[i] THEN {
count ← count + 1;
IF count = n THEN GOTO Found;
};
REPEAT
Found => {
primitive ← class.primitives[i];
assembly ← NARROW[primitive.assembly];
};
FINISHED => {
primitive ← NIL;
assembly ← NIL;
};
ENDLOOP;
};
NthHitData: PUBLIC PROC [class: Classification, n: NAT] RETURNS [hitData: REF ANY] = {
Find the nth primitive hit by the ray and its corresponding displaylist assembly.
count: NAT ← 0;
IF n = 0 OR n > class.count THEN RETURN[NIL];
FOR i: NAT IN [1..class.count] DO
IF class.stills[i] THEN {
count ← count + 1;
IF count = n THEN GOTO Found;
};
REPEAT
Found => {
hitData ← class.surfaces[i];
};
FINISHED => {
hitData ← NIL;
};
ENDLOOP;
};
LastTopLevelAssemAndPrim: PUBLIC PROC [class: Classification, root: Slice] RETURNS [assembly: Slice, primitive: Primitive] = {
Find the first top level assembly hit by the ray and the primitive at which the ray last leaves that top level assembly.
lastNum: NAT ← class.count;
lastTopLevelIndex: NAT ← 1;
firstPrim: Primitive ← class.primitives[1];
firstTopLevel, thisAssembly: Slice;
IF lastNum = 0 THEN RETURN[NIL, NIL];
thisAssembly ← NARROW[firstPrim.assembly];
firstTopLevel ← DisplayListToTree.AncestorAtLevel[thisAssembly, root, 1];
FOR i: NAT DECREASING IN [2..lastNum] DO
thisAssembly ← NARROW[class.primitives[i].assembly];
IF DisplayListToTree.IsSuccessorOf[thisAssembly, firstTopLevel] THEN GOTO Found;
REPEAT
Found => lastTopLevelIndex ← i;
ENDLOOP;
primitive ← class.primitives[lastTopLevelIndex];
assembly ← NARROW[primitive.assembly];
assembly ← firstTopLevel;
};
LastTopLevelHitData: PUBLIC PROC [class: Classification, root: Slice] RETURNS [hitData: REF ANY] = {
Find the first top level assembly hit by the ray and the primitive at which the ray last leaves that top level assembly.
lastNum: NAT ← class.count;
lastTopLevelIndex: NAT ← 1;
firstPrim: Primitive ← class.primitives[1];
firstTopLevel, thisAssembly: Slice;
IF lastNum = 0 THEN RETURN[NIL];
thisAssembly ← NARROW[firstPrim.assembly];
firstTopLevel ← DisplayListToTree.AncestorAtLevel[thisAssembly, root, 1];
FOR i: NAT DECREASING IN [2..lastNum] DO
thisAssembly ← NARROW[class.primitives[i].assembly];
IF DisplayListToTree.IsSuccessorOf[thisAssembly, firstTopLevel] THEN GOTO Found;
REPEAT
Found => lastTopLevelIndex ← i;
ENDLOOP;
hitData ← class.surfaces[lastTopLevelIndex];
};
RayMeetsZConstantPlane: PUBLIC PROC [localRay: Ray, z: REAL] RETURNS [hitPoint: Point3d, parallel: BOOL] = {
We assume the ray and the z constant plane are in the same coordinate frame. As usual the ray equations are:
x = localRay.basePt[1] + t*localRay.direction[1];
y = localRay.basePt[2] + t*localRay.direction[2];
z = localRay.basePt[3] + t*localRay.direction[3];
If direction[3] is almost zero then report parallel.
almostZero: REAL ← 1.0e-12;
t: REAL;
p: Point3d;
d: Vector3d;
[p, d] ← SVRay.GetLocalRay[localRay];
IF ABS[d[3]] < almostZero THEN {
hitPoint ← [0,0,0];
parallel ← TRUE;
RETURN;
}
ELSE {
t ← (z - p[3])/d[3];
hitPoint[1] ← p[1] + t*d[1];
hitPoint[2] ← p[2] + t*d[2];
hitPoint[3] ← z;
parallel ← FALSE;
};
};

RayMeetsPlaneOfCoordSystem: PUBLIC PROC [coordSys: CoordSystem, rayWorld: Ray, whichPlane: NAT, depth: REAL ← 0] RETURNS [pointWorld: Point3d, parallel: BOOL] = {
Finds the intersection of the ray with one of the three orthogonal planes of coordSys. If whichPlane = 1 this will be the x=0 (yz) plane, whichPlane = 2 then the y=0 plane, whichPlane = 3 then the z = 0 plane. Assumes ray is initially in camera coordinates. Returns the ray-plane intersection in camera coordinates, or parallel = TRUE if the ray is parallel to the plane. As usual the ray equations are:
x = localRay.basePt[1] + t*localRay.direction[1];
y = localRay.basePt[2] + t*localRay.direction[2];
z = localRay.basePt[3] + t*localRay.direction[3];
If direction[3] is almost zero then report parallel.
almostZero: REAL ← 1.0e-12;
t: REAL;
localRay: Ray;
hitPoint: Point3d;
p: Point3d;
d: Vector3d;
localRay ← SVRay.TransformRay[rayWorld, CoordSys.FindWorldInTermsOf[coordSys]];
[p, d] ← SVRay.GetLocalRay[localRay];
SELECT whichPlane FROM
1 => { -- The x = depth plane
IF ABS[d[1]] < almostZero THEN {
pointWorld ← [depth,0,0];
parallel ← TRUE;
RETURN;
}
ELSE {
t ← (depth - p[1])/d[1];
hitPoint[1] ← depth;
hitPoint[2] ← p[2] + t*d[2];
hitPoint[3] ← p[3] + t*d[3];
parallel ← FALSE;
};
};
2 => { -- The y = depth plane
IF ABS[d[2]] < almostZero THEN {
pointWorld ← [0,depth,0];
parallel ← TRUE;
RETURN;
}
ELSE {
t ← (depth - p[2])/d[2];
hitPoint[1] ← p[1] + t*d[1];
hitPoint[2] ← depth;
hitPoint[3] ← p[3] + t*d[3];
parallel ← FALSE;
};
};
3 => { -- The z = depth plane
IF ABS[d[3]] < almostZero THEN {
pointWorld ← [0,0,depth];
parallel ← TRUE;
RETURN;
}
ELSE {
t ← (depth - p[3])/d[3];
hitPoint[1] ← p[1] + t*d[1];
hitPoint[2] ← p[2] + t*d[2];
hitPoint[3] ← depth;
parallel ← FALSE;
};
};
ENDCASE => ERROR;
SVRay.ReturnRayToPool[localRay];
pointWorld ← Matrix3d.Update[hitPoint, CoordSys.WRTWorld[coordSys]];
};
END.