ScanConverterImpl:
CEDAR
MONITOR
IMPORTS Inline, Real, RealFns, Runtime, ShowTime
EXPORTS ScanConverter
= BEGIN
Pair: TYPE ~ ImagerBasic.Pair;
Bezier: TYPE ~ ImagerBasic.Bezier;
These parameters control the precision with which the inner loop b subdivision is done.
lgXScale: NAT ~ 6;
xScale: NAT ~ 64; -- must be a power of two.
flatness: REAL ← 4; -- 1/max allowed error in pixels.
This parameter controls how the path gets pruned back to fit in fixed-point space.
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;
Maximum point buffer size (the whole problem is subdivided if this is exceeded).
maxPointTableSize: NAT ← LAST[NAT]/2;
Some inlines for basic bit-hacking operations.
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
In device coordinates, the coordinates of point i is
(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] ~ {
path: Graphics.Path ← Graphics.NewPath[6];
dc: Graphics.Context ← Graphics.NewContext[];
dc.Translate[cubic.xorg, 100];
[] ← dc.SetPaintMode[invert];
dc.Scale[1.0/xScale, 400.0/(1+LAST[CARDINAL]/8)];
Graphics.MoveTo[path, cubic.x0, 0];
Graphics.CurveTo[path, cubic.x1, cubic.y1, cubic.x2, cubic.y2, cubic.x3, cubic.y3];
Graphics.MoveTo[path, 0, yRel, FALSE];
Graphics.LineTo[path, LAST[CARDINAL]/8, yRel];
dc.DrawStroke[path];
Process.Pause[Process.MsecToTicks[dlay]];
dc.DrawStroke[path];
};
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};
Let garbage collector get it.
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;
Free old sequence here
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<
LAST[
CARDINAL]/8
AND yDelta <
LAST[
CARDINAL]/16
DO
yScale ← 2*yScale;
lgYScale ← lgYScale + 1;
yDelta ← Real.FScale[yDelta, 1];
ENDLOOP;
cubic.yScale ← yScale;
IF b.b3.y < b.b0.y THEN {t: Bezier ← [b.b3, b.b2, b.b1, b.b0]; b ← t; cubic.ascending ← FALSE}
ELSE cubic.ascending ← TRUE;
ymin ← b.b0.y;
yorg ← cubic.yorg ← FloorI[ymin];
cubic.outlineNumber ← devicePath.numberOfOutlines;
cubic.x0 ← Real.RoundC[Real.FScale[b.b0.x-xorg, lgXScale]];
cubic.x1 ← Real.RoundC[Real.FScale[b.b1.x-xorg, lgXScale]];
cubic.x2 ← Real.RoundC[Real.FScale[b.b2.x-xorg, lgXScale]];
cubic.x3 ← Real.RoundC[Real.FScale[b.b3.x-xorg, lgXScale]];
cubic.yOffset ← Real.FixC[Real.FScale[ymin-yorg, lgYScale]];
cubic.y1 ← Real.RoundC[Real.FScale[b.b1.y-ymin, lgYScale]];
cubic.y2 ← Real.RoundC[Real.FScale[b.b2.y-ymin, lgYScale]];
cubic.y3 ← Real.RoundC[Real.FScale[b.b3.y-ymin, lgYScale]];
cubic.iterationsUntilFlat ← IterationsUntilFlat[b];
cubic.yFirstScan ← CeilingI[ymin-0.5];
cubic.scanCount ← CeilingI[b.b3.y-0.5] - cubic.yFirstScan;
cubic.exclude ← devicePath.excluding;
IF cubic.scanCount = 0 THEN devicePath.length ← devicePath.length - 1;
};
FixUpJoints:
PROC [devicePath: DevicePath, outlineStart, outlineEnd:
NAT] ~ {
FOR j:
NAT
IN [outlineStart..outlineEnd)
DO
i: NAT ~ IF j = outlineStart THEN outlineEnd-1 ELSE j-1;
cubicI: Cubic ~ devicePath.seq[i];
cubicJ: Cubic ~ devicePath.seq[j];
iup: BOOLEAN ~ cubicI.ascending;
jup: BOOLEAN ~ cubicJ.ascending;
SELECT TRUE FROM
iup AND jup => {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] ~ {
First find the coefficients of the y projection.
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;
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;
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;
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: 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] ~ {
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:
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[];
FREE[pointTable];
FREE[wrap];
FREE[bucketTable];
};
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.
Michael Plass, May 13, 1983 12:01 pm. Fixed bug in AppendMonotoneShortPiece that caused infinitesimal pieces that straddled scanlines to be discarded.
Michael Plass, May 13, 1983 1:48 pm. Changed AppendBezier to avoid possible loss of significant figures when calculating roots of the quadratic.
Michael Plass, June 20, 1983 8:58 am. Renamed IPScan to ScanConverter.