DIRECTORY CoordSys, SVGraphics, Matrix3d, RealFns, Imager, SV3d, SVBasicTypes, SVBoundBox, SVBoundSphere, SVModelTypes, SVPolygon3d, SVRayTypes, SVVector3d; SVBoundSphereImpl: CEDAR PROGRAM IMPORTS CoordSys, SVGraphics, Matrix3d, RealFns, SVBoundBox, SVPolygon3d, SVVector3d EXPORTS SVBoundSphere = BEGIN BoundHedron: TYPE = SVBasicTypes.BoundHedron; BoundSphere: TYPE = REF BoundSphereObj; BoundSphereObj: TYPE = SVBasicTypes.BoundSphereObj; Camera: TYPE = SVModelTypes.Camera; CoordSystem: TYPE = SVModelTypes.CoordSystem; Matrix4by4: TYPE = SV3d.Matrix4by4; Point3d: TYPE = SV3d.Point3d; Poly3d: TYPE = SV3d.Poly3d; Ray: TYPE = SVRayTypes.Ray; Vector3d: TYPE = SV3d.Vector3d; gCirclePolygon: Poly3d; PI: REAL = 3.14159265358979; Init: PROC [] = { gCirclePolygon _ PolyOnUnitCircle[20]; }; PolyOnUnitCircle: PROC [edges: NAT] RETURNS [poly: Poly3d] ~ { theta: REAL _ 0.0; realEdges: REAL _ edges; delta: REAL _ 2.0*PI/realEdges; x, y: REAL; poly _ SVPolygon3d.CreatePoly[edges]; FOR i: NAT IN [0..edges) DO x _ RealFns.Sin[theta]; y _ RealFns.Cos[theta]; poly _ SVPolygon3d.AddPolyPoint[poly, [x, y, 0]]; theta _ theta + delta; ENDLOOP; }; CopyBoundSphere: PUBLIC PROC [boundSphere: BoundSphere] RETURNS [newBS: BoundSphere] = { newBS _ NEW[BoundSphereObj _ [ boundSphere.center, boundSphere.radius, boundSphere.radiusSquared]]; }; BoundSphereFromBoundHedron: PUBLIC PROC [bh: BoundHedron, worldCS: CoordSystem, localCS: CoordSystem] RETURNS [boundSphere: BoundSphere] = { cmWORLD, bhPtWORLD, cmlocal: Point3d; maxIndex: NAT; maxDistSquared, distSquared, radius: REAL; localWorld: Matrix4by4 _ CoordSys.WRTWorld[localCS]; IF bh = NIL THEN {boundSphere _ NIL; RETURN}; cmlocal _ SVBoundBox.CenterOfMassBoundHedron[bh]; cmWORLD _ Matrix3d.Update[cmlocal, localWorld]; maxIndex _ 0; bhPtWORLD _ Matrix3d.Update[bh[0], localWorld]; maxDistSquared _ SVVector3d.MagnitudeSquared[SVVector3d.Sub[cmWORLD, bhPtWORLD]]; FOR i: NAT IN[1..bh.len) DO bhPtWORLD _ Matrix3d.Update[bh[i], localWorld]; distSquared _ SVVector3d.MagnitudeSquared[SVVector3d.Sub[cmWORLD, bhPtWORLD]]; IF distSquared > maxDistSquared THEN { maxIndex _ i; maxDistSquared _ distSquared; }; ENDLOOP; radius _ RealFns.SqRt[maxDistSquared]; boundSphere _ NEW[BoundSphereObj _ [center: cmWORLD, radius: radius, radiusSquared: radius*radius]]; }; BoundSphereFromValues: PUBLIC PROC [centerWORLD: Point3d, radius: REAL] RETURNS [boundSphere: BoundSphere] = { boundSphere _ NEW[BoundSphereObj _ [centerWORLD, radius, radius*radius]]; }; UnionCombineBoundSpheres: PUBLIC PROC [bs1, bs2: BoundSphere] RETURNS [newBS: BoundSphere] = { d, unitD: Vector3d; almostZero: REAL _ 1.0e-12; magD: REAL; IF bs1 = NIL OR bs2 = NIL THEN {newBS _ NIL; RETURN}; d _ SVVector3d.Sub[bs2.center, bs1.center]; magD _ SVVector3d.Magnitude[d]; IF bs1.radius > bs2.radius THEN { IF bs1.radius - magD >= bs2.radius THEN {newBS _ CopyBoundSphere[bs1]; RETURN}; } ELSE { IF bs2.radius - magD >= bs1.radius THEN {newBS _ CopyBoundSphere[bs2]; RETURN}; }; IF ABS[magD] < almostZero THEN { IF bs1.radius > bs2.radius THEN {newBS _ CopyBoundSphere[bs1]; RETURN} ELSE {newBS _ CopyBoundSphere[bs2]; RETURN} }; newBS _ NEW[BoundSphereObj]; unitD _ SVVector3d.Scale[d, 1.0/magD]; newBS.radius _ (bs1.radius + magD + bs2.radius)/2.0; newBS.radiusSquared _ newBS.radius*newBS.radius; newBS.center _ SVVector3d.Add[bs1.center, bs2.center]; newBS.center _ SVVector3d.Add[newBS.center, SVVector3d.Scale[unitD, bs2.radius - bs1.radius]]; newBS.center _ SVVector3d.Scale[newBS.center, 0.5]; }; IntersectionCombineBoundSpheres: PUBLIC PROC [bs1, bs2: BoundSphere] RETURNS [newBS: BoundSphere] = { c, cSquared, x, y: REAL; o2minuso1: Vector3d; IF bs1 = NIL AND bs2 = NIL THEN {newBS _ NIL; RETURN}; IF bs1 = NIL THEN {newBS _ CopyBoundSphere[bs2]; RETURN}; IF bs2 = NIL THEN {newBS _ CopyBoundSphere[bs1]; RETURN}; o2minuso1 _ SVVector3d.Sub[bs2.center, bs1.center]; cSquared _ SVVector3d.MagnitudeSquared[o2minuso1]; c _ RealFns.SqRt[cSquared]; IF c > (bs1.radius + bs2.radius) THEN { -- No intersection. Return a radius zero sphere. newBS _ NEW[BoundSphereObj]; newBS.center _ bs1.center; newBS.radius _ 0.0; newBS.radiusSquared _ 0.0; RETURN; }; IF (c + bs1.radius) < bs2.radius THEN { -- bs1 is contained in bs2 newBS _ CopyBoundSphere[bs1]; RETURN; }; IF (c + bs2.radius) < bs1.radius THEN { -- bs2 is contained in bs1 newBS _ CopyBoundSphere[bs2]; }; newBS _ NEW[BoundSphereObj]; x _ (bs1.radiusSquared - bs2.radiusSquared + cSquared)/(2.0*c); y _ RealFns.SqRt[bs1.radiusSquared - x*x]; newBS.center _ SVVector3d.Add[SVVector3d.Scale[o2minuso1, x/c], bs1.center]; newBS.radius _ y; newBS.radiusSquared _ y*y; }; DifferenceCombineBoundSpheres: PUBLIC PROC [bs1, bs2: BoundSphere] RETURNS [newBS: BoundSphere] = { IF bs1 = NIL THEN {newBS _ NIL; RETURN}; newBS _ CopyBoundSphere[bs1]; }; DrawBoundSphere: PUBLIC PROC [dc: Imager.Context, boundSphere: BoundSphere, camera: Camera] = { circleMat, unitCircleMat: Matrix4by4; circlePoly: Poly3d; rad: REAL; centerToEyepoint: Vector3d; centerCAMERA: Point3d; worldCS: CoordSystem; eyepointCAMERA: Point3d _ [0, 0, camera.focalLength]; IF boundSphere = NIL THEN RETURN; rad _ boundSphere.radius; worldCS _ CoordSys.Parent[camera.coordSys]; centerCAMERA _ CoordSys.FromCSToCS[boundSphere.center, worldCS, camera.coordSys]; centerToEyepoint _ SVVector3d.VectorFromPoints[centerCAMERA, eyepointCAMERA]; unitCircleMat _ MakeAlignedMat[centerToEyepoint, centerCAMERA]; circleMat _ Matrix3d.LocalScale[unitCircleMat, rad, rad, rad]; circlePoly _ SVPolygon3d.TransformByMat[gCirclePolygon, circleMat]; SVGraphics.DrawPolygonAbsolute[dc, circlePoly, 1, butt, camera]; }; MakeAlignedMat: PRIVATE PROC [zaxis: Vector3d, origin: Point3d] RETURNS [mat: Matrix4by4] = { xAxis: Vector3d; yAxisOfCamera: Vector3d _ [0,1,0]; IF SVVector3d.Parallel[yAxisOfCamera, zaxis] THEN xAxis _ [1,0,0] ELSE xAxis _ SVVector3d.CrossProduct[yAxisOfCamera, zaxis]; mat _ Matrix3d.MakeMatFromZandXAxis[zaxis, xAxis, origin]; }; Init[]; END. –File: SVBoundSphereImpl.mesa Last edited by: Eric Bier on May 4, 1987 11:36:29 pm PDT Copyright c 1984 by Xerox Corporation. All rights reserved. Contents: Computes a sphere which is guaranteed to bound a given polyhedron. Implements operations on such spheres. Generate a regular polygon whose vertices sit on the unit circle, centered on the origin, in the z=0 plane. For now we just use a simple heuristic. Use the center of mass as the center of the sphere. Use the distance from this center to the farthest point as the radius. Remember to convert all coordinates to WORLD. A sphere which contains bs1 and bs2 will have diameter r1 + ||c2-c1|| +r2 (or 2r1 if bs1 completely contains bs2 and vice-versa). One diameter will contain the points c1-r1d and c2+r2d where d is the unit vector in the c2-c1 direction. Hence, the center is at (c1-r1d + c2+r2d)/2 = (c1 + c2 + (r2-r1)d)/2. If one sphere contains the other, handle as a special case and RETURN There is a problem if the two spheres are almost identical. Normal case. Pretend that bs1 is centered on [0,0] and bs2 on [c,0] then they intersect, if at all, at the points [x, +-SqRt[r2 - x2]], where x = (r2-R2+c2)/2c. Hence, for general bs1 and bs2, their intersection is bounded by the sphere centered at (x/c)(bs1.center-bs2.center) + bs1.center, with radius SqRt[r2 - x2]. For most cases, just use the first (positive) sphere. It is hard to do any better than this. Find a coordinate system S whose z-axis points from sphere center to eyepoint, origin on the sphere center and zy plane containing the y-axis of CAMERA. We describe S in terms of CAMERA coordinates. Scale SCAMERA by the radius of the boundSphere and draw absolutely (since all points are already in CAMERA coords). Create a Matrix4by4 with origin at origin whose z axis is parallel to zaxis and whose x axis is orthogonal to both zaxis and the y axis of the reference coordinate frame (CAMERA). Κ<˜Ihead™Jšœ8™8Jšœ Οmœ1™L™kJšœžœ˜Jšœ žœ ˜Jšœžœžœ ˜Jšœžœ˜ Jšœ%˜%šžœžœžœ ž˜J˜J˜Jšœ1˜1Jšœ˜—Jšžœ˜J˜J˜—šŸœžœžœžœ˜Xšœžœ˜Lšœ˜Lšœ˜Lšœ˜—L˜L˜—L˜šŸœžœžœ?žœ˜ŒLšœΤ™ΤLšœΟuœ œ œ ˜%Lšœ žœ˜Lšœ%žœ˜*Jšœ œ*˜4L˜Lš žœžœžœžœžœ˜-Lšœ œ*˜1Lšœ œ œ œ˜/L˜ Lšœ œ œ˜/Lšœ> œ œ˜Qšžœžœžœ ž˜Lšœ œ œ˜/Lšœ; œ œ˜Nšžœžœ˜&L˜ Lšœ˜L˜——Lšžœ˜Lšœ&˜&šœžœ˜"Lšœ  œ1˜A—Lšœ˜—š Ÿœžœžœ œžœžœ˜nLšœžœ œ˜ILšœ˜—L˜šŸœžœžœžœ˜^Lš œ­Οbœ ‘œ‘œK‘œ‘œ‘œ™³L˜Lšœ žœ ˜Lšœžœ˜ L˜Lšžœžœžœžœžœ žœžœ˜5Lšœ+˜+šœ˜L™E—šžœžœ˜!Lšžœ!žœ žœ˜O—šœžœ˜Lšžœ!žœ žœ˜O—˜L™;—šžœžœžœ˜ Lšžœžœ žœ˜FLšžœ žœ˜+L˜L˜L™ —Lšœžœ˜Lšœ&˜&Lšœ4˜4Lšœ0˜0Lšœ6˜6Lšœ^˜^Lšœ3˜3Lšœ˜L˜—šŸœžœžœžœ˜eLšœq œ œ œ œ œœ œ œ™²Lšœžœ˜L˜Lšžœžœžœžœžœ žœžœ˜6Lšœ žœžœ žœ˜9Lšœ žœžœ žœ˜9Lšœ3˜3Lšœ2˜2Lšœ˜šœ!žœ3˜XLšœžœ˜Lšœ˜Lšœ˜Lšœ˜Lšžœ˜L˜—šœB˜BLšœžœ˜%L˜—šœB˜BLšœ˜L˜—Lšœžœ˜Lšœ?˜?Lšœ*˜*LšœL˜LLšœ˜Lšœ˜Lšœ˜L˜—šŸœžœžœžœ˜cLšœ]™]Lš žœžœžœ žœžœ˜(Lšœ˜Lšœ˜—L˜šŸœžœžœC˜_LšœΠ œf™ΌJšœ%˜%Jšœ˜Jšœž˜ Jšœ˜Jšœ œ ˜J˜Jšœ œ'˜5J˜Jšžœžœžœžœ˜!Jšœ˜Jšœ+˜+Jšœ œE˜QJšœ5 œ  œ˜MJšœ7 œ˜?Jšœ>˜>LšœC˜CLšœ@˜@Lšœ˜L˜—šŸœžœžœ$žœ˜]šœ³™³Jšœ˜Jšœ"˜"Jšžœ+žœ˜AJšžœ7˜;Jšœ:˜:Jšœ˜—L˜L˜L˜—J˜Jšžœ˜—…—p&B