<> <> <> DIRECTORY IGScanConverter, Imager, Inline, Mopcodes, Real, Scaled ; IGScanConverterImpl: CEDAR MONITOR IMPORTS Inline, Real, Scaled EXPORTS IGScanConverter = BEGIN OPEN IGScanConverter; <> xLimit: NAT _ 60; yLimit: NAT _ 60; <<>> <> BITAND: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zAND}; BITOR: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zOR}; BITXOR: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = TRUSTED MACHINE CODE {Mopcodes.zXOR}; Floor8: PROC[a: CARDINAL] RETURNS [NAT] = INLINE {RETURN[Inline.BITSHIFT[a, -8]]}; Mid: PROC[a, b: CARDINAL] RETURNS [CARDINAL] = INLINE {RETURN[Inline.BITSHIFT[(a+b),-1]]}; Rec6: TYPE = RECORD [a, b, c, d, e, f: CARDINAL]; ShortVec: TYPE = RECORD [x, y: CARDINAL]; XValueFor: PUBLIC PROCEDURE [cubic: CubicRec, y: Scaled.Value] RETURNS [INTEGER] = { <> OPEN cubic; yRel: CARDINAL; IF y.Ceiling[] < ymin THEN RETURN [LAST[INTEGER]]; IF y.Floor[] > ymax THEN RETURN [FIRST[INTEGER]]; yRel _ y.MINUS[Scaled.FromInt[ymin]].Scale[8].Round[]; IF yRel <= y0 THEN IF yRel < y0 OR openAt0 THEN RETURN [LAST[INTEGER]]; IF yRel >= y3 THEN IF yRel > y3 OR openAt3 THEN RETURN [FIRST[INTEGER]]; WHILE y3 - y0 > 3 -- Required to guarantee termination. AND 0 # <<-- The following quantity is zero iff x0, x1, x2, and x3 match in their high-order bits.>> BITAND[ BITOR[BITXOR[x0, x1], BITOR[BITXOR[x1, x2], BITXOR[x2, x3]]], LAST[CARDINAL]-255 ] DO a: ShortVec _ [Mid[x0, x1], Mid[y0, y1]]; b: ShortVec _ [Mid[x1, x2], Mid[y1, y2]]; c: ShortVec _ [Mid[x2, x3], Mid[y2, y3]]; ab: ShortVec _ [Mid[a.x, b.x], Mid[a.y, b.y]]; bc: ShortVec _ [Mid[b.x, c.x], Mid[b.y, c.y]]; p: ShortVec _ [Mid[ab.x, bc.x], Mid[ab.y, bc.y]]; IF yRel> Reset: PUBLIC PROCEDURE [devicePath: DevicePath] = { devicePath.length _ 0; devicePath.numberOfOutlines _ 0; }; AppendMonotoneShortPiece: PROCEDURE [devicePath: DevicePath, bezier: ScaledBezier] = { OPEN bezier; 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; cubic.ascending _ TRUE; IF y3.LESS[y0] THEN { [x0, y0, x1, y1, x2, y2, x3, y3] _ RecScaled8[x3, y3, x2, y2, x1, y1, x0, y0]; cubic.ascending _ FALSE; }; cubic.outlineNumber _ devicePath.numberOfOutlines; cubic.xmin _ MIN[x0.Floor[], x1.Floor[], x2.Floor[], x3.Floor[]]; cubic.ymin _ y0.Floor[]; cubic.ymax _ y3.Ceiling[]; cubic.x0 _ x0.MINUS[Scaled.FromInt[cubic.xmin]].PLUS[Scaled.half].Scale[8].Round[]; cubic.x1 _ x1.MINUS[Scaled.FromInt[cubic.xmin]].PLUS[Scaled.half].Scale[8].Round[]; cubic.x2 _ x2.MINUS[Scaled.FromInt[cubic.xmin]].PLUS[Scaled.half].Scale[8].Round[]; cubic.x3 _ x3.MINUS[Scaled.FromInt[cubic.xmin]].PLUS[Scaled.half].Scale[8].Round[]; cubic.y0 _ y0.MINUS[Scaled.FromInt[cubic.ymin]].Scale[8].Round[]; cubic.y1 _ y1.MINUS[Scaled.FromInt[cubic.ymin]].Scale[8].Round[]; cubic.y2 _ y2.MINUS[Scaled.FromInt[cubic.ymin]].Scale[8].Round[]; cubic.y3 _ y3.MINUS[Scaled.FromInt[cubic.ymin]].Scale[8].Round[]; IF cubic.y0 = cubic.y3 THEN devicePath.length _ devicePath.length - 1; }; AppendMonotonePiece: PROCEDURE [devicePath: DevicePath, b: ScaledBezier] = { xmin: INTEGER _ MIN[b.x0.Floor[], b.x1.Floor[], b.x2.Floor[], b.x3.Floor[]]; xmax: INTEGER _ MAX[b.x0.Ceiling[], b.x1.Ceiling[], b.x2.Ceiling[], b.x3.Ceiling[]]; ymin: INTEGER _ MIN[b.y0.Floor[], b.y1.Floor[], b.y2.Floor[], b.y3.Floor[]]; ymax: INTEGER _ MAX[b.y0.Ceiling[], b.y1.Ceiling[], b.y2.Ceiling[], b.y3.Ceiling[]]; b1, b2: ScaledBezier; IF xmax - xmin < LAST[NAT]/256 AND ymax - ymin < LAST[NAT]/256 AND (xmax - xmin <= xLimit OR ymax - ymin <= yLimit) THEN AppendMonotoneShortPiece[devicePath, b] ELSE { [b1, b2] _ Split[b]; AppendMonotonePiece[devicePath, b1]; AppendMonotonePiece[devicePath, b2]; }; }; AppendMonotoneBezier: PROCEDURE [devicePath: DevicePath, bezier: Imager.Bezier] = { s: ScaledBezier _ [ Scaled.FromReal[bezier.b0.x], Scaled.FromReal[bezier.b0.y], Scaled.FromReal[bezier.b1.x], Scaled.FromReal[bezier.b1.y], Scaled.FromReal[bezier.b2.x], Scaled.FromReal[bezier.b2.y], Scaled.FromReal[bezier.b3.x], Scaled.FromReal[bezier.b3.y] ]; AppendMonotonePiece[devicePath, s] }; Interpolate: PROCEDURE [t: REAL, a, b: Imager.Vec] RETURNS [Imager.Vec] = { RETURN[[b.x*t+a.x*(1-t), b.y*t+a.y*(1-t)]]; }; SubDivide: PROCEDURE [b: Imager.Bezier, t: REAL] RETURNS [low, high: Imager.Bezier] = BEGIN OPEN b; q1, q2, q3, qp1, qp2, q: Imager.Vec; 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: PROCEDURE [devicePath: DevicePath, bezier: Imager.Bezier] = { <> c0: REAL = bezier.b0.y; c1: REAL = 3*(bezier.b1.y - c0); t: REAL = 3*(bezier.b2.y - bezier.b1.y); c2: REAL = t - c1; c3: REAL = bezier.b3.y - c0 - t; <> d0: REAL = c1; d1: REAL = 2*c2; d2: REAL = 3*c3; <> t0, t1: REAL _ -1; IF d2 # 0.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-sqrt)/2; t1 _ (-b+sqrt)/2; }; } ELSE IF d1#0.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: Imager.Bezier; [middle, high] _ SubDivide[bezier, 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: Imager.Bezier; [low, high] _ SubDivide[bezier, 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, bezier]; }; numberOfDeltas: INT _ 0; sumOfAbsDeltas: REAL _ 0.0; maxDelta: REAL _ 0.0; Delta: PROCEDURE [delta: REAL] = { <> numberOfDeltas _ numberOfDeltas + 1; sumOfAbsDeltas _ sumOfAbsDeltas + ABS[delta]; IF ABS[delta] > maxDelta THEN maxDelta _ ABS[delta]; }; DeltaStats: PROCEDURE RETURNS [n: INT, sum: REAL, max: REAL] = { n _ numberOfDeltas; sum _ sumOfAbsDeltas; max _ maxDelta; numberOfDeltas _ 0; sumOfAbsDeltas _ maxDelta _ 0.0; }; PushPath: PUBLIC PROCEDURE [ devicePath: DevicePath, path: Imager.Path, transformation: Imager.Transformation ] = { firstPoint, lastPoint: Imager.Vec; started: BOOLEAN _ FALSE; outlineStart: NAT _ devicePath.length; Move: PROC [v: Imager.Vec] = { IF started THEN Close[]; outlineStart _ devicePath.length; started _ TRUE; firstPoint _ lastPoint _ v; }; Line: PROC [v: Imager.Vec] = { started _ TRUE; AppendBezier[devicePath, [lastPoint, Interpolate[0.3333333, lastPoint, v], Interpolate[0.6666667, lastPoint, v], v]]; lastPoint _ v; }; Curve: PROC [v1, v2, v3: Imager.Vec] = { started _ TRUE; AppendBezier[devicePath, [lastPoint, v1, v2, v3]]; lastPoint _ v3; }; Close: PROC = { IF started AND lastPoint # firstPoint THEN Line[firstPoint]; FOR j: NAT IN [outlineStart..devicePath.length) DO i: NAT = IF j = outlineStart THEN devicePath.length-1 ELSE j-1; cubicI: Cubic = devicePath.seq[i]; cubicJ: Cubic = devicePath.seq[j]; iup: BOOLEAN = cubicI.ascending; jup: BOOLEAN = cubicJ.ascending; IF iup THEN cubicI.openAt3 _ FALSE ELSE cubicI.openAt0 _ NOT jup; IF jup THEN cubicJ.openAt0 _ iup ELSE cubicJ.openAt3 _ FALSE; ENDLOOP; started _ FALSE; }; path.generateProc[path, transformation, Move, Line, Curve]; Close[]; devicePath.numberOfOutlines _ devicePath.numberOfOutlines + 1; }; PopPath: PUBLIC PROCEDURE [devicePath: DevicePath] = { devicePath.numberOfOutlines _ devicePath.numberOfOutlines-1; WHILE devicePath.length > 0 AND devicePath.seq[devicePath.length-1].outlineNumber = devicePath.numberOfOutlines DO devicePath.length _ devicePath.length - 1; ENDLOOP; }; ActivePieceTable: TYPE = REF ActivePieceTableRec; ActivePieceTableRec: TYPE = RECORD [ SEQUENCE maxLength: NAT OF ActivePieceRec ]; ActivePieceRec: TYPE = RECORD [ sortKey: INTEGER, pieceIndex: NAT ]; activePieceTable: ActivePieceTable _ NIL; AllocActivePieceTable: ENTRY PROC [size: NAT] RETURNS [a: ActivePieceTable] = { IF activePieceTable # NIL AND activePieceTable.maxLength >= size THEN {a _ activePieceTable; activePieceTable _ NIL} ELSE a _ NEW[ActivePieceTableRec[size]] }; FreeActivePieceTable: ENTRY PROC [a: ActivePieceTable] = { IF activePieceTable = NIL OR a.maxLength > activePieceTable.maxLength THEN activePieceTable _ a }; shellD: ARRAY [1..11] OF CARDINAL = [1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 65535]; ShellSort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] = TRUSTED { length: NAT _ startPlusLength - start; passesPlusOne: [1..11] _ 1; startPtr: LONG POINTER TO ActivePieceRec _ @(table[start]); endPtr: LONG POINTER TO ActivePieceRec _ @(table[startPlusLength-1]) + SIZE[ActivePieceRec]; 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[ActivePieceRec]; iPtr: LONG POINTER TO ActivePieceRec _ startPtr; FOR iPtr: LONG POINTER TO ActivePieceRec _ startPtr, iPtr + SIZE[ActivePieceRec] UNTIL iPtr = endPtr DO a: ActivePieceRec _ iPtr^; jPtr: LONG POINTER TO ActivePieceRec _ iPtr; b: LONG POINTER TO ActivePieceRec; WHILE LOOPHOLE[(b _ jPtr-hTimesSize), LONG CARDINAL] >= LOOPHOLE[startPtr, LONG CARDINAL] AND a.sortKey < b^.sortKey DO jPtr^ _ b^; jPtr _ b; ENDLOOP; jPtr^ _ a; ENDLOOP; ENDLOOP; }; InsertionSort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] = { FOR i: NAT IN [start..startPlusLength) DO a: ActivePieceRec _ table[i]; b: ActivePieceRec; j: NAT _ i; WHILE j>0 AND a.sortKey < (b _ table[j-1]).sortKey DO table[j] _ b; j _ j-1 ENDLOOP; table[j] _ a; ENDLOOP; }; Sort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] _ ShellSort; WrapTable: TYPE = REF WrapTableRec; WrapTableRec: TYPE = RECORD [ SEQUENCE maxLength: NAT OF INTEGER ]; wrapTable: WrapTable _ NIL; AllocWrapTable: ENTRY PROC [size: NAT] RETURNS [w: WrapTable] = { IF wrapTable # NIL AND wrapTable.maxLength >= size THEN {w _ wrapTable; wrapTable _ NIL} ELSE w _ NEW[WrapTableRec[size]] }; FreeWrapTable: ENTRY PROC [w: WrapTable] = { IF wrapTable = NIL OR w.maxLength > wrapTable.maxLength THEN wrapTable _ w }; ScanConvert: PUBLIC PROCEDURE [devicePath: DevicePath, LineProc: PROC[xmin, xmax, y: INTEGER]] = { length: NAT _ devicePath.length; outlines: NAT _ devicePath.numberOfOutlines; active: ActivePieceTable _ AllocActivePieceTable[length]; wrap: WrapTable _ AllocWrapTable[outlines]; firstActive, firstUnActivated: NAT _ 0; y: INTEGER _ FIRST[INTEGER]; FOR i: NAT IN [0..length) DO active[i] _ [sortKey: devicePath.seq[i].ymin, pieceIndex: i]; ENDLOOP; Sort[active, 0, length]; WHILE firstActive xStart THEN LineProc[xStart, a.sortKey, y]; nonZeroWrapCount _ nonZeroWrapCount - 1; }; wrap[k] _ w; ENDLOOP; ENDLOOP; FreeActivePieceTable[active]; FreeWrapTable[wrap]; }; END.