DIRECTORY
Inline USING [BITAND, BITOR, BITSHIFT, BITXOR, LongDiv, LongMult],
IPImagerBasic USING [Bezier, Pair],
IPScan USING [],
Real USING [FixC, FScale, RoundC, RoundI, SqRt],
RealFns USING [ArcTan, Cos, Sin],
Runtime USING [BoundsFault],
ShowTime USING [GetMark];

IPScanImpl: CEDAR MONITOR
IMPORTS Inline, Real, RealFns, Runtime, ShowTime
EXPORTS IPScan
= BEGIN OPEN IPImagerBasic;
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]]};
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
];

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
];

ShortVec: 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] ~ {
};

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] _ ShortVec[Shift[abx+bcx+7, -3], Shift[aby+bcy+3, -2]];
[x2, y2] _ ShortVec[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] _ ShortVec[Shift[bcx+3, -2], Shift[bcy, -1] - yShift];
[x2, y2] _ ShortVec[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 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.y3 = 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] ~ {
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;
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: 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] ~ {
segmentCount: NAT ~ devicePath.length;
yMin: INTEGER ~ MAX[ymin, devicePath.ymin];
yMax: INTEGER ~ MIN[ymax, devicePath.ymax];
bucketTable: BucketTable _ InitialBucketTable[devicePath, yMin, yMax ! Runtime.BoundsFault => GOTO Bisect];
scanLineCrossings: NAT ~ bucketTable.seq[bucketTable.length-1];
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];
ScanConvert[devicePath, proc, m, yMax];
}
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 w = 0 THEN {
IF activeWrapCount = outlines THEN
proc[xStart, y, point.x-xStart, 1];
activeWrapCount _ activeWrapCount - 1;
};
w _ w + point.wrapDelta;
IF w = 0 THEN {
activeWrapCount _ activeWrapCount + 1;
IF activeWrapCount = outlines THEN xStart _ point.x;
};
}
ELSE {
IF w = 0 THEN {
activeWrapCount _ activeWrapCount + 1;
IF activeWrapCount = outlines THEN xStart _ point.x;
};
w _ w + point.wrapDelta;
IF w = 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 m=yMin THEN ERROR;
ScanConvert[devicePath, proc, yMin, m];
ScanConvert[devicePath, proc, m, yMax];
};
};

trapCount: CARDINAL _ 0;
xTrap, yTrap: INTEGER _ FIRST[INTEGER];

timeMarkAfterAllocates: PUBLIC LONG CARDINAL _ 0;
timeMarkAfterEvals: PUBLIC LONG CARDINAL _ 0;
timeMarkAfterSort: PUBLIC LONG CARDINAL _ 0;

END.
ØIPScanImpl.mesa
Based on NewScanImpl.mesa, Created February 16, 1983 by Michael Plass

Last edited by:
Michael Plass, April 12, 1983 12:38 pm
Doug Wyatt, April 12, 1983 2:22 pm

These parameters control the precision with which the inner loop b subdivision is done. 

This parameter controls how the path gets pruned back to fit in fixed-point space.

Maximum point buffer size (the whole problem is subdivided if this is exceeded).

Some inlines for basic bit-hacking operations.
In device coordinates, the coordinates of point i is
(xi/xScale + 1/2 + xorg, (yi+yOffset)/yScale + yorg)
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];
Let garbage collector get it.
Free old sequence here
First find the coefficients of the y projection.
Now find the coefficients of the derivative.
Find where the derivative vanishes.
Now break it up as needed
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.
FREE[pointTable];
FREE[wrap];
FREE[bucketTable];
�Êÿ˜
headš
œ™J™EJ™™J™&J™"—J˜š
Ïk	˜	Jšœ�œ�œ�œ�œ�œ˜BJšœ�œ˜#Jšœ�œ˜Jšœ�œ&˜0Jšœ�œ˜!Jšœ�œ˜Jšœ	�œ˜——J˜šœ�œ
�˜Jš�œ)˜0Jš�œ˜Jšœ�œ
�œ˜J™š
œX™XJšœ
�œ˜Jšœ�œÏc˜,Jšœ
�œž!˜5—J™š
œR™RJšœ�œ
ž—
˜°
Jšœ
�œ�œ
�œ˜—J™™PJšœ�œ�œ
�œ˜%—J™™.šÐknœ�œ�œ�œ
�œ�˜7Jšœ
�œ�œ˜—šŸœ�œ�œ�œ
�œ�˜6Jšœ
�œ�œ˜—šŸœ�œ�œ�œ
�œ�˜7Jšœ�œ�œ˜—š
Ïnœ�œ�œ�œ�œ
�œ�˜?Jšœ�œ�œ˜ —Jš œ�œ�œ�œ
�œ�œ�œ�œ˜bJš œ�œ�œ�œ
�œ�œ�œ�œ
˜Yš
 œ�œ�œ�œ�œ˜-Jšœ�œ�œ˜)Jš
