<> <> 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] ~ { <> <> <> <> 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];>> <> }; 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]; }; <> }; 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[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] ~ { <> 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; }; }; <> 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; <> <> 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.