IGScanConverterImpl:
CEDAR
MONITOR
IMPORTS Inline, Real, Scaled
EXPORTS IGScanConverter
= BEGIN OPEN IGScanConverter;
These parameters limit the extent of the pieces in either the x or y directions. Decreasing these paramters will use more devicepath storage, but will lead to fewer subdivisions in the inner loop. Tune them to minimize the overall time.
xLimit: NAT ← 60;
yLimit: NAT ← 60;
Some inlines for basic bit-hacking operations.
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] = {
Returns LAST[INTEGER] if y is below the piece, FIRST[INTEGER] if it is above, otherwise the x-intercept rounded to the nearest 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<p.y
THEN [x1, y1, x2, y2, x3, y3] ← Rec6[a.x, a.y, ab.x, ab.y, p.x, p.y]
ELSE IF yRel=p.y THEN RETURN [Floor8[p.x]+xmin]
ELSE [x0, y0, x1, y1, x2, y2] ← Rec6[p.x, p.y, bc.x, bc.y, c.x, c.y]
ENDLOOP;
RETURN [Floor8[x3]+xmin]
};
RecScaled8: PROC [a,b,c,d,e,f,g,h: Scaled.Value] RETURNS [Scaled.Value, Scaled.Value, Scaled.Value, Scaled.Value, Scaled.Value, Scaled.Value, Scaled.Value, Scaled.Value] = {RETURN [a,b,c,d,e,f,g,h]};
ScaledBezier: TYPE = RECORD [x0, y0, x1, y1, x2, y2, x3, y3: Scaled.Value];
Split:
PROCEDURE [bezier: ScaledBezier]
RETURNS [ScaledBezier, ScaledBezier] = {
ScaledVec: TYPE = RECORD [x, y: Scaled.Value];
Mid: PROC [a, b: Scaled.Value] RETURNS [Scaled.Value] = {RETURN [a.PLUS[b].PLUS[Scaled.epsilon].Scale[-1]]};
a: ScaledVec ← [Mid[bezier.x0, bezier.x1], Mid[bezier.y0, bezier.y1]];
b: ScaledVec ← [Mid[bezier.x1, bezier.x2], Mid[bezier.y1, bezier.y2]];
c: ScaledVec ← [Mid[bezier.x2, bezier.x3], Mid[bezier.y2, bezier.y3]];
ab: ScaledVec ← [Mid[a.x, b.x], Mid[a.y, b.y]];
bc: ScaledVec ← [Mid[b.x, c.x], Mid[b.y, c.y]];
p: ScaledVec ← [Mid[ab.x, bc.x], Mid[ab.y, bc.y]];
RETURN [[bezier.x0, bezier.y0, a.x, a.y, ab.x, ab.y, p.x, p.y], [p.x, p.y, bc.x, bc.y, c.x, c.y, bezier.x3, bezier.y3]]
};
Allocate:
PUBLIC
PROCEDURE
RETURNS [devicePath: DevicePath] = {
devicePath ← NEW[DevicePathRec];
devicePath.length ← 0;
devicePath.numberOfOutlines ← 0;
devicePath.seq ← NEW[DevicePathSeqRec[10]];
};
Release:
PUBLIC
PROCEDURE [devicePath: DevicePath] = {devicePath ←
NIL};
Let garbage collector get it.
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;
Free old sequence here
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] = {
First find the coefficients of the y projection.
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;
Now find the coefficients of the derivative.
d0: REAL = c1;
d1: REAL = 2*c2;
d2: REAL = 3*c3;
Find where the derivative vanishes.
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;
Now break it up as needed
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] = {
This is used to monitor the effects of roundoff error in the computation of the monotone pieces. The globals are meant to be examined with the debugger.
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<length
DO
nonZeroWrapCount: NAT ← 0;
xStart: INTEGER ← FIRST[INTEGER];
FOR i:
NAT
IN [0..outlines)
DO
wrap[i] ← 0;
ENDLOOP;
IF firstActive=firstUnActivated THEN y ← active[firstUnActivated].sortKey
ELSE y ← y+1;
WHILE firstUnActivated<length
AND y=active[firstUnActivated].sortKey
DO
firstUnActivated ← firstUnActivated+1;
ENDLOOP;
FOR i:
NAT
IN [firstActive..firstUnActivated)
DO
active[i].sortKey ← XValueFor[devicePath.seq[active[i].pieceIndex]^, Scaled.FromInt[y].PLUS[Scaled.half]];
ENDLOOP;
Sort[active, firstActive, firstUnActivated];
WHILE firstActive<firstUnActivated
AND active[firstActive].sortKey =
FIRST[
INTEGER]
DO
firstActive ← firstActive+1;
ENDLOOP;
FOR i:
NAT
IN [firstActive..firstUnActivated)
DO
a: ActivePieceRec ← active[i];
k: NAT ← devicePath.seq[a.pieceIndex].outlineNumber;
w: INTEGER ← wrap[k];
IF a.sortKey = LAST[INTEGER] THEN EXIT;
IF w = 0
THEN {
nonZeroWrapCount ← nonZeroWrapCount + 1;
IF nonZeroWrapCount = outlines THEN xStart ← a.sortKey;
};
IF devicePath.seq[a.pieceIndex].ascending THEN w ← w + 1 ELSE w ← w - 1;
IF w = 0
THEN {
IF nonZeroWrapCount = outlines
AND a.sortKey
> xStart
THEN
LineProc[xStart, a.sortKey, y];
nonZeroWrapCount ← nonZeroWrapCount - 1;
};
wrap[k] ← w;
ENDLOOP;
ENDLOOP;
FreeActivePieceTable[active];
FreeWrapTable[wrap];
};
END.