<> <> <> <> DIRECTORY ImagerManhattan USING [Polygon, Visibility], SF USING [Add, Box, BoxAction, Empty, Intersect, Max, Min, Nonempty, Vec]; ImagerManhattanImpl: CEDAR MONITOR IMPORTS SF EXPORTS ImagerManhattan ~ BEGIN OPEN ImagerManhattan, SF; InvalidManhattanPolygon: PUBLIC ERROR ~ CODE; Validate: PUBLIC PROC [polygon: Polygon] RETURNS [Polygon] ~ { IF polygon # NIL THEN { a: Polygon _ polygon; b: Polygon _ polygon.rest; IF Empty[a.first] THEN ERROR InvalidManhattanPolygon; UNTIL b = NIL DO IF Empty[b.first] THEN ERROR InvalidManhattanPolygon; IF NOT ( (a.first.min.s = b.first.min.s AND a.first.max.s = b.first.max.s AND a.first.max.f <= b.first.min.f) OR a.first.max.s <= b.first.min.s ) 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 Box _ GetScratch[]; last: LIST OF Box _ scratch; secondLastRowStart: LIST OF Box _ NIL; lastRowStart: LIST OF Box _ last; secondLastRowCount: INTEGER _ -1; lastRowCount: INTEGER _ 0; Run: PROC[sMin, fMin: INTEGER, fSize: NAT] ~ { fMaxCurrent: INTEGER ~ last.first.max.f; IF 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 Box _ lastRowStart; THROUGH [0..lastRowCount) DO t.first.max.s _ t.first.max.s + timesToRepeatScanline; t _ t.rest; ENDLOOP; }; last.first _ [[0, 0], [0, 0]]; 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; }; IF scratch.first.max.f>scratch.first.min.f 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 Box, boxesPerRow: INT] RETURNS [success: BOOLEAN] ~ { <> <> <> <> max: INTEGER; s: LIST OF Box _ secondLastRowStart; t: LIST OF 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 Box] ~ { FreeScratch[rectangleList]; }; Copy: PUBLIC PROC [polygon: Polygon] RETURNS [copy: Polygon] ~ { scratch: LIST OF Box _ GetScratch[]; last: LIST OF 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 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 { IF r.s >= s THEN RETURN; WHILE r.s < s DO IF r.currentRow = r.currentBox AND r.repeatCount > 1 THEN { delta: INTEGER _ MIN[r.repeatCount-1, s-r.s]; r.s _ r.s + delta; r.repeatCount _ r.repeatCount - delta; } ELSE Advance[r]; ENDLOOP; }; TestReader: PROC [polygon: Polygon] ~ { reader: Reader _ NewReader[polygon]; Run: PROC [box: 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 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: Box] RETURNS [inverse: Polygon] ~ { c: LIST OF Box _ GetScratch[]; last: LIST OF Box _ c; bb: 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 Box _ b, p.rest UNTIL p=NIL DO r: 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];>> <> }; Difference: PUBLIC PROC [a, b: Polygon] RETURNS [diff: Polygon] ~ { bb: 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]; }; <> }; Shift: PUBLIC PROC [polygon: Polygon, sShift, fShift: INTEGER] ~ { shift: Vec ~ [s: sShift, f: fShift]; WHILE polygon # NIL DO polygon.first.min _ Add[polygon.first.min, shift]; polygon.first.max _ 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: 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 Box] RETURNS [r: LIST OF Box] ~ { b: LIST OF 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 Box] RETURNS [Polygon] ~ { b: LIST OF Box _ SplitOffSecondHalf[rectangleList]; a: LIST OF Box _ rectangleList; IF b = NIL THEN { WHILE a # NIL DO a1: LIST OF Box _ a; a _ a1.rest; a1.rest _ NIL; IF Nonempty[a1.first] THEN b _ FullyDestructiveUnion[b, a1]; ENDLOOP; RETURN [b] } ELSE RETURN [FullyDestructiveUnion[Canonicalize[a], Canonicalize[b]]]; }; BoundingBox: PUBLIC PROC [polygon: Polygon] RETURNS [Box] ~ { box: Box _ [min: [s: 0, f: 0], max: [s: 0, f: 0]]; IF polygon#NIL THEN { box _ polygon.first; FOR each: Polygon _ polygon.rest, each.rest UNTIL each=NIL DO box.min _ box.min.Min[each.first.min]; box.max _ box.max.Max[each.first.max]; ENDLOOP; }; RETURN[box]; }; 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: 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: BoxAction, runs: BOOL _ FALSE] ~ { IF runs THEN { WHILE polygon # NIL DO sMinRow: NAT ~ polygon.first.min.s; sMaxRow: NAT ~ polygon.first.max.s; FOR s: NAT 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: Box, boxAction: BoxAction, runs: BOOL] ~ { IF runs THEN { row: Polygon _ polygon; WHILE row#NIL DO smin: NAT ~ row.first.min.s; smax: NAT ~ row.first.max.s; IF smax<=box.min.s THEN NULL ELSE IF smin>=box.max.s THEN EXIT ELSE FOR s: NAT IN [MAX[smin, box.min.s]..MIN[smax, box.max.s]) DO run: 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: NAT ~ t.first.min.f; fmax: NAT ~ 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: Box ~ each.first.Intersect[box]; IF clippedBox.Nonempty 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 = [[sMin, fMin], [sMax, 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; }; }; 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 Box] ~ { <> scratch: LIST OF Box _ GetScratch[]; last: LIST OF 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; }; }; <> globalAvail: LIST OF Box _ NIL; availCount: INT _ 0; availLimit: INT _ 1000; scratchChunkSize: NAT _ 8; CreateFromBox: PUBLIC ENTRY PROC [deviceRectangle: Box] RETURNS [polygon: Polygon] ~ { ENABLE UNWIND => NULL; IF Empty[deviceRectangle] 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 Box] ~ { ENABLE UNWIND => NULL; empty: Box ~ [[0, 0], [0, 0]]; t: LIST OF Box; <> <> 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 Box] ~ { ENABLE UNWIND => NULL; limit: INT _ MAX[availLimit, 0]; IF scratch # NIL THEN { t: LIST OF 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 Box _ globalAvail; globalAvail _ globalAvail.rest; t.rest _ NIL; availCount _ availCount - 1; ENDLOOP; }; END.