GGBoundBoxImpl.mesa
Copyright c 1985 by Xerox Corporation. All rights reserved.
Last edited by Bier on March 9, 1987 9:08:56 pm PST
Contents: Procedures for creating and combining bounding boxes for refresh efficiency.
Pier, May 12, 1987 5:28:18 pm PDT
David Kurlander August 23, 1986 5:04:15 pm PDT
DIRECTORY
--Feedback, --GGBasicTypes, GGBoundBox, GGInterfaceTypes, GGModelTypes, GGSegmentTypes, GGSelect, GGShapes, Imager, ImagerTransformation, Lines2d, Real, RealFns, Vectors2d;
GGBoundBoxImpl:
CEDAR
PROGRAM
IMPORTS --Feedback,-- GGBoundBox, GGSelect, GGShapes, Imager, ImagerTransformation, Lines2d, RealFns, Vectors2d
EXPORTS GGBoundBox = BEGIN
BoundBox: TYPE = REF BoundBoxObj;
BoundBoxObj: TYPE = GGBasicTypes.BoundBoxObj;
Circle: TYPE = GGBasicTypes.Circle;
Edge: TYPE = GGBasicTypes.Edge;
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;
SliceDescriptorGenerator: TYPE = GGModelTypes.SliceDescriptorGenerator;
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] = {
nextBox: BoundBox;
sliceDescGen: SliceDescriptorGenerator ← GGSelect.SelectedSlices[scene, selectClass];
bigBox ← GGBoundBox.NullBoundBox[];
FOR sliceD: SliceDescriptor ← GGSelect.NextSliceDescriptor[sliceDescGen], GGSelect.NextSliceDescriptor[sliceDescGen]
UNTIL sliceD=
NIL
DO
nextBox ← sliceD.slice.class.getBoundBox[sliceD.slice, sliceD.parts];
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.
nextBox: BoundBox;
sliceDescGen: SliceDescriptorGenerator ← GGSelect.SelectedSlices[scene, selectClass];
IF useSelected THEN RETURN[BoundBoxOfSelected[scene, selectClass]];
bigBox ← GGBoundBox.NullBoundBox[];
FOR sliceD: SliceDescriptor ← GGSelect.NextSliceDescriptor[sliceDescGen], GGSelect.NextSliceDescriptor[sliceDescGen]
UNTIL sliceD=
NIL
DO
In the common case, drag will be the only non-null descriptor.
overlay, rubber, drag, movingParts: SliceDescriptor;
[----, overlay, rubber, drag] ← sliceD.slice.class.movingParts[sliceD.slice, sliceD.parts];
movingParts ← sliceD.slice.class.unionParts[overlay, rubber];
movingParts ← sliceD.slice.class.unionParts[movingParts, drag];
nextBox ← sliceD.slice.class.getBoundBox[sliceD.slice, movingParts.parts];
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 ← Vectors2d.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 ← Lines2d.NearestPointOnEdge[testPoint, globalBoxEdge];
thisDist2 ← Vectors2d.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] ← Lines2d.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] ← Lines2d.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;
};
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 Feedback.Problem[msg: "Not yet implemented"];
RETURN[NIL, 0];
};
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 ← Lines2d.CreateEdge[[bBox.loX, bBox.loY], [bBox.loX, bBox.hiY]];
1 => edge ← Lines2d.CreateEdge[[bBox.loX, bBox.hiY], [bBox.hiX, bBox.hiY]];
2 => edge ← Lines2d.CreateEdge[[bBox.hiX, bBox.hiY], [bBox.hiX, bBox.loY]];
3 => edge ← Lines2d.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 => Lines2d.FillEdge[[bBox.loX, bBox.loY], [bBox.loX, bBox.hiY], edge];
1 => Lines2d.FillEdge[[bBox.loX, bBox.hiY], [bBox.hiX, bBox.hiY], edge];
2 => Lines2d.FillEdge[[bBox.hiX, bBox.hiY], [bBox.hiX, bBox.loY], edge];
3 => Lines2d.FillEdge[[bBox.hiX, bBox.loY], [bBox.loX, bBox.loY], edge];
ENDCASE => ERROR;
};
globalEdge: Edge;
globalBoxEdge: Edge;
Init:
PROC [] = {
globalEdge ← Lines2d.CreateEmptyEdge[];
globalBoxEdge ← Lines2d.CreateEmptyEdge[];
};
Init[];
END.