File: SVBoundBoxImpl.mesa
Last edited by Bier on August 9, 1984 1:22:27 am PDT
Copyright © 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.
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] = {
A pyramid with base of size sx by sz on the y=0 plane and tip at [0, sy, 0].
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] = {
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].
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] = {
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.
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] = {
Bounds a disk (centered on y axis) with radius r at y = h;
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] = {
A boundHedron is expressed in local coordinates.
For now, draw a line from each point to every other.
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] = {
Find the average of all of the points in the boundhedron.
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] = {
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.
minX, minY, minZ, maxX, maxY, maxZ: REAL;
localPt, cameraPt: Point3d;
projectPt: Point2d;
IF bh = NIL THEN {boundBox ← NIL; RETURN};
boundBox ←
NEW[BoundBoxObj];
Initialize minX, minY, and minZ to the values for the first boundhedron point.
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];
Now look at the rest of the points.
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] = {
Boundbox is in camera coords so this is easy.
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] = {
Bound box is in perspective camera coords. Convert to screen and draw.
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;
bound box is in perspective camera coords. Convert to screen and draw.
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.