GGBoundBoxImpl.mesa
Copyright c 1985 by Xerox Corporation. All rights reserved.
Last edited by Bier on July 16, 1987 12:26:37 pm PDT
Contents: Procedures for creating and combining bounding boxes for refresh efficiency.
Pier, May 22, 1992 6:10 pm PDT
David Kurlander August 23, 1986 5:04:15 pm PDT
Bier, March 10, 1990 5:23:46 pm PST
DIRECTORY
GGCoreTypes, GGBoundBox, Imager, ImagerTransformation, Lines2d, Real, RealFns, Vectors2d;
GGBoundBoxImpl: CEDAR PROGRAM
IMPORTS Imager, ImagerTransformation, Lines2d, Real, RealFns, Vectors2d
EXPORTS GGBoundBox = BEGIN
BoundBox: TYPE = REF BoundBoxObj;
BoundBoxObj: TYPE = GGCoreTypes.BoundBoxObj;
Edge: TYPE = GGCoreTypes.Edge;
MaskArray: TYPE = GGBoundBox.MaskArray;
Point: TYPE = Imager.VEC;
Vector: TYPE = Imager.VEC;
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];
};
bigReal: REAL = 100000.0;
reallyBigReal: REAL = 1000000.0;
infiniteRect: Imager.Rectangle = [-bigReal, -bigReal, reallyBigReal, reallyBigReal];
RectangleFromBoundBox: PUBLIC PROC [bBox: BoundBox] RETURNS [rect: Imager.Rectangle] = {
IF bBox=NIL OR bBox.infinite THEN rect ← infiniteRect
ELSE 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 ← CreateBoundBox[0, 0, xPixels, yPixels];
bBox ← 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.
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: GGCoreTypes.BoundBoxObj] RETURNS [BOOL] = {
RETURN[ NOT (test.x < box.loX OR test.x > box.hiX OR test.y < box.loY OR test.y > box.hiY) ];
};
PointIsInGrownBox: PUBLIC PROC [test: Point, box: BoundBox, offset: REAL] RETURNS [BOOL] = {
RETURN[ NOT (test.x < box.loX-offset OR test.x > box.hiX+offset OR test.y < box.loY-offset OR test.y > box.hiY+offset) ];
};
Centroid: PUBLIC PROC [box: BoundBox] RETURNS [centroid: Point ← [0.0, 0.0], success: BOOL ← TRUE] = {
IF box.null OR box.infinite THEN {success ← FALSE; RETURN};
centroid ← [(box.loX + box.hiX)/2.0, (box.loY + box.hiY)/2.0];
};
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.
EraseWithinBoundBox: PUBLIC PROC [dc: Imager.Context, bBox: BoundBox] = {
EraseWithinBoundBoxAux: PROC = {
Imager.SetColor[dc, Imager.white];
Imager.MaskRectangle[dc, IF bBox.infinite THEN infiniteRect ELSE [x: bBox.loX, y: bBox.loY, w: bBox.hiX-bBox.loX, h: bBox.hiY-bBox.loY] ];
};
IF bBox.null OR bBox.infinite THEN RETURN;
IF bBox.null THEN RETURN;
Imager.DoSave[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.
CatchableMul: PROC [a, b: REAL] RETURNS [REAL] = {RETURN [a*b]};
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;
index: NAT ← 0;
tolerance2: REAL;
IF bBox.null OR bBox.infinite THEN
RETURN[bestDist: 99999.0, bestJoint: 999, bestPoint: [-1.0, -1.0], success: FALSE];
tolerance2 ← CatchableMul[tolerance, tolerance ! Real.RealException =>
{tolerance2 ← Real.LargestNumber; CONTINUE}];
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;
index: NAT ← 0;
tolerance2: REAL;
IF bBox.null OR bBox.infinite THEN
RETURN[bestDist: 99999.0, bestSeg: 999, bestPoint: [-1.0, -1.0], success: FALSE];
tolerance2 ← CatchableMul[tolerance, tolerance ! Real.RealException =>
{tolerance2 ← Real.LargestNumber; CONTINUE}];
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];
};
No longer needed because intersections are computed on the fly.
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;
EXITS
End => NULL;
};
ENDLOOP;
IF pointCount > 2 THEN ERROR;
};
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;
};
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;
emptyBoundBox: PUBLIC BoundBox;
Init: PROC [] = {
globalEdge ← Lines2d.CreateEmptyEdge[];
globalBoxEdge ← Lines2d.CreateEmptyEdge[];
emptyBoundBox ← NEW[GGCoreTypes.BoundBoxObj ← [loX: Real.LargestNumber, loY: Real.LargestNumber, hiX: Real.SmallestNormalizedNumber, hiY: Real.SmallestNormalizedNumber, null: TRUE, infinite: FALSE] ];
};
Init[];
END.