DIRECTORY
CoordSys,
CSGGraphics,
Graphics,
GraphicsColor,
SV2d,
SV3d,
SVBoundBox,
SVModelTypes,
SVPolygon3d,
SVRayTypes,
SVVector3d;

SVBoundBoxImpl: PROGRAM
IMPORTS CoordSys, CSGGraphics, Graphics, SVPolygon3d, SVVector3d
EXPORTS SVBoundBox =
BEGIN

Camera: TYPE = SVModelTypes.Camera;
CoordSystem: TYPE = SVModelTypes.CoordSystem;
Point2d: TYPE = SV2d.Point2d;
Point3d: TYPE = SV3d.Point3d;
PointSetOp: TYPE = SVRayTypes.PointSetOp;
Poly3d: TYPE = SV3d.Poly3d;
Vector: TYPE = SV3d.Vector;

BoundHedron: TYPE = REF BoundHedronObj;
BoundHedronObj: TYPE = SVModelTypes.BoundHedronObj;

BoundBox: TYPE = REF BoundBoxObj;
BoundBoxObj: TYPE = SVModelTypes.BoundBoxObj;
	
CreateBoundHedron: PUBLIC PROC [len: NAT] RETURNS [bh: BoundHedron] = {
bh _ NEW[BoundHedronObj[len]];
bh.len _ 0;
};
AddBoundHedronPoint: PUBLIC PROC [bh: BoundHedron, point: Point3d] = {
IF bh.len = bh.maxVerts THEN ERROR
ELSE {
bh[bh.len] _ point;
bh.len _ bh.len + 1;
};
};	-- end of AddBoundHedronPoint
AddBoundHedronPoly: PUBLIC PROC [bh: BoundHedron, poly: Poly3d] = {
FOR i: NAT IN[0..poly.len) DO
AddBoundHedronPoint[bh, poly[i]];
ENDLOOP;
};
RectangularBoundHedron: PUBLIC PROC [sx, sy, sz: REAL] RETURNS [bh: BoundHedron] = {
sx2, sy2, sz2: REAL;
sx2 _ sx/2;
sy2 _ sy/2;
sz2 _ sz/2;
bh _ CreateBoundHedron[8];
AddBoundHedronPoint[bh, [-sx2, sy2, sz2]];
AddBoundHedronPoint[bh, [-sx2, sy2, -sz2]];
AddBoundHedronPoint[bh, [sx2, sy2, -sz2]];
AddBoundHedronPoint[bh, [sx2, sy2, sz2]];
AddBoundHedronPoint[bh, [-sx2, -sy2, sz2]];
AddBoundHedronPoint[bh, [-sx2, -sy2, -sz2]];
AddBoundHedronPoint[bh, [sx2, -sy2, -sz2]];
AddBoundHedronPoint[bh, [sx2, -sy2, sz2]];
};	-- end of RectangularBoundHedron
RectangularBoundHedron2: PUBLIC PROC [x1, x2, y1, y2, z1, z2: REAL] RETURNS [bh: BoundHedron] = {
bh _ CreateBoundHedron[8];
AddBoundHedronPoint[bh, [x1, y2, z2]];
AddBoundHedronPoint[bh, [x1, y2, z1]];
AddBoundHedronPoint[bh, [x2, y2, z1]];
AddBoundHedronPoint[bh, [x2, y2, z2]];
AddBoundHedronPoint[bh, [x1, y1, z2]];
AddBoundHedronPoint[bh, [x1, y1, z1]];
AddBoundHedronPoint[bh, [x2, y1, z1]];
AddBoundHedronPoint[bh, [x2, y1, z2]];
};	-- end of RectangularBoundHedron2
PyramidBoundHedron: PUBLIC PROC [sx, sy, sz: REAL] RETURNS [bh: BoundHedron] = {
sx2, sz2: REAL;
sx2 _ sx/2;
sz2 _ sz/2;
bh _ CreateBoundHedron[5];
AddBoundHedronPoint[bh, [-sx2, 0, sz2]];
AddBoundHedronPoint[bh, [-sx2, 0, -sz2]];
AddBoundHedronPoint[bh, [sx2, 0, -sz2]];
AddBoundHedronPoint[bh, [sx2, 0, sz2]];
AddBoundHedronPoint[bh, [0, sy, 0]];
};	-- end of PyramidBoundHedron
HexagonalBoundHedron: PUBLIC PROC [r, hOver2: REAL] RETURNS [bh: BoundHedron] = {
topPoly, bottomPoly: Poly3d;
bh _ CreateBoundHedron[12];
topPoly _ SVPolygon3d.CircumHexagon[hOver2, r];
bottomPoly _ SVPolygon3d.CircumHexagon[-hOver2, r];
AddBoundHedronPoly[bh, topPoly];
AddBoundHedronPoly[bh, bottomPoly];
};
HexPyramidBoundHedron: PUBLIC PROC [r, h: REAL] RETURNS [bh: BoundHedron] = {
base: Poly3d;
base _ SVPolygon3d.CircumHexagon[0, r];
bh _ CreateBoundHedron[7];
AddBoundHedronPoly[bh, base];
AddBoundHedronPoint[bh, [0, h, 0]];
};	-- end of HexPyramidBoundHedron
GeneralConeBoundHedron: PUBLIC PROC [r1, h1, r2, h2: REAL] RETURNS [bh: BoundHedron] = {
poly: Poly3d;
bh _ CreateBoundHedron[12];
poly _ SVPolygon3d.CircumHexagon[h1, r1];
AddBoundHedronPoly[bh, poly];
poly _ SVPolygon3d.CircumHexagon[h2, r2];
AddBoundHedronPoly[bh, poly];
};	-- end of GeneralConeBoundHedron
DiskBoundHedron: PUBLIC PROC [r, h: REAL] RETURNS [bh: BoundHedron] = {
poly: Poly3d;
bh _ CreateBoundHedron[6];
poly _ SVPolygon3d.CircumHexagon[h, r];
AddBoundHedronPoly[bh, poly];
};	-- end of DiskBoundHedron
ClearBoundHedron: PUBLIC PROC [bh: BoundHedron] = {
bh.len _ 0;
};
	
