DIRECTORY CoordSys, SVRay, Imager, Matrix3d, Rope, SV2d, SV3d, SVBasicTypes, SVBoundBox, SVBoundSphere, SVModelTypes, SVSceneTypes, SVVector3d; SVRayImpl: CEDAR PROGRAM IMPORTS CoordSys, Matrix3d, Rope, SVBoundBox, SVBoundSphere, SVVector3d EXPORTS SVRay, SVSceneTypes = BEGIN BoundBox: TYPE = SVBasicTypes.BoundBox; BoundSphere: TYPE = SVBasicTypes.BoundSphere; 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; StuffCameraRay: PUBLIC PROC [ray: Ray, screenPoint: Point2d, camera: Camera] = { 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 _ 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] = { worldCAMERA: Matrix4by4; realRay: REF RayObj _ NARROW[ray]; realRay.basePt _ realRay.worldBasePt _ basePt; realRay.direction _ realRay.worldDirection _ direction; 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] = { 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] = { 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] = { 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]; 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] = { 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, cameraWORLD]; 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]; 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] = { 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] = { 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] = { 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; }; Init: PROC = { globalRayPool _ NEW[RayPoolObj]; FOR i: NAT IN[1..globalRayPoolCount] DO globalRayPool[i] _ NEW[RayObj]; ENDLOOP; globalRayPoolPointer _ globalRayPoolCount; }; Init[]; END. File: SVRayImpl.mesa Last edited by Bier on June 1, 1987 11:05:42 am 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. 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. 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. 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. Useful for shadow rays which originate in the scene. Assumes basePt and direction are in WORLD coordinates. Includes camera information. Because of slicing, we need to include Camera information. Useful for interaction rays, which are independent of camera and lighting information. Does non include camera information. Useful for shadow rays which originate in the scene. Assumes basePt and directionPt are in WORLD coordinates. Does not include camera information. basePt and direction must be in the frame of localCS. We leave the camera and world parts alone since we wish to use it intact. Exactly like TransformRay except that the ray will remember its WORLD coordinate self even after it is transformed to somewhere else. We leave the camera part alone since we wish to use it intact. We leave the camera and world parts alone since we wish to use it intact. Dispatches to the appropriate one of the three procs below. Dispatches to the appropriate one of the three procs below. 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. Hit testing for bounding spheres. Create a Ray Pool ΚN– "cedar" style˜Iheadšœ™Iprocšœ3™3Lšœ’™’L˜šΟk ˜ Lšœ…˜…—L˜šœ  ˜Lšœ@˜GLšœœ˜—L˜Lš˜˜Lšœ œ˜'Lšœ œ˜-Lšœœ˜#Lšœœœ˜-Lšœœ œ˜9Lšœœ˜Lšœ œ˜-Lšœ œ˜#L˜Lšœ œ˜Lšœ œœ˜#Lšœœ œ˜/Lšœ œ˜L˜Lšœ œΟc%˜QL˜Lšœ œœ˜#Lšœœ˜/L˜Lšœ œœ ˜Lšœ œ˜+L˜Lšœœ˜šΟbΠbkŸ œœ˜Lšœ˜Lšœ˜Lšœ˜Lšœ˜Lšœ˜Lšœ˜Lšœ œœ˜Lšœ œœ˜L˜—Lšœœ˜Lšœœ˜L˜LšŸœœœ ˜LšŸ œœœœ˜7Lšœ˜L˜L˜Lšœπ™πLšœΤ™ΤL˜—šΟnœœœ5˜PLšœJœ’™ςLšœ œ œ˜"LšœL˜LLšœœ˜Lšœœ˜šœ!œ˜)Lšœd˜dL˜—šœž˜!LšœJ˜JL˜—L˜L˜—š‘œœœ5˜YLšœJœ’™ςLšœ œ œ˜"LšœΟuœ ˜Lšœ;˜;šœ!œ˜)LšœP˜PL˜—šœž˜!Lšœ6˜6L˜—Lšœœ˜L˜Lšœ’œ&˜1LšœS’œ˜ZLšœm’œ˜tLšœœ˜L˜—L˜š‘œœœ3˜WLšœ œ œ˜"Lšœ-˜-Lšœ8˜8Lšœœ˜Lšœœ˜L˜L˜—š‘ œœœE˜_LšœZœ+™ŠLšœ’œ ˜Lšœ œ œ˜"Lšœ.˜.šœ7˜7L™:—Lšœ’œO˜ZLšœ4’œ˜—šœœ˜Lšœ/˜/Lšœ5˜5L˜—Lšœœ˜Lšœ+˜+Lšœ1˜1L˜Lšœ-˜-Lšœž˜ L™—š‘œœœœ˜RLšœœ˜ Lšœ˜Lšœ œ ˜Lšœ œ˜Lšœ9˜9šœP˜PL™I—šœœ˜Lšœ/˜/Lšœ5˜5L˜—šœœ˜Lšœ-˜-Lšœ3˜3L˜—Lšœ-˜-Lšœ+˜+Lšœž˜—L˜š‘œœœž˜=Lšœœ˜Lšœœ˜Lšœœ˜Lšœ:˜:LšœC˜CL˜Lšœœž ˜%šœœœ˜/LšœI˜ILšœR˜RL˜—Lšœœ˜Lšœž˜L˜—š ‘ œœœœž˜dLšœœ˜"Lšœ˜Lšœ œ˜ Lšœœ˜Lšœœ˜Lšœ<˜Lšœ5˜5Lšœ)’œ˜=Lšœ!˜!Lšœ0˜0Lšœ(ž˜>Lšœ(˜.Lšœ˜L˜——L˜š‘œ œœœ˜Všœ ˜Lšœ˜Lšœ(˜(Lšœ$˜$—Lšœœ˜L˜L˜—š‘œ œœœ˜Všœœ˜Lšœœ˜8Lšœ#œ˜FLšœ!œ˜B—Lšœœ˜L˜L˜™!L™—L˜—L˜š‘œœ˜Lšœ™L™Lšœœ ˜ šœœœ˜'Lšœœ ˜Lšœ˜—Lšœ*˜*L˜—L˜˜L˜—L˜Lšœ˜L˜L˜—…—4Pl