File: CastRays.mesa
Last edited by Bier on March 20, 1987 1:38:03 pm PST
Author: Eric Bier in the summer of 1982
Contents: The ray casting (as opposed to tree building) part of the CSG package. CSG.mesa builds the trees
DIRECTORY
AtomButtonsTypes, Imager, IO, Rope, SV2d, SV3d, SVBasicTypes, SVModelTypes, SVRayTypes, SVSceneTypes, ViewerClasses;
CastRays: CEDAR DEFINITIONS =
BEGIN
Assembly: TYPE = SVSceneTypes.Assembly;
BoundBox: TYPE = SVBasicTypes.BoundBox;
Camera: TYPE = SVModelTypes.Camera;
Classification: TYPE = SVRayTypes.Classification;
Color: TYPE = Imager.Color;
Composite: TYPE = SVRayTypes.Composite;
CoordSystem: TYPE = SVModelTypes.CoordSystem;
FeedbackData: TYPE = AtomButtonsTypes.FeedbackData;
LightSourceList: TYPE = SVModelTypes.LightSourceList;
Matrix4by4: TYPE = SV3d.Matrix4by4;
Point2d: TYPE = SV2d.Point2d;
Point3d: TYPE = SV3d.Point3d;
Primitive: TYPE = SVRayTypes.Primitive;
Ray: TYPE = SVRayTypes.Ray;
Vector3d: TYPE = SV3d.Vector3d;
Viewer: TYPE = ViewerClasses.Viewer;
Surface: TYPE = SVRayTypes.Surface; -- REF ANY;
CSGTree: TYPE = SVRayTypes.CSGTree;
maxSceneDepth: NAT = 20;
PointSetOp: TYPE = SVRayTypes.PointSetOp;
{union, intersection, difference}
ParameterArray: TYPE = SVRayTypes.ParameterArray;
SurfaceArray: TYPE = SVRayTypes.SurfaceArray;
InOutArray: TYPE = SVRayTypes.InOutArray;
NormalArray: TYPE = SVRayTypes.NormalArray;
PrimitiveArray: TYPE = SVRayTypes.PrimitiveArray;
Generally Useful Procedures
In CastRaysImplA
DrawTree: PROC [tree: CSGTree, lightSources: LightSourceList, camera: Camera, aisRope: Rope.ROPE, bAndWOnly: BOOL, notify: NotifyOfProgressProc ← NoOpNotifyOfProgress, clientData: REF ANY ← NIL, feedback: FeedbackData] RETURNS [success: BOOL, maxRed, maxGreen, maxBlue, maxBlack: NAT];
The basic ray tracing procedure. Makes a ray tracing of the given CSGTree, according to the specifications in camera. DrawTree calls notify once before starting each line (row) of pixels.
DrawTreeWithStartLine: PROC [startLine: REAL, tree: CSGTree, lightSources: LightSourceList, camera: Camera, aisRope: Rope.ROPE, bAndWOnly: BOOL, notify: NotifyOfProgressProc ← NoOpNotifyOfProgress, clientData: REF ANY ← NIL, feedback: FeedbackData] RETURNS [success: BOOL, maxRed, maxGreen, maxBlue, maxBlack: NAT];
Exactly like DrawTree except that only lines with y>startLine are traced. (Useful mostly for debugging when starting the ray trace from the beginning would be too expensive).
NotifyOfProgressProc: TYPE = PROC [currentY, minX, minY, maxX, maxY: REAL, clientData: REF ANY ← NIL];
NoOpNotifyOfProgress: NotifyOfProgressProc;
DrawTree calls a procedure of this type after finishing each scan line.
SingleRay: PROC [cameraPoint: Point2d, tree: CSGTree, lightSources: LightSourceList, camera: Camera, feedback: FeedbackData, makeStream: BOOL ← FALSE] RETURNS [color: Color];
Cast a single ray at the scene from point [x, y] (in CAMERA coordinates on the z = 0 plane). Report the results to the output stream and find the color at that point.
SingleRay2: PROC [cameraPoint: Point2d, tree: CSGTree, camera: Camera, consolidate: BOOL ← TRUE, feedback: FeedbackData, makeStream: BOOL ← FALSE] RETURNS [class: Classification, rayWorld: Ray];
Cast a single ray at the scene from the given cameraPoint (point in CAMERA coords on the z = 0 plane).
The client must be sure to call CastRays.ReturnClassToPool[class] and CSG.ReturnRayToPool when he is done with these.
The following 4 routines are used along with SingleRay2 to unpack the resulting classification record.
In CastRaysImplB
SortClassByPrimitive: 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.
NthSurfacePointAndNormal: 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.
LastOfFirstPointAndNormal: 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.
LastTopLevelPointAndNormal: PROC [class: Classification, rayWorld: Ray, root: Assembly] 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".
NthAssemblyAndPrimitive: PROC [class: Classification, n: NAT] RETURNS [assembly: Assembly, primitive: Primitive];
Find the nth primitive hit by the ray and its corresponding displaylist assembly.
LastTopLevelAssemAndPrim: PROC [class: Classification, root: Assembly] RETURNS [assembly: Assembly, 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.
RayMeetsZConstantPlane: PROC [localRay: Ray, z: REAL] RETURNS [hitPoint: Point3d, parallel: BOOL];
Returns hitPoint in local coordinates. We assume the ray and the z constant plane are in the same coordinate frame.
RayMeetsPlaneOfCoordSystem: PROC [coordSys: CoordSystem, rayWorld: Ray, whichPlane: NAT, depth: REAL ← 0] RETURNS [pointWorld: Point3d, parallel: BOOL];
Given a ray in camera coordinates, we find its intersection with the x=depth (or y=depth or z=depth) plane of coordSys.
NthHitData: PROC [class: Classification, n: NAT] RETURNS [hitData: REF ANY];
LastOfFirstHitData: PROC [class: Classification] RETURNS [hitData: REF ANY];
LastTopLevelHitData: PROC [class: Classification, root: Assembly] RETURNS [hitData: REF ANY];
Mostly Used Internally
RayCast: PROC [cameraPoint: Point2d, worldRay: Ray, node: REF ANY, consolidate: BOOL ← TRUE, feedback: FeedbackData ← NIL, 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.
RayCastBoundingSpheres: PROC [worldRay: Ray, node: REF ANY, consolidate: BOOL ← TRUE, feedback: FeedbackData ← NIL, makeStream: BOOL ← FALSE, indent: NAT ← 0] RETURNS [class: Classification];
RayCastNoBBoxes: PROC [worldRay: Ray, node: REF ANY, consolidate: BOOL ← TRUE, feedback: FeedbackData ← NIL, makeStream: BOOL ← FALSE, indent: NAT ← 0] RETURNS [class: Classification];
Like RayCast but ignore any bounding boxes which were computed. This is useful if the ray does not originate from the screen (as for computing shadows). Of course, bounding spheres would be useful in this case.
HitsTree: PROC [worldRay: Ray, tree: CSGTree] RETURNS [BOOL];
Reports true if worldRay hits any object in tree (i.e. if any object is visible at this point).
FirstHit: PROC [worldRay: Ray, tree: CSGTree, useBoundSpheres: BOOL, feedback: FeedbackData, makeStream: BOOL ← FALSE, indent: NAT ← 0] RETURNS [hits: BOOL, t: REAL];
Like HitsTree but returns the parameter value at the first hit, if any. First Hit is used by SVFancyRays for shadows (i.e. to determine which light sources are visible).
Pools of Large Records for Recycling.
GetClassFromPool: PROC RETURNS [class: Classification];
ReturnClassToPool: PROC [class: Classification];
MakeClassAMiss: PROC [class: Classification];
Rearranges class to correspond to a complete miss.
Private Procedures (for communication between the several implementation modules)
EmptyClass: PROC RETURNS [class: Classification];
WriteStreamComp: PROC [comp: Composite, class: Classification, feedback: FeedbackData, makeStream: BOOL, indent: NAT];
WriteStreamPrim: PROC [prim: Primitive, class: Classification, feedback: FeedbackData, makeStream: BOOL, indent: NAT];
UnionCombine: PROC [leftClass, rightClass: Classification, consolidate: BOOL] RETURNS [combinedClass: Classification];
IntersectionCombine: PROC [leftClass, rightClass: Classification, consolidate: BOOL] RETURNS [combinedClass: Classification];
DifferenceCombine: PROC [leftClass, rightClass: Classification, consolidate: BOOL] RETURNS [combinedClass: Classification];
END.