DrawBoundHedron: PUBLIC PROC [dc: Graphics.Context, bh: BoundHedron, localWRTWorld: CoordSystem, camera: Camera, screen: CoordSystem] = {
FOR i: NAT IN[0..bh.len) DO
FOR j: NAT IN[0..bh.len) DO
IF i#j THEN {
CSGGraphics.SetCP[dc, bh[i], camera, localWRTWorld];
CSGGraphics.DrawTo[dc, bh[j], camera, localWRTWorld];};
ENDLOOP;
ENDLOOP;
};
	
CenterOfMassBoundHedron: PUBLIC PROC [bh: BoundHedron] RETURNS [cm: Point3d] = {
sum: Vector;
realLen: REAL;
sum _ [0,0,0];
FOR i: NAT IN[0..bh.len) DO
sum _ SVVector3d.Add[sum, bh[i]];
ENDLOOP;
realLen _ bh.len;
cm _ SVVector3d.Scale[sum, 1.0/realLen];
};

BoundBoxFromBoundHedron: PUBLIC PROC [bh: BoundHedron, camera: Camera, localCS: CoordSystem] RETURNS [boundBox: BoundBox] = {
minX, minY, minZ, maxX, maxY, maxZ: REAL;
localPt, cameraPt: Point3d;
projectPt: Point2d;

IF bh = NIL THEN {boundBox _ NIL; RETURN};
boundBox _ NEW[BoundBoxObj];
localPt _ bh[0];
cameraPt _ CSGGraphics.LocalToCamera[localPt, localCS];
projectPt _ CSGGraphics.DoProjection[cameraPt, camera];
minX _ maxX _ projectPt[1];
minY _ maxY _ projectPt[2];
minZ _ maxZ _ cameraPt[3];
FOR i: NAT IN[1..bh.len) DO
localPt _ bh[i];
cameraPt _ CSGGraphics.LocalToCamera[localPt, localCS];
projectPt _ CSGGraphics.DoProjection[cameraPt, camera];
IF projectPt[1] < minX THEN minX _ projectPt[1]
ELSE IF projectPt[1] > maxX THEN maxX _ projectPt[1];
IF projectPt[2] < minY THEN minY _ projectPt[2]
ELSE IF projectPt[2] > maxY THEN maxY _ projectPt[2];
IF cameraPt[3] < minZ THEN minZ _ cameraPt[3]
ELSE IF cameraPt[3] > maxZ THEN maxZ _ cameraPt[3];
ENDLOOP;
boundBox.minVert[1] _ minX;
boundBox.minVert[2] _ minY;
boundBox.minVert[3] _ minZ;
boundBox.maxVert[1] _ maxX;
boundBox.maxVert[2] _ maxY;
boundBox.maxVert[3] _ maxZ;
};	-- end of BoundBoxFromBoundHedron
BoundBoxFromValues: PUBLIC PROC [minX, minY, maxX, maxY: REAL] RETURNS [boundBox: BoundBox] = {
boundBox _ NEW[BoundBoxObj];
boundBox.minVert[1] _ minX;
boundBox.minVert[2] _ minY;
boundBox.minVert[3] _ 0;
boundBox.maxVert[1] _ maxX;
boundBox.maxVert[2] _ maxY;
boundBox.maxVert[3] _ 0;
};	-- end of BoundBoxFromValues
PointInBoundBox: PUBLIC PROC [cameraPoint: Point2d, boundBox: BoundBox] RETURNS [BOOL] = {
IF boundBox = NIL THEN RETURN[TRUE] -- NIL is used to represent an infinite bounding box
ELSE RETURN[
boundBox.minVert[1] <= cameraPoint[1] AND cameraPoint[1]<=boundBox.maxVert[1]
AND
boundBox.minVert[2] <= cameraPoint[2] AND cameraPoint[2]<=boundBox.maxVert[2]]
};	-- end of PointInBoundBox

