ImagerManhattanImpl.mesa
Copyright Ó 1984, 1985, 1986, 1987, 1989, 1990, 1991 by Xerox Corporation. All rights reserved.
Michael Plass, August 2, 1989 12:51:53 pm PDT
Doug Wyatt, March 7, 1986 4:36:43 pm PST
Russ Atkinson (RRA) December 18, 1990 11:44 am PST
DIRECTORY
ImagerManhattan USING [Polygon, Visibility],
SF USING [Box, BoxAction, BoxGenerator, Vec],
SFInline USING [Add, Empty, Intersect, Nonempty];
Polygon: TYPE ~ ImagerManhattan.Polygon;
Visibility: TYPE ~ ImagerManhattan.Visibility;
InvalidManhattanPolygon: PUBLIC ERROR ~ CODE;
Validate:
PUBLIC
PROC [polygon: Polygon]
RETURNS [Polygon] ~ {
IF polygon #
NIL
THEN {
a: Polygon ¬ polygon;
amins: INTEGER ¬ a.first.min.s;
aminf: INTEGER ¬ a.first.min.f;
amaxs: INTEGER ¬ a.first.max.s;
amaxf: INTEGER ¬ a.first.max.f;
DO
b: Polygon = a.rest;
IF amins >= amaxs OR aminf >= amaxf THEN ERROR InvalidManhattanPolygon;
IF b =
NIL
THEN
EXIT
ELSE {
bmins: INTEGER = b.first.min.s;
bminf: INTEGER = b.first.min.f;
bmaxs: INTEGER = b.first.max.s;
bmaxf: INTEGER = b.first.max.f;
SELECT
TRUE
FROM
amaxs <= bmins => {};
(amins = bmins AND amaxs = bmaxs AND amaxf <= bminf) => {};
ENDCASE => ERROR InvalidManhattanPolygon;
a ¬ b;
amins ¬ bmins;
aminf ¬ bminf;
amaxs ¬ bmaxs;
amaxf ¬ bmaxf;
};
ENDLOOP;
};
RETURN [polygon]
};
CreateFromRuns:
PUBLIC
PROC [
runs:
PROC[run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT],
repeat:
PROC[timesToRepeatScanline:
NAT]]]
RETURNS [polygon: Polygon] ~ {
scratch: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ scratch;
secondLastRowStart: LIST OF SF.Box ¬ NIL;
lastRowStart: LIST OF SF.Box ¬ last;
secondLastRowCount: INTEGER ¬ -1;
lastRowCount: INTEGER ¬ 0;
Run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT] ~ {
fMaxCurrent: INTEGER ~ last.first.max.f;
IF lastRowCount > 0
AND sMin = last.first.min.s
THEN {
IF last.first.max.s-last.first.min.s # 1 THEN ERROR;
SELECT fMin
FROM
= fMaxCurrent => {last.first.max.f ¬ last.first.max.f + fSize};
> fMaxCurrent => {
IF last.rest = NIL THEN last.rest ¬ GetScratch[];
last ¬ last.rest;
last.first ¬ [min: [s: sMin, f: fMin], max: [s: sMin+1, f: fMin+fSize]];
lastRowCount ¬ lastRowCount + 1;
};
ENDCASE => ERROR;
}
ELSE {
IF secondLastRowCount = lastRowCount
AND secondLastRowStart.first.max.s = lastRowStart.first.min.s
AND TryToMergeRows[secondLastRowStart, lastRowCount]
THEN {
last ¬ lastRowStart;
lastRowStart ¬ secondLastRowStart;
secondLastRowCount ¬ -1;
}
ELSE {
IF last.rest = NIL THEN last.rest ¬ GetScratch[];
last ¬ last.rest;
};
secondLastRowStart ¬ lastRowStart;
secondLastRowCount ¬ lastRowCount;
last.first ¬ [min: [s: sMin, f: fMin], max: [s: sMin+1, f: fMin+fSize]];
lastRowStart ¬ last;
lastRowCount ¬ 1;
IF secondLastRowStart.first.max.s > sMin THEN ERROR;
};
};
Repeat:
PROC[timesToRepeatScanline:
NAT] ~ {
t: LIST OF SF.Box ¬ lastRowStart;
THROUGH [0..lastRowCount)
DO
t.first.max.s ¬ t.first.max.s + timesToRepeatScanline;
t ¬ t.rest;
ENDLOOP;
};
last.first ¬ [[FIRST[INTEGER], FIRST[INTEGER]], [FIRST[INTEGER], FIRST[INTEGER]]];
runs[Run, Repeat];
IF secondLastRowCount = lastRowCount
AND secondLastRowStart.first.max.s = lastRowStart.first.min.s
AND TryToMergeRows[secondLastRowStart, lastRowCount]
THEN {
last ¬ secondLastRowStart;
THROUGH [0..lastRowCount-1)
DO
last ¬ last.rest;
ENDLOOP;
};
SELECT
TRUE
FROM
scratch.first.max.f > scratch.first.min.f => {
polygon ¬ scratch;
scratch ¬ last.rest;
last.rest ¬ NIL;
};
ENDCASE => {
polygon ¬ scratch.rest;
scratch.rest ¬ last.rest;
last.rest ¬ NIL;
};
FreeScratch[scratch];
};
TryToMergeRows:
PROC [secondLastRowStart:
LIST
OF
SF.Box, boxesPerRow:
INT]
RETURNS [success:
BOOLEAN] ~ {
Assume
the secondLast row and the last row have the same number of boxes,
boxes in the secondLast row all have the same sSize,
boxes in the last row all have the same sSize.
max: INTEGER;
s: LIST OF SF.Box ¬ secondLastRowStart;
t: LIST OF SF.Box ¬ secondLastRowStart;
FOR i: INT IN [0..boxesPerRow) DO t ¬ t.rest ENDLOOP;
IF boxesPerRow = 0 THEN RETURN [TRUE];
FOR i:
INT
IN [0..boxesPerRow)
DO
IF s.first.min.f # t.first.min.f OR s.first.max.f # t.first.max.f THEN RETURN [FALSE];
s ¬ s.rest; t ¬ t.rest;
ENDLOOP;
t ¬ s; s ¬ secondLastRowStart;
max ¬ t.first.max.s;
FOR i:
INT
IN [0..boxesPerRow)
DO
s.first.max.s ¬ max;
s ¬ s.rest;
ENDLOOP;
RETURN [TRUE];
};
Destroy:
PUBLIC
PROC [rectangleList:
LIST
OF
SF.Box] ~ {
FreeScratch[rectangleList];
};
Copy:
PUBLIC
PROC [polygon: Polygon]
RETURNS [copy: Polygon] ~ {
scratch: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ scratch;
WHILE polygon #
NIL
DO
IF last.rest = NIL THEN {last.rest ¬ GetScratch[]};
last ¬ last.rest;
last.first ¬ polygon.first;
polygon ¬ polygon.rest;
ENDLOOP;
IF last = scratch
THEN copy ¬ NIL
ELSE {
copy ¬ scratch.rest;
scratch.rest ¬ last.rest;
last.rest ¬ NIL;
};
FreeScratch[scratch];
};
Reader:
TYPE ~
RECORD [
s, fMin, fMax: INTEGER,
repeatCount: CARDINAL,
done: BOOLEAN,
currentRow, currentBox: LIST OF SF.Box
];
NewReader:
PROC [polygon: Polygon]
RETURNS [Reader] ~
INLINE {
IF polygon =
NIL
THEN RETURN [[LAST[INTEGER], 0, 0, 0, TRUE, NIL, NIL]]
ELSE
RETURN [[
s: polygon.first.min.s,
fMin: polygon.first.min.f,
fMax: polygon.first.max.f,
repeatCount: polygon.first.max.s-polygon.first.min.s,
done: FALSE,
currentRow: polygon,
currentBox: polygon
]]
};
Advance:
UNSAFE
PROC [r:
POINTER
TO Reader] ~
UNCHECKED {
next: Polygon ¬ r.currentBox.rest;
IF next =
NIL
OR next.first.min.s # r.currentRow.first.min.s
THEN {
IF r.repeatCount > 1
THEN {
r.repeatCount ¬ r.repeatCount - 1;
r.s ¬ r.s + 1;
next ¬ r.currentRow;
}
ELSE
IF next #
NIL
THEN {
r.currentRow ¬ next;
r.repeatCount ¬ next.first.max.s-next.first.min.s;
r.s ¬ next.first.min.s;
};
};
IF next =
NIL
THEN r ¬ [LAST[INTEGER], 0, 0, 0, TRUE, NIL, NIL]
ELSE {
r.fMin ¬ next.first.min.f;
r.fMax ¬ next.first.max.f;
r.currentBox ¬ next;
IF r.repeatCount = 0 THEN Advance[r];
};
};
SkipTo:
UNSAFE
PROC [r:
POINTER
TO Reader, s:
INTEGER] ~
UNCHECKED {
WHILE r.s < s
DO
IF r.currentRow = r.currentBox AND r.repeatCount > 1
THEN {
delta: INTEGER ¬ MIN[INTEGER[r.repeatCount]-1, s-r.s];
r.s ¬ r.s + delta;
r.repeatCount ¬ INTEGER[r.repeatCount] - delta;
}
ELSE Advance[r];
ENDLOOP;
};
TestReader:
PROC [polygon: Polygon] ~ {
reader: Reader ¬ NewReader[polygon];
Run:
PROC [box:
SF.Box] ~ {
IF reader.done THEN ERROR;
IF box.min.s # reader.s THEN ERROR;
IF (box.max.s-box.min.s)#1 THEN ERROR;
IF box.min.f # reader.fMin THEN ERROR;
IF box.max.f # reader.fMax THEN ERROR;
TRUSTED {Advance[@reader]};
};
Map[polygon, Run, TRUE];
IF NOT reader.done THEN ERROR;
};
Union:
PUBLIC
PROC [a, b: Polygon]
RETURNS [Polygon] ~ {
Runs:
PROC[run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT], repeat:
PROC[timesToRepeatScanline:
NAT]] ~
TRUSTED {
aReader: Reader ¬ NewReader[a];
bReader: Reader ¬ NewReader[b];
UNTIL aReader.done
AND bReader.done
DO
as: INTEGER ¬ aReader.s;
bs: INTEGER ¬ bReader.s;
s: INTEGER ¬ MIN[as, bs];
duplicates: NAT ¬ MIN[aReader.repeatCount, bReader.repeatCount];
somethingInScanline: BOOLEAN ¬ FALSE;
WHILE s = aReader.s
OR s = bReader.s
DO
fStart: INTEGER ¬ LAST[INTEGER];
fEnd: INTEGER;
IF s = aReader.s THEN {fStart ¬ aReader.fMin};
IF s = bReader.s THEN {fStart ¬ MIN[fStart, bReader.fMin]};
fEnd ¬ fStart;
DO
SELECT
TRUE
FROM
s = aReader.s
AND aReader.fMin <= fEnd => {
fEnd ¬ MAX[fEnd, aReader.fMax];
Advance[@aReader];
};
s = bReader.s
AND bReader.fMin <= fEnd => {
fEnd ¬ MAX[fEnd, bReader.fMax];
Advance[@bReader];
};
ENDCASE => EXIT;
ENDLOOP;
IF fEnd > fStart THEN {run[s, fStart, fEnd - fStart]; somethingInScanline ¬ TRUE};
ENDLOOP;
IF as = s
AND bs = s
AND duplicates > 1
THEN {
IF somethingInScanline THEN repeat[duplicates-1];
SkipTo[@aReader, s+duplicates];
SkipTo[@bReader, s+duplicates];
};
ENDLOOP;
};
RETURN[CreateFromRuns[Runs]];
};
Intersection:
PUBLIC
PROC [a, b: Polygon]
RETURNS [Polygon] ~ {
Runs:
PROC[run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT], repeat:
PROC[timesToRepeatScanline:
NAT]] ~
TRUSTED {
aReader: Reader ¬ NewReader[a];
bReader: Reader ¬ NewReader[b];
DO
duplicates: NAT;
s: INTEGER;
somethingInScanline: BOOLEAN ¬ FALSE;
IF aReader.s < bReader.s THEN SkipTo[@aReader, bReader.s]; IF aReader.done THEN EXIT;
IF aReader.s > bReader.s THEN SkipTo[@bReader, aReader.s]; IF bReader.done THEN EXIT;
s ¬ aReader.s;
duplicates ¬ MIN[aReader.repeatCount, bReader.repeatCount] - 1;
WHILE s = aReader.s
AND s = bReader.s
DO
fMin: INTEGER ¬ MAX[aReader.fMin, bReader.fMin];
fMax: INTEGER ¬ MIN[aReader.fMax, bReader.fMax];
IF fMin < fMax THEN {run[s, fMin, fMax - fMin]; somethingInScanline ¬ TRUE};
SELECT fMax
FROM
aReader.fMax => {Advance[@aReader]};
bReader.fMax => {Advance[@bReader]};
ENDCASE => ERROR;
ENDLOOP;
IF somethingInScanline
AND duplicates > 0
THEN {
repeat[duplicates];
SkipTo[@aReader, s+1+duplicates];
SkipTo[@bReader, s+1+duplicates];
};
ENDLOOP;
};
RETURN[CreateFromRuns[Runs]];
};
Invert:
PROC [b: Polygon, universe:
SF.Box]
RETURNS [inverse: Polygon] ~ {
c: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ c;
bb: SF.Box ¬ BoundingBox[b];
sMin: INTEGER ¬ MIN[universe.min.s, bb.min.s];
fMin: INTEGER ¬ MIN[universe.min.f, bb.min.f];
sMax: INTEGER ¬ MAX[universe.max.s, bb.max.s];
fMax: INTEGER ¬ MAX[universe.max.f, bb.max.f];
Emit:
PROC [s0, f0, s1, f1:
INTEGER] ~ {
s0 ¬ MAX[s0, universe.min.s];
s1 ¬ MIN[s1, universe.max.s];
f0 ¬ MAX[f0, universe.min.f];
f1 ¬ MIN[f1, universe.max.f];
IF s0 < s1
AND f0 < f1
THEN {
IF last.rest = NIL THEN last.rest ¬ GetScratch[];
last ¬ last.rest;
last.first ¬ [[s0, f0], [s1, f1]];
};
};
s: INTEGER ¬ sMin;
f: INTEGER ¬ fMax;
FOR p:
LIST
OF
SF.Box ¬ b, p.rest
UNTIL p=
NIL
DO
r: SF.Box ~ p.first;
IF r.min.s > sMin
OR p=b
THEN {
Emit[sMin, f, s, fMax];
f ¬ fMin;
sMin ¬ s;
s ¬ r.min.s;
Emit[sMin, f, s, fMax];
sMin ¬ s;
s ¬ r.max.s;
};
IF sMin # r.min.s OR s # r.max.s THEN ERROR;
Emit[sMin, f, s, r.min.f];
f ¬ r.max.f;
ENDLOOP;
Emit[sMin, f, s, fMax];
Emit[s, fMin, sMax, fMax];
IF c = last
THEN inverse ¬ NIL
ELSE {
inverse ¬ c.rest;
c.rest ¬ last.rest;
last.rest ¬ NIL;
};
FreeScratch[c];
[] ← Validate[inverse];
IF Intersection[b, inverse] # NIL THEN ERROR;
};
Difference:
PUBLIC
PROC [a, b: Polygon]
RETURNS [diff: Polygon] ~ {
bb: SF.Box ¬ BoundingBox[a];
bInverse: Polygon ¬ Invert[b, bb];
IF a #
NIL
AND a.rest =
NIL
THEN { diff ¬ bInverse }
ELSE { diff ¬ Intersection[a, bInverse]; FreeScratch[bInverse] };
IF NOT Equal[Union[a, b], Union[diff, b]] THEN ERROR;
};
Shift:
PUBLIC
PROC [polygon: Polygon, sShift, fShift:
INTEGER] ~ {
shift: SF.Vec ~ [s: sShift, f: fShift];
WHILE polygon #
NIL
DO
polygon.first.min ¬ SFInline.Add[polygon.first.min, shift];
polygon.first.max ¬ SFInline.Add[polygon.first.max, shift];
polygon ¬ polygon.rest;
ENDLOOP;
};
FullyDestructiveUnion:
PROC [a, b: Polygon]
RETURNS [u: Polygon] ~ {
u ¬ Union[a, b];
FreeScratch[a];
FreeScratch[b];
};
DestructiveUnion:
PUBLIC
PROC [a, b: Polygon]
RETURNS [u: Polygon] ~ {
u ¬ Union[a, b];
FreeScratch[a];
};
DestructiveIntersection:
PUBLIC
PROC [a, b: Polygon]
RETURNS [i: Polygon ¬
NIL] ~ {
IF a = NIL OR b = NIL THEN RETURN [NIL];
IF b.rest =
NIL
THEN { i ¬ DestructiveClip[a, b.first] }
ELSE { i ¬ Intersection[a, b]; FreeScratch[a] };
};
DestructiveClip:
PUBLIC
PROC [a: Polygon, b:
SF.Box]
RETURNS [i: Polygon ¬
NIL] ~ {
last: Polygon ¬ NIL;
junk: Polygon ¬ NIL;
UNTIL a =
NIL
DO
p: Polygon ¬ a;
sMin: INTEGER ¬ MAX[p.first.min.s, b.min.s];
fMin: INTEGER ¬ MAX[p.first.min.f, b.min.f];
sMax: INTEGER ¬ MIN[p.first.max.s, b.max.s];
fMax: INTEGER ¬ MIN[p.first.max.f, b.max.f];
a ¬ a.rest;
IF sMax <= sMin OR fMax <= fMin
THEN {p.rest ¬ junk; junk ¬ p}
ELSE {
p.first ¬ [[sMin, fMin], [sMax, fMax]];
IF last = NIL THEN i ¬ last ¬ p ELSE {last.rest ¬ p; last ¬ p};
}
ENDLOOP;
IF last # NIL THEN last.rest ¬ NIL;
FreeScratch[junk];
};
DestructiveDifference:
PUBLIC
PROC [a, b: Polygon]
RETURNS [d: Polygon] ~ {
d ¬ Difference[a, b];
FreeScratch[a];
};
SplitOffSecondHalf:
PROC [a:
LIST
OF
SF.Box]
RETURNS [r:
LIST
OF
SF.Box] ~ {
b: LIST OF SF.Box ¬ a;
n: INT ¬ 0;
WHILE a#
NIL
DO
a ¬ a.rest; n ¬ n + 1;
b ¬ b.rest;
IF a = NIL THEN EXIT; a ¬ a.rest; n ¬ n + 1;
ENDLOOP;
IF n < 8
THEN r ¬
NIL
ELSE {r ¬ b.rest; b.rest ¬ NIL};
};
Canonicalize:
PUBLIC
PROC [rectangleList:
LIST
OF
SF.Box]
RETURNS [Polygon] ~ {
b: LIST OF SF.Box ¬ SplitOffSecondHalf[rectangleList];
a: LIST OF SF.Box ¬ rectangleList;
IF b =
NIL
THEN {
WHILE a #
NIL
DO
a1: LIST OF SF.Box ¬ a;
a ¬ a1.rest;
a1.rest ¬ NIL;
IF SFInline.Nonempty[a1.first] THEN b ¬ FullyDestructiveUnion[b, a1];
ENDLOOP;
RETURN [b]
}
ELSE RETURN [FullyDestructiveUnion[Canonicalize[a], Canonicalize[b]]];
};
CreateFromBoxes:
PUBLIC
PROC [boxes:
SF.BoxGenerator]
RETURNS [Polygon] ~ {
head: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ head;
new: LIST OF SF.Box ¬ NIL;
AddBox:
PROC [box:
SF.Box] ~ {
IF SFInline.Nonempty[box]
THEN {
IF last.rest = NIL THEN last.rest ¬ GetScratch[];
last ¬ last.rest;
last.first ¬ box;
};
};
boxes[AddBox];
{t: LIST OF SF.Box ¬ last.rest; last.rest ¬ NIL; new ¬ head.rest; head.rest ¬ t};
FreeScratch[head]; head ¬ last ¬ NIL;
RETURN [Validate[new ! InvalidManhattanPolygon => CONTINUE]];
RETURN [Canonicalize[new]];
};
BoundingBox:
PUBLIC
PROC [polygon: Polygon]
RETURNS [
SF.Box] ~ {
IF polygon #
NIL
THEN {
bmins: INTEGER ¬ polygon.first.min.s;
bminf: INTEGER ¬ polygon.first.min.f;
bmaxs: INTEGER ¬ polygon.first.max.s;
bmaxf: INTEGER ¬ polygon.first.max.f;
FOR each: Polygon ¬ polygon.rest, each.rest
UNTIL each=
NIL
DO
emins: INTEGER = each.first.min.s;
eminf: INTEGER = each.first.min.f;
emaxs: INTEGER = each.first.max.s;
emaxf: INTEGER = each.first.max.f;
IF emins < bmins THEN bmins ¬ emins;
IF eminf < bminf THEN bminf ¬ eminf;
IF emaxs > bmaxs THEN bmaxs ¬ emaxs;
IF emaxf > bmaxf THEN bmaxf ¬ emaxf;
ENDLOOP;
RETURN [[min: [s: bmins, f: bminf], max: [s: bmaxs, f: bmaxf]]];
};
RETURN [[min: [s: 0, f: 0], max: [s: 0, f: 0]]];
};
CountBoxes:
PUBLIC
PROC [polygon: Polygon]
RETURNS [boxes:
INT ¬ 0] ~ {
WHILE polygon #
NIL
DO
boxes ¬ boxes + 1;
polygon ¬ polygon.rest;
ENDLOOP;
};
CountRuns:
PUBLIC
PROC [polygon: Polygon]
RETURNS [runs:
INT ¬ 0] ~ {
WHILE polygon #
NIL
DO
runs ¬ runs + NAT[polygon.first.max.s-polygon.first.min.s];
polygon ¬ polygon.rest;
ENDLOOP;
};
TestCreate:
PROC [polygon: Polygon]
RETURNS [Polygon] ~ {
Runs:
PROC [run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT], repeat:
PROC[timesToRepeatScanline:
NAT]] ~ {
boxAction:
SF.BoxAction ~ {
run[sMin: box.min.s, fMin: box.min.f, fSize: box.max.f-box.min.f]
};
Map[polygon: polygon, boxAction: boxAction, runs: TRUE];
};
RETURN [CreateFromRuns[Runs]]
};
Map:
PUBLIC
PROC [polygon: Polygon, boxAction:
SF.BoxAction, runs:
BOOL ¬
FALSE] ~ {
IF runs
THEN {
WHILE polygon #
NIL
DO
sMinRow: INTEGER ~ polygon.first.min.s;
sMaxRow: INTEGER ~ polygon.first.max.s;
FOR s:
INTEGER
IN [sMinRow..sMaxRow)
DO
FOR t: Polygon ¬ polygon, t.rest
UNTIL (t =
NIL
OR t.first.min.s # sMinRow)
DO
boxAction[[min: [s: s, f: t.first.min.f], max: [s: s+1, f: t.first.max.f]]];
ENDLOOP;
ENDLOOP;
UNTIL (polygon =
NIL
OR polygon.first.min.s # sMinRow)
DO
polygon ¬ polygon.rest;
ENDLOOP;
ENDLOOP;
}
ELSE {
FOR each: Polygon ¬ polygon, each.rest
UNTIL each=
NIL
DO
boxAction[each.first];
ENDLOOP;
};
};
Clip:
PUBLIC
PROC [polygon: Polygon, box:
SF.Box, boxAction:
SF.BoxAction, runs:
BOOL] ~ {
IF runs
THEN {
row: Polygon ¬ polygon;
WHILE row#
NIL
DO
smin: INTEGER ~ row.first.min.s;
smax: INTEGER ~ row.first.max.s;
IF smax<=box.min.s THEN NULL
ELSE IF smin>=box.max.s THEN EXIT
ELSE
FOR s:
INTEGER
IN [
MAX[smin, box.min.s]..
MIN[smax, box.max.s])
DO
run: SF.Box ¬ [min: [s: s, f: 0], max: [s: s+1, f: 0]];
FOR t: Polygon ¬ row, t.rest
UNTIL t=
NIL
OR t.first.min.s#smin
DO
fmin: INTEGER ~ t.first.min.f;
fmax: INTEGER ~ t.first.max.f;
IF fmax<=box.min.f THEN NULL
ELSE IF fmin>=box.max.f THEN EXIT
ELSE {
run.min.f ¬ MAX[fmin, box.min.f];
run.max.f ¬ MIN[fmax, box.max.f];
boxAction[run];
};
ENDLOOP;
ENDLOOP;
UNTIL row=NIL OR row.first.min.s#smin DO row ¬ row.rest ENDLOOP;
ENDLOOP;
}
ELSE {
FOR each: Polygon ¬ polygon, each.rest
UNTIL each=
NIL
DO
IF each.first.max.s<=box.min.s
THEN
NULL
ELSE IF each.first.min.s>=box.max.s THEN EXIT
ELSE {
clippedBox: SF.Box ~ SFInline.Intersect[each.first, box];
IF SFInline.Nonempty[clippedBox] THEN boxAction[clippedBox];
};
ENDLOOP;
};
};
IsVisible:
PUBLIC
PROC [mask, clipper: Polygon]
RETURNS [visibility: Visibility] ~ {
IF mask = NIL OR clipper = NIL THEN RETURN [invisible];
IF mask.rest =
NIL
AND clipper.rest =
NIL
THEN {
sMin: INTEGER ~ MAX[mask.first.min.s, clipper.first.min.s];
sMax: INTEGER ~ MIN[mask.first.max.s, clipper.first.max.s];
fMin: INTEGER ~ MAX[mask.first.min.f, clipper.first.min.f];
fMax: INTEGER ~ MIN[mask.first.max.f, clipper.first.max.f];
IF sMax <= sMin OR fMax <= fMin THEN RETURN [invisible];
IF mask.first = [min: [s: sMin, f: fMin], max: [s: sMax, f: fMax]]
THEN
RETURN [visible];
RETURN [partlyVisible];
}
ELSE {
intersection: Polygon ¬ Intersection[mask, clipper];
visibility ¬
IF intersection =
NIL
THEN invisible
ELSE IF Equal[intersection, mask] THEN visible
ELSE partlyVisible;
Destroy[intersection];
intersection ¬ NIL;
};
};
ClipBoxToMask:
PUBLIC
PROC [box:
SF.Box, mask: Polygon, action:
PROC [
SF.Box]] ~ {
bmins: INTEGER = box.min.s;
bminf: INTEGER = box.min.f;
bmaxs: INTEGER = box.max.s;
bmaxf: INTEGER = box.max.f;
IF bmins < bmaxs
AND bminf < bmaxf
THEN
FOR list:
LIST
OF
SF.Box ¬ mask, list.rest
UNTIL list=
NIL
DO
mins: INTEGER ¬ list.first.min.s;
maxs: INTEGER ¬ list.first.max.s;
IF bmins > mins THEN mins ¬ bmins;
IF bmaxs < maxs THEN maxs ¬ bmaxs;
IF mins < maxs
THEN {
minf: INTEGER ¬ list.first.min.f;
maxf: INTEGER ¬ list.first.max.f;
IF bminf > minf THEN minf ¬ bminf;
IF bmaxf < maxf THEN maxf ¬ bmaxf;
IF minf < maxf THEN action[[min: [s: mins, f: minf], max: [s: maxs, f: maxf]]];
};
ENDLOOP;
};
Equal:
PUBLIC
PROC [a, b: Polygon]
RETURNS [
BOOLEAN] ~ {
WHILE a#
NIL
AND b#
NIL
AND a#b
DO
IF a.first # b.first THEN RETURN [FALSE];
a ¬ a.rest;
b ¬ b.rest;
ENDLOOP;
RETURN [a = b];
};
FromList:
PROC [numbers:
LIST
OF
REF]
RETURNS [new:
LIST
OF
SF.Box] ~ {
For creating a new list via the debugger.
scratch: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ scratch;
WHILE numbers #
NIL
DO
sMin: REF INT ¬ NARROW[numbers.first];
fMin: REF INT ¬ NARROW[numbers.rest.first];
sMax: REF INT ¬ NARROW[numbers.rest.rest.first];
fMax: REF INT ¬ NARROW[numbers.rest.rest.rest.first];
IF last.rest = NIL THEN {last.rest ¬ GetScratch[]};
last ¬ last.rest;
last.first ¬ [[sMin, fMin], [sMax, fMax]];
numbers ¬ numbers.rest.rest.rest.rest;
ENDLOOP;
IF last = scratch
THEN { new ¬ NIL }
ELSE {
new ¬ scratch.rest;
scratch.rest ¬ last.rest;
last.rest ¬ NIL;
};
};
Free list management
globalAvail: LIST OF SF.Box ¬ NIL;
availCount: INT ¬ 0;
availLimit: INT ¬ 1000;
scratchChunkSize: NAT ¬ 8;
CreateFromBox:
PUBLIC
ENTRY
PROC [box:
SF.Box]
RETURNS [polygon: Polygon] ~ {
ENABLE UNWIND => NULL; -- RRA: no reasonable errors in here
IF SFInline.Empty[box] THEN RETURN [NIL];
IF availCount = 0 THEN RETURN [LIST[box]];
polygon ¬ globalAvail;
polygon.first ¬ box;
globalAvail ¬ polygon.rest;
polygon.rest ¬ NIL;
availCount ¬ availCount - 1;
};
GetScratch:
ENTRY
PROC
RETURNS [scratch:
LIST
OF
SF.Box] ~ {
ENABLE UNWIND => NULL; -- RRA: no reasonable errors in here
empty: SF.Box ~ [[0, 0], [0, 0]];
t: LIST OF SF.Box;
Consistency check:
t ← globalAvail; FOR i: INT IN [0..availCount) DO t ← t.rest ENDLOOP; IF t#NIL THEN ERROR;
WHILE availCount < scratchChunkSize
DO
globalAvail ¬ CONS[empty, globalAvail];
availCount ¬ availCount + 1;
ENDLOOP;
scratch ¬ t ¬ globalAvail;
THROUGH [0..scratchChunkSize-1) DO t ¬ t.rest ENDLOOP;
globalAvail ¬ t.rest;
availCount ¬ availCount - scratchChunkSize;
t.rest ¬ NIL;
};
FreeScratch:
ENTRY
PROC [scratch:
LIST
OF
SF.Box] ~ {
ENABLE UNWIND => NULL; -- RRA: no reasonable errors in here
limit: INT ¬ MAX[availLimit, 0];
IF scratch #
NIL
THEN {
t: LIST OF SF.Box ¬ scratch;
UNTIL t.rest =
NIL
DO
t ¬ t.rest;
availCount ¬ availCount + 1;
ENDLOOP;
availCount ¬ availCount + 1;
t.rest ¬ globalAvail;
globalAvail ¬ scratch;
};
WHILE availCount > limit
DO
t: LIST OF SF.Box ¬ globalAvail;
globalAvail ¬ globalAvail.rest;
t.rest ¬ NIL;
availCount ¬ availCount - 1;
ENDLOOP;
};