-- File: SVBoundBoxImpl.mesa
-- Last edited by Bier on December 18, 1982 1:36 am
-- Author: Eric Bier on June 23, 1983 2:24 pm
-- 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,
CSG,
CSGGraphics,
Graphics,
GraphicsColor,
Matrix3d,
SV2d,
SVBoundBox,
SVPolygon3d;
SVBoundBoxImpl: PROGRAM
IMPORTS CoordSys, CSGGraphics, Graphics, SVPolygon3d
EXPORTS SVBoundBox =
BEGIN
Camera: TYPE = CSGGraphics.Camera;
CoordSystem: TYPE = REF CoordSysObj;
CoordSysObj: TYPE = CoordSys.CoordSysObj;
Point2d: TYPE = SV2d.Point2d;
Point3d: TYPE = Matrix3d.Point3d;
PointSetOp: TYPE = CSG.PointSetOp;
Poly3d: TYPE = SVPolygon3d.Poly3d;
BoundHedron: TYPE = REF BoundHedronObj;
BoundHedronObj: TYPE = SVBoundBox.BoundHedronObj;
-- RECORD [
-- len: NAT,
-- seq: SEQUENCE numVerts: NAT OF Point3d];
BoundBox: TYPE = REF BoundBoxObj;
BoundBoxObj: TYPE = SVBoundBox.BoundBoxObj;
-- RECORD [
-- minVert: Point3d, ( min x, y and z makes this lower-left-deep)
-- maxVert: Point3d]; ( max x, y and z makes this upper-right-shallow)
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;
};
BoundBoxFromBoundHedron: PUBLIC PROC [bh: BoundHedron, camera: Camera, localCS: CoordSystem] RETURNS [boundBox: BoundBox] = {
-- For each point of the bound hedron, find its perspective 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;
perspecPt: Point2d;
boundBox ← NEW[BoundBoxObj];
localPt ← bh[0];
cameraPt ← CSGGraphics.LocalToCamera[localPt, localCS];
perspecPt ← CSGGraphics.GetPerspective[cameraPt, camera];
minX ← maxX ← perspecPt[1];
minY ← maxY ← perspecPt[2];
minZ ← maxZ ← cameraPt[3];
FOR i: NAT IN[1..bh.len) DO
localPt ← bh[i];
cameraPt ← CSGGraphics.LocalToCamera[localPt, localCS];
perspecPt ← CSGGraphics.GetPerspective[cameraPt, camera];
IF perspecPt[1] < minX THEN minX ← perspecPt[1]
ELSE IF perspecPt[1] > maxX THEN maxX ← perspecPt[1];
IF perspecPt[2] < minY THEN minY ← perspecPt[2]
ELSE IF perspecPt[2] > maxY THEN maxY ← perspecPt[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.
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] = {
newBB ← NEW[BoundBoxObj];
FOR i: NAT IN[1..3] DO
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] = {
newBB ← NEW[BoundBoxObj];
FOR i: NAT IN[1..3] DO
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] = {
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;
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.