UnionCombineBoundBoxes: PUBLIC PROC [bb1, bb2: BoundBox] RETURNS [newBB: BoundBox] = {
IF bb1 = NIL OR bb2 = NIL THEN {newBB _ NIL; RETURN};
newBB _ NEW[BoundBoxObj];
FOR i: NAT IN[1..3] DO
newBB.minVert[i] _ bb2.minVert[i];
newBB.minVert[i] _ Min[bb1.minVert[i], bb2.minVert[i]];
newBB.maxVert[i] _ Max[bb1.maxVert[i], bb2.maxVert[i]];
ENDLOOP;
};	-- end of UnionCombineBoundBoxes
IntersectionCombineBoundBoxes: PUBLIC PROC [bb1, bb2: BoundBox] RETURNS [newBB: BoundBox] = {
IF bb1 = NIL AND bb2 = NIL THEN {newBB _ NIL; RETURN};
newBB _ NEW[BoundBoxObj];
FOR i: NAT IN[1..3] DO
SELECT TRUE FROM
bb1 = NIL => {
newBB.minVert[i] _ bb2.minVert[i];
newBB.maxVert[i] _ bb2.maxVert[i];
};
bb2 = NIL => {
newBB.minVert[i] _ bb1.minVert[i];
newBB.maxVert[i] _ bb1.maxVert[i];
};
ENDCASE => {
newBB.minVert[i] _ Max[bb1.minVert[i], bb2.minVert[i]];
newBB.maxVert[i] _ Min[bb1.maxVert[i], bb2.maxVert[i]];
};
ENDLOOP;
}; -- end of IntersectionCombineBoundBoxes
DifferenceCombineBoundBoxes: PUBLIC PROC [bb1, bb2: BoundBox] RETURNS [newBB: BoundBox] = {
IF bb1 = NIL THEN {newBB _ NIL; RETURN};
newBB _ NEW[BoundBoxObj];
FOR i: NAT IN[1..3] DO
newBB.minVert[i] _ bb1.minVert[i];
newBB.maxVert[i] _ bb1.maxVert[i];
ENDLOOP;
}; -- end of DifferenceCombineBoundBoxes
	

