GGBoundBoxImpl.mesa
Copyright c 1985 by Xerox Corporation. All rights reserved.
Last edited by Bier on December 28, 1986 2:47:12 pm PST
Contents: Procedures for creating and combining bounding boxes for refresh efficiency.
Pier, December 12, 1986 1:33:10 pm PST
David Kurlander August 23, 1986 5:04:15 pm PDT
DIRECTORY
GGBasicTypes, GGBoundBox, GGError, GGLines, GGModelTypes, GGInterfaceTypes, GGObjects, GGSegmentTypes, GGSelect, GGShapes, GGVector, Imager, ImagerTransformation, Real, RealFns;
GGBoundBoxImpl: CEDAR PROGRAM
IMPORTS GGBoundBox, GGError, GGLines, GGObjects, GGSelect, GGShapes, GGVector, Imager, ImagerTransformation, RealFns
EXPORTS GGBoundBox = BEGIN
BoundBox: TYPE = REF BoundBoxObj;
BoundBoxObj: TYPE = GGBasicTypes.BoundBoxObj;
Circle: TYPE = GGBasicTypes.Circle;
Edge: TYPE = GGBasicTypes.Edge;
EntityGenerator: TYPE = GGModelTypes.EntityGenerator;
Joint: TYPE = GGModelTypes.Joint;
Line: TYPE = GGBasicTypes.Line;
MaskArray: TYPE = GGBoundBox.MaskArray;
Outline: TYPE = GGModelTypes.Outline;
OutlineDescriptor: TYPE = GGModelTypes.OutlineDescriptor;
Point: TYPE = GGBasicTypes.Point;
Scene: TYPE = GGModelTypes.Scene;
Segment: TYPE = GGSegmentTypes.Segment;
SegmentGenerator: TYPE = GGModelTypes.SegmentGenerator;
Sequence: TYPE = GGModelTypes.Sequence;
Slice: TYPE = GGModelTypes.Slice;
SliceDescriptor: TYPE = GGModelTypes.SliceDescriptor;
SliceParts: TYPE = GGModelTypes.SliceParts;
Traj: TYPE = GGModelTypes.Traj;
TrajGenerator: TYPE = GGModelTypes.TrajGenerator;
Vector: TYPE = GGBasicTypes.Vector;
emptyBoundBox: PUBLIC BoundBox ← NEW[GGBasicTypes.BoundBoxObj ← [loX: Real.LargestNumber, loY: Real.LargestNumber, hiX: Real.SmallestNormalizedNumber, hiY: Real.SmallestNormalizedNumber, null: TRUE, infinite: FALSE] ];
Routines which create a new boundBox.
CreateBoundBox: PUBLIC PROC [loX, loY, hiX, hiY: REAL, null: BOOL ← FALSE, infinite: BOOL ← FALSE] RETURNS [bBox: BoundBox] = {
bBox ← NEW[BoundBoxObj ← [loX, loY, hiX, hiY, null, infinite]];
};
NullBoundBox: PUBLIC PROC [] RETURNS [bBox: BoundBox] = {
bBox ← NEW[BoundBoxObj ← [0,0,0,0, TRUE, FALSE]];
};
CopyBoundBox: PUBLIC PROC [bBox: BoundBox] RETURNS [copy: BoundBox] = {
copy ← NEW[BoundBoxObj ← [bBox.loX, bBox.loY, bBox.hiX, bBox.hiY, bBox.null, bBox.infinite]];
};
UpdateCopyBoundBox: PUBLIC PROC [bBox: BoundBox, from: BoundBox] = {
bBox^ ← from^;
};
BoundBoxOfBoxes: PUBLIC PROC [list: LIST OF BoundBox] RETURNS [bigBox: BoundBox] = {
bigBox ← NEW[BoundBoxObj];
WHILE list # NIL AND list.first.null DO list ← list.rest ENDLOOP;
IF list = NIL THEN {bigBox.null ← TRUE; bigBox.infinite ← FALSE; RETURN};
CopyContents[bigBox, list.first];
FOR bBoxList: LIST OF BoundBox ← list.rest, bBoxList.rest UNTIL bBoxList = NIL DO
IF bBoxList.first.infinite THEN {bigBox.null ← FALSE; bigBox.infinite ← TRUE; RETURN};
EnlargeByBox[bBox: bigBox, by: bBoxList.first];
ENDLOOP;
};
BoundBoxOfBoundBox: PUBLIC PROC [box: BoundBox, transform: ImagerTransformation.Transformation] RETURNS [newBox: BoundBox] = {
rect: Imager.Rectangle ← RectangleFromBoundBox[box];
rect ← ImagerTransformation.TransformRectangle[transform, rect];
newBox ← BoundBoxFromRectangle[rect];
};
UpdateBoundBoxOfBoundBox: PUBLIC PROC [bBox: BoundBox, localBox: BoundBox, transform: ImagerTransformation.Transformation] = {
rect: Imager.Rectangle ← RectangleFromBoundBox[localBox];
rect ← ImagerTransformation.TransformRectangle[transform, rect];
UpdateBoundBoxFromRectangle[bBox, rect];
};
BoundBoxFromRectangle: PUBLIC PROC [rect: Imager.Rectangle] RETURNS [bBox: BoundBox] = {
bBox ← NEW[BoundBoxObj ← [rect.x, rect.y, rect.x + rect.w, rect.y + rect.h, FALSE, FALSE]];
};
UpdateBoundBoxFromRectangle: PUBLIC PROC [bBox: BoundBox, rect: Imager.Rectangle] = {
bBox^ ← [rect.x, rect.y, rect.x + rect.w, rect.y + rect.h, FALSE, FALSE];
};
RectangleFromBoundBox: PUBLIC PROC [bBox: BoundBox] RETURNS [rect: Imager.Rectangle] = {
IF bBox.infinite THEN ERROR;
IF bBox.null THEN rect ← [bBox.loX, bBox.loY, 0.0, 0.0]
ELSE rect ← [bBox.loX, bBox.loY, bBox.hiX - bBox.loX, bBox.hiY - bBox.loY];
};
BoundBoxOfPixelArray: PUBLIC PROC [pa: Imager.PixelArray] RETURNS [bBox: BoundBox] = {
xPixels, yPixels: REAL;
xPixels ← pa.sSize;
yPixels ← pa.fSize;
bBox ← GGBoundBox.CreateBoundBox[0, 0, xPixels, yPixels];
bBox ← GGBoundBox.BoundBoxOfBoundBox[bBox, pa.m];
};
BoundBoxOfBitMap: PUBLIC PROC [base: LONG POINTER, wordsPerLine: NAT,
sMin, fMin, sSize, fSize: NAT, tx, ty: INTEGER ← 0] RETURNS [bBox: BoundBox] = {
Computes a bounding box in units of screen dots for the given bit map. The lower left corner will be [0,0].
};
Routines which modify or return an existing boundBox.
AllowForJoints: PUBLIC PROC [box: BoundBox] = {
cpHalf: REAL ← GGModelTypes.halfJointSize + 1;
box^ ← [loX: box.loX-cpHalf, loY: box.loY-cpHalf, hiX: box.hiX+cpHalf, hiY: box.hiY+cpHalf, null: box.null, infinite: box.infinite];
};
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 {CopyContents[to: bBox, from: 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];
};
EnlargeByPoint: PUBLIC PROC [bBox: BoundBox, point: Point] = {
IF bBox.infinite THEN RETURN;
IF bBox.null THEN {
bBox.loX ← bBox.hiX ← point.x;
bBox.loY ← bBox.hiY ← point.y;
bBox.null ← FALSE;
RETURN;
};
bBox.loX ← MIN[bBox.loX, point.x];
bBox.hiX ← MAX[bBox.hiX, point.x];
bBox.loY ← MIN[bBox.loY, point.y];
bBox.hiY ← MAX[bBox.hiY, point.y];
};
EnlargeByVector: PUBLIC PROC [bBox: BoundBox, vector: Vector] = {
Update bBox to be the bounding box of itself and itself offset by vector. Useful to take drop shadows into account, for instance.
IF bBox.null OR bBox.infinite THEN RETURN;
IF vector.x <0.0
THEN bBox.loX ← bBox.loX + vector.x
ELSE bBox.hiX ← bBox.hiX + vector.x;
IF vector.y <0.0
THEN bBox.loY ← bBox.loY + vector.y
ELSE bBox.hiY ← bBox.hiY + vector.y;
};
EnlargeByOffset: PUBLIC PROC [bBox: BoundBox, offset: REAL] = {
Enlarges bBox to include a border of width offset around bBox. Useful to allow for stroke width of a segment, for instance.
IF bBox.null OR bBox.infinite THEN RETURN;
bBox.loX ← bBox.loX - offset;
bBox.hiX ← bBox.hiX + offset;
bBox.loY ← bBox.loY - offset;
bBox.hiY ← bBox.hiY + offset;
};
UpdateBoundBox: PUBLIC PROC [bBox: BoundBox, loX, loY, hiX, hiY: REAL] = {
bBox.loX ← loX;
bBox.loY ← loY;
bBox.hiX ← hiX;
bBox.hiY ← hiY;
bBox.null ← FALSE;
bBox.infinite ← FALSE;
};
Routines which operate on BoundBoxObj (which is presumably allocated on the execution stack).
PointIsInBox: PUBLIC PROC [test: Point, box: GGBasicTypes.BoundBoxObj] RETURNS [BOOL] = {
RETURN[ NOT (test.x < box.loX OR test.x > box.hiX OR test.y < box.loY OR test.y > box.hiY) ];
};
Routines which require knowledge of Gargoyle data structures.
BoundBoxOfSelected: PUBLIC PROC [scene: Scene, selectClass: GGInterfaceTypes.SelectionClass ← normal] RETURNS [bigBox: BoundBox] = {
entityGen: EntityGenerator;
entity: REF ANY;
nextBox: BoundBox;
bigBox ← GGBoundBox.NullBoundBox[];
entityGen ← GGSelect.SelectedStuff[scene, selectClass];
FOR entity ← GGObjects.NextEntity[entityGen], GGObjects.NextEntity[entityGen] UNTIL entity = NIL DO
WITH entity SELECT FROM
sliceD: SliceDescriptor => {
nextBox ← sliceD.slice.class.getBoundBox[sliceD.slice, sliceD.parts];
};
outlineD: OutlineDescriptor => {
nextBox ← outlineD.slice.class.getBoundBox[outlineD.slice, outlineD.parts];
};
ENDCASE => ERROR;
EnlargeByBox[bBox: bigBox, by: nextBox];
ENDLOOP;
};
useSelected: BOOL ← FALSE;
BoundBoxOfMoving: PUBLIC PROC [scene: Scene, selectClass: GGInterfaceTypes.SelectionClass ← normal] 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.
entityGen: EntityGenerator;
entity: REF ANY;
nextBox: BoundBox;
IF useSelected THEN RETURN[BoundBoxOfSelected[scene, selectClass]];
bigBox ← GGBoundBox.NullBoundBox[];
entityGen ← GGSelect.SelectedStuff[scene, selectClass];
FOR entity ← GGObjects.NextEntity[entityGen], GGObjects.NextEntity[entityGen] UNTIL entity = NIL DO
WITH entity SELECT FROM
sliceD: SliceDescriptor => {
movingParts: SliceParts ← sliceD.slice.class.movingParts[sliceD.slice, sliceD.parts];
nextBox ← sliceD.slice.class.getBoundBox[sliceD.slice, movingParts];
};
outlineD: OutlineDescriptor => {
movingParts: SliceParts ← outlineD.slice.class.movingParts[outlineD.slice, outlineD.parts];
nextBox ← outlineD.slice.class.getBoundBox[outlineD.slice, movingParts];
};
ENDCASE => ERROR;
EnlargeByBox[bBox: bigBox, by: nextBox];
ENDLOOP;
};
Utilities
CopyContents: PROC [to: BoundBox, from: BoundBox] = {
to^ ← [from.loX, from.loY, from.hiX, from.hiY, from.null, from.infinite];
};
AllowForArrowHeads: PROC [bBox: BoundBox, traj: Traj] = {
arrowHeight, arrowHalfWidth, firstWidth, lastWidth, delta: REAL;
firstWidth ← GGTraj.FetchSegment[traj, 0].strokeWidth;
lastWidth ← GGTraj.FetchSegment[traj, GGTraj.HiSegment[traj]].strokeWidth;
[arrowHeight, arrowHalfWidth] ← GGShapes.ArrowSize[MAX[firstWidth, lastWidth]];
IF arrowHalfWidth > GGModelTypes.halfJointSize THEN {
delta ← arrowHalfWidth - GGModelTypes.halfJointSize;
bBox.loX ← bBox.loX - delta;
bBox.hiX ← bBox.hiX + delta;
bBox.loY ← bBox.loY - delta;
bBox.hiY ← bBox.hiY + delta;
};
};
Drawing BoundBoxes.
DrawBoundBox: PUBLIC PROC [dc: Imager.Context, bBox: BoundBox] = {
GGShapes.DrawRectangle[dc, bBox.loX, bBox.loY, bBox.hiX, bBox.hiY];
};
EraseWithinBoundBox: PUBLIC PROC [dc: Imager.Context, bBox: BoundBox] = {
EraseWithinBoundBoxAux: PROC = {
rect: Imager.Rectangle ← [x: bBox.loX, y: bBox.loY, w: bBox.hiX-bBox.loX, h: bBox.hiY-bBox.loY];
Imager.SetColor[dc, Imager.white];
Imager.MaskRectangle[dc, rect];
};
IF bBox.null OR bBox.infinite THEN RETURN;
Imager.DoSaveAll[dc, EraseWithinBoundBoxAux];
};
Clip: PUBLIC PROC [dc: Imager.Context, bBox: BoundBox] = {
IF bBox.null THEN ERROR;
IF bBox.infinite THEN RETURN;
Imager.ClipRectangle[dc, [bBox.loX, bBox.loY, (bBox.hiX-bBox.loX), (bBox.hiY-bBox.loY)]];
};
Hit Testing BoundBoxes.
NearestPoint: PUBLIC PROC [bBox: BoundBox, testPoint: Point, tolerance: REAL ← 1E6, mask: MaskArray ← ALL[TRUE] ] RETURNS [bestDist: REAL, bestJoint: NAT, bestPoint: Point, success: BOOL] = {
Finds the corner of bBox which is in mask and nearest to testPoint (and its distance from testPoint). Number the corners of a bBox 0..3 clockwise starting with the lower left corner.
thisPoint: Point;
thisDist2, bestDist2: REAL;
tolerance2: REAL ← tolerance*tolerance;
index: NAT ← 0;
IF bBox.null OR bBox.infinite THEN
RETURN[bestDist: 99999.0, bestJoint: 999, bestPoint: [-1.0, -1.0], success: FALSE];
bestPoint ← [-1.0, -1.0];
bestDist2 ← 1E12; -- better be big enough
bestJoint ← 9999;
success ← FALSE;
FOR index IN [0..4) DO
IF mask[index] THEN {
thisPoint ← BoxPoint[bBox, index];
thisDist2 ← GGVector.DistanceSquared[thisPoint, testPoint];
IF thisDist2 < bestDist2 THEN {
bestDist2 ← thisDist2;
bestJoint ← index;
bestPoint ← thisPoint;
IF bestDist2 < tolerance2 THEN success ← TRUE;
};
};
ENDLOOP;
bestDist ← RealFns.SqRt[bestDist2];
};
NearestSegment: PUBLIC PROC [bBox: BoundBox, testPoint: Point, tolerance: REAL ← 1E6, mask: MaskArray ← ALL[TRUE] ] RETURNS [bestDist: REAL, bestSeg: NAT, bestPoint: Point, success: BOOL] = {
Finds the segment of bBox which is in mask and nearest to testPoint (and its distance from testPoint). Number the segments of a bBox 0..3 clockwise starting with the left edge.
thisDist2, bestDist2: REAL;
thisPoint: Point;
tolerance2: REAL ← tolerance*tolerance;
index: NAT ← 0;
IF bBox.null OR bBox.infinite THEN
RETURN[bestDist: 99999.0, bestSeg: 999, bestPoint: [-1.0, -1.0], success: FALSE];
bestPoint ← [-1.0, -1.0];
bestDist2 ← 1E12; -- better be big enough
bestSeg ← 9999;
success ← FALSE;
FOR index IN [0..4) DO
IF mask[index] THEN {
FillBoxEdge[globalBoxEdge, bBox, index];
thisPoint ← GGLines.NearestPointOnEdge[testPoint, globalBoxEdge];
thisDist2 ← GGVector.DistanceSquared[thisPoint, testPoint];
IF thisDist2 < bestDist2 THEN {
bestDist2 ← thisDist2;
bestSeg ← index;
bestPoint ← thisPoint;
IF thisDist2 < tolerance2 THEN success ← TRUE;
};
};
ENDLOOP;
bestDist ← RealFns.SqRt[bestDist2];
};
LineMeetsBoundBox: PUBLIC PROC [bBox: BoundBox, line: Line] RETURNS [points: LIST OF Point, pointCount: NAT] = {
noHit: BOOL;
hits: ARRAY[0..3] OF BOOL;
hitPoints: ARRAY[0..3] OF Point;
hitPoint: Point;
epsilon: REAL = 0.072;
Find the intersections of the given line with bBox. pointCount will be at most 2.
points ← NIL;
pointCount ← 0;
FOR i: NAT IN [0..3] DO hits[i] ← FALSE; ENDLOOP;
FOR i: NAT IN [0..2] DO
FillBoxEdge[globalEdge, bBox, i];
[hitPoints[i], noHit] ← GGLines.LineMeetsEdge[line, globalEdge]; -- global scratch edge
IF noHit THEN LOOP;
IF i>0 AND hits[i-1] THEN {
IF ABS[hitPoints[i].x - hitPoints[i-1].x] < epsilon THEN LOOP;
IF ABS[hitPoints[i].y - hitPoints[i-1].y] < epsilon THEN LOOP;
};
points ← CONS[hitPoint, points];
pointCount ← pointCount + 1;
hits[i] ← TRUE;
REPEAT
FINISHED => {
FillBoxEdge[globalEdge, bBox, 3];
[hitPoints[3], noHit] ← GGLines.LineMeetsEdge[line, globalEdge];
IF noHit THEN GOTO End;
IF hits[2] THEN {
IF ABS[hitPoints[3].x - hitPoints[2].x] < epsilon THEN GOTO End;
IF ABS[hitPoints[3].y - hitPoints[2].y] < epsilon THEN GOTO End;
};
IF hits[0] THEN {
IF ABS[hitPoints[3].x - hitPoints[0].x] < epsilon THEN GOTO End;
IF ABS[hitPoints[3].y - hitPoints[0].y] < epsilon THEN GOTO End;
};
points ← CONS[hitPoint, points];
pointCount ← pointCount + 1;
hits[3] ← TRUE;
EXITS
End => NULL;
};
ENDLOOP;
IF pointCount > 2 THEN ERROR;
};
CircleMeetsBoundBox: PUBLIC PROC [bBox: BoundBox, circle: Circle] RETURNS [points: LIST OF Point, pointCount: NAT] = {
Find the intersections of the given circle with bBox. pointCount will be at most 8.
SIGNAL GGError.Problem[msg: "Not yet implemented"];
};
BoxPoint: PROC [bBox: BoundBox, index: NAT] RETURNS [point: Point] ~ {
[Artwork node; type 'ArtworkInterpress on' to command tool]
Number the joints 0..3 clockwise starting at the lower left hand corner. Return the requested point.
IF bBox.null OR bBox.infinite THEN ERROR;
SELECT index FROM
0 => point ← [bBox.loX, bBox.loY];
1 => point ← [bBox.loX, bBox.hiY];
2 => point ← [bBox.hiX, bBox.hiY];
3 => point ← [bBox.hiX, bBox.loY];
ENDCASE => ERROR;
};
BoxEdge: PRIVATE PROC [bBox: BoundBox, index: NAT] RETURNS [edge: Edge] = {
IF bBox.null OR bBox.infinite THEN ERROR;
SELECT index FROM
0 => edge ← GGLines.CreateEdge[[bBox.loX, bBox.loY], [bBox.loX, bBox.hiY]];
1 => edge ← GGLines.CreateEdge[[bBox.loX, bBox.hiY], [bBox.hiX, bBox.hiY]];
2 => edge ← GGLines.CreateEdge[[bBox.hiX, bBox.hiY], [bBox.hiX, bBox.loY]];
3 => edge ← GGLines.CreateEdge[[bBox.hiX, bBox.loY], [bBox.loX, bBox.loY]];
ENDCASE => ERROR;
};
FillBoxEdge: PRIVATE PROC [edge: Edge, bBox: BoundBox, index: NAT] = {
IF bBox.null OR bBox.infinite THEN ERROR;
SELECT index FROM
0 => GGLines.FillEdge[[bBox.loX, bBox.loY], [bBox.loX, bBox.hiY], edge];
1 => GGLines.FillEdge[[bBox.loX, bBox.hiY], [bBox.hiX, bBox.hiY], edge];
2 => GGLines.FillEdge[[bBox.hiX, bBox.hiY], [bBox.hiX, bBox.loY], edge];
3 => GGLines.FillEdge[[bBox.hiX, bBox.loY], [bBox.loX, bBox.loY], edge];
ENDCASE => ERROR;
};
globalEdge: Edge;
globalBoxEdge: Edge;
Init: PROC [] = {
globalEdge ← GGLines.CreateEmptyEdge[];
globalBoxEdge ← GGLines.CreateEmptyEdge[];
};
Init[];
END.