UFCubicScanImpl:
CEDAR
MONITOR
IMPORTS Graphics, CGPath, CGVector, Inline, Real, Scaled
EXPORTS UFCubicScan
= BEGIN OPEN UFCubicScan;
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];
Vec: 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
AND 0 #
BITAND[
BITOR[BITXOR[x0, x1], BITOR[BITXOR[x1, x2], BITXOR[x2, x3]]],
LAST[CARDINAL]-255
] DO
a: Vec ← [Mid[x0, x1], Mid[y0, y1]];
b: Vec ← [Mid[x1, x2], Mid[y1, y2]];
c: Vec ← [Mid[x2, x3], Mid[y2, y3]];
ab: Vec ← [Mid[a.x, b.x], Mid[a.y, b.y]];
bc: Vec ← [Mid[b.x, c.x], Mid[b.y, c.y]];
p: Vec ← [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 THEN AppendMonotoneShortPiece[devicePath, b]
ELSE {
[b1, b2] ← Split[b];
AppendMonotonePiece[devicePath, b1];
AppendMonotonePiece[devicePath, b2];
};
};
AppendMonotoneBezier:
PROCEDURE [devicePath: DevicePath, bezier: CGCubic.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: CGVector.Vec]
RETURNS [r: CGVector.Vec] =
BEGIN OPEN CGVector;
r ← Add[Mul[b, t], Mul[a, 1-t]];
END;
SubDivide:
PROCEDURE [b: CGCubic.Bezier, t:
REAL]
RETURNS [low, high: CGCubic.Bezier] =
BEGIN OPEN b;
q1, q2, q3, qp1, qp2, q: CGVector.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: CGCubic.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: CGCubic.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: CGCubic.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: GraphicsBasic.Path,
map: PROC [GraphicsBasic.Vec] RETURNS [GraphicsBasic.Vec] ← NIL
] = {
firstPoint, lastPoint: GraphicsBasic.Vec;
started: BOOLEAN ← FALSE;
outlineStart: NAT ← devicePath.length;
Move:
PROC [v: GraphicsBasic.Vec] = {
IF started THEN Close[];
outlineStart ← devicePath.length;
started ← TRUE;
firstPoint ← lastPoint ← v;
};
Line:
PROC [v: GraphicsBasic.Vec] = {
started ← TRUE;
AppendBezier[devicePath, [lastPoint, Interpolate[0.3333333, lastPoint, v], Interpolate[0.6666667, lastPoint, v], v]];
lastPoint ← v;
};
Curve:
PROC [v1, v2, v3: GraphicsBasic.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;
};
CGPath.MapAndFilter[path, map, 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;
};
PathFromDevicePath:
PROCEDURE [devicePath: DevicePath]
RETURNS [path: GraphicsBasic.Path] = {
Useful for debugging the DevicePath building code
started: BOOLEAN ← FALSE;
lastX, lastY: REAL;
path ← Graphics.NewPath[];
FOR i:
NAT
IN [0..devicePath.length)
DO
cubic: Cubic ← devicePath.seq[i];
X: PROC [xRel: CARDINAL] RETURNS [REAL] = {RETURN[cubic.xmin-0.5+(xRel/256.0)]};
Y: PROC [yRel: CARDINAL] RETURNS [REAL] = {RETURN[cubic.ymin+(yRel/256.0)]};
IF
NOT started
THEN {
IF cubic.ascending THEN Graphics.MoveTo[path, X[cubic.x0], Y[cubic.y0]]
ELSE Graphics.MoveTo[path, X[cubic.x3], Y[cubic.y3]];
started ← TRUE;
};
[lastX, lastY] ← Graphics.LastPoint[path];
lastX ← lastX - X[IF cubic.ascending THEN cubic.x0 ELSE cubic.x3];
lastY ← lastY - Y[IF cubic.ascending THEN cubic.y0 ELSE cubic.y3];
IF lastX # 0.0 OR lastY # 0.0 THEN lastX ← lastY ← 0.0; -- Breakpoint here to check for broken paths
IF cubic.ascending THEN Graphics.CurveTo[path, X[cubic.x1], Y[cubic.y1], X[cubic.x2], Y[cubic.y2], X[cubic.x3], Y[cubic.y3]]
ELSE Graphics.CurveTo[path, X[cubic.x2], Y[cubic.y2], X[cubic.x1], Y[cubic.y1], X[cubic.x0], Y[cubic.y0]]
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
};
Sort:
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;
};
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
CARDINAL[Inline.
BITAND[w, 1]] = 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
CARDINAL[Inline.
BITAND[w, 1]] = 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.