DrawBoundBox: PUBLIC PROC [dc: Graphics.Context, boundBox: BoundBox, screen: CoordSystem] = {
lowerLeft, upperLeft, upperRight, lowerRight: Point2d;
IF boundBox = NIL THEN RETURN;
lowerLeft _ CoordSys.CameraToScreen[[boundBox.minVert[1], boundBox.minVert[2]], screen];
upperLeft _ CoordSys.CameraToScreen[[boundBox.minVert[1], boundBox.maxVert[2]], screen];
upperRight _ CoordSys.CameraToScreen[[boundBox.maxVert[1], boundBox.maxVert[2]], screen];
lowerRight _ CoordSys.CameraToScreen[[boundBox.maxVert[1], boundBox.minVert[2]], screen];
Graphics.SetCP[dc, lowerLeft[1], lowerLeft[2]];
Graphics.DrawTo[dc, upperLeft[1], upperLeft[2]];
Graphics.DrawTo[dc, upperRight[1], upperRight[2]];
Graphics.DrawTo[dc, lowerRight[1], lowerRight[2]];
Graphics.DrawTo[dc, lowerLeft[1], lowerLeft[2]];
};	-- end of DrawBoundBox
ComplementBoundBox: PUBLIC PROC [dc: Graphics.Context, boundBox: BoundBox, screen: CoordSystem] = {
path: Graphics.Path _ Graphics.NewPath[4];
mark: Graphics.Mark;
lowerLeft, upperLeft, upperRight, lowerRight: Point2d;
lowerLeft _ CoordSys.CameraToScreen[[boundBox.minVert[1], boundBox.minVert[2]], screen];
upperLeft _ CoordSys.CameraToScreen[[boundBox.minVert[1], boundBox.maxVert[2]], screen];
upperRight _ CoordSys.CameraToScreen[[boundBox.maxVert[1], boundBox.maxVert[2]], screen];
lowerRight _ CoordSys.CameraToScreen[[boundBox.maxVert[1], boundBox.minVert[2]], screen];
Graphics.MoveTo[path, lowerLeft[1], lowerLeft[2]];
Graphics.LineTo[path, upperLeft[1], upperLeft[2]];
Graphics.LineTo[path, upperRight[1], upperRight[2]];
Graphics.LineTo[path, lowerRight[1], lowerRight[2]];
mark _ Graphics.Save[dc];
[] _ Graphics.SetPaintMode[dc, invert];
Graphics.SetColor[dc, GraphicsColor.black];
Graphics.DrawArea[dc, path];
Graphics.Restore[dc, mark];
};	-- end of ComplementBoundBox
	
Min: PROC [a, b: REAL] RETURNS [REAL] = {
RETURN[IF a < b THEN a ELSE b];
};

Max: PROC [a, b: REAL] RETURNS [REAL] = {
RETURN[IF a > b THEN a ELSE b];
};

