File: SVRayImpl.mesa
Last edited by Bier on May 4, 1987 10:57:17 pm PDT
Contents: The csg Solids Interface. Essentially maintains a database of csg trees each of which contains one or more combined primitives. Maintaining a tree involves creating primitives and adding them to trees with the csg operations, intersection, union, and difference.
DIRECTORY
CoordSys, SVRay, Imager, Matrix3d, Rope, SV2d, SV3d, SVBasicTypes, SVBoundBox, SVBoundSphere, SVModelTypes, SVRayTypes, SVVector3d;
SVRayImpl:
CEDAR PROGRAM
IMPORTS CoordSys, Matrix3d, Rope, SVBoundBox, SVBoundSphere, SVVector3d
EXPORTS SVRay, SVRayTypes =
BEGIN
BoundBox: TYPE = SVBasicTypes.BoundBox;
BoundSphere: TYPE = SVBasicTypes.BoundSphere;
Camera: TYPE = SVModelTypes.Camera;
Classification: TYPE = REF ClassificationObj;
ClassificationObj: TYPE = SVRayTypes.ClassificationObj;
Color: TYPE = Imager.Color;
CoordSystem: TYPE = SVModelTypes.CoordSystem;
Matrix4by4: TYPE = SV3d.Matrix4by4;
Point2d: TYPE = SV2d.Point2d;
Point3d: TYPE = SV3d.Point3d;
Primitive: TYPE = REF PrimitiveObj;
PrimitiveObj: TYPE = SVRayTypes.PrimitiveObj;
Vector3d: TYPE = SV3d.Vector3d;
PointSetOp: TYPE = SVRayTypes.PointSetOp; -- {union, intersection, difference};
Composite: TYPE = REF CompositeObj;
CompositeObj: TYPE = SVRayTypes.CompositeObj;
CSGTree: TYPE = REF CSGTreeObj;
CSGTreeObj: TYPE = SVRayTypes.CSGTreeObj;
Ray: TYPE = SVRayTypes.Ray;
RayObj:
PUBLIC
TYPE =
RECORD [
basePt: Point3d,
direction: Vector3d,
cameraBasePt: Point3d,
cameraDirection: Vector3d,
worldBasePt: Point3d,
worldDirection: Point3d,
cameraValid: BOOL ← FALSE,
worldValid: BOOL ← FALSE];
globalRayPoolCount: NAT = 15;
globalRayPoolPointer: NAT;
RayPool: TYPE = REF RayPoolObj;
RayPoolObj: TYPE = ARRAY[1..globalRayPoolCount] OF Ray;
globalRayPool: RayPool;
In my current plan, all of the instances of each surface type will refer to the same underlying csg surface expressed in the instance (unit dimensions) coordinate system. Hence, I will build these primitve shapes into the code (this more or less must be done anyway because the formulas - x^2 + y^2 = R^2; z = constant, etc. - are hard to enter symbolically in Mesa).
However, for rapid rendering, I will have a line-drawing approximation to each world surface. These will involve a sweep-based representation with a finite mesh (translational sweep for blocks, rotational for cylinders and spheres). I will create one such representation for each of the primitive solid types in the same instance coordinate system in which the exact csg reps are defined. Rendering line-drawings with the sweep reps will then involve, using the same matrix transforms as are used to place the csg shapes, followed by a perspective transform and a call to 2d graphics routines.
StuffCameraRay:
PUBLIC
PROC [ray: Ray, screenPoint: Point2d, camera: Camera] = {
Creates a ray which passes through screenPoint. screenPoint should be in CAMERA coordinates. If camera.projection = orthogonal, the ray is perpendicular to the screen. If camera.projection = perspective, the ray has the same direction [eyepoint, screenPoint]. In any case, the ray originates from screenPoint (not, alas, eyepoint) and has "length" camera.focalLength.
realRay: REF RayObj ← NARROW[ray];
realRay.basePt ← realRay.cameraBasePt ← [screenPoint[1], screenPoint[2], 0];
realRay.cameraValid ← TRUE;
realRay.worldValid ← FALSE;
IF camera.projection = perspective
THEN {
realRay.direction ← realRay.cameraDirection ← [screenPoint[1], screenPoint[2], -camera.focalLength];
}
ELSE {
-- orthographic projection
realRay.direction ← realRay.cameraDirection ← [0, 0, -camera.focalLength];
};
};
StuffWorldRayFromCamera:
PUBLIC
PROC [ray: Ray, screenPoint: Point2d, camera: Camera] = {
Creates a ray which passes through screenPoint. screenPoint should be in CAMERA coordinates. If camera.projection = orthogonal, the ray is perpendicular to the screen. If camera.projection = perspective, the ray has the same direction [eyepoint, screenPoint]. In any case, the ray originates from screenPoint (not, alas, eyepoint) and has "length" camera.focalLength.
realRay: REF RayObj ← NARROW[ray];
cameraWorld: Matrix4by4;
realRay.cameraBasePt ← [screenPoint[1], screenPoint[2], 0];
IF camera.projection = perspective
THEN {
realRay.cameraDirection ← [screenPoint[1], screenPoint[2], -camera.focalLength];
}
ELSE {
-- orthographic projection
realRay.cameraDirection ← [0, 0, -camera.focalLength];
};
realRay.cameraValid ← TRUE;
cameraWorld ← CoordSys.WRTWorld[camera.coordSys];
realRay.basePt ← realRay.worldBasePt ← Matrix3d.Update[realRay.cameraBasePt, cameraWorld];
realRay.direction ← realRay.worldDirection ← Matrix3d.UpdateVectorEvenScaling[realRay.cameraDirection, cameraWorld];
realRay.worldValid ← TRUE;
};
StuffCameraRayLiterally:
PUBLIC
PROC [ray: Ray, base: Point3d, direction: Vector3d] = {
realRay: REF RayObj ← NARROW[ray];
realRay.basePt ← realRay.cameraBasePt ← base;
realRay.direction ← realRay.cameraDirection ← direction;
realRay.cameraValid ← TRUE;
realRay.worldValid ← FALSE;
};
StuffWorldRay:
PUBLIC
PROC [ray: Ray, basePt: Point3d, direction: Vector3d, camera: Camera] = {
Useful for shadow rays which originate in the scene. Assumes basePt and direction are in WORLD coordinates. Includes camera information.
worldCAMERA: Matrix4by4;
realRay: REF RayObj ← NARROW[ray];
realRay.basePt ← realRay.worldBasePt ← basePt;
realRay.direction ← realRay.worldDirection ← direction;
Because of slicing, we need to include Camera information.
worldCAMERA ← CoordSys.FindAInTermsOfB[CoordSys.Parent[camera.coordSys], camera.coordSys];
realRay.cameraBasePt ← Matrix3d.Update[basePt, worldCAMERA];
realRay.cameraDirection ← Matrix3d.UpdateVectorEvenScaling[direction, worldCAMERA];
realRay.cameraValid ← TRUE;
realRay.worldValid ← TRUE;
};
StuffWorldOnlyRay:
PUBLIC
PROC [ray: Ray, basePt: Point3d, direction: Vector3d] = {
Useful for interaction rays, which are independent of camera and lighting information. Does non include camera information.
realRay: REF RayObj ← NARROW[ray];
realRay.basePt ← realRay.worldBasePt ← basePt;
realRay.direction ← realRay.worldDirection ← direction;
realRay.cameraValid ← FALSE;
realRay.worldValid ← TRUE;
};
StuffWorldRayFromPoints:
PUBLIC
PROC [ray: Ray, basePt: Point3d, directionPt: Point3d] = {
Useful for shadow rays which originate in the scene. Assumes basePt and directionPt are in WORLD coordinates. Does not include camera information.
realRay: REF RayObj ← NARROW[ray];
direction: Vector3d ← SVVector3d.Sub[directionPt, basePt];
realRay.basePt ← realRay.worldBasePt ← basePt;
realRay.direction ← realRay.worldDirection ← direction;
realRay.cameraValid ← FALSE;
realRay.worldValid ← TRUE;
};
StuffLocalRay:
PUBLIC
PROC [ray: Ray, basePt: Point3d, direction: Vector3d, camera: Camera, localCS: CoordSystem] = {
basePt and direction must be in the frame of localCS.
realRay: REF RayObj ← NARROW[ray];
realRay.basePt ← basePt;
realRay.direction ← direction;
realRay.cameraValid ← FALSE;
realRay.worldValid ← FALSE;
};
EvaluateWorldRay:
PUBLIC
PROC [ray: Ray, t:
REAL]
RETURNS [pt: Point3d] = {
realRay: REF RayObj ← NARROW[ray];
p: Point3d;
d: Vector3d;
IF NOT realRay.worldValid THEN ERROR;
p ← realRay.worldBasePt;
d ← realRay.worldDirection;
pt[1] ← p[1] + t*d[1];
pt[2] ← p[2] + t*d[2];
pt[3] ← p[3] + t*d[3];
};
EvaluateCameraRay:
PUBLIC
PROC [ray: Ray, t:
REAL]
RETURNS [pt: Point3d] = {
realRay: REF RayObj ← NARROW[ray];
p: Point3d;
d: Vector3d;
IF NOT realRay.cameraValid THEN ERROR;
p ← realRay.cameraBasePt;
d ← realRay.cameraDirection;
pt[1] ← p[1] + t*d[1];
pt[2] ← p[2] + t*d[2];
pt[3] ← p[3] + t*d[3];
};
EvaluateLocalRay:
PUBLIC
PROC [ray: Ray, t:
REAL]
RETURNS [pt: Point3d] = {
realRay: REF RayObj ← NARROW[ray];
p: Point3d;
d: Vector3d;
p ← realRay.basePt;
d ← realRay.direction;
pt[1] ← p[1] + t*d[1];
pt[2] ← p[2] + t*d[2];
pt[3] ← p[3] + t*d[3];
};
EvaluateLocalRay2:
PUBLIC
PROC [ray: Ray, t:
REAL]
RETURNS [x, y, z:
REAL] = {
realRay: REF RayObj ← NARROW[ray];
p: Point3d;
d: Vector3d;
p ← realRay.basePt;
d ← realRay.direction;
x ← p[1] + t*d[1];
y ← p[2] + t*d[2];
z ← p[3] + t*d[3];
};
GetCameraRay:
PUBLIC
PROC [ray: Ray]
RETURNS [basePt: Point3d, direction: Vector3d] = {
realRay: REF RayObj ← NARROW[ray];
IF NOT realRay.cameraValid THEN ERROR;
basePt ← realRay.cameraBasePt;
direction ← realRay.cameraDirection;
};
GetWorldRay:
PUBLIC
PROC [ray: Ray]
RETURNS [basePt: Point3d, direction: Vector3d] = {
realRay: REF RayObj ← NARROW[ray];
IF NOT realRay.worldValid THEN ERROR;
basePt ← realRay.worldBasePt;
direction ← realRay.worldDirection;
};
GetLocalRay:
PUBLIC
PROC [ray: Ray]
RETURNS [basePt: Point3d, direction: Vector3d] = {
realRay: REF RayObj ← NARROW[ray];
basePt ← realRay.basePt;
direction ← realRay.direction;
};
CreateRay:
PUBLIC
PROC
RETURNS [ray: Ray] = {
ray ← NEW[RayObj];
};
GetRayFromPool:
PUBLIC
PROC
RETURNS [ray: Ray] = {
IF globalRayPoolPointer = 0 THEN SIGNAL RayPoolEmpty;
ray ← globalRayPool[globalRayPoolPointer];
globalRayPoolPointer ← globalRayPoolPointer -1;
};
RayPoolEmpty: SIGNAL = CODE;
ReturnRayToPool:
PUBLIC
PROC [ray: Ray] = {
IF globalRayPoolPointer = globalRayPoolCount THEN SIGNAL RayPoolFull;
globalRayPoolPointer ← globalRayPoolPointer + 1;
globalRayPool[globalRayPoolPointer] ← ray;
};
RayPoolFull: SIGNAL = CODE;
TransformRay:
PUBLIC
PROC [ray: Ray, mat: Matrix4by4]
RETURNS [newRay: Ray] = {
realRay, realNewRay: REF RayObj;
newRay ← GetRayFromPool[];
realNewRay ← NARROW[newRay];
realRay ← NARROW[ray];
realNewRay.basePt ← Matrix3d.Update[realRay.basePt, mat];
realNewRay.direction ← Matrix3d.UpdateVectorEvenScaling[realRay.direction, mat];
We leave the camera and world parts alone since we wish to use it intact.
IF realRay.cameraValid
THEN {
realNewRay.cameraBasePt ← realRay.cameraBasePt;
realNewRay.cameraDirection ← realRay.cameraDirection;
};
IF realRay.worldValid
THEN {
realNewRay.worldBasePt ← realRay.worldBasePt;
realNewRay.worldDirection ← realRay.worldDirection;
};
realNewRay.cameraValid ← realRay.cameraValid;
realNewRay.worldValid ← realRay.worldValid;
}; -- end of TransformRay
TransformRayToWorld:
PUBLIC
PROC [ray: Ray, camera
WORLD: Matrix4by4]
RETURNS [newRay: Ray] = {
Exactly like TransformRay except that the ray will remember its WORLD coordinate self even after it is transformed to somewhere else.
realRay, realNewRay: REF RayObj;
newRay ← GetRayFromPool[];
realNewRay ← NARROW[newRay];
realRay ← NARROW[ray];
realNewRay.basePt ← Matrix3d.Update[realRay.basePt, cameraWORLD];
realNewRay.direction ← Matrix3d.UpdateVectorEvenScaling[realRay.direction, camera
WORLD];
We leave the camera part alone since we wish to use it intact.
IF realRay.cameraValid
THEN {
realNewRay.cameraBasePt ← realRay.cameraBasePt;
realNewRay.cameraDirection ← realRay.cameraDirection;
};
realNewRay.worldValid ← TRUE;
realNewRay.worldBasePt ← realNewRay.basePt;
realNewRay.worldDirection ← realNewRay.direction;
realNewRay.cameraValid ← realRay.cameraValid;
}; -- end of TransformRayToWorld
TransformNewRay:
PUBLIC
PROC [ray: Ray, mat: Matrix4by4]
RETURNS [newRay: Ray] = {
realRay, realNewRay: REF RayObj;
newRay ← CreateRay[];
realNewRay ← NARROW[newRay];
realRay ← NARROW[ray];
realNewRay.basePt ← Matrix3d.Update[realRay.basePt, mat];
realNewRay.direction ← Matrix3d.UpdateVectorEvenScaling[realRay.direction, mat];
We leave the camera and world parts alone since we wish to use it intact.
IF realRay.cameraValid
THEN {
realNewRay.cameraBasePt ← realRay.cameraBasePt;
realNewRay.cameraDirection ← realRay.cameraDirection;
};
IF realRay.worldValid
THEN {
realNewRay.worldBasePt ← realRay.worldBasePt;
realNewRay.worldDirection ← realRay.worldDirection;
};
realNewRay.cameraValid ← realRay.cameraValid;
realNewRay.worldValid ← realRay.worldValid;
}; -- end of TransformNewRay
AddRay:
PUBLIC
PROC [ray1, ray2: Ray] = {
-- puts sum in ray2
real1, real2: REF RayObj;
real1 ← NARROW[ray1];
real2 ← NARROW[ray2];
real2.basePt ← SVVector3d.Add[real1.basePt, real2.basePt];
real2.direction ← SVVector3d.Add[real1.direction, real2.direction];
real2.cameraValid ← FALSE; -- for now
IF real1.worldValid
AND real2.worldValid
THEN {
real2.worldBasePt ← SVVector3d.Add[real1.worldBasePt, real2.worldBasePt];
real2.worldDirection ← SVVector3d.Add[real1.worldDirection, real2.worldDirection];
}
ELSE real2.worldValid ← FALSE;
}; -- end of AddRay
SubtractRays:
PUBLIC
PROC [ray1, ray2: Ray]
RETURNS [ray1MinusRay2: Ray] = {
-- allocates a new ray.
realRay, real1, real2: REF RayObj;
ray1MinusRay2 ← CreateRay[];
realRay ← NARROW[ray1MinusRay2];
real1 ← NARROW[ray1];
real2 ← NARROW[ray2];
realRay.basePt ← SVVector3d.Sub[real1.basePt, real2.basePt];
realRay.direction ← SVVector3d.Sub[real1.direction, real2.direction];
realRay.cameraValid ← FALSE; -- for now
IF real1.worldValid
AND real2.worldValid
THEN {
realRay.worldBasePt ← SVVector3d.Sub[real1.worldBasePt, real2.worldBasePt];
realRay.worldDirection ← SVVector3d.Sub[real1.worldDirection, real2.worldDirection];
realRay.worldValid ← TRUE;
}
ELSE realRay.worldValid ← FALSE;
}; -- end of SubtractRays
CopyClass:
PUBLIC
PROC [class: Classification]
RETURNS [copy: Classification] = {
copy ← NEW[ClassificationObj];
copy.count ← class.count;
copy.params ← class.params;
copy.surfaces ← class.surfaces;
copy.primitives ← class.primitives;
copy.classifs ← class.classifs;
copy.normals ← class.normals;
};
MakeCompositeCell:
PUBLIC
PROC [name: Rope.
ROPE, operation: PointSetOp, LeftSolidPtr:
REF
ANY, RightSolidPtr:
REF
ANY]
RETURNS [c: Composite] = {
c ← NEW[CompositeObj ← [name, operation, LeftSolidPtr, RightSolidPtr, NIL, NIL]];
};
MakeCSGTree:
PUBLIC
PROC [son:
REF
ANY, backgroundColor: Color, shadows:
BOOL]
RETURNS [tree: CSGTree] = {
name: Rope.ROPE;
IF son = NIL THEN name ← "Empty Scene"
ELSE {
WITH son
SELECT
FROM
prim: Primitive => name ← prim.name;
comp: Composite => name ← comp.name;
ENDCASE => ERROR;
};
tree ← NEW[CSGTreeObj ← [name, TRUE, son, backgroundColor, shadows]];
};
CombineBoundBoxes:
PUBLIC
PROC [bb1, bb2: BoundBox, op: PointSetOp]
RETURNS [newBB: BoundBox] = {
Dispatches to the appropriate one of the three procs below.
SELECT op
FROM
union => newBB ← SVBoundBox.UnionCombineBoundBoxes[bb1, bb2];
intersection => newBB ← SVBoundBox.IntersectionCombineBoundBoxes[bb1, bb2];
difference => newBB ← SVBoundBox.DifferenceCombineBoundBoxes[bb1, bb2];
ENDCASE => ERROR;
};
CombineBoundSpheres:
PUBLIC
PROC [bs1, bs2: BoundSphere, op: PointSetOp]
RETURNS [newBS: BoundSphere] = {
Dispatches to the appropriate one of the three procs below.
SELECT op
FROM
union => newBS ← SVBoundSphere.UnionCombineBoundSpheres[bs1, bs2];
intersection => newBS ← SVBoundSphere.IntersectionCombineBoundSpheres[bs1, bs2];
difference => newBS ← SVBoundSphere.DifferenceCombineBoundSpheres[bs1, bs2];
ENDCASE => ERROR;
};
RayHitsBoundSphere:
PUBLIC
PROC [worldRay: Ray, boundSphere: BoundSphere]
RETURNS [
BOOL] = {
One could just use the ray-sphere intersection test, but we only need to know IF the ray hits, not where. So instead, we compute the distance from the center of the sphere to the ray and compare with the radius of the sphere.
magRaySquared, dotProd, dotProdSquared, rCosThetaSquared, dSquared, rSquared: REAL;
vecToCenter: Vector3d;
basePtWORLD: Point3d;
directionWORLD: Vector3d;
IF boundSphere = NIL THEN RETURN[TRUE]; -- NIL is used to represent an infinite bounding sphere
[basePtWORLD, directionWORLD] ← GetWorldRay[worldRay];
magRaySquared ← SVVector3d.MagnitudeSquared[directionWORLD];
vecToCenter ← SVVector3d.Sub[boundSphere.center, basePtWORLD];
rSquared ← SVVector3d.MagnitudeSquared[vecToCenter];
dotProd ← SVVector3d.DotProduct[directionWORLD, vecToCenter];
dotProdSquared ← dotProd*dotProd;
rCosThetaSquared ← dotProdSquared/magRaySquared;
dSquared ← rSquared - rCosThetaSquared; -- Pythagorean Theorem
RETURN[dSquared <= boundSphere.radiusSquared];
};
PointSetOpToRope:
PUBLIC PROC [pointSetOp: PointSetOp]
RETURNS [opRope: Rope.
ROPE] = {
SELECT pointSetOp
FROM
union => opRope ← "union";
intersection => opRope ← "intersection";
difference => opRope ← "difference";
ENDCASE => ERROR;
};
RopeToPointSetOp:
PUBLIC PROC [opRope: Rope.
ROPE]
RETURNS [pointSetOp: PointSetOp] = {
SELECT
TRUE
FROM
Rope.Equal[opRope, "union", TRUE] => pointSetOp ← union;
Rope.Equal[opRope, "intersection", TRUE] => pointSetOp ← intersection;
Rope.Equal[opRope, "difference", TRUE] => pointSetOp ← difference;
ENDCASE => ERROR;
};
Hit testing for bounding spheres.
Init:
PROC = {
Create a Ray Pool
globalRayPool ← NEW[RayPoolObj];
FOR i:
NAT
IN[1..globalRayPoolCount]
DO
globalRayPool[i] ← NEW[RayObj];
ENDLOOP;
globalRayPoolPointer ← globalRayPoolCount;
};
END.