œ˜—š
 œ�œ�œ�œ�œ˜/Jšœ�œ�œ˜)Jš
œ˜——J˜Jšœ�œ�œ
˜šœ
�œ�œ˜Jšœ�œž˜'Jšœ�œ
˜Jšœ	�œ
˜Jšœ�œžœ
ž;˜]Jšœ�œž.˜>Jšœ�œ
˜Jšœ	�œ
˜J˜Jš
œ˜Jšœ�œ
˜
Jšœ�œ
˜Jšœ�œ
˜šœ�˜š
œ4™4Jš
œ4™4——J˜—J˜Jšœ�œ�œ˜,šœ�œ�œ˜%Jšœ�œ˜Jšœ�œ˜Jšœ�œ˜Jšœ�œ�œ
�œ˜Jšœ�œ�œ
�œ˜Jšœ�œ
˜Jšœ�œ˜J˜—J˜šœ�œ�œ˜!Jš�œ�œ
�œ˜ J˜—J˜Jšœ
�œ�œ�œ˜)Jšœ�œ�œ
˜Jšœ	�œ˜Jšœ�œ˜J˜š
 œ�œ
�œ�œ�œ˜>Jš
œ˜Jš
œ˜Jšœ
�œ	�œ�œ˜:Jš
œ˜Jš
œ˜—J˜Jšœ�œ˜Jšœ�œ�œ
˜J˜š œ�œ�œ˜7J™*J™-Jš
œ™J™Jšœ�œ
�œ™1Jš
œ#™#Jš
œS™SJšœ�œ™&Jšœ�œ
�œ™.J™Jš
œ)™)J™Jš
œ˜—J˜š
 	œ�œ�œ�œ�œ˜Lšœ�œ
