<> <> <<>> <> <> <> DIRECTORY Inline USING [BITAND, BITOR, BITSHIFT, BITXOR, LongDiv, LongMult], ImagerBasic USING [Pair, Bezier], Real USING [FixC, FScale, RoundC, RoundI, SqRt], RealFns USING [ArcTan, Cos, Sin], Runtime USING [BoundsFault], ScanConverter, ShowTime USING [GetMark]; ScanConverterImpl: CEDAR MONITOR IMPORTS Inline, Real, RealFns, Runtime, ShowTime EXPORTS ScanConverter = BEGIN Pair: TYPE ~ ImagerBasic.Pair; Bezier: TYPE ~ ImagerBasic.Bezier; <<>> <> lgXScale: NAT ~ 6; xScale: NAT ~ 64; -- must be a power of two. flatness: REAL _ 4; -- 1/max allowed error in pixels. <<>> <> deviceMax: REAL _ 32000; -- Must be strictly less than fixedMax, preferably with a comfortable margin. Too small a margin will lead to excess subdivisions in the pruning step. fixedMax: REAL _ LAST[NAT]-1; <<>> <> maxPointTableSize: NAT _ LAST[NAT]/2; <<>> <> BITAND: PROC [a, b: CARDINAL] RETURNS[CARDINAL] ~ INLINE {RETURN[Inline.BITAND[a,b]]}; BITANDI: PROC [a, b: INTEGER] RETURNS[INTEGER] ~ INLINE {RETURN[Inline.BITAND[a,b]]}; BITOR: PROC [a, b: CARDINAL] RETURNS[CARDINAL] ~ INLINE {RETURN[Inline.BITOR[a,b]]}; BITXOR: PROC [a, b: CARDINAL] RETURNS[CARDINAL] ~ INLINE {RETURN[Inline.BITXOR[a,b]]}; Shift: PROC [a: CARDINAL, b: INTEGER] RETURNS[CARDINAL] ~ INLINE {RETURN[Inline.BITSHIFT[a,b]]}; ShortScaledFloor: PROC [a: CARDINAL] RETURNS[NAT] ~ INLINE {RETURN[Inline.BITSHIFT[a, -lgXScale]]}; Mid: PROC [a, b: CARDINAL] RETURNS[CARDINAL] ~ INLINE {RETURN[Inline.BITSHIFT[(a+b),-1]]}; FloorI: PROC [r: REAL] RETURNS[t: INTEGER] ~ { t _ Real.RoundI[r]; IF t > r THEN t _ t-1 }; CeilingI: PROC [r: REAL] RETURNS[t: INTEGER] ~ { t _ Real.RoundI[r]; IF t < r THEN t _ t+1 }; Cubic: TYPE ~ REF CubicRec; CubicRec: TYPE ~ RECORD [ xorg, yorg: INTEGER, -- in device units yScale: CARDINAL, yOffset: CARDINAL, yFirstScan: INTEGER, -- yFirstScan + 1/2 defines the first scan line that crosses this piece. scanCount: NAT, -- number of scan lines that cross this piece. ascending: BOOLEAN, exclude: BOOLEAN, iterationsUntilFlat: [0..32), outlineNumber: [0..512), x0: CARDINAL, x1, y1: CARDINAL, x2, y2: CARDINAL, x3, y3: CARDINAL <> <<(xi/xScale + 1/2 + xorg, (yi+yOffset)/yScale + yorg)>> ]; DevicePath: PUBLIC TYPE ~ REF DevicePathRec; DevicePathRec: PUBLIC TYPE ~ RECORD [ length: NAT _ 0, numberOfOutlines: NAT _ 0, excludingOutlines: NAT _ 0, ymin: INTEGER _ LAST[INTEGER], ymax: INTEGER _ FIRST[INTEGER], excluding: BOOLEAN, seq: REF DevicePathSeqRec ]; DevicePathSeqRec: TYPE ~ RECORD [ SEQUENCE maxLength: NAT OF Cubic ]; ShortPair: TYPE ~ RECORD [x, y: CARDINAL]; crude: BOOLEAN _ FALSE; XVcalls: INT _ 0; XViterations: INT _ 0; Stats: PROC RETURNS[calls, iterations: INT, average: REAL] ~ { calls _ XVcalls; iterations _ XViterations; average _ IF calls=0 THEN 0.0 ELSE iterations/(calls+0.0); XVcalls _ XViterations _ 0; }; dlay: CARDINAL _ 500; dbug: BOOLEAN = FALSE; ShowCubicRec: PROC [cubic: CubicRec, yRel: CARDINAL] ~ { <> <> <> <<[] _ dc.SetPaintMode[invert];>> <> <> <> <> <> <> <> <> }; XValueFor: PROC [cubic: Cubic, yMinusHalf: INTEGER] RETURNS[ans: INTEGER] ~ { cubicRec: CubicRec _ cubic^; {OPEN cubicRec; yRel: CARDINAL _ NAT[(yMinusHalf - yorg) * yScale + Shift[yScale, -1] - yOffset]; XVcalls _ XVcalls + 1; XViterations _ XViterations + iterationsUntilFlat; IF dbug THEN ShowCubicRec[cubicRec, yRel]; IF yRel > y3 THEN RETURN [ShortScaledFloor[x3]+xorg]; IF crude THEN RETURN [ShortScaledFloor[x3]+xorg]; THROUGH [0..iterationsUntilFlat) DO abx, aby, bcx, bcy: CARDINAL; IF y3 > LAST[CARDINAL]/8 THEN { y3 _ Shift[y3, -1]; y2 _ Shift[y2, -1]; y1 _ Shift[y1, -1]; yRel _ Shift[yRel, -1]; }; abx _ x0 + 2*x1 + x2; aby _ 2*y1 + y2; bcx _ x1 + 2*x2 + x3; bcy _ y1 + 2*y2 + y3; IF Shift[yRel, 3] < aby+bcy THEN { [x3, y3] _ ShortPair[Shift[abx+bcx+7, -3], Shift[aby+bcy+3, -2]]; [x2, y2] _ ShortPair[Shift[abx+3, -2], Shift[aby, -1]]; x1 _ Shift[x0+x1, -1]; yRel _ 2*yRel; } ELSE { yShift: CARDINAL _ Shift[aby+bcy+3, -2]; x0 _ Shift[abx+bcx+7, -3]; [x1, y1] _ ShortPair[Shift[bcx+3, -2], Shift[bcy, -1] - yShift]; [x2, y2] _ ShortPair[Shift[x2+x3, -1], y2+y3 - yShift]; y3 _ 2*y3 - yShift; yRel _ 2*yRel - yShift; }; IF dbug THEN ShowCubicRec[cubicRec, yRel]; ENDLOOP; IF yRel > y3 THEN ERROR; IF y3=0 OR BITAND[BITXOR[x0, x3], LAST[CARDINAL]-(xScale-1)] = 0 THEN ans _ ShortScaledFloor[x0] + xorg ELSE IF x3>x0 THEN ans _ xorg + ShortScaledFloor[x0 + Inline.LongDiv[Inline.LongMult[yRel, x3-x0], y3]] ELSE ans _ xorg + ShortScaledFloor[x3 + Inline.LongDiv[Inline.LongMult[y3-yRel, x0-x3], y3]]; }}; Allocate: PUBLIC PROC RETURNS[devicePath: DevicePath] ~ { devicePath _ NEW[DevicePathRec]; devicePath.length _ 0; devicePath.numberOfOutlines _ 0; devicePath.excludingOutlines _ 0; devicePath.ymin _ LAST[INTEGER]; devicePath.ymax _ FIRST[INTEGER]; devicePath.seq _ NEW[DevicePathSeqRec[10]]; }; Release: PUBLIC PROC [devicePath: DevicePath] ~ {devicePath _ NIL}; <> Reset: PUBLIC PROC [devicePath: DevicePath] ~ { devicePath.length _ 0; devicePath.numberOfOutlines _ 0; devicePath.excludingOutlines _ 0; devicePath.ymin _ LAST[INTEGER]; devicePath.ymax _ FIRST[INTEGER]; }; ExtendDevicePath: PROC [devicePath: DevicePath] RETURNS[cubic: Cubic] ~ { cubic _ IF devicePath.length < devicePath.seq.maxLength THEN devicePath.seq[devicePath.length] ELSE NIL; IF cubic = NIL THEN cubic _ NEW[CubicRec]; IF devicePath.length = devicePath.seq.maxLength THEN { new: REF DevicePathSeqRec _ NEW[ DevicePathSeqRec[MIN[LAST[NAT]-3, devicePath.length+devicePath.length/3+1]] ]; FOR i: NAT IN [0..devicePath.length) DO new[i] _ devicePath.seq[i]; ENDLOOP; <> devicePath.seq _ new; }; devicePath.seq[devicePath.length] _ cubic; devicePath.length _ devicePath.length + 1; }; IterationsUntilFlat: PROC [b: Bezier] RETURNS[iterationsUntilFlat: NAT] ~ { deltaX: REAL ~ b.b3.x - b.b0.x; deltaY: REAL ~ b.b3.y - b.b0.y; theta: REAL ~ RealFns.ArcTan[deltaY, deltaX]; cos: REAL ~ RealFns.Cos[theta]; sin: REAL ~ RealFns.Sin[theta]; y1: REAL ~ (b.b1.y-b.b0.y)*cos - (b.b1.x-b.b0.x)*sin; y2: REAL ~ (b.b2.y-b.b0.y)*cos - (b.b2.x-b.b0.x)*sin; r: REAL ~ IF ABS[y2] > 0 THEN y1/y2 ELSE 10.0; e: REAL _ MAX[ABS[y1], ABS[y2]]*flatness; iterationsUntilFlat _ 0; WHILE e>1 DO iterationsUntilFlat _ iterationsUntilFlat+1; e _ Real.FScale[e, -1]; ENDLOOP; IF r IN [0.5..2.0] THEN iterationsUntilFlat _ Shift[iterationsUntilFlat * 695 + 1023, -10]; }; AppendMonotoneShortPiece: PROC [devicePath: DevicePath, b: Bezier, xmin: REAL] ~ { cubic: Cubic ~ ExtendDevicePath[devicePath]; xorg: REAL ~ (cubic.xorg _ FloorI[xmin-0.5]); yScale: CARDINAL _ 1; lgYScale: CARDINAL _ 0; yDelta: REAL _ ABS[b.b0.y-b.b3.y]; ymin, yorg: REAL; WHILE yScale {IF cubicI.yFirstScan + cubicI.scanCount # cubicJ.yFirstScan THEN ERROR}; iup AND (NOT jup) => {IF cubicI.yFirstScan + cubicI.scanCount # cubicJ.yFirstScan + cubicJ.scanCount THEN ERROR}; (NOT iup) AND jup => {IF cubicI.yFirstScan # cubicJ.yFirstScan THEN ERROR}; (NOT iup) AND (NOT jup) => {IF cubicI.yFirstScan # cubicJ.yFirstScan + cubicJ.scanCount THEN ERROR}; ENDCASE => ERROR; ENDLOOP; }; Clip: PROC [p: Pair] RETURNS[Pair] ~ { RETURN[[MAX[MIN[p.x, fixedMax], -fixedMax], MAX[MIN[p.y, fixedMax], -fixedMax]]]; }; AppendMonotoneBezier: PROC [devicePath: DevicePath, bezier: Bezier] ~ { SubDivide: PROC ~ { Mid: PROC [a, b: REAL] RETURNS[REAL] ~ INLINE{RETURN[Real.FScale[a+b, -1]]}; a: Pair _ [Mid[bezier.b0.x, bezier.b1.x], Mid[bezier.b0.y, bezier.b1.y]]; b: Pair _ [Mid[bezier.b1.x, bezier.b2.x], Mid[bezier.b1.y, bezier.b2.y]]; c: Pair _ [Mid[bezier.b2.x, bezier.b3.x], Mid[bezier.b2.y, bezier.b3.y]]; ab: Pair _ [Mid[a.x, b.x], Mid[a.y, b.y]]; bc: Pair _ [Mid[b.x, c.x], Mid[b.y, c.y]]; abc: Pair _ [Mid[ab.x, bc.x], Mid[ab.y, bc.y]]; AppendMonotoneBezier[devicePath, [bezier.b0, a, ab, abc]]; AppendMonotoneBezier[devicePath, [abc, bc, c, bezier.b3]]; }; xmin: REAL ~ MIN[bezier.b0.x, bezier.b1.x, bezier.b2.x, bezier.b3.x]; xmax: REAL ~ MAX[bezier.b0.x, bezier.b1.x, bezier.b2.x, bezier.b3.x]; yEndMin: REAL ~ MIN[bezier.b0.y, bezier.b3.y]; ymin: REAL ~ MIN[yEndMin, bezier.b1.y, bezier.b2.y]; ymax: REAL ~ MAX[bezier.b0.y, bezier.b1.y, bezier.b2.y, bezier.b3.y]; xAbsMax: REAL ~ MAX[ABS[xmin], ABS[xmax]]; yAbsMax: REAL ~ MAX[ABS[ymin], ABS[ymax]]; IF xAbsMax > fixedMax OR yAbsMax > fixedMax THEN { IF (yAbsMax <= fixedMax AND (xmin >= deviceMax OR xmax <= -deviceMax)) OR (xAbsMax <= fixedMax AND (ymin >= deviceMax OR ymax <= -deviceMax)) OR MIN[ABS[xmin],ABS[xmax],ABS[ymin],ABS[ymax]] >= deviceMax THEN { AppendMonotoneBezier[devicePath, [Clip[bezier.b0],Clip[bezier.b1],Clip[bezier.b2],Clip[bezier.b3]]]; } ELSE SubDivide[]; } ELSE IF xmax - xmin <= LAST[CARDINAL]/(8*xScale) AND ymax - ymin <= LAST[CARDINAL]/8 AND bezier.b1.y >= yEndMin AND bezier.b2.y >= yEndMin THEN { AppendMonotoneShortPiece[devicePath, bezier, xmin]; IF NOT devicePath.excluding THEN { devicePath.ymin _ MIN[devicePath.ymin, FloorI[ymin]]; devicePath.ymax _ MAX[devicePath.ymax, CeilingI[ymax]]; }; } ELSE SubDivide[]; }; Interpolate: PROC [t: REAL, a, b: Pair] RETURNS[r: Pair] ~ {RETURN [[a.x*(1-t)+b.x*t, a.y*(1-t)+b.y*t]]}; SubDivide: PROC [b: Bezier, t: REAL] RETURNS[low, high: Bezier] ~ BEGIN OPEN b; q1, q2, q3, qp1, qp2, q: Pair; q1 _ Interpolate[t, b0, b1]; q2 _ Interpolate[t, b1, b2]; q3 _ Interpolate[t, b2, b3]; qp1 _ Interpolate[t, q1, q2]; qp2 _ Interpolate[t, q2, q3]; q _ Interpolate[t, qp1, qp2]; low _ [b0: b0, b1: q1, b2: qp1, b3: q]; high _ [b0: q, b1: qp2, b2: q3, b3: b3]; END; AppendBezier: PROC [devicePath: DevicePath, b: Bezier] ~ { <> c0: REAL ~ b.b0.y; c1: REAL ~ 3*(b.b1.y - c0); t: REAL ~ 3*(b.b2.y - b.b1.y); c2: REAL ~ t - c1; c3: REAL ~ b.b3.y - c0 - t; <> d0: REAL ~ c1; d1: REAL ~ 2*c2; d2: REAL ~ 3*c3; <> t0, t1: REAL _ -1; tt0, tt1: REAL _ -1; IF ABS[d2] > 0 THEN { b: REAL ~ d1/d2; c: REAL ~ d0/d2; d: REAL ~ b*b-4*c; IF d>=0 THEN { sqrt: REAL ~ Real.SqRt[d]; t0 _ (-b-(IF b>0 THEN sqrt ELSE -sqrt))/2.0; t1 _ IF ABS[t0] > 0 THEN c/t0 ELSE 0.0; }; } ELSE IF ABS[d1] > 0 THEN t0 _ -d0/d1; <> t0 _ MIN[1.0, MAX[0.0, t0]]; t1 _ MIN[1.0, MAX[0.0, t1]]; IF t0 > t1 THEN {t: REAL _ t0; t0 _ t1; t1 _ t}; IF 0.0 < t0 AND t0 < t1 AND t1 < 1.0 THEN { low, middle, high: Bezier; [middle, high] _ SubDivide[b, t1]; [low, middle] _ SubDivide[middle, t0/t1]; Delta[low.b2.y-low.b3.y]; low.b2.y _ low.b3.y; Delta[middle.b1.y-middle.b0.y]; middle.b1.y _ middle.b0.y; Delta[middle.b2.y-middle.b3.y]; middle.b2.y _ middle.b3.y; Delta[high.b1.y-high.b0.y]; high.b1.y _ high.b0.y; AppendMonotoneBezier[devicePath, low]; AppendMonotoneBezier[devicePath, middle]; AppendMonotoneBezier[devicePath, high]; } ELSE IF t0 IN (0.0..1.0) OR t1 IN (0.0..1.0) THEN { low, high: Bezier; [low, high] _ SubDivide[b, IF t0 IN (0.0..1.0) THEN t0 ELSE t1]; Delta[low.b2.y-low.b3.y]; low.b2.y _ low.b3.y; Delta[high.b1.y-high.b0.y]; high.b1.y _ high.b0.y; AppendMonotoneBezier[devicePath, low]; AppendMonotoneBezier[devicePath, high]; } ELSE AppendMonotoneBezier[devicePath, b]; }; numberOfDeltas: INT _ 0; sumOfAbsDeltas: REAL _ 0.0; maxDelta: REAL _ 0.0; Delta: PROC [delta: REAL] ~ { <> numberOfDeltas _ numberOfDeltas + 1; sumOfAbsDeltas _ sumOfAbsDeltas + ABS[delta]; IF ABS[delta] > maxDelta THEN maxDelta _ ABS[delta]; }; DeltaStats: PROC RETURNS[n: INT, sum: REAL, max: REAL] ~ { n _ numberOfDeltas; sum _ sumOfAbsDeltas; max _ maxDelta; numberOfDeltas _ 0; sumOfAbsDeltas _ maxDelta _ 0.0; }; PushPath: PUBLIC PROC [devicePath: DevicePath, gen: PROC [move: PROC [Pair], line: PROC [Pair], curve: PROC [Pair, Pair, Pair]], exclude: BOOLEAN ] ~ { firstPoint, lastPoint: Pair; started: BOOLEAN _ FALSE; outlineStart: NAT _ devicePath.length; startingLength: NAT ~ devicePath.length; Move: PROC [v: Pair] ~ { IF started THEN Close[] ELSE started _ TRUE; outlineStart _ devicePath.length; firstPoint _ lastPoint _ v; }; Line: PROC [v: Pair] ~ { IF NOT started THEN Move[[0,0]]; AppendBezier[devicePath, [lastPoint, Interpolate[0.333333, lastPoint, v], Interpolate[0.666667, lastPoint, v], v]]; lastPoint _ v; }; Curve: PROC [v1, v2, v3: Pair] ~ { IF NOT started THEN Move[[0,0]]; AppendBezier[devicePath, [lastPoint, v1, v2, v3]]; lastPoint _ v3; }; Close: PROC ~ { IF lastPoint # firstPoint THEN Line[firstPoint]; FixUpJoints[devicePath, outlineStart, devicePath.length]; }; devicePath.excluding _ exclude; gen[Move, Line, Curve]; IF started THEN Close[]; devicePath.numberOfOutlines _ devicePath.numberOfOutlines + 1; IF devicePath.length > startingLength AND exclude THEN devicePath.excludingOutlines _ devicePath.excludingOutlines + 1; }; PopPath: PUBLIC PROC [devicePath: DevicePath] ~ { exclude: BOOLEAN _ FALSE; devicePath.numberOfOutlines _ devicePath.numberOfOutlines-1; IF devicePath.length > 0 AND devicePath.seq[devicePath.length-1].outlineNumber = devicePath.numberOfOutlines AND devicePath.seq[devicePath.length-1].exclude THEN devicePath.excludingOutlines _ devicePath.excludingOutlines - 1; WHILE devicePath.length > 0 AND devicePath.seq[devicePath.length-1].outlineNumber = devicePath.numberOfOutlines DO devicePath.length _ devicePath.length - 1; ENDLOOP; }; PointTable: TYPE ~ REF PointTableRec; PointTableRec: TYPE ~ RECORD [ SEQUENCE maxLength: NAT OF Point ]; OffsetInteger: TYPE ~ RECORD [valueMinusFirstInteger: CARDINAL]; Point: TYPE ~ RECORD [ x: INTEGER, wrapDelta: [-1..1], exclude: BOOLEAN, outlineNumber: [0..512) ]; shellD: ARRAY [1..11] OF CARDINAL ~ [1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 65535]; ShellSort: PROC [table: PointTable, start, length: NAT] ~ TRUSTED { IF length>0 THEN { passesPlusOne: [1..11] _ 1; startPtr: LONG POINTER TO Point _ @(table[start]); endPtr: LONG POINTER TO Point _ @(table[start+length-1]) + SIZE[Point]; UNTIL shellD[passesPlusOne _ passesPlusOne+1] >= length DO NULL ENDLOOP; FOR pass: NAT DECREASING IN [1..passesPlusOne) DO h: NAT _ shellD[pass]; hTimesSize: CARDINAL _ h*SIZE[Point]; FOR iPtr: LONG POINTER TO Point _ startPtr, iPtr + SIZE[Point] UNTIL iPtr = endPtr DO a: Point _ iPtr^; jPtr: LONG POINTER TO Point _ iPtr; b: LONG POINTER TO Point; WHILE LOOPHOLE[(b _ jPtr-hTimesSize), LONG CARDINAL] >= LOOPHOLE[startPtr, LONG CARDINAL] AND a.x < b^.x DO jPtr^ _ b^; jPtr _ b; ENDLOOP; jPtr^ _ a; ENDLOOP; ENDLOOP; }; }; WrapTable: TYPE ~ REF WrapTableRec; WrapTableRec: TYPE ~ RECORD [ SEQUENCE maxLength: NAT OF INTEGER ]; BucketTable: TYPE ~ REF BucketTableRec; BucketTableRec: TYPE ~ RECORD [maxXinLine: CARDINAL, seq: SEQUENCE length: NAT OF INTEGER]; InitialBucketTable: PROC [devicePath: DevicePath, ymin: INTEGER, ymax: INTEGER] RETURNS[bucketTable: BucketTable] ~ { maxXinLine: CARDINAL _ 0; bucketTable _ NEW[BucketTableRec[ymax-ymin+2]]; FOR i: NAT IN [0..bucketTable.length) DO bucketTable.seq[i] _ 0; ENDLOOP; FOR i: NAT IN [0..devicePath.length) DO cubic: Cubic ~ devicePath.seq[i]; start: INTEGER ~ MAX[cubic.yFirstScan, ymin]-ymin; end: INTEGER ~ MIN[cubic.yFirstScan+cubic.scanCount, ymax]-ymin; IF end > start THEN { bucketTable.seq[start] _ bucketTable.seq[start] + 1; bucketTable.seq[end] _ bucketTable.seq[end] - 1; }; ENDLOOP; {s1, s2: NAT _ 0; FOR i: NAT IN [0..bucketTable.length) DO s1 _ s1 + bucketTable.seq[i]; maxXinLine _ MAX[maxXinLine, s1]; bucketTable.seq[i] _ s2; s2 _ s2 + s1; ENDLOOP; }; bucketTable.maxXinLine _ maxXinLine; }; ScanConvert: PUBLIC PROC [devicePath: DevicePath, proc: PROC [x, y, w, h: INTEGER], ymin: INTEGER, ymax: INTEGER, parityFill: BOOLEAN] ~ { segmentCount: NAT ~ devicePath.length; yMin: INTEGER ~ MAX[ymin, devicePath.ymin]; yMax: INTEGER ~ MIN[ymax, devicePath.ymax]; IF yMax > yMin THEN { bucketTable: BucketTable _ InitialBucketTable[devicePath, yMin, yMax ! Runtime.BoundsFault => GOTO Bisect]; scanLineCrossings: NAT ~ bucketTable.seq[bucketTable.length-1]; parityMask: CARDINAL _ IF parityFill THEN 1 ELSE LAST[CARDINAL]; IF scanLineCrossings > maxPointTableSize AND yMax>yMin+1 THEN { m: INTEGER _ yMin; WHILE bucketTable.seq[m-yMin] * 2 < scanLineCrossings DO m _ m+1; ENDLOOP; bucketTable _ NIL; ScanConvert[devicePath, proc, yMin, m, parityFill]; ScanConvert[devicePath, proc, m, yMax, parityFill]; } ELSE { outlines: NAT ~ devicePath.numberOfOutlines; wrap: WrapTable ~ NEW[WrapTableRec[outlines]]; pointTable: PointTable ~ NEW[PointTableRec[scanLineCrossings]]; points: NAT _ 0; maxXinLine: INTEGER _ 0; PartA: PROC = { IF devicePath.excludingOutlines = devicePath.numberOfOutlines THEN ERROR; timeMarkAfterAllocates _ ShowTime.GetMark[]; FOR i: NAT IN [0..outlines) DO wrap[i] _ 0; ENDLOOP; FOR i: NAT IN [0..segmentCount) DO cubic: Cubic ~ devicePath.seq[i]; firstScan: INTEGER ~ MAX[cubic.yFirstScan, yMin]; endScan: INTEGER ~ MIN[cubic.yFirstScan+cubic.scanCount, ymax]; point: Point; point.wrapDelta _ IF cubic.ascending THEN +1 ELSE -1; point.exclude _ cubic.exclude; point.outlineNumber _ cubic.outlineNumber; FOR y: INTEGER IN [firstScan..endScan) DO x: INTEGER _ XValueFor[cubic, y]; IF ABS[y-yTrap] < 3 AND ABS[x-xTrap] < 3 THEN trapCount _ trapCount + 1; point.x _ x; TRUSTED { bPtr: LONG POINTER TO INTEGER _ @(bucketTable.seq[y-yMin]); pointTable[bPtr^] _ point; bPtr^ _ bPtr^ + 1; points _ points + 1; }; ENDLOOP; ENDLOOP; IF points # scanLineCrossings THEN ERROR; }; PartB: PROC = { activeWrapCount: INTEGER _ devicePath.excludingOutlines; y: INTEGER _ yMin; pointNumber: NAT _ 0; FOR line: NAT IN [0..bucketTable.length) DO y: INTEGER ~ yMin + line; firstPointOnNextLine: NAT ~ bucketTable.seq[line]; numberOfPointsOnLine: NAT ~ firstPointOnNextLine - pointNumber; xStart: INTEGER; IF numberOfPointsOnLine > 2 THEN ShellSort[pointTable, pointNumber, numberOfPointsOnLine] ELSE IF numberOfPointsOnLine = 2 THEN { p1, p2: Point; IF (p1 _ pointTable[pointNumber]).x > (p2 _ pointTable[pointNumber+1]).x THEN {pointTable[pointNumber] _ p2; pointTable[pointNumber+1] _ p1} }; WHILE pointNumber < firstPointOnNextLine DO point: Point ~ pointTable[pointNumber]; w: INTEGER _ wrap[point.outlineNumber]; pointNumber _ pointNumber + 1; IF point.exclude THEN { IF BITANDI[w, parityMask] = 0 THEN { IF activeWrapCount = outlines THEN proc[xStart, y, point.x-xStart, 1]; activeWrapCount _ activeWrapCount - 1; }; w _ w + point.wrapDelta; IF BITANDI[w, parityMask] = 0 THEN { activeWrapCount _ activeWrapCount + 1; IF activeWrapCount = outlines THEN xStart _ point.x; }; } ELSE { IF BITANDI[w, parityMask] = 0 THEN { activeWrapCount _ activeWrapCount + 1; IF activeWrapCount = outlines THEN xStart _ point.x; }; w _ w + point.wrapDelta; IF BITANDI[w, parityMask] = 0 THEN { IF activeWrapCount = outlines THEN proc[xStart, y, point.x-xStart, 1]; activeWrapCount _ activeWrapCount - 1; }; }; wrap[point.outlineNumber] _ w; ENDLOOP; ENDLOOP; }; PartA[]; timeMarkAfterEvals _ ShowTime.GetMark[]; timeMarkAfterSort _ ShowTime.GetMark[]; PartB[]; <> <> <> }; EXITS Bisect => { yMin: INTEGER ~ MAX[ymin, devicePath.ymin]; yMax: INTEGER ~ MIN[ymax, devicePath.ymax]; m: INTEGER ~ (yMax+yMin)/2; IF yMax <= yMin THEN RETURN; IF m=yMin THEN ERROR; ScanConvert[devicePath, proc, yMin, m, parityFill]; ScanConvert[devicePath, proc, m, yMax, parityFill]; }; }; }; trapCount: CARDINAL _ 0; xTrap, yTrap: INTEGER _ FIRST[INTEGER]; timeMarkAfterAllocates: PUBLIC LONG CARDINAL _ 0; timeMarkAfterEvals: PUBLIC LONG CARDINAL _ 0; timeMarkAfterSort: PUBLIC LONG CARDINAL _ 0; END. <> <> <>