[Indigo]<Solidviews>SolidModeler>SVBoundBoxImpl.mesa!16

File: SVBoundBoxImpl.mesa

Last edited by Bier on June 1, 1987 10:38:38 am PDT

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, SVGraphics, Imager, SV2d, SV3d, SVAssembly, SVBasicTypes, SVBoundBox, SVModelTypes, SVPolygon3d, SVSceneTypes, SVSelect, SVVector3d;

SVBoundBoxImpl: CEDAR PROGRAM

IMPORTS CoordSys, SVGraphics, Imager, SVAssembly, SVPolygon3d, SVSelect, SVVector3d

EXPORTS SVBoundBox =

BEGIN

BoundBox: TYPE = REF BoundBoxObj;

BoundBoxObj: TYPE = SVBasicTypes.BoundBoxObj;

BoundHedron: TYPE = REF BoundHedronObj;

BoundHedronObj: TYPE = SVBasicTypes.BoundHedronObj;

Camera: TYPE = SVModelTypes.Camera;

CoordSystem: TYPE = SVModelTypes.CoordSystem;

Point2d: TYPE = SV2d.Point2d;

Point3d: TYPE = SV3d.Point3d;

PointSetOp: TYPE = SVSceneTypes.PointSetOp;

Poly3d: TYPE = SV3d.Poly3d;

Scene: TYPE = SVSceneTypes.Scene;

SelectionClass: TYPE = SVSelect.SelectionClass;

SliceDescriptor: TYPE = SVSceneTypes.SliceDescriptor;

SliceDescriptorGenerator: TYPE = SVSceneTypes.SliceDescriptorGenerator;

Vector3d: TYPE = SV3d.Vector3d;

Creating a BoundHedron

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: Imager.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 {

SVGraphics.SetCP[dc, bh[i], camera, CoordSys.WRTCamera[localWRTWorld, camera.coordSys]];

SVGraphics.DrawTo[dc, bh[j], camera, CoordSys.WRTCamera[localWRTWorld, camera.coordSys]];};

ENDLOOP;

};

CenterOfMassBoundHedron: PUBLIC PROC [bh: BoundHedron] RETURNS [cm: Point3d] = {

Find the average of all of the points in the boundhedron.

sum: Vector3d;

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] = {

IF bh = NIL THEN {boundBox ← NIL; RETURN};

boundBox ← NEW[BoundBoxObj];

FillBoundBoxFromBoundHedron[bh, camera, localCS, boundBox];

};

FillBoundBoxFromBoundHedron: PUBLIC PROC [bh: BoundHedron, camera: Camera, localCS: CoordSystem, 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, maxX, maxY: REAL;

localPt, cameraPt: Point3d;

projectPt: Point2d;

IF bh = NIL THEN {boundBox.infinite ← TRUE; RETURN};

Initialize minX, minY, and minZ to the values for the first boundhedron point.

localPt ← bh[0];

cameraPt ← SVGraphics.LocalToCamera[localPt, localCS, camera.coordSys];

projectPt ← SVGraphics.DoProjection[cameraPt, camera];

minX ← maxX ← projectPt[1];

minY ← maxY ← projectPt[2];

Now look at the rest of the points.

FOR i: NAT IN[1..bh.len) DO

localPt ← bh[i];

cameraPt ← SVGraphics.LocalToCamera[localPt, localCS, camera.coordSys];

projectPt ← SVGraphics.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];

ENDLOOP;

boundBox.loX ← minX;

boundBox.loY ← minY;

boundBox.hiX ← maxX;

boundBox.hiY ← maxY;

boundBox.null ← boundBox.infinite ← FALSE;

}; -- end of BoundBoxFromBoundHedron

Creating a BoundBox

BoundBoxFromValues: PUBLIC PROC [minX, minY, maxX, maxY: REAL] RETURNS [boundBox: BoundBox] = {

boundBox ← NEW[BoundBoxObj];

boundBox.loX ← minX;

boundBox.loY ← minY;

boundBox.hiX ← maxX;

boundBox.hiY ← maxY;

boundBox.null ← boundBox.infinite ← FALSE;

}; -- end of BoundBoxFromValues