˜,Jšœ�œ�œ=˜QJš
œ˜Jš
œ2˜2Jš�œ�œ˜*Jš�œ�œ
�œ˜5Jš�œ�œ
�œ˜1š�œ�˜#Jšœ�œ
˜š�œ�œ
�œ�œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜—Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜š�œ�œ˜"Jš
œ@˜@Jš
œ6˜6Jš
œ˜Jš
œ˜Jš
œ
˜
—š�œ˜Jšœ�œ˜(Jš
œ˜Jš
œ?˜?Jš
œ6˜6Jš
œ˜Jš
œ˜Jš
œ˜—Jš�œ�œ˜*Jš�œ
˜—Jš�œ�œ
�œ
˜š�œ�œ
�œ
�œ	�œ
�œ˜@Jš�œ"˜&—š�œ
�œ˜
Jš�œU˜YJš�œY˜]——Jš
œ˜—J˜š œ�œ
�œ
�œ˜9Jšœ
�œ˜ Jš
œ˜Jš
œ ˜ Jš
œ!˜!Jšœ�œ
�œ˜ Jšœ�œ
�œ˜!Jšœ�œ˜+J˜—J˜š œ�œ
�œ)�œ˜BJ™—J˜š œ�œ
�œ˜.Jš
œ˜Jš
œ ˜ Jš
œ!˜!Jšœ�œ
�œ˜ Jšœ�œ
�œ˜!Jš
œ˜—J˜š œ�œ�œ˜HJš	œ�œ.�œ#�œ
�œ
˜hJš�œ	�œ
�œ	�œ˜*š�œ-�œ˜6šœ�œ�œ
˜ Jšœ�œ
�œ
�œ.˜KJš
œ˜—š�œ�œ
�œ�˜'Jš
œ˜Jš
�˜—Jš
œ™Jš
œ˜Jš
œ˜—Jš
œ*˜*Jš
œ*˜*Jš
œ˜—J˜š œ�œ�œ�œ˜JJšœ�œ˜Jšœ�œ˜Jšœ�œ"˜-Jšœ�œ˜Jšœ�œ˜Jšœ�œ-˜5Jšœ�œ-˜5Jš	œ�œ�œ�œ�œ˜)Jš	œ�œ�œ
�œ�œ˜)Jš
œ˜š�œ�˜Jš
œ,˜,Jš
œ˜Jš�œ
˜—Jš�œ�œ�œD˜[Jš
œ˜—J˜š œ�œ˜6Jšœ�œ˜Jš
œ,˜,Jšœ�œ#˜-Jšœ�œ˜Jšœ
�œ˜Jšœ�œ�œ˜"Jšœ�œ
˜š
�œ�œ
�œ�œ
�œ
�œ�˜?Jš
œ˜Jš
œ˜Jš
œ ˜ Jš�œ
˜—Jš
œ˜Jš�œ�œA�œ
˜^Jš�œ�œ
˜Jš
œ˜Jš
œ!˜!Jš
œ2˜2Jš
œ;˜;Jš
œ;˜;Jš
œ;˜;Jš
œ;˜;Jš
œ<˜<Jš
œ;˜;Jš
œ;˜;Jš
œ;˜;Jš
œ3˜3Jš
œ&˜&Jšœ�
œ4˜:Jš
œ%˜%Jš�œ
�œ+˜?Jš
œ˜—J˜š œ�œ3�œ˜Lš�œ�œ
�œ�˜+Jš	œ�œ�œ�œ�œ˜8Jš
œ"˜"Jš
œ"˜"Jšœ�œ˜ Jšœ�œ˜ š
�˜Jš	œ�œ	�œ:�œ
�œ˜XJšœ�œ�œ
�œM�œ
�œ˜qJšœ
�œ�œ	�œ'�œ
�œ˜KJš
œ
�œ�œ�œ
�œ:�œ
�œ˜dJš�œ�œ
˜—Jš�œ
˜—Jš
œ˜—J˜š œ�œ
�œ
˜%Jš
�œ�œ
�œ�œ
�œ˜QJš
œ˜—J˜š œ�œ,˜Fš 	œ�œ˜Jš œ�œ�œ�œ
�œ�œ
�œ˜KJš
œI˜IJš
œI˜IJš
œI˜IJš
œ*˜*Jš
œ*˜*Jš
œ/˜/Jš
œ:˜:Jš
œ:˜:J˜—Jšœ�œ�œ5˜EJšœ�œ�œ5˜EJšœ	�œ�œ˜.Jšœ�œ�œ$˜4Jšœ�œ�œ5˜EJš	œ	�œ�œ
�œ�œ˜*Jš	œ	�œ�œ
�œ�œ˜*š�œ�œ�œ˜2Jš�œ�œ�œ˜FJš�œ�œ�œ˜Fš�œ
�œ
�œ�œ�œ�œ�œ˜CJš
œd˜dJš
œ
˜
—Jš�œ
˜Jš
œ
˜
—š�œ
�œ�œ
�œ
�œ�œ
�œ�œ�œ�œ˜‘
Jš
œ3˜3š�œ
�œ�œ˜"Jšœ�œ ˜5Jšœ�œ"˜7J˜—J˜
—Jš�œ
˜Jš
œ˜—J˜š œ�œ�œ�œ˜9Jšœ
�œ'˜.—J˜š 	œ�œ�œ�œ˜@Jš�œ
�œ˜
J˜J˜J˜J˜J˜J˜J˜Jš
œ'˜'Jš
œ(˜(Jš�œ
˜—J˜š œ�œ'˜9™0Jšœ�œ
˜Jšœ�œ˜Jšœ�œ˜Jšœ�œ
˜Jšœ�œ˜—™,Jšœ�œ˜Jšœ�œ˜Jšœ�œ˜—™#Jšœ�œ˜š�œ
�œ˜Jšœ�œ	˜Jšœ�œ	˜Jšœ�œ˜š�œ�œ˜Jšœ�œ˜J˜J˜Jš
œ˜—Jš
œ
˜
—Jš�œ
�œ�œ
˜ —™Jšœ�œ�œ˜Jšœ�œ�œ˜Jš�œ	�œ�œ˜0š�œ
�œ	�œ
�œ˜+Jš
œ˜Jš
œ"˜"Jš
œ)˜)Jš
œ.˜.Jš
œ:˜:Jš
œ:˜:Jš
œ2˜2Jš
œ&˜&Jš
œ)˜)Jš
œ'˜'Jš
œ
˜
—š�œ
�œ�œ�œ�œ�œ˜3Jš
œ˜Jš	œ�œ�œ�œ�œ˜@Jš
œ.˜.Jš
œ2˜2Jš
œ&˜&Jš
œ'˜'Jš
œ
˜
—Jš�œ%˜)—Jš
œ˜—J˜Jšœ�œ˜Jšœ�œ˜Jšœ
�œ˜J˜š œ�œ�œ˜J™™
Jš
œ$˜$Jšœ"�œ˜-Jš�œ
�œ�œ�œ˜4Jš
œ˜—J˜š 
œ�œ
�œ�œ�œ�œ˜:Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ ˜ Jš
œ˜—J˜š œ�œ
�œ˜-Jš	œ�œ�œ�œ�œ˜MJšœ	�˜Jš
œ˜Jš
œ˜Jšœ	�œ�œ
˜Jšœ�œ˜&Jšœ�œ˜(š œ�œ
˜Jš�œ	�œ	�œ�œ
˜,Jš
œ!˜!Jš
œ˜Jš
œ˜—š œ�œ
˜Jš�œ
�œ	�œ
˜ Jš
œs˜sJš
œ˜Jš
œ˜—š œ�œ˜!Jš�œ
�œ	�œ
˜ Jš
œ2˜2Jš
œ˜Jš
œ˜—š œ�œ˜Jš�œ�œ˜0Jš
œ9˜9Jš
œ˜—Jš
œ˜Jš
œ˜Jš�œ	�œ	˜Jš
œ>˜>Jš�œ$�œ	�œA˜wJš
œ˜—J˜š œ�œ
�œ˜0Jšœ	�œ�œ
˜Jš
œ<˜<Jš�œ�œQ�œ,�œA˜â
š�œ�œQ�˜rJš
œ*˜*Jš
�˜—Jš
œ˜—J˜Jšœ�œ�œ˜%šœ�œ�œ˜Jš�œ�œ
�œ˜ J˜—J˜Jšœ�œ�œ�œ˜@J˜šœ�œ�œ˜Jšœ�œ
˜Jš
œ˜Jšœ	�œ
˜Jš
œ˜J˜—J˜Jšœ�œ	�œ
�œ<˜]J˜š 	œ�œ#�œ�œ˜Bš�œ	�œ˜Jš
œ˜Jšœ
�œ
�œ
�œ˜2Jš	œ�œ
�œ
�œ$�œ˜GJš�œ3�œ
�œ
�œ
˜Hš	�œ�œ
�
œ
�œ�˜1Jšœ�œ˜Jšœ�œ�œ˜%š�œ�œ
�œ�œ�œ�˜UJš
œ˜Jšœ�œ
�œ
�œ˜#Jšœ�œ
�œ
�œ˜š�œ
�œ�œ
�œ�œ�œ
�œ�œ�˜kJš
œ˜Jš
œ	˜	Jš�œ
˜—Jš
œ
˜
Jš�œ
˜—Jš�œ
˜—Jš
œ˜—Jš
œ˜—J˜Jšœ�œ�œ˜#šœ�œ�œ˜Jš�œ�œ
�œ
�˜"J˜—J˜Jšœ
�œ�œ˜'Jšœ�œ�œ�œ�œ	�œ
�œ
�œ˜[J˜š
 œ�œ�œ�œ�œ˜tJšœ�œ˜Jšœ�œ˜/š�œ�œ
�œ�˜(Jš
œ˜Jš�œ
˜—š�œ�œ
�œ�˜'Jš
œ!˜!Jšœ�œ�œ˜2Jšœ�œ�œ.˜@š�œ
�œ˜Jš
œ4˜4Jš
œ0˜0Jš
œ˜—Jš�œ
˜—šœ	�œ˜š�œ�œ
�œ�˜(Jš
œ˜Jšœ
�œ˜!Jš
œ˜Jš
œ
˜
Jš�œ
˜—J˜—Jš
œ$˜$Jš
œ˜—J˜š œ�œ
�œ˜0Jšœ�œ
�œ˜ Jšœ�œ�œ˜!Jšœ�œ˜&Jšœ�œ�œ˜+Jšœ�œ�œ˜+Jšœ^�œ	˜kJšœ�œ)˜?š�œ'�œ
�œ˜?Jšœ�œ˜š�œ1�˜8J˜Jš�œ
˜—Jšœ�œ
˜Jš
œ'˜'Jš
œ'˜'Jš
œ
˜
—š�œ˜Jšœ
�œ˜,Jšœ�œ˜.Jšœ�œ#˜?Jšœ�œ˜Jšœ�œ˜š œ�œ˜Jš�œ<�œ
�œ
˜IJš
œ,˜,š�œ�œ
�œ�˜Jš
œ˜Jš�œ
˜—š�œ�œ
�œ�˜"Jš
œ!˜!Jšœ�œ�œ˜1Jšœ	�œ�œ)˜?J˜
Jšœ�œ�œ�œ˜5Jš
œ˜Jš
œ*˜*š�œ�œ
�œ�˜)Jšœ�œ˜!Jš
�œ
�œ�œ
�œ�œ˜HJš
œ˜š�œ˜	Jš	œ�œ
�œ
�œ
�œ˜;Jš
œ˜Jš
œ˜J˜Jš
œ˜—Jš�œ
˜—Jš�œ
˜—Jš�œ�œ
�œ
˜)J˜—š œ�œ˜Jšœ�œ ˜8Jšœ�œ˜Jšœ
�œ˜š�œ�œ
�œ�˜+Jšœ�œ˜Jšœ�œ˜2Jšœ�œ&˜?Jšœ�œ
˜š�œ�˜ Jš
œ8˜8—š�œ
�œ�œ˜'J˜š�œG�˜MJš
œ>˜>—J˜—š�œ$�˜+Jš
œ'˜'Jšœ�œ˜'Jš
œ˜š�œ�œ˜š�œ�œ˜š�œ�˜"Jš
œ#˜#—Jš
œ&˜&J˜—Jš
œ˜š�œ�œ˜Jš
œ&˜&Jš�œ�œ˜4J˜—Jš
œ
˜
—š�œ˜š�œ�œ˜Jš
œ&˜&Jš�œ�œ˜4J˜—Jš
œ˜š�œ�œ˜š�œ�˜"Jš
œ#˜#—Jš
œ&˜&J˜—J˜—Jš
œ˜Jš�œ
˜—Jš�œ
˜—J˜—J˜Jš
œ(˜(Jš
œ'˜'J˜Jš
œ™Jš
œ™Jš
œ™J˜—š�œ˜Jšœ�œ�œ˜+Jšœ�œ�œ˜+Jšœ�œ˜Jš�œ�œ
�œ
˜Jš
œ'˜'Jš
œ'˜'Jš
œ˜—Jš
œ˜—J˜Jšœ�œ˜Jšœ�œ�œ
�œ˜'J˜Jšœ�œ
�œ
�œ˜1Jšœ�œ
�œ
�œ˜-Jšœ�œ
�œ
�œ˜,J˜Jš�œ
˜——…—MÂn™