END.
ŽFile: SVBoundBoxImpl.mesa
Last edited by Bier on August 9, 1984 1:22:27 am PDT
Copyright c 1984 by Xerox Corporation.  All rights reserved.
Contents: Procedures for creating bounding polyhedra of master objects, and for deriving "3-d" bounding boxes from these polyhedra.  Procedures for combining these bounding boxes with union, intersection and difference operators.
A pyramid with base of size sx by sz on the y=0 plane and tip at [0, sy, 0].
A pyramid having base a hexagon around the circle (of radius r centered on [0, 0, 0] on the y=0 plane) and having tip at [0, h, 0].
Bounds a cone slice (cone around y axis) with radius r1 at y=h1 and radius r2 at y = h2.  Currently uses two hexagons.  Octagons may follow.
Bounds a disk (centered on y axis) with radius r at y = h;
A boundHedron is expressed in local coordinates.
For now, draw a line from each point to every other.
Find the average of all of the points in the boundhedron.
For each point of the bound hedron, find its perspective or orthogonal projection into camera coordinates.  Do not project z.  Find min x, y, z and max x, y, z as you go.
Initialize minX, minY, and minZ to the values for the first boundhedron point.
Now look at the rest of the points.
Boundbox is in camera coords so this is easy.
Bound box is in perspective camera coords.  Convert to screen and draw.
bound box is in perspective camera coords.  Convert to screen and draw.
Κ-–

