ImagerManhattanImpl.mesa
Michael Plass, February 13, 1984 10:05:19 am 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.sSizesize;
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: INTEGERMIN[as, bs];
duplicates: NATMIN[aReader.repeatCount, bReader.repeatCount];
somethingInScanline: BOOLEANFALSE;
WHILE s = aReader.s OR s = bReader.s DO
fStart: INTEGERLAST[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: BOOLEANFALSE;
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: INTEGERMAX[aReader.fMin, bReader.fMin];
fMax: INTEGERMIN[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: INTEGERMIN[universe.sMin, bb.sMin];
fMin: INTEGERMIN[universe.fMin, bb.fMin];
sMax: INTEGERMAX[universe.sMin + universe.sSize, bb.sMin + bb.sSize];
fMax: INTEGERMAX[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: INTEGERLAST[INTEGER];
sMax, fMax: INTEGERFIRST[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: INTEGERFIRST[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[mask.first.sMin + mask.first.sSize, clipper.first.sMin+clipper.first.sSize];
fMin: INTEGER ~ MAX[mask.first.fMin, clipper.first.fMin];
fMax: INTEGER ~ MIN[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 INTNARROW[numbers.first];
fMin: REF INTNARROW[numbers.rest.first];
sSize: REF INTNARROW[numbers.rest.rest.first];
fSize: REF INTNARROW[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: INTMAX[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.