[Indigo]<Solidviews>SolidModeler>SVRayImpl.mesa!5

File: SVRayImpl.mesa

Last edited by Bier on September 24, 1987 12:19:43 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

SVCoordSys, SVRay, Imager, SVMatrix3d, Rope, SV2d, SV3d, SVBasicTypes, SVBoundBox, SVBoundSphere, SVModelTypes, SVSceneTypes, SVVector3d;

SVRayImpl: CEDAR PROGRAM

IMPORTS SVCoordSys, SVMatrix3d, Rope, SVBoundBox, SVBoundSphere, SVVector3d

EXPORTS SVRay, SVSceneTypes =

BEGIN

BoundBox: TYPE = SVBasicTypes.BoundBox;

Sphere: TYPE = SV3d.Sphere;

Camera: TYPE = SVModelTypes.Camera;

Classification: TYPE = REF ClassificationObj;

ClassificationObj: TYPE = SVSceneTypes.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 = SVSceneTypes.PrimitiveObj;

Vector3d: TYPE = SV3d.Vector3d;

PointSetOp: TYPE = SVSceneTypes.PointSetOp; -- {union, intersection, difference};

Composite: TYPE = REF CompositeObj;

CompositeObj: TYPE = SVSceneTypes.CompositeObj;

CSGTree: TYPE = REF CSGTreeObj;

CSGTreeObj: TYPE = SVSceneTypes.CSGTreeObj;

Ray: TYPE = SVSceneTypes.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] = {

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 ← SVCoordSys.WRTWorld[camera.coordSys];

realRay.basePt ← realRay.worldBasePt ← SVMatrix3d.Update[realRay.cameraBasePt, cameraWorld];

realRay.direction ← realRay.worldDirection ← SVMatrix3d.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 ← SVCoordSys.FindAInTermsOfB[SVCoordSys.Parent[camera.coordSys], camera.coordSys];

realRay.cameraBasePt ← SVMatrix3d.Update[basePt, worldCAMERA];

realRay.cameraDirection ← SVMatrix3d.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 ← SVMatrix3d.Update[realRay.basePt, mat];

realNewRay.direction ← SVMatrix3d.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, cameraWORLD: 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 ← SVMatrix3d.Update[realRay.basePt, cameraWORLD];

realNewRay.direction ← SVMatrix3d.UpdateVectorEvenScaling[realRay.direction, cameraWORLD];

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 ← SVMatrix3d.Update[realRay.basePt, mat];

realNewRay.direction ← SVMatrix3d.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: Sphere, op: PointSetOp] RETURNS [newBS: Sphere] = {

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: Sphere] 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;

};

Init[];

END.