<> <> <> DIRECTORY Basics USING [BITAND, BITOR, BITSHIFT, bitsPerWord, BITXOR, LongDiv, LongMult], ImagerManhattan USING [CreateFromRuns], ImagerPixelMaps USING [BoundedWindow, Function], ImagerScanConverter, PrincOps USING [BBptr, BBTableSpace], PrincOpsUtils USING [AlignedBBTable, BITBLT], Real USING [FixC, FScale, RoundC, RoundI, SqRt], RealFns USING [ArcTan, Cos, Sin]; ImagerScanConverterImpl: CEDAR PROGRAM IMPORTS Basics, ImagerManhattan, ImagerPixelMaps, PrincOpsUtils, Real, RealFns EXPORTS ImagerScanConverter ~ BEGIN OPEN ImagerScanConverter; Bezier: TYPE ~ RECORD [s0, f0, s1, f1, s2, f2, s3, f3: REAL]; Pair: TYPE ~ RECORD [s, f: REAL]; <<-- These parameters control the precision with which the inner loop b subdivision is done. >> lgFScale: NAT ~ 6; fScale: NAT ~ 64; -- must be a power of two. flatness: REAL _ 4; -- 1/max allowed error in pixels. <<-- Some inlines for basic bit-hacking operations.>> BITAND: PROC [a, b: CARDINAL] RETURNS[CARDINAL] ~ INLINE {RETURN[Basics.BITAND[a, b]]}; BITANDI: PROC [a, b: INTEGER] RETURNS[INTEGER] ~ INLINE {RETURN[LOOPHOLE[Basics.BITAND[LOOPHOLE[a], LOOPHOLE[b]]]]}; BITOR: PROC [a, b: CARDINAL] RETURNS[CARDINAL] ~ INLINE {RETURN[Basics.BITOR[a, b]]}; BITXOR: PROC [a, b: CARDINAL] RETURNS[CARDINAL] ~ INLINE {RETURN[Basics.BITXOR[a, b]]}; Shift: PROC [a: CARDINAL, b: INTEGER] RETURNS [CARDINAL] ~ INLINE {RETURN[Basics.BITSHIFT[a, b]]}; ShortScaledFloor: PROC [a: CARDINAL] RETURNS [INTEGER] ~ INLINE {RETURN[Basics.BITSHIFT[a, -lgFScale]]}; Mid: PROC [a, b: CARDINAL] RETURNS[CARDINAL] ~ INLINE {RETURN[Basics.BITSHIFT[(a+b),-1]]}; FloorI: PROC [r: REAL] RETURNS [t: INTEGER] ~ INLINE {t _ Real.RoundI[r]; IF t > r THEN t _ t-1}; CeilingI: PROC [r: REAL] RETURNS [t: INTEGER] ~ INLINE {t _ Real.RoundI[r]; IF t < r THEN t _ t+1}; deltaWrap: ARRAY Direction OF INTEGER ~ [1, -1]; FValueFor: PROC [piece: LIST OF PieceRep, sMinusHalf: INTEGER] RETURNS [ans: INTEGER] ~ { ShortPair: TYPE ~ RECORD [a, b: CARDINAL]; p: PieceRep _ piece.first; sRel: CARDINAL _ NAT[(sMinusHalf - p.sOrg) * p.sScale + Shift[p.sScale, -1] - p.sOffset]; IF sRel > p.s3 THEN RETURN [ShortScaledFloor[p.f3]+p.fOrg]; THROUGH [0..p.iterationsUntilFlat) DO sAB, fAB, sBC, fBC: CARDINAL; IF p.s3 > LAST[CARDINAL]/8 THEN { p.s3 _ Shift[p.s3, -1]; p.s2 _ Shift[p.s2, -1]; p.s1 _ Shift[p.s1, -1]; sRel _ Shift[sRel, -1]; }; fAB _ p.f0 + 2*p.f1 + p.f2; sAB _ 2*p.s1 + p.s2; fBC _ p.f1 + 2*p.f2 + p.f3; sBC _ p.s1 + 2*p.s2 + p.s3; IF Shift[sRel, 3] < sAB+sBC THEN { [p.s3, p.f3] _ ShortPair[Shift[sAB+sBC+3, -2], Shift[fAB+fBC+7, -3]]; [p.s2, p.f2] _ ShortPair[Shift[sAB, -1], Shift[fAB+3, -2]]; p.f1 _ Shift[p.f0+p.f1, -1]; sRel _ 2*sRel; } ELSE { sShift: CARDINAL _ Shift[sAB+sBC+3, -2]; p.f0 _ Shift[fAB+fBC+7, -3]; [p.s1, p.f1] _ ShortPair[Shift[sBC, -1] - sShift, Shift[fBC+3, -2]]; [p.s2, p.f2] _ ShortPair[p.s2+p.s3 - sShift, Shift[p.f2+p.f3, -1]]; p.s3 _ 2*p.s3 - sShift; sRel _ 2*sRel - sShift; }; ENDLOOP; IF sRel > p.s3 THEN ERROR; IF p.s3=0 OR BITAND[BITXOR[p.f0, p.f3], LAST[CARDINAL]-(fScale-1)] = 0 THEN ans _ ShortScaledFloor[p.f0] + p.fOrg ELSE IF p.f3>p.f0 THEN ans _ p.fOrg + ShortScaledFloor[p.f0 + Basics.LongDiv[Basics.LongMult[sRel, p.f3-p.f0], p.s3]] ELSE ans _ p.fOrg + ShortScaledFloor[p.f3 + Basics.LongDiv[Basics.LongMult[p.s3-sRel, p.f0-p.f3], p.s3]]; }; IterationsUntilFlat: PROC [b: Bezier] RETURNS [iterationsUntilFlat: NAT] ~ { deltaX: REAL ~ b.s3 - b.s0; deltaY: REAL ~ b.f3 - b.f0; <> theta: REAL ~ RealFns.ArcTan[deltaY, deltaX]; cos: REAL ~ RealFns.Cos[theta]; sin: REAL ~ RealFns.Sin[theta]; y1: REAL ~ (b.f1-b.f0)*cos - (b.s1-b.s0)*sin; y2: REAL ~ (b.f2-b.f0)*cos - (b.s2-b.s0)*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 _ (iterationsUntilFlat * 695 + 1023)/1024; }; marginSize: REAL _ 8.0; Interpolate: PROC [t: REAL, a, b: Pair] RETURNS[r: Pair] ~ {RETURN [[a.s*(1-t)+b.s*t, a.f*(1-t)+b.f*t]]}; SubDivide: PROC [b: Bezier, t: REAL] RETURNS[low, high: Bezier] ~ BEGIN b0: Pair ~ [b.s0, b.f0]; b1: Pair ~ [b.s1, b.f1]; b2: Pair ~ [b.s2, b.f2]; b3: Pair ~ [b.s3, b.f3]; 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.s, b0.f, q1.s, q1.f, qp1.s, qp1.f, q.s, q.f]; high _ [q.s, q.f, qp2.s, qp2.f, q3.s, q3.f, b3.s, b3.f]; END; CreatePath: PUBLIC PROC [ pathProc: ImagerScanConverter.PathProc, clipBox: ImagerScanConverter.DeviceRectangle, scratch: DevicePath _ NIL -- for re-use of storage ] RETURNS [DevicePath] ~ { devicePath: DevicePathRep; AppendSegment: PROC [s0, f0, s1, f1: REAL] ~ { segment: SegmentRep; IF s1 < s0 THEN { segment.direction _ decreasing; segment.s0 _ s1; segment.f0 _ f1; segment.s1 _ s0; segment.f1 _ f0; } ELSE { segment.direction _ increasing; segment.s0 _ s0; segment.f0 _ f0; segment.s1 _ s1; segment.f1 _ f1; }; segment.sFirstScan _ CeilingI[segment.s0-0.5]; segment.scanCount _ CeilingI[segment.s1-0.5] - segment.sFirstScan; IF segment.scanCount # 0 THEN { devicePath.scanLineCrossings _ devicePath.scanLineCrossings + segment.scanCount; IF segment.sFirstScan < devicePath.sMin THEN devicePath.sMin _ segment.sFirstScan; IF segment.sFirstScan + INTEGER[segment.scanCount] > devicePath.sMax THEN devicePath.sMax _ segment.sFirstScan + segment.scanCount; devicePath.fMin _ MIN[devicePath.fMin, FloorI[segment.f0], FloorI[segment.f1]]; devicePath.fMax _ MAX[devicePath.fMax, CeilingI[segment.f0], CeilingI[segment.f1]]; IF scratch = NIL OR scratch.segmentList = NIL THEN devicePath.segmentList _ CONS[segment, devicePath.segmentList] ELSE { t: LIST OF SegmentRep _ scratch.segmentList; scratch.segmentList _ t.rest; t.rest _ devicePath.segmentList; t.first _ segment; devicePath.segmentList _ t; }; }; }; AppendMonotoneShortPiece: PROC [b: Bezier, fMin: REAL] ~ { iterationsUntilFlat: NAT _ IterationsUntilFlat[b]; IF iterationsUntilFlat = 0 THEN AppendSegment[b.s0, b.f0, b.s3, b.f3] ELSE { piece: PieceRep; fOrg: REAL ~ (piece.fOrg _ FloorI[fMin-0.5]); sDelta: REAL _ ABS[b.s0-b.s3]; sMin, sOrg: REAL; lgSScale: CARDINAL _ 0; piece.sScale _ 1; WHILE piece.sScale devicePath.sMax THEN devicePath.sMax _ piece.sFirstScan + piece.scanCount; IF piece.fOrg < devicePath.fMin THEN devicePath.fMin _ piece.fOrg; devicePath.fMax _ MAX[devicePath.fMax, piece.fOrg + ShortScaledFloor[MAX[piece.f0, piece.f1, piece.f2, piece.f3]]+1]; IF scratch = NIL OR scratch.pieceList = NIL THEN devicePath.pieceList _ CONS[piece, devicePath.pieceList] ELSE { t: LIST OF PieceRep _ scratch.pieceList; scratch.pieceList _ t.rest; t.rest _ devicePath.pieceList; t.first _ piece; devicePath.pieceList _ t; }; }; }; }; sInnerMin: REAL _ MAX[-REAL[LAST[NAT]-2], REAL[clipBox.sMin]]; sInnerMax: REAL _ MIN[REAL[LAST[NAT]-2], REAL[clipBox.sMin] + clipBox.sSize]; fInnerMin: REAL _ MAX[-REAL[LAST[NAT]-2], REAL[clipBox.fMin]]; fInnerMax: REAL _ MIN[REAL[LAST[NAT]-2], REAL[clipBox.fMin] + clipBox.fSize]; sOuterMin: REAL _ MAX[-REAL[LAST[NAT]-1], sInnerMin - marginSize]; sOuterMax: REAL _ MIN[REAL[LAST[NAT]-1], sInnerMax + marginSize]; fOuterMin: REAL _ MAX[-REAL[LAST[NAT]-1], fInnerMin - marginSize]; fOuterMax: REAL _ MIN[REAL[LAST[NAT]-1], fInnerMax + marginSize]; ClipS: PROC [s: REAL] RETURNS [REAL] ~ {RETURN[MAX[MIN[s, sOuterMax], sOuterMin]]}; ClipF: PROC [f: REAL] RETURNS [REAL] ~ {RETURN[MAX[MIN[f, fOuterMax], fOuterMin]]}; AppendMonotoneBezier: PROC [bezier: Bezier] ~ { SubDivide: PROC ~ { Mid: PROC [a, b: REAL] RETURNS[REAL] ~ INLINE {RETURN[Real.FScale[a+b, -1]]}; a: Pair _ [Mid[bezier.s0, bezier.s1], Mid[bezier.f0, bezier.f1]]; b: Pair _ [Mid[bezier.s1, bezier.s2], Mid[bezier.f1, bezier.f2]]; c: Pair _ [Mid[bezier.s2, bezier.s3], Mid[bezier.f2, bezier.f3]]; ab: Pair _ [Mid[a.s, b.s], Mid[a.f, b.f]]; bc: Pair _ [Mid[b.s, c.s], Mid[b.f, c.f]]; abc: Pair _ [Mid[ab.s, bc.s], Mid[ab.f, bc.f]]; AppendMonotoneBezier[[bezier.s0, bezier.f0, a.s, a.f, ab.s, ab.f, abc.s, abc.f]]; AppendMonotoneBezier[[abc.s, abc.f, bc.s, bc.f, c.s, c.f, bezier.s3, bezier.f3]]; }; fMin: REAL ~ MIN[bezier.f0, bezier.f1, bezier.f2, bezier.f3]; fMax: REAL ~ MAX[bezier.f0, bezier.f1, bezier.f2, bezier.f3]; sEndMin: REAL ~ MIN[bezier.s0, bezier.s3]; sMin: REAL ~ MIN[sEndMin, bezier.s1, bezier.s2]; sMax: REAL ~ MAX[bezier.s0, bezier.s1, bezier.s2, bezier.s3]; sMinRegion: INTEGER _ SELECT sMin FROM < sOuterMin => -2, < sInnerMin => -1, <= sInnerMax => 0, <= sOuterMax => 1, ENDCASE => 2; fMinRegion: INTEGER _ SELECT fMin FROM < fOuterMin => -2, < fInnerMin => -1, <= fInnerMax => 0, <= fOuterMax => 1, ENDCASE => 2; sMaxRegion: INTEGER _ SELECT sMax FROM < sOuterMin => -2, < sInnerMin => -1, <= sInnerMax => 0, <= sOuterMax => 1, ENDCASE => 2; fMaxRegion: INTEGER _ SELECT fMax FROM < fOuterMin => -2, < fInnerMin => -1, <= fInnerMax => 0, <= fOuterMax => 1, ENDCASE => 2; IF MAX[ABS[sMinRegion], ABS[fMinRegion], ABS[sMinRegion], ABS[fMinRegion]] <= 1 THEN { IF sMax-sMin <= LAST[CARDINAL]/8 AND bezier.s1 >= sEndMin AND bezier.s2 >= sEndMin AND fMax-fMin <= LAST[CARDINAL]/(8*fScale) THEN AppendMonotoneShortPiece[bezier, fMin] ELSE SubDivide[]; } ELSE IF sMinRegion > 0 OR sMaxRegion < 0 OR fMinRegion > 0 OR fMaxRegion < 0 THEN AppendMonotoneBezier[[ ClipS[bezier.s0], ClipF[bezier.f0], ClipS[bezier.s1], ClipF[bezier.f1], ClipS[bezier.s2], ClipF[bezier.f2], ClipS[bezier.s3], ClipF[bezier.f3] ]] ELSE SubDivide[]; }; AppendBezier: PROC [b: Bezier] ~ { <> c0: REAL ~ b.s0; c1: REAL ~ 3*(b.s1 - c0); t: REAL ~ 3*(b.s2 - b.s1); c2: REAL ~ t - c1; c3: REAL ~ b.s3 - 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]; <> low.s2 _ low.s3; middle.s1 _ middle.s0; middle.s2 _ middle.s3; high.s1 _ high.s0; AppendMonotoneBezier[low]; AppendMonotoneBezier[middle]; AppendMonotoneBezier[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]; <> low.s2 _ low.s3; high.s1 _ high.s0; AppendMonotoneBezier[low]; AppendMonotoneBezier[high]; } ELSE AppendMonotoneBezier[b]; }; firstPoint, lastPoint: Pair; started: BOOLEAN _ FALSE; Move: PROC [s, f: REAL] ~ { IF started THEN Close[] ELSE started _ TRUE; firstPoint _ lastPoint _ [s, f]; }; Line: PROC [s, f: REAL] ~ { b1, b2: Pair; IF NOT started THEN Move[s, f]; IF lastPoint.s IN [sOuterMin..sOuterMax] AND lastPoint.f IN [fOuterMin..fOuterMax] AND s IN [sOuterMin..sOuterMax] AND f IN [fOuterMin..fOuterMax] THEN AppendSegment[lastPoint.s, lastPoint.f, s, f] ELSE { b1 _ Interpolate[0.333333, lastPoint, [s, f]]; b2 _ Interpolate[0.666667, lastPoint, [s, f]]; AppendBezier[[lastPoint.s, lastPoint.f, b1.s, b1.f, b2.s, b2.f, s, f]]; }; lastPoint _ [s, f]; }; Curve: PROC [s1, f1, s2, f2, s3, f3: REAL] ~ { IF NOT started THEN Move[s1, f1]; AppendBezier[[lastPoint.s, lastPoint.f, s1, f1, s2, f2, s3, f3]]; lastPoint _ [s3, f3]; }; Close: PROC ~ { IF lastPoint # firstPoint THEN Line[firstPoint.s, firstPoint.f]; }; devicePath.scanLineCrossings _ 0; devicePath.sMin _ LAST[INTEGER]; devicePath.sMax _ FIRST[INTEGER]; devicePath.fMin _ LAST[INTEGER]; devicePath.fMax _ FIRST[INTEGER]; pathProc[Move, Line, Curve]; IF started THEN Close[]; IF devicePath.sMin > devicePath.sMax THEN devicePath.sMin _ devicePath.sMax _ devicePath.fMin _ devicePath.fMax _ 0; IF scratch # NIL THEN { devicePath.pointTable _ scratch.pointTable; devicePath.bucketTable _ scratch.bucketTable; WHILE scratch.segmentList # NIL DO segmentList: LIST OF SegmentRep _ scratch.segmentList; scratch.segmentList _ scratch.segmentList.rest; segmentList.rest _ NIL; ENDLOOP; WHILE scratch.pieceList # NIL DO pieceList: LIST OF PieceRep _ scratch.pieceList; scratch.pieceList _ scratch.pieceList.rest; pieceList.rest _ NIL; ENDLOOP; scratch^ _ devicePath; RETURN [scratch] }; RETURN [NEW[DevicePathRep _ devicePath]]; }; shellD: ARRAY [1..11] OF CARDINAL ~ [1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 65535]; Key: PROC [point: Point] RETURNS [CARDINAL] ~ TRUSTED INLINE {RETURN[LOOPHOLE[point]]}; 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 Key[a] < Key[b^] DO jPtr^ _ b^; jPtr _ b; ENDLOOP; jPtr^ _ a; ENDLOOP; ENDLOOP; }; }; InitialBucketTable: PROC [devicePath: DevicePath, smin: INTEGER, smax: INTEGER, scratch: BucketTable] RETURNS [bucketTable: BucketTable] ~ { bucketTableSize: NAT _ smax - smin + 2; bucketTable _ IF scratch # NIL AND scratch.maxLength >= bucketTableSize THEN scratch ELSE NEW [BucketTableRec[bucketTableSize]]; bucketTable.length _ bucketTableSize; FOR i: NAT IN [0..bucketTableSize) DO bucketTable.seq[i] _ 0; ENDLOOP; FOR s: LIST OF SegmentRep _ devicePath.segmentList, s.rest UNTIL s = NIL DO start: INTEGER ~ MAX[s.first.sFirstScan, smin] - smin; end: INTEGER ~ MIN[s.first.sFirstScan+s.first.scanCount, smax] - smin; IF end > start THEN { bucketTable.seq[start] _ bucketTable.seq[start] + 1; bucketTable.seq[end] _ bucketTable.seq[end] - 1; }; ENDLOOP; FOR p: LIST OF PieceRep _ devicePath.pieceList, p.rest UNTIL p = NIL DO start: INTEGER ~ MAX[p.first.sFirstScan, smin] - smin; end: INTEGER ~ MIN[p.first.sFirstScan+p.first.scanCount, smax] - smin; IF end > start THEN { bucketTable.seq[start] _ bucketTable.seq[start] + 1; bucketTable.seq[end] _ bucketTable.seq[end] - 1; }; ENDLOOP; {sum, sumSum: NAT _ 0; FOR i: NAT IN [0..bucketTable.length) DO sum _ sum + bucketTable.seq[i]; bucketTable.seq[i] _ sumSum; sumSum _ sumSum + sum; ENDLOOP; }; }; BoundingBox: PUBLIC PROC [devicePath: DevicePath] RETURNS [ImagerScanConverter.DeviceRectangle] ~ { RETURN [[devicePath.sMin, devicePath.fMin, devicePath.sMax-devicePath.sMin, devicePath.fMax-devicePath.fMin]] }; NumberOfRuns: PUBLIC PROC [devicePath: DevicePath] RETURNS [numberOfRuns: INT] ~ { numberOfRuns _ devicePath.scanLineCrossings/2; }; maxBucketTableSize: NAT _ 808; maxPointTableSize: NAT _ 808*4; Convert: PROC [ devicePath: DevicePath, resultProc: PROC [devicePath: DevicePath, sStart, sEnd: INTEGER], clipBox: ImagerScanConverter.DeviceRectangle ] ~ { sStart: INTEGER _ MAX[clipBox.sMin, devicePath.sMin]; sFinal: INTEGER ~ MIN[INT[clipBox.sMin+clipBox.sSize], devicePath.sMax]; sEnd: INTEGER _ sFinal; fOrigin: INTEGER _ devicePath.fMin; bucketTable: BucketTable; WHILE sStart < sFinal DO IF sEnd - sStart > maxBucketTableSize THEN sEnd _ sStart + maxBucketTableSize; bucketTable _ devicePath.bucketTable _ InitialBucketTable[devicePath, sStart, sEnd, devicePath.bucketTable]; IF bucketTable.seq[bucketTable.length-1] > maxPointTableSize THEN { sEnd _ sStart; WHILE bucketTable.seq[sEnd-sStart] < maxPointTableSize DO sEnd _ sEnd+1; ENDLOOP; IF sEnd > sStart+1 THEN sEnd _ sEnd - 1; bucketTable _ devicePath.bucketTable _ InitialBucketTable[devicePath, sStart, sEnd, devicePath.bucketTable]; }; CHECKED { scanLineCrossings: NAT ~ bucketTable.seq[bucketTable.length-1]; pointTable: PointTable ~ devicePath.pointTable _ IF devicePath.pointTable # NIL AND devicePath.pointTable.maxLength >= scanLineCrossings THEN devicePath.pointTable ELSE NEW[PointTableRec[scanLineCrossings]]; points: NAT _ 0; FOR p: LIST OF SegmentRep _ devicePath.segmentList, p.rest UNTIL p = NIL DO firstScan: INTEGER ~ MAX[p.first.sFirstScan, sStart]; endScan: INTEGER ~ MIN[p.first.sFirstScan+p.first.scanCount, sEnd]; IF endScan > firstScan THEN TRUSTED { direction: Direction ~ p.first.direction; w: REAL ~ MAX[ABS[p.first.f1-p.first.f0], ABS[p.first.s1-p.first.s0]]; <> sDelta: INTEGER _ Real.RoundI[16536*(p.first.s1-p.first.s0)/w]; fDelta: INTEGER ~ Real.RoundI[16536*(p.first.f1-p.first.f0)/w]; fAbsDelta: INTEGER ~ ABS[fDelta]; fSignDelta: INTEGER ~ IF fAbsDelta = fDelta THEN 1 ELSE -1; sReal: REAL ~ firstScan + 0.5; fReal: REAL ~ p.first.f0 + (sReal-p.first.s0)*(p.first.f1-p.first.f0)/(p.first.s1-p.first.s0); f: INTEGER _ FloorI[fReal+0.5]; e: INTEGER _ IF fAbsDelta = fDelta THEN Real.RoundI[(f+0.5-fReal)*sDelta] ELSE Real.RoundI[(fReal-f+0.5)*sDelta]; bPtr: LONG POINTER TO INTEGER _ @(bucketTable.seq[firstScan-sStart]); IF sDelta <= 0 THEN { IF sDelta < 0 OR endScan # firstScan + 1 THEN ERROR; sDelta _ fAbsDelta; <> }; FOR s: INTEGER IN [firstScan..endScan) DO pointTable[bPtr^] _ [fRel: f-fOrigin, direction: direction]; bPtr^ _ bPtr^ + 1; points _ points + 1; bPtr _ bPtr + SIZE[INTEGER]; e _ e - fAbsDelta; WHILE e<0 DO f _ f + fSignDelta; e _ e + sDelta; ENDLOOP; ENDLOOP; }; ENDLOOP; FOR p: LIST OF PieceRep _ devicePath.pieceList, p.rest UNTIL p = NIL DO firstScan: INTEGER ~ MAX[p.first.sFirstScan, sStart]; endScan: INTEGER ~ MIN[p.first.sFirstScan+p.first.scanCount, sEnd]; direction: Direction _ p.first.direction; FOR s: INTEGER IN [firstScan..endScan) DO f: INTEGER _ FValueFor[p, s]; TRUSTED { bPtr: LONG POINTER TO INTEGER _ @(bucketTable.seq[s-sStart]); pointTable[bPtr^] _ [fRel: f-fOrigin, direction: direction]; bPtr^ _ bPtr^ + 1; points _ points + 1; }; ENDLOOP; ENDLOOP; IF points # scanLineCrossings THEN ERROR; resultProc[devicePath, sStart, sEnd]; }; sStart _ sEnd; sEnd _ sFinal; ENDLOOP; }; ConvertToRuns: PUBLIC PROC [ devicePath: DevicePath, runProc: PROC [sMin, fMin: INTEGER, fSize: NAT], clipBox: ImagerScanConverter.DeviceRectangle, parityFill: BOOLEAN _ FALSE ] ~ { Result: PROC [devicePath: DevicePath, sStart, sEnd: INTEGER] ~ { bucketTable: BucketTable ~ devicePath.bucketTable; pointTable: PointTable ~ devicePath.pointTable; parityMask: CARDINAL ~ IF parityFill THEN 1 ELSE LAST[CARDINAL]; scanLineCrossings: NAT ~ bucketTable.seq[bucketTable.length-1]; fOrigin: INTEGER ~ devicePath.fMin; wrap: INTEGER _ 0; pointNumber: NAT _ 0; FOR line: NAT IN [0..bucketTable.length) DO s: INTEGER ~ sStart + line; firstPointOnNextLine: NAT ~ bucketTable.seq[line]; numberOfPointsOnLine: NAT ~ firstPointOnNextLine - pointNumber; fStart: INTEGER; IF numberOfPointsOnLine = 2 THEN { p1, p2: Point; IF Key[p1 _ pointTable[pointNumber]] > Key[p2 _ pointTable[pointNumber+1]] THEN {pointTable[pointNumber] _ p2; pointTable[pointNumber+1] _ p1} } ELSE ShellSort[pointTable, pointNumber, numberOfPointsOnLine]; WHILE pointNumber < firstPointOnNextLine DO point: Point ~ pointTable[pointNumber]; pointNumber _ pointNumber + 1; IF BITANDI[wrap, parityMask] = 0 THEN fStart _ point.fRel + fOrigin; wrap _ wrap + deltaWrap[point.direction]; IF BITANDI[wrap, parityMask] = 0 THEN { fMin: INTEGER _ MAX[fStart, clipBox.fMin]; fMax: INTEGER _ MIN[point.fRel + fOrigin, clipBox.fMin+clipBox.fSize]; IF fMax > fMin THEN runProc[s, fMin, fMax-fMin]; }; ENDLOOP; IF wrap # 0 THEN ERROR; ENDLOOP; }; Convert[devicePath, Result, clipBox]; }; ConvertToPixels: PUBLIC PROC [ devicePath: DevicePath, pixelMap: PixelMap, value: CARDINAL, parityFill: BOOLEAN, function: Function ] ~ { clipBox: DeviceRectangle _ ImagerPixelMaps.BoundedWindow[pixelMap]; lgBitsPerPixel: INTEGER _ pixelMap.refRep.lgBitsPerPixel; rast: CARDINAL _ pixelMap.refRep.rast; bbTableSpace: PrincOps.BBTableSpace; bbPtr: PrincOps.BBptr _ InitBBTable[]; InitBBTable: PROC RETURNS [bb: PrincOps.BBptr] ~ TRUSTED INLINE { bb _ PrincOpsUtils.AlignedBBTable[@bbTableSpace]; bb^ _ [ dst: [word: NIL, bit: 0], dstBpl: rast*Basics.bitsPerWord, src: [word: @replicatedPixel, bit: 0], srcDesc: [gray[[yOffset: 0, widthMinusOne: 0, heightMinusOne: 0]]], height: 1, width: 0, flags: [direction: forward, disjoint: TRUE, disjointItems: TRUE, gray: TRUE, srcFunc: function.srcFunc, dstFunc: function.dstFunc] ]; }; replicatedPixel: CARDINAL _ BITAND[value, Shift[1, Shift[1, lgBitsPerPixel]]-1] * ( SELECT lgBitsPerPixel FROM 0 => 0FFFFH, 1 => 05555H, 2 => 01111H, 3 => 00101H, 4 => 00001H, ENDCASE => ERROR ); Result: PROC [devicePath: DevicePath, sStart, sEnd: INTEGER] ~ TRUSTED { bb: PrincOps.BBptr ~ bbPtr; pointer: LONG POINTER ~ pixelMap.refRep.pointer; words: LONG CARDINAL ~ pixelMap.refRep.words; fBase: INTEGER ~ pixelMap.fOrigin; destLine: LONG POINTER _ pointer + Basics.LongMult[sStart-pixelMap.sOrigin, rast]; Run: PROC [fMin, fSize: INTEGER] ~ TRUSTED INLINE { bitIndex: CARDINAL _ Shift[fMin-fBase, lgBitsPerPixel]; bb.width _ Shift[fSize, lgBitsPerPixel]; bb.dst.word _ destLine + bitIndex / Basics.bitsPerWord; bb.dst.bit _ bitIndex MOD Basics.bitsPerWord; IF bb.dst.word-pointer < 0 OR bb.dst.word-pointer+NAT[bb.width+15]/16 > words THEN ERROR; PrincOpsUtils.BITBLT[bb]; }; bucketTable: BucketTable ~ devicePath.bucketTable; pointTable: PointTable ~ devicePath.pointTable; parityMask: CARDINAL ~ IF parityFill THEN 1 ELSE LAST[CARDINAL]; scanLineCrossings: NAT ~ bucketTable.seq[bucketTable.length-1]; fOrigin: INTEGER ~ devicePath.fMin; wrap: INTEGER _ 0; pointNumber: NAT _ 0; FOR line: NAT IN [0..bucketTable.length) DO s: INTEGER ~ sStart + line; firstPointOnNextLine: NAT ~ bucketTable.seq[line]; numberOfPointsOnLine: NAT ~ firstPointOnNextLine - pointNumber; fStart: INTEGER; IF numberOfPointsOnLine = 2 THEN { p1, p2: Point; IF Key[p1 _ pointTable[pointNumber]] > Key[p2 _ pointTable[pointNumber+1]] THEN {pointTable[pointNumber] _ p2; pointTable[pointNumber+1] _ p1} } ELSE ShellSort[pointTable, pointNumber, numberOfPointsOnLine]; WHILE pointNumber < firstPointOnNextLine DO point: Point ~ pointTable[pointNumber]; pointNumber _ pointNumber + 1; IF BITANDI[wrap, parityMask] = 0 THEN fStart _ point.fRel + fOrigin; wrap _ wrap + deltaWrap[point.direction]; IF BITANDI[wrap, parityMask] = 0 THEN { fMin: INTEGER _ MAX[fStart, clipBox.fMin]; fMax: INTEGER _ MIN[point.fRel + fOrigin, clipBox.fMin+clipBox.fSize]; IF fMax > fMin THEN Run[fMin, fMax-fMin]; }; ENDLOOP; IF wrap # 0 THEN ERROR; destLine _ destLine + rast; ENDLOOP; }; Convert[devicePath, Result, clipBox]; }; ConvertToManhattanPolygon: PUBLIC PROC [ devicePath: DevicePath, clipBox: DeviceRectangle, parityFill: BOOLEAN ] RETURNS [LIST OF DeviceRectangle] ~ { Runs: PROC [ run: PROC [sMin, fMin: INTEGER, fSize: NAT], repeat: PROC [timesToRepeatScanline: NAT]] ~ { ConvertToRuns[devicePath, run, clipBox, parityFill]; }; RETURN [ImagerManhattan.CreateFromRuns[Runs]]; }; END.