"cedar" style˜Iheadš
œ™Iprocš
œ4™4Jšœ
Οm
œ1™<Lš
œε
™ε
L˜š
Οk	˜	Lš
œ	˜	Lš
œ˜Lš
œ	˜	Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜L˜
Lš
œ˜L˜Lš
œ˜—L˜šœž˜Lšžœ9˜@Lšžœ
˜—Lš
ž˜˜Lšœžœ˜#Lšœ
žœ˜-Lšœ	žœ˜Lšœ	žœ˜Lšœžœ˜)Lšœžœ˜Lšœžœ˜L˜Lšœ
žœžœ˜'Lšœžœ˜3L˜Lšœ
žœžœ
˜!Lšœ
žœ˜-Lš
œ
˜
—š
Οnœžœ
žœžœžœ˜GLšœžœ˜Lš
œ˜Lš
œ˜—šŸœžœ
žœ&˜FLšžœžœ
ž˜"šžœ˜Lš
œ˜Lš
œ˜Lš
œ˜—LšœΟc˜ —šŸœžœ
žœ$˜Cšžœžœ
žœž˜Lš
œ!˜!—Lšžœ
˜Lš
œ˜—š
Ÿœžœ
žœžœžœ˜TLšœžœ
˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ*˜*Lš
œ+˜+Lš
œ*˜*Lš
œ)˜)Lš
œ+˜+Lš
œ,˜,Lš
œ+˜+Lš
œ*˜*Lšœ  ˜#—š
Ÿœžœ
žœžœžœ˜aLš
œ˜Lš
œ&˜&Lš
œ&˜&Lš
œ&˜&Lš
œ&˜&Lš
œ&˜&Lš
œ&˜&Lš
œ&˜&Lš
œ&˜&Lšœ !˜$—š
Ÿœžœ
žœžœžœ˜PLš
œL™LLšœ
žœ
˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ(˜(Lš
œ)˜)Lš
œ(˜(Lš
œ'˜'Lš
œ$˜$Lšœ ˜—š
Ÿœžœ
žœ
žœžœ˜QLš
œ˜Lš
œ˜Lš
œ/˜/Lš
œ3˜3Lš
œ ˜ Lš
œ#˜#Lš
œ˜—š
Ÿœžœ
žœžœžœ˜MLš
œƒ
™ƒ
Lš
œ
˜
Lš
œ'˜'Lš
œ˜Lš
œ˜Lš
œ#˜#Lšœ ˜"—š
Ÿœžœ
žœžœžœ˜XLš
œŒ
™Œ
Lš
œ
˜
Lš
œ˜Lš
œ)˜)Lš
œ˜Lš
œ)˜)Lš
œ˜Lšœ  ˜#—š
Ÿœžœ
žœžœžœ˜GLš
œ:™:Lš
œ
˜
Lš
œ˜Lš
œ'˜'Lš
œ˜Lšœ ˜—šŸœžœ
žœ˜3Lš
œ˜Lš
œ˜—Lš
œ
˜
šŸœžœ
žœm˜‰
Lš
œ0™0Lš
œ4™4šžœžœ
žœž˜šžœžœ
žœž˜šžœžœ˜
Lš
œ4˜4Lš
œ7˜7——Lšžœ
˜—Lšžœ
˜Lš
œ˜—Lš
œ
˜
šŸœžœ
žœžœ˜PL™9Lš
œ˜Lšœ	žœ
˜Lš
œ˜šžœžœ
žœž˜Lš
œ!˜!—Lšžœ
˜Lš
œ˜Lš
œ(˜(Lš
œ˜L˜—šŸœžœ
žœ9žœ˜}Lš
œͺ
™ͺ
Lšœ$žœ
˜)Lš
œ˜Lš
œ˜L˜Lš
žœžœ
žœ
žœžœ˜*šœžœ˜Lš
œN™N—Lš
œ˜Lš
œ7˜7Lš
œ7˜7Lš
œ˜Lš
œ˜š
œ˜L™#—šžœžœ
žœž˜Lš
œ˜Lš
œ7˜7Lš
œ7˜7Lšžœžœ˜/Lšžœ
žœžœ˜5Lšžœžœ˜/Lšžœ
žœžœ˜5Lšžœžœ˜-Lšžœ
žœžœ˜3—Lšžœ
˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lšœ !˜$—š
Ÿœžœ
žœžœžœ˜_Lšœžœ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lšœ ˜—š
Ÿœžœ
žœ,žœžœ˜ZLš
œ-™-Lšžœžœ
žœ
žœ
žœ 4˜Xšžœ
žœ
˜Lšœ&žœ$˜MLš
ž˜Lšœ&žœ%˜N—Lšœ ˜—L˜šŸœžœ
žœžœ˜VLšžœžœ
žœžœ
žœ
žœžœ˜5Lšœžœ˜šžœžœ
žœž˜Lš
œ"˜"Lš
œ7˜7Lš
œ7˜7—Lšžœ
˜Lšœ  ˜#—šŸœžœ
žœžœ˜]Lšžœžœ
žœžœ
žœ
žœžœ˜6Lšœžœ˜šžœžœ
žœž˜šžœ
žœ
ž˜šœžœ˜Lš
œ"˜"Lš
œ"˜"L˜—šœžœ˜Lš
œ"˜"Lš
œ"˜"L˜—šžœ˜Lš
œ7˜7Lš
œ7˜7L˜———Lšžœ
˜Lšœ '˜*—šŸœžœ
žœžœ˜[Lš
žœžœ
žœ
žœžœ˜(Lšœžœ˜šžœžœ
žœž˜Lš
œ"˜"Lš
œ"˜"—Lšžœ
˜Lšœ %˜(—Lš
œ
˜
L˜šŸœžœ
žœD˜]Lš
œG™GLš
œ6˜6Lšžœžœ
žœ
žœ
˜Lš
œX˜XLš
œX˜XLš
œY˜YLš
œY˜YLš
œ/˜/Lš
œ0˜0Lš
œ2˜2Lš
œ2˜2Lš
œ0˜0Lšœ ˜—šŸœžœ
žœD˜cLš
œ*˜*Lš
œ˜Lš
œG™GLš
œ6˜6Lš
œX˜XLš
œX˜XLš
œY˜YLš
œY˜YLš
œ2˜2Lš
œ2˜2Lš
œ4˜4Lš
œ4˜4Lš
œ˜Lš
œ'˜'Lš
œ+˜+Lš
œ˜Lš
œ˜Lšœ ˜—Lš
œ
˜
š
Ÿœžœžœžœžœ˜)Lšžœ
žœžœžœ˜Lš
œ˜L˜—š
Ÿœžœžœžœžœ˜)Lšžœ
žœžœžœ˜Lš
œ˜—L˜Lšžœ
˜—…—$¨5c