ImagerManhattanImpl.mesa
Copyright (C) 1984, Xerox Corporation. All rights reserved.
Michael Plass, November 8, 1984 3:29:29 pm PST
DIRECTORY ImagerManhattan;
ImagerManhattanImpl:
CEDAR MONITOR
EXPORTS ImagerManhattan ~ BEGIN OPEN ImagerManhattan;
InvalidManhattanPolygon:
PUBLIC
ERROR ~
CODE;
Validate:
PUBLIC
PROC [polygon: Polygon]
RETURNS [Polygon] ~ {
IF polygon #
NIL
THEN {
a: Polygon ← polygon;
b: Polygon ← polygon.rest;
IF a.first.sSize = 0 OR a.first.sSize = 0 THEN ERROR InvalidManhattanPolygon;
UNTIL b =
NIL
DO
IF b.first.sSize = 0 OR b.first.sSize = 0 THEN ERROR InvalidManhattanPolygon;
IF
NOT (
(a.first.sMin = b.first.sMin AND a.first.sSize = b.first.sSize AND a.first.fMin+a.first.fSize <= b.first.fMin)
OR a.first.sMin+a.first.sSize <= b.first.sMin
)
THEN ERROR InvalidManhattanPolygon;
a ← b;
b ← b.rest;
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 DeviceRectangle ← GetScratch[];
last: LIST OF DeviceRectangle ← scratch;
secondLastRowStart: LIST OF DeviceRectangle ← NIL;
lastRowStart: LIST OF DeviceRectangle ← last;
secondLastRowCount: INTEGER ← -1;
lastRowCount: INTEGER ← 0;
Run:
PROC[sMin, fMin:
INTEGER, fSize:
NAT] ~ {
fMaxCurrent: INTEGER ~ last.first.fMin+last.first.fSize;
IF sMin = last.first.sMin
THEN {
IF last.first.sSize # 1 THEN ERROR;
SELECT fMin
FROM
= fMaxCurrent => {last.first.fSize ← last.first.fSize + fSize};
> fMaxCurrent => {
IF last.rest = NIL THEN last.rest ← GetScratch[];
last ← last.rest;
last.first ← [sMin: sMin, fMin: fMin, sSize: 1, fSize: fSize];
lastRowCount ← lastRowCount + 1;
};
ENDCASE => ERROR;
}
ELSE {
IF secondLastRowCount = lastRowCount
AND secondLastRowStart.first.sMin + secondLastRowStart.first.sSize = lastRowStart.first.sMin
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 ← [sMin: sMin, fMin: fMin, sSize: 1, fSize: fSize];
lastRowStart ← last;
lastRowCount ← 1;
IF secondLastRowStart.first.sMin + secondLastRowStart.first.sSize > sMin THEN ERROR;
};
};
Repeat:
PROC[timesToRepeatScanline:
NAT] ~ {
t: LIST OF DeviceRectangle ← lastRowStart;
THROUGH [0..lastRowCount)
DO
t.first.sSize ← t.first.sSize + timesToRepeatScanline;
t ← t.rest;
ENDLOOP;
};
last.first ← [FIRST[INTEGER], FIRST[INTEGER], 0, 0];
runs[Run, Repeat];
IF secondLastRowCount = lastRowCount
AND secondLastRowStart.first.sMin + secondLastRowStart.first.sSize = lastRowStart.first.sMin
AND TryToMergeRows[secondLastRowStart, lastRowCount]
THEN {
last ← secondLastRowStart;
THROUGH [0..lastRowCount-1)
DO
last ← last.rest;
ENDLOOP;
};
IF scratch.first.fSize # 0
THEN {
polygon ← scratch;
scratch ← last.rest;
last.rest ← NIL;
}
ELSE IF last = scratch THEN polygon ← NIL
ELSE {
polygon ← scratch.rest;
scratch.rest ← last.rest;
last.rest ← NIL;
};
FreeScratch[scratch];
};
TryToMergeRows:
PROC [secondLastRowStart:
LIST
OF DeviceRectangle, 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.
size: NAT;
s: LIST OF DeviceRectangle ← secondLastRowStart;
t: LIST OF DeviceRectangle ← 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.fMin # t.first.fMin OR s.first.fSize # t.first.fSize THEN RETURN [FALSE];
s ← s.rest; t ← t.rest;
ENDLOOP;
t ← s; s ← secondLastRowStart;
size ← s.first.sSize + t.first.sSize;
FOR i:
INT
IN [0..boxesPerRow)
DO
s.first.sSize ← size;
s ← s.rest;
ENDLOOP;
RETURN [TRUE];
};
Destroy:
PUBLIC
PROC [rectangleList:
LIST
OF DeviceRectangle] ~ {
FreeScratch[rectangleList];
};
Copy:
PUBLIC
PROC [polygon: Polygon]
RETURNS [copy: Polygon] ~ {
scratch: LIST OF DeviceRectangle ← GetScratch[];
last: LIST OF DeviceRectangle ← 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 DeviceRectangle
];
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.sMin,
fMin: polygon.first.fMin,
fMax: polygon.first.fMin+polygon.first.fSize,
repeatCount: polygon.first.sSize,
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.sMin # r.currentRow.first.sMin
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.sSize;
r.s ← next.first.sMin;
};
};
IF next = NIL THEN r^ ← [LAST[INTEGER], 0, 0, 0, TRUE, NIL, NIL]
ELSE {
r.fMin ← next.first.fMin;
r.fMax ← r.fMin + next.first.fSize;
r.currentBox ← next;
IF r.repeatCount = 0 THEN Advance[r];
};
};
SkipTo:
UNSAFE
PROC [r:
POINTER
TO Reader, s:
INTEGER] ~
UNCHECKED {
IF r.s >= s THEN RETURN;
WHILE r.s < s DO Advance[r] ENDLOOP;
};
TestReader:
PROC [polygon: Polygon] ~ {
reader: Reader ← NewReader[polygon];
Run:
PROC [sMin, fMin:
INTEGER, fSize:
NAT] ~ {
IF reader.done THEN ERROR;
IF sMin # reader.s THEN ERROR;
IF fMin # reader.fMin THEN ERROR;
IF fMin+fSize # reader.fMax THEN ERROR;
TRUSTED {Advance[@reader]};
};
MapRuns[polygon, Run];
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 duplicates > 0
THEN {
IF somethingInScanline THEN repeat[duplicates];
SkipTo[@aReader, s+1+duplicates];
SkipTo[@bReader, s+1+duplicates];
};
ENDLOOP;
};
RETURN[CreateFromRuns[Runs]];
};
Invert:
PROC [b: Polygon, universe: DeviceRectangle]
RETURNS [inverse: Polygon] ~ {
c: LIST OF DeviceRectangle ← GetScratch[];
last: LIST OF DeviceRectangle ← c;
bb: DeviceRectangle ← BoundingBox[b];
sMin: INTEGER ← MIN[universe.sMin, bb.sMin];
fMin: INTEGER ← MIN[universe.fMin, bb.fMin];
sMax: INTEGER ← MAX[universe.sMin + universe.sSize, bb.sMin + bb.sSize];
fMax: INTEGER ← MAX[universe.fMin + universe.fSize, bb.fMin + bb.fSize];
Emit:
PROC [s0, f0, s1, f1:
INTEGER] ~ {
s0 ← MAX[s0, universe.sMin];
s1 ← MIN[s1, universe.sMin+universe.sSize];
f0 ← MAX[f0, universe.fMin];
f1 ← MIN[f1, universe.fMin+universe.fSize];
IF s0 < s1
AND f0 < f1
THEN {
IF last.rest = NIL THEN last.rest ← GetScratch[];
last ← last.rest;
last.first ← [s0, f0, s1-s0, f1-f0];
};
};
s: INTEGER ← sMin;
f: INTEGER ← fMax;
FOR p:
LIST
OF DeviceRectangle ← b, p.rest
UNTIL p=
NIL
DO
r: DeviceRectangle ~ p.first;
IF r.sMin > sMin
OR p=b
THEN {
Emit[sMin, f, s, fMax];
f ← fMin;
sMin ← s;
s ← r.sMin;
Emit[sMin, f, s, fMax];
sMin ← s;
s ← r.sMin + r.sSize;
};
IF sMin # r.sMin OR s # r.sMin + r.sSize THEN ERROR;
Emit[sMin, f, s, r.fMin];
f ← r.fMin + r.fSize;
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: DeviceRectangle ← 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] ~ {
IPair: TYPE ~ RECORD [s, f: INTEGER];
WHILE polygon #
NIL
DO
[polygon.first.sMin, polygon.first.fMin] ← IPair[polygon.first.sMin + sShift, polygon.first.fMin + fShift];
polygon ← polygon.rest;
ENDLOOP;
};
DestructiveUnion:
PUBLIC
PROC [a, b: Polygon]
RETURNS [u: Polygon] ~ {
u ← Union[a, b];
FreeScratch[a];
FreeScratch[b];
};
SplitOffSecondHalf:
PROC [a:
LIST
OF DeviceRectangle]
RETURNS [r:
LIST
OF DeviceRectangle] ~ {
b: LIST OF DeviceRectangle ← 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 DeviceRectangle]
RETURNS [Polygon] ~ {
b: LIST OF DeviceRectangle ← SplitOffSecondHalf[rectangleList];
a: LIST OF DeviceRectangle ← rectangleList;
IF b =
NIL
THEN {
WHILE a #
NIL
DO
a1: LIST OF DeviceRectangle ← a;
a ← a1.rest;
a1.rest ← NIL;
IF a1.first.sSize > 0 AND a1.first.fSize > 0 THEN b ← DestructiveUnion[b, a1];
ENDLOOP;
RETURN [b]
}
ELSE RETURN [DestructiveUnion[Canonicalize[a], Canonicalize[b]]];
};
BoundingBox:
PUBLIC
PROC [polygon: Polygon]
RETURNS [DeviceRectangle] ~ {
sMin, fMin: INTEGER ← LAST[INTEGER];
sMax, fMax: INTEGER ← FIRST[INTEGER];
WHILE polygon #
NIL
DO
r: DeviceRectangle ← polygon.first;
IF r.sSize # 0
AND r.fSize # 0
THEN {
sMin ← MIN[sMin, r.sMin];
fMin ← MIN[fMin, r.fMin];
sMax ← MAX[sMax, r.sMin+r.sSize];
fMax ← MAX[fMax, r.fMin+r.fSize];
};
polygon ← polygon.rest;
ENDLOOP;
IF sMin > sMax THEN {sMin ← fMin ← sMax ← fMax ← 0};
RETURN [[sMin: sMin, fMin: fMin, sSize: sMax-sMin, fSize: fMax-fMin]]
};
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 + polygon.first.sSize;
polygon ← polygon.rest;
ENDLOOP;
};
TestCreate:
PROC [polygon: Polygon]
RETURNS [Polygon] ~ {
Runs:
PROC[
run: PROC[sMin, fMin: INTEGER, fSize: NAT],
repeat: PROC[timesToRepeatScanline: NAT]] ~ {MapRuns[polygon, run]};
RETURN [CreateFromRuns[Runs]]
};
MapRuns:
PUBLIC
PROC [polygon: Polygon, run:
PROC [sMin, fMin:
INTEGER, fSize:
NAT]] ~ {
s: INTEGER ← FIRST[INTEGER];
WHILE polygon #
NIL
DO
sMinRow: INTEGER ~ polygon.first.sMin;
sMaxRow: INTEGER ~ sMinRow + polygon.first.sSize;
FOR s:
INTEGER
IN [sMinRow..sMaxRow)
DO
FOR t: Polygon ← polygon, t.rest
UNTIL (t =
NIL
OR t.first.sMin # sMinRow)
DO
run[s, t.first.fMin, t.first.fSize];
ENDLOOP;
ENDLOOP;
UNTIL (polygon =
NIL
OR polygon.first.sMin # sMinRow)
DO
polygon ← polygon.rest;
ENDLOOP;
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.sMin, clipper.first.sMin];
sMax:
INTEGER ~
MIN[
INT[mask.first.sMin] + mask.first.sSize, clipper.first.sMin+clipper.first.sSize];
the INTs are here because 15 bits might not be enough.
fMin: INTEGER ~ MAX[mask.first.fMin, clipper.first.fMin];
fMax: INTEGER ~ MIN[INT[mask.first.fMin] + mask.first.fSize, clipper.first.fMin+clipper.first.fSize];
IF sMax <= sMin OR fMax <= fMin THEN RETURN [invisible];
IF mask.first = [sMin, fMin, sMax-sMin, fMax-fMin] 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;
};
};
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 DeviceRectangle] ~ {
For creating a new list via the debugger.
scratch: LIST OF DeviceRectangle ← GetScratch[];
last: LIST OF DeviceRectangle ← scratch;
WHILE numbers #
NIL
DO
sMin: REF INT ← NARROW[numbers.first];
fMin: REF INT ← NARROW[numbers.rest.first];
sSize: REF INT ← NARROW[numbers.rest.rest.first];
fSize: REF INT ← NARROW[numbers.rest.rest.rest.first];
IF last.rest = NIL THEN {last.rest ← GetScratch[]};
last ← last.rest;
last.first ← [sMin^, fMin^, sSize^, fSize^];
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 DeviceRectangle ← NIL;
availCount: INT ← 0;
availLimit: INT ← 1000;
scratchChunkSize:
NAT ← 8;
CreateFromBox:
PUBLIC
ENTRY
PROC [deviceRectangle: DeviceRectangle]
RETURNS [polygon: Polygon] ~ {
ENABLE UNWIND => NULL;
IF deviceRectangle.sSize = 0 OR deviceRectangle.fSize = 0 THEN RETURN [NIL];
IF availCount = 0 THEN RETURN [LIST[deviceRectangle]];
polygon ← globalAvail;
polygon.first ← deviceRectangle;
globalAvail ← polygon.rest;
polygon.rest ← NIL;
availCount ← availCount - 1;
};
GetScratch:
ENTRY
PROC
RETURNS [scratch:
LIST
OF DeviceRectangle] ~ {
ENABLE UNWIND => NULL;
empty: DeviceRectangle ~ [0, 0, 0, 0];
t: LIST OF DeviceRectangle;
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 DeviceRectangle] ~ {
ENABLE UNWIND => NULL;
limit: INT ← MAX[availLimit, 0];
IF scratch #
NIL
THEN {
t: LIST OF DeviceRectangle ← 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 DeviceRectangle ← globalAvail;
globalAvail ← globalAvail.rest;
t.rest ← NIL;
availCount ← availCount - 1;
ENDLOOP;
};
END.