<<>> <> <> <> <> <> <<>> DIRECTORY ImagerManhattan USING [Polygon, Visibility], SF USING [Box, BoxAction, BoxGenerator, Vec], SFInline USING [Add, Empty, Intersect, Nonempty]; ImagerManhattanImpl: CEDAR MONITOR IMPORTS SFInline EXPORTS ImagerManhattan ~ BEGIN 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; }; last = scratch => { polygon ¬ 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] ~ { <> <> <> <> 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];>> <> }; 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] }; <> }; 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] ~ { <> 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; }; }; <> 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] ~ { < 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] ~ { < NULL; -- RRA: no reasonable errors in here>> empty: SF.Box ~ [[0, 0], [0, 0]]; t: LIST OF SF.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 SF.Box] ~ { < 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; }; END.