BoundBoxFromRectangle: PUBLIC PROC [rect: Imager.Rectangle, camera: Camera] RETURNS [bBox: BoundBox] = {

lo, hi: Point2d;

bBox ← NEW[BoundBoxObj ← [rect.x, rect.y, rect.x + rect.w, rect.y + rect.h, FALSE, FALSE]];

lo ← CoordSys.ScreenToCamera[[bBox.loX, bBox.loY], camera.screenCS];

hi ← CoordSys.ScreenToCamera[[bBox.hiX, bBox.hiY], camera.screenCS];

bBox.loX ← lo[1]; bBox.loY ← lo[2];

bBox.hiX ← hi[1]; bBox.hiY ← hi[2];

};

NullBoundBox: PUBLIC PROC [] RETURNS [bBox: BoundBox] = {

bBox ← NEW[BoundBoxObj ← [0,0,0,0, TRUE, FALSE]];

};

EnlargeByBox: PUBLIC PROC [bBox: BoundBox, by: BoundBox] = {

IF bBox.infinite OR by.null THEN RETURN;

IF by.infinite THEN {bBox.infinite ← TRUE; bBox.null ← FALSE; RETURN};

IF bBox.null THEN {bBox^ ← by^; RETURN};

bBox.loX ← MIN[bBox.loX, by.loX];

bBox.hiX ← MAX[bBox.hiX, by.hiX];

bBox.loY ← MIN[bBox.loY, by.loY];

bBox.hiY ← MAX[bBox.hiY, by.hiY];

};

BoundBoxOfMoving: PUBLIC PROC [scene: Scene, camera: Camera] RETURNS [bigBox: BoundBox] = {

routine called to calculate the boundBox of all objects that are about to move; that is, all selected slices, selected CPs, selected joints AND the dangling segments of selected joints AND the segments of selected CPs.

sGen: SliceDescriptorGenerator;

sliceD: SliceDescriptor;

nextBox: BoundBox;

bigBox ← NullBoundBox[];

sGen ← SVSelect.SelectedSlices[scene, normal];

FOR sliceD ← SVSelect.NextSliceDescriptor[sGen], SVSelect.NextSliceDescriptor[sGen] UNTIL sliceD = NIL DO

overlay, rubber, drag, movingParts: SliceDescriptor;

[----, overlay, rubber, drag] ← SVAssembly.MovingParts[sliceD.slice, sliceD.parts];

movingParts ← SVAssembly.UnionParts[overlay, rubber];

movingParts ← SVAssembly.UnionParts[movingParts, drag];

nextBox ← SVAssembly.GetBoundBox[sliceD.slice, movingParts.parts, camera];

EnlargeByBox[bBox: bigBox, by: nextBox];

ENDLOOP;

};

BoundBoxOfSelected: PUBLIC PROC [scene: Scene, camera: Camera, selectClass: SelectionClass] RETURNS [bigBox: BoundBox] = {

sGen: SliceDescriptorGenerator;

nextBox: BoundBox;

bigBox ← NullBoundBox[];

sGen ← SVSelect.SelectedSlices[scene, selectClass];

FOR sliceD: SliceDescriptor ← SVSelect.NextSliceDescriptor[sGen], SVSelect.NextSliceDescriptor[sGen] UNTIL sliceD = NIL DO

nextBox ← SVAssembly.GetBoundBox[sliceD.slice, sliceD.parts, camera];

EnlargeByBox[bBox: bigBox, by: nextBox];

ENDLOOP;

};

PointInBoundBox: PUBLIC PROC [cameraPoint: Point2d, boundBox: BoundBox] RETURNS [BOOL] = {

Boundbox is in camera coords so this is easy.

IF boundBox = NIL OR boundBox.infinite THEN RETURN[TRUE]; -- NIL means infinite

IF boundBox.null THEN RETURN[FALSE];

RETURN[

boundBox.loX <= cameraPoint[1] AND cameraPoint[1]<=boundBox.hiX

AND

boundBox.loY <= cameraPoint[2] AND cameraPoint[2]<=boundBox.hiY]

}; -- 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];

newBB.loX ← bb2.loX;

newBB.loX ← Min[bb1.loX, bb2.loX];

newBB.hiX ← Max[bb1.hiX, bb2.hiX];

newBB.loY ← bb2.loY;

newBB.loY ← Min[bb1.loY, bb2.loY];

newBB.hiY ← Max[bb1.hiY, bb2.hiY];

}; -- 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];

SELECT TRUE FROM

bb1 = NIL => {

newBB.loX ← bb2.loX;

newBB.hiX ← bb2.hiX;

newBB.loY ← bb2.loY;

newBB.hiY ← bb2.hiY;

};

bb2 = NIL => {

newBB.loX ← bb1.loX;

newBB.hiX ← bb1.hiX;

newBB.loY ← bb1.loY;

newBB.hiY ← bb1.hiY;

};

ENDCASE => {

newBB.loX ← Max[bb1.loX, bb2.loX];

newBB.hiX ← Min[bb1.hiX, bb2.hiX];

newBB.loY ← Max[bb1.loY, bb2.loY];

newBB.hiY ← Min[bb1.hiY, bb2.hiY];

};

}; -- end of IntersectionCombineBoundBoxes

DifferenceCombineBoundBoxes: PUBLIC PROC [bb1, bb2: BoundBox] RETURNS [newBB: BoundBox] = {

IF bb1 = NIL THEN {newBB ← NIL; RETURN};

newBB ← NEW[BoundBoxObj];

newBB.loX ← bb1.loX;

newBB.hiX ← bb1.hiX;

newBB.loY ← bb1.loY;

newBB.hiY ← bb1.hiY;

}; -- end of DifferenceCombineBoundBoxes

OutsideOf: PUBLIC PROC [test, bound: BoundBox] RETURNS [BOOL] = {

RETURN[

test.hiX < bound.loX OR test.loX > bound.hiX OR

test.hiY < bound.loY OR test.loY > bound.hiY ];

};

DrawBoundBox: PUBLIC PROC [dc: Imager.Context, boundBox: BoundBox, screen: CoordSystem] = {

Bound box is in perspective camera coords. Convert to screen and draw.

lowerLeft, upperLeft, upperRight, lowerRight: Point2d;

RectanglePath: Imager.PathProc = {

moveTo[[lowerLeft[1], lowerLeft[2]]];

lineTo[[upperLeft[1], upperLeft[2]]];

lineTo[[ upperRight[1], upperRight[2]]];

lineTo[[ lowerRight[1], lowerRight[2]]];

lineTo[[lowerLeft[1], lowerLeft[2]]];

};

IF boundBox = NIL OR boundBox.null OR boundBox.infinite THEN RETURN;

lowerLeft ← CoordSys.CameraToScreen[[boundBox.loX, boundBox.loY], screen];

upperLeft ← CoordSys.CameraToScreen[[boundBox.loX, boundBox.hiY], screen];

upperRight ← CoordSys.CameraToScreen[[boundBox.hiX, boundBox.hiY], screen];

lowerRight ← CoordSys.CameraToScreen[[boundBox.hiX, boundBox.loY], screen];

Imager.SetStrokeWidth[dc, 1.0];

Imager.MaskStroke[dc, RectanglePath, TRUE];

}; -- end of DrawBoundBox

EraseWithinBoundBox: PUBLIC PROC [dc: Imager.Context, boundBox: BoundBox, screen: CoordSystem] = {

Bound box is in perspective camera coords. Convert to screen and draw.

EraseWithinBoundBoxAux: PROC = {

rect: Imager.Rectangle ← [x: lowerLeft[1], y: lowerLeft[2], w: upperRight[1]-lowerLeft[1], h: upperRight[2]-lowerLeft[2]];

Imager.SetColor[dc, Imager.white];

Imager.MaskRectangle[dc, rect];

};

lowerLeft, upperRight: Point2d;

IF boundBox = NIL OR boundBox.null OR boundBox.infinite THEN RETURN;

lowerLeft ← CoordSys.CameraToScreen[[boundBox.loX, boundBox.loY], screen];

upperRight ← CoordSys.CameraToScreen[[boundBox.hiX, boundBox.hiY], screen];

Imager.DoSaveAll[dc, EraseWithinBoundBoxAux];

}; -- end of DrawBoundBox

Clip: PUBLIC PROC [dc: Imager.Context, bBox: BoundBox, screen: CoordSystem] = {

lowerLeft, upperRight: Point2d;

IF bBox.null THEN ERROR;

IF bBox.infinite THEN RETURN;

lowerLeft ← CoordSys.CameraToScreen[[bBox.loX, bBox.loY], screen];

upperRight ← CoordSys.CameraToScreen[[bBox.hiX, bBox.hiY], screen];

Imager.ClipRectangle[dc, [lowerLeft[1], lowerLeft[2], (upperRight[1]-lowerLeft[1]), (upperRight[2]-lowerLeft[2])]];

};

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.