DIRECTORY
Basics USING [BITAND, BITOR, BITSHIFT, bitsPerWord, BITXOR, LongDiv, LongMult],
ImagerManhattan USING [CreateFromBox, CreateFromRuns],
ImagerPath USING [PathProc, Transform],
ImagerPixelMap USING [BoundedWindow, Intersect, DeviceRectangle, PixelMap],
ImagerScanConverter USING [Function],
ImagerScanConverterPrivate USING [BucketTable, BucketTableRec, DevicePathRep, Direction, PieceRep, Point, PointTable, PointTableRec, SegmentRep],
ImagerTransformation USING [Transformation],
PrincOps USING [BBptr, BBTableSpace],
PrincOpsUtils USING [AlignedBBTable, BITBLT],
Real USING [FixC, FScale, RoundC, RoundI],
RealFns USING [ArcTan, Cos, Sin, SqRt],
Vector2 USING [VEC];
~
BEGIN
Bezier: TYPE ~ RECORD [s0, f0, s1, f1, s2, f2, s3, f3: REAL];
Pair: TYPE ~ RECORD [s, f: REAL];
PixelMap: TYPE ~ ImagerPixelMap.PixelMap;
DevicePath: TYPE ~ REF DevicePathRep;
DevicePathRep: PUBLIC TYPE ~ ImagerScanConverterPrivate.DevicePathRep;
BucketTable: TYPE ~ ImagerScanConverterPrivate.BucketTable;
BucketTableRec: TYPE ~ ImagerScanConverterPrivate.BucketTableRec;
Direction: TYPE ~ ImagerScanConverterPrivate.Direction;
PieceRep: TYPE ~ ImagerScanConverterPrivate.PieceRep;
Point: TYPE ~ ImagerScanConverterPrivate.Point;
PointTable: TYPE ~ ImagerScanConverterPrivate.PointTable;
PointTableRec: TYPE ~ ImagerScanConverterPrivate.PointTableRec;
SegmentRep: TYPE ~ ImagerScanConverterPrivate.SegmentRep;
Function: TYPE ~ ImagerScanConverter.Function;
VEC: TYPE ~ Vector2.VEC;
DeviceRectangle:
TYPE ~ ImagerPixelMap.DeviceRectangle;
-- These parameters control the precision with which the inner loop b subdivision is done.
lgFScale: NAT ~ 6;
fScale: NAT ~ 64; -- must be a power of two.
flatness: REAL ← 4; -- 1/max allowed error in pixels.
-- This parameter controls how much scratch storage a devicePath retains.
retainScratch: INT ← 30;
-- Some inlines for basic bit-hacking operations.
BITAND:
PROC [a, b:
CARDINAL]
RETURNS[
CARDINAL]
~ INLINE {RETURN[Basics.BITAND[a, b]]};
BITANDI:
PROC [a, b:
INTEGER]
RETURNS[
INTEGER]
~ INLINE {RETURN[LOOPHOLE[Basics.BITAND[LOOPHOLE[a], LOOPHOLE[b]]]]};
BITOR:
PROC [a, b:
CARDINAL]
RETURNS[
CARDINAL]
~ INLINE {RETURN[Basics.BITOR[a, b]]};
BITXOR:
PROC [a, b:
CARDINAL]
RETURNS[
CARDINAL]
~ INLINE {RETURN[Basics.BITXOR[a, b]]};
Shift:
PROC [a:
CARDINAL, b:
INTEGER]
RETURNS [
CARDINAL]
~ INLINE {RETURN[Basics.BITSHIFT[a, b]]};
ShortScaledFloor:
PROC [a:
CARDINAL]
RETURNS [
INTEGER]
~ INLINE {RETURN[Basics.BITSHIFT[a, -lgFScale]]};
Mid:
PROC [a, b:
CARDINAL]
RETURNS[
CARDINAL]
~ INLINE {RETURN[Basics.BITSHIFT[(a+b),-1]]};
FloorI:
PROC [r:
REAL]
RETURNS [t:
INTEGER]
~ INLINE {t ← Real.RoundI[r]; IF t > r THEN t ← t-1};
CeilingI:
PROC [r:
REAL]
RETURNS [t:
INTEGER]
~ INLINE {t ← Real.RoundI[r]; IF t < r THEN t ← t+1};
deltaWrap: ARRAY Direction OF INTEGER ~ [1, -1];
FValueFor:
PROC [piece:
LIST
OF PieceRep, sMinusHalf:
INTEGER]
RETURNS [ans:
INTEGER] ~ {
ShortPair: TYPE ~ RECORD [a, b: CARDINAL];
p: PieceRep ← piece.first;
sRel: CARDINAL ← NAT[(sMinusHalf - p.sOrg) * p.sScale + Shift[p.sScale, -1] - p.sOffset];
IF sRel > p.s3 THEN RETURN [ShortScaledFloor[p.f3]+p.fOrg];
THROUGH [0..p.iterationsUntilFlat)
DO
sAB, fAB, sBC, fBC: CARDINAL;
IF p.s3 >
LAST[
CARDINAL]/8
THEN {
p.s3 ← Shift[p.s3, -1];
p.s2 ← Shift[p.s2, -1];
p.s1 ← Shift[p.s1, -1];
sRel ← Shift[sRel, -1];
};
fAB ← p.f0 + 2*p.f1 + p.f2;
sAB ← 2*p.s1 + p.s2;
fBC ← p.f1 + 2*p.f2 + p.f3;
sBC ← p.s1 + 2*p.s2 + p.s3;
IF Shift[sRel, 3] < sAB+sBC
THEN {
[p.s3, p.f3] ← ShortPair[Shift[sAB+sBC+3, -2], Shift[fAB+fBC+7, -3]];
[p.s2, p.f2] ← ShortPair[Shift[sAB, -1], Shift[fAB+3, -2]];
p.f1 ← Shift[p.f0+p.f1, -1];
sRel ← 2*sRel;
}
ELSE {
sShift: CARDINAL ← Shift[sAB+sBC+3, -2];
p.f0 ← Shift[fAB+fBC+7, -3];
[p.s1, p.f1] ← ShortPair[Shift[sBC, -1] - sShift, Shift[fBC+3, -2]];
[p.s2, p.f2] ← ShortPair[p.s2+p.s3 - sShift, Shift[p.f2+p.f3, -1]];
p.s3 ← 2*p.s3 - sShift;
sRel ← 2*sRel - sShift;
};
ENDLOOP;
IF sRel > p.s3 THEN ERROR;
IF p.s3=0
OR
BITAND[
BITXOR[p.f0, p.f3],
LAST[
CARDINAL]-(fScale-1)] = 0
THEN ans ← ShortScaledFloor[p.f0] + p.fOrg
ELSE
IF p.f3>p.f0
THEN ans ← p.fOrg + ShortScaledFloor[p.f0 + Basics.LongDiv[Basics.LongMult[sRel, p.f3-p.f0], p.s3]]
ELSE ans ← p.fOrg + ShortScaledFloor[p.f3 + Basics.LongDiv[Basics.LongMult[p.s3-sRel, p.f0-p.f3], p.s3]];
};
SlowIterationsUntilFlat:
PROC [b: Bezier]
RETURNS [iterationsUntilFlat:
NAT] ~
INLINE {
Not used now, but a little easier to uderstand than the real one below.
deltaX: REAL ~ b.s3 - b.s0;
deltaY: REAL ~ b.f3 - b.f0;
this could be speeded up, if necessary
theta: REAL ~ RealFns.ArcTan[deltaY, deltaX];
cos: REAL ~ RealFns.Cos[theta];
sin: REAL ~ RealFns.Sin[theta];
y1: REAL ~ (b.f1-b.f0)*cos - (b.s1-b.s0)*sin;
y2: REAL ~ (b.f2-b.f0)*cos - (b.s2-b.s0)*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 ← (iterationsUntilFlat * 695 + 1023)/1024;
};
IterationsUntilFlat:
PROC [b: Bezier]
RETURNS [iterationsUntilFlat:
NAT] ~ {
deltaX: REAL ~ b.s3 - b.s0;
deltaY: REAL ~ b.f3 - b.f0;
dSqr: REAL ~ deltaX*deltaX + deltaY*deltaY;
y1d: REAL ~ deltaX*(b.f1-b.f0) - deltaY*(b.s1-b.s0);
y2d: REAL ~ deltaX*(b.f2-b.f0) - deltaY*(b.s2-b.s0);
ed: REAL ~ MAX[ABS[y1d], ABS[y2d]]*flatness;
eded: REAL ← ed*ed;
iterationsUntilFlat ← 0;
WHILE eded>dSqr
DO
iterationsUntilFlat ← iterationsUntilFlat+1;
eded ← Real.FScale[eded, -2];
ENDLOOP;
IF iterationsUntilFlat > 2
AND ((y1d>=0) = (y2d>=0))
AND
ABS[y1d]
IN [Real.FScale[
ABS[y2d], -1]..Real.FScale[
ABS[y2d], 1]]
THEN {
In this case, the convergence is faster.
iterationsUntilFlat ← (iterationsUntilFlat * 695 + 1023)/1024;
};
};
marginSize: REAL ← 8.0;
Interpolate:
PROC [t:
REAL, a, b: Pair]
RETURNS [r: Pair] ~
{RETURN [[a.s*(1-t)+b.s*t, a.f*(1-t)+b.f*t]]};
SubDivide:
PROC [b: Bezier, t:
REAL]
RETURNS [low, high: Bezier] ~ {
b0: Pair ~ [b.s0, b.f0];
b1: Pair ~ [b.s1, b.f1];
b2: Pair ~ [b.s2, b.f2];
b3: Pair ~ [b.s3, b.f3];
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.s, b0.f, q1.s, q1.f, qp1.s, qp1.f, q.s, q.f];
high ← [q.s, q.f, qp2.s, qp2.f, q3.s, q3.f, b3.s, b3.f];
};
GetScratchSegmentList:
PROC [scratch: DevicePath]
RETURNS [s:
LIST
OF SegmentRep] ~ {
IF scratch = NIL THEN RETURN [NIL];
s ← scratch.segmentList;
scratch.segmentList ← NIL;
IF scratch.scratchSegmentList #
NIL
THEN {
IF s = NIL THEN s ← scratch.scratchSegmentList
ELSE {
t: LIST OF SegmentRep ← s;
UNTIL t.rest =
NIL
DO
t ← t.rest;
ENDLOOP;
t.rest ← scratch.scratchSegmentList;
};
scratch.scratchSegmentList ← NIL;
};
};
GetScratchPieceList:
PROC [scratch: DevicePath]
RETURNS [s:
LIST
OF PieceRep] ~ {
IF scratch = NIL THEN RETURN [NIL];
s ← scratch.pieceList;
scratch.pieceList ← NIL;
IF scratch.scratchPieceList #
NIL
THEN {
IF s = NIL THEN s ← scratch.scratchPieceList
ELSE {
t: LIST OF PieceRep ← s;
UNTIL t.rest =
NIL
DO
t ← t.rest;
ENDLOOP;
t.rest ← scratch.scratchPieceList;
};
scratch.scratchPieceList ← NIL;
};
};
TrimScratchSegmentList:
PROC [s:
LIST
OF SegmentRep]
RETURNS [trimmed:
LIST
OF SegmentRep] ~ {
trimmed ← s;
IF s #
NIL
AND retainScratch > 0
THEN {
last: LIST OF SegmentRep ← s;
FOR i:
INT
IN [1..retainScratch)
UNTIL last =
NIL
DO
last ← last.rest;
ENDLOOP;
IF last #
NIL
THEN {
s ← last.rest;
last.rest ← NIL;
}
ELSE s ← NIL;
};
WHILE s #
NIL
DO
t: LIST OF SegmentRep ← s;
s ← t.rest;
t.rest ← NIL;
ENDLOOP;
};
TrimScratchPieceList:
PROC [s:
LIST
OF PieceRep]
RETURNS [trimmed:
LIST
OF PieceRep] ~ {
trimmed ← s;
IF s #
NIL
AND retainScratch > 0
THEN {
last: LIST OF PieceRep ← s;
FOR i:
INT
IN [1..retainScratch)
UNTIL last =
NIL
DO
last ← last.rest;
ENDLOOP;
IF last #
NIL
THEN {
s ← last.rest;
last.rest ← NIL;
}
ELSE s ← NIL;
};
WHILE s #
NIL
DO
t: LIST OF PieceRep ← s;
s ← t.rest;
t.rest ← NIL;
ENDLOOP;
};
CreatePath:
PUBLIC
PROC [
path: ImagerPath.PathProc,
transformation: ImagerTransformation.Transformation,
clipBox: DeviceRectangle,
scratch: DevicePath ← NIL -- for re-use of storage
] RETURNS [DevicePath] ~ {
devicePath: DevicePathRep;
scratchSegmentList: LIST OF SegmentRep ← GetScratchSegmentList[scratch];
scratchPieceList: LIST OF PieceRep ← GetScratchPieceList[scratch];
AppendSegment:
PROC [s0, f0, s1, f1:
REAL] ~ {
segment: SegmentRep;
IF NOT s0 IN [sOuterMin..sOuterMax] AND
f0 IN [fOuterMin..fOuterMax] AND
s1 IN [sOuterMin..sOuterMax] AND
f1 IN [fOuterMin..fOuterMax] THEN ERROR;
IF s1 < s0
THEN {
segment.direction ← decreasing;
segment.s0 ← s1;
segment.f0 ← f1;
segment.s1 ← s0;
segment.f1 ← f0;
}
ELSE {
segment.direction ← increasing;
segment.s0 ← s0;
segment.f0 ← f0;
segment.s1 ← s1;
segment.f1 ← f1;
};
segment.sFirstScan ← CeilingI[segment.s0-0.5];
segment.scanCount ← CeilingI[segment.s1-0.5] - segment.sFirstScan;
IF segment.scanCount # 0
THEN {
devicePath.scanLineCrossings ← devicePath.scanLineCrossings + segment.scanCount;
IF segment.sFirstScan < devicePath.sMin THEN devicePath.sMin ← segment.sFirstScan;
IF segment.sFirstScan + INTEGER[segment.scanCount] > devicePath.sMax THEN devicePath.sMax ← segment.sFirstScan + segment.scanCount;
devicePath.fMin ← MIN[devicePath.fMin, FloorI[segment.f0], FloorI[segment.f1]];
devicePath.fMax ← MAX[devicePath.fMax, CeilingI[segment.f0], CeilingI[segment.f1]];
IF scratchSegmentList =
NIL
THEN
devicePath.segmentList ← CONS[segment, devicePath.segmentList]
ELSE {
t: LIST OF SegmentRep ← scratchSegmentList;
scratchSegmentList ← t.rest;
t.rest ← devicePath.segmentList;
t.first ← segment;
devicePath.segmentList ← t;
};
};
};
AppendMonotoneShortPiece:
PROC [b: Bezier, fMin:
REAL] ~ {
iterationsUntilFlat: NAT ← IterationsUntilFlat[b];
IF iterationsUntilFlat = 0 THEN AppendSegment[b.s0, b.f0, b.s3, b.f3]
ELSE {
piece: PieceRep;
fOrg: REAL ~ (piece.fOrg ← FloorI[fMin-0.5]);
sDelta: REAL ← ABS[b.s0-b.s3];
sMin, sOrg: REAL;
lgSScale: CARDINAL ← 0;
piece.sScale ← 1;
WHILE piece.sScale<
LAST[
CARDINAL]/8
AND sDelta <
LAST[
CARDINAL]/16
DO
piece.sScale ← 2*piece.sScale;
lgSScale ← lgSScale + 1;
sDelta ← Real.FScale[sDelta, 1];
ENDLOOP;
IF b.s3 < b.s0
THEN {
t: Bezier ← [b.s3, b.f3, b.s2, b.f2, b.s1, b.f1, b.s0, b.f0];
b ← t;
piece.direction ← decreasing}
ELSE piece.direction ← increasing;
sMin ← b.s0;
sOrg ← piece.sOrg ← FloorI[sMin];
piece.f0 ← Real.RoundC[Real.FScale[b.f0-fOrg, lgFScale]];
piece.f1 ← Real.RoundC[Real.FScale[b.f1-fOrg, lgFScale]];
piece.f2 ← Real.RoundC[Real.FScale[b.f2-fOrg, lgFScale]];
piece.f3 ← Real.RoundC[Real.FScale[b.f3-fOrg, lgFScale]];
piece.sOffset ← Real.FixC[Real.FScale[sMin-sOrg, lgSScale]];
piece.s1 ← Real.RoundC[Real.FScale[b.s1-sMin, lgSScale]];
piece.s2 ← Real.RoundC[Real.FScale[b.s2-sMin, lgSScale]];
piece.s3 ← Real.RoundC[Real.FScale[b.s3-sMin, lgSScale]];
piece.iterationsUntilFlat ← iterationsUntilFlat;
piece.sFirstScan ← CeilingI[sMin-0.5];
piece.scanCount ← CeilingI[b.s3-0.5] - piece.sFirstScan;
IF piece.scanCount # 0
THEN {
devicePath.scanLineCrossings ← devicePath.scanLineCrossings + piece.scanCount;
IF piece.sFirstScan < devicePath.sMin THEN devicePath.sMin ← piece.sFirstScan;
IF piece.sFirstScan + INTEGER[piece.scanCount] > devicePath.sMax THEN devicePath.sMax ← piece.sFirstScan + piece.scanCount;
IF piece.fOrg < devicePath.fMin THEN devicePath.fMin ← piece.fOrg;
devicePath.fMax ← MAX[devicePath.fMax, piece.fOrg + ShortScaledFloor[MAX[piece.f0, piece.f1, piece.f2, piece.f3]]+1];
IF scratchPieceList =
NIL
THEN
devicePath.pieceList ← CONS[piece, devicePath.pieceList]
ELSE {
t: LIST OF PieceRep ← scratchPieceList;
scratchPieceList ← t.rest;
t.rest ← devicePath.pieceList;
t.first ← piece;
devicePath.pieceList ← t;
};
};
};
};
sInnerMin: REAL ← MAX[-REAL[LAST[NAT]-2], REAL[clipBox.sMin]];
sInnerMax: REAL ← MIN[REAL[LAST[NAT]-2], REAL[clipBox.sMin] + clipBox.sSize];
fInnerMin: REAL ← MAX[-REAL[LAST[NAT]-2], REAL[clipBox.fMin]];
fInnerMax: REAL ← MIN[REAL[LAST[NAT]-2], REAL[clipBox.fMin] + clipBox.fSize];
sOuterMin: REAL ← MAX[-REAL[LAST[NAT]-1], sInnerMin - marginSize];
sOuterMax: REAL ← MIN[REAL[LAST[NAT]-1], sInnerMax + marginSize];
fOuterMin: REAL ← MAX[-REAL[LAST[NAT]-1], fInnerMin - marginSize];
fOuterMax: REAL ← MIN[REAL[LAST[NAT]-1], fInnerMax + marginSize];
ClipS: PROC [s: REAL] RETURNS [REAL] ~ {RETURN[MAX[MIN[s, sOuterMax], sOuterMin]]};
ClipF: PROC [f: REAL] RETURNS [REAL] ~ {RETURN[MAX[MIN[f, fOuterMax], fOuterMin]]};
AppendMonotoneBezier:
PROC [bezier: Bezier] ~ {
SubDivide:
PROC ~ {
Mid: PROC [a, b: REAL] RETURNS[REAL] ~ INLINE {RETURN[Real.FScale[a+b, -1]]};
a: Pair ← [Mid[bezier.s0, bezier.s1], Mid[bezier.f0, bezier.f1]];
b: Pair ← [Mid[bezier.s1, bezier.s2], Mid[bezier.f1, bezier.f2]];
c: Pair ← [Mid[bezier.s2, bezier.s3], Mid[bezier.f2, bezier.f3]];
ab: Pair ← [Mid[a.s, b.s], Mid[a.f, b.f]];
bc: Pair ← [Mid[b.s, c.s], Mid[b.f, c.f]];
abc: Pair ← [Mid[ab.s, bc.s], Mid[ab.f, bc.f]];
AppendMonotoneBezier[[bezier.s0, bezier.f0, a.s, a.f, ab.s, ab.f, abc.s, abc.f]];
AppendMonotoneBezier[[abc.s, abc.f, bc.s, bc.f, c.s, c.f, bezier.s3, bezier.f3]];
};
fMin: REAL ~ MIN[bezier.f0, bezier.f1, bezier.f2, bezier.f3];
fMax: REAL ~ MAX[bezier.f0, bezier.f1, bezier.f2, bezier.f3];
sEndMin: REAL ~ MIN[bezier.s0, bezier.s3];
sMin: REAL ~ MIN[sEndMin, bezier.s1, bezier.s2];
sMax: REAL ~ MAX[bezier.s0, bezier.s1, bezier.s2, bezier.s3];
sMinRegion:
INTEGER ←
SELECT sMin
FROM
< sOuterMin => -2,
< sInnerMin => -1,
<= sInnerMax => 0,
<= sOuterMax => 1,
ENDCASE => 2;
fMinRegion:
INTEGER ←
SELECT fMin
FROM
< fOuterMin => -2,
< fInnerMin => -1,
<= fInnerMax => 0,
<= fOuterMax => 1,
ENDCASE => 2;
sMaxRegion:
INTEGER ←
SELECT sMax
FROM
< sOuterMin => -2,
< sInnerMin => -1,
<= sInnerMax => 0,
<= sOuterMax => 1,
ENDCASE => 2;
fMaxRegion:
INTEGER ←
SELECT fMax
FROM
< fOuterMin => -2,
< fInnerMin => -1,
<= fInnerMax => 0,
<= fOuterMax => 1,
ENDCASE => 2;
IF MAX[ABS[sMinRegion], ABS[fMinRegion], ABS[sMaxRegion], ABS[fMaxRegion]] <= 1
THEN {
IF sMax-sMin <= LAST[CARDINAL]/8 AND bezier.s1 >= sEndMin AND bezier.s2 >= sEndMin AND fMax-fMin <= LAST[CARDINAL]/(8*fScale) THEN AppendMonotoneShortPiece[bezier, fMin]
ELSE SubDivide[];
}
ELSE
IF sMinRegion > 0
OR sMaxRegion < 0
OR fMinRegion > 0
OR fMaxRegion < 0
THEN
AppendMonotoneBezier[[
ClipS[bezier.s0], ClipF[bezier.f0],
ClipS[bezier.s1], ClipF[bezier.f1],
ClipS[bezier.s2], ClipF[bezier.f2],
ClipS[bezier.s3], ClipF[bezier.f3]
]]
ELSE SubDivide[];
};
AppendBezier:
PROC [b: Bezier] ~ {
First find the coefficients of the s projection.
c0: REAL ~ b.s0;
c1: REAL ~ 3*(b.s1 - c0);
t: REAL ~ 3*(b.s2 - b.s1);
c2: REAL ~ t - c1;
c3: REAL ~ b.s3 - 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 ~ RealFns.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];
force monotonicity, in case of roundoff error
low.s2 ← low.s3;
middle.s1 ← middle.s0;
middle.s2 ← middle.s3;
high.s1 ← high.s0;
AppendMonotoneBezier[low];
AppendMonotoneBezier[middle];
AppendMonotoneBezier[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];
force monotonicity, in case of roundoff error
low.s2 ← low.s3;
high.s1 ← high.s0;
AppendMonotoneBezier[low];
AppendMonotoneBezier[high];
}
ELSE AppendMonotoneBezier[b];
};
firstPoint, lastPoint: Pair;
started: BOOLEAN ← FALSE;
Move:
PROC[p:
VEC] ~ {
firstPoint ← lastPoint ← [p.x, p.y];
};
Line:
PROC[p:
VEC] ~ {
s: REAL ~ p.x; f: REAL ~ p.y;
b1, b2: Pair;
IF lastPoint.s IN [sOuterMin..sOuterMax] AND lastPoint.f IN [fOuterMin..fOuterMax]
AND s IN [sOuterMin..sOuterMax] AND f IN [fOuterMin..fOuterMax]
THEN AppendSegment[lastPoint.s, lastPoint.f, s, f]
ELSE {
b1 ← Interpolate[0.333333, lastPoint, [s, f]];
b2 ← Interpolate[0.666667, lastPoint, [s, f]];
AppendBezier[[lastPoint.s, lastPoint.f, b1.s, b1.f, b2.s, b2.f, s, f]];
};
lastPoint ← [s, f];
};
Curve:
PROC[p1, p2, p3:
VEC] ~ {
AppendBezier[[lastPoint.s, lastPoint.f, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y]];
lastPoint ← [p3.x, p3.y];
};
Close:
PROC ~ {
IF lastPoint # firstPoint THEN Line[[firstPoint.s, firstPoint.f]];
};
devicePath.scanLineCrossings ← 0;
devicePath.sMin ← LAST[INTEGER];
devicePath.sMax ← FIRST[INTEGER];
devicePath.fMin ← LAST[INTEGER];
devicePath.fMax ← FIRST[INTEGER];
ImagerPath.Transform[path: path, m: transformation,
moveTo: Move, lineTo: Line, curveTo: Curve, close: Close];
IF devicePath.sMin > devicePath.sMax
THEN
devicePath.sMin ← devicePath.sMax ← devicePath.fMin ← devicePath.fMax ← 0;
IF scratch #
NIL
THEN {
devicePath.pointTable ← scratch.pointTable;
devicePath.bucketTable ← scratch.bucketTable;
devicePath.scratchSegmentList ← TrimScratchSegmentList[scratchSegmentList];
devicePath.scratchPieceList ← TrimScratchPieceList[scratchPieceList];
scratch^ ← devicePath;
RETURN [scratch]
};
RETURN [NEW[DevicePathRep ← devicePath]];
};
shellD: ARRAY [1..11] OF CARDINAL ~ [1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 65535];
Key: PROC [point: Point] RETURNS [CARDINAL] ~ TRUSTED INLINE {RETURN[LOOPHOLE[point]]};
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 Key[a] < Key[b^]
DO
jPtr^ ← b^;
jPtr ← b;
ENDLOOP;
jPtr^ ← a;
ENDLOOP;
ENDLOOP;
};
};
InitialBucketTable:
PROC [devicePath: DevicePath, smin:
INTEGER, smax:
INTEGER, scratch: BucketTable]
RETURNS [bucketTable: BucketTable] ~ {
bucketTableSize: NAT ← smax - smin + 2;
bucketTable ←
IF scratch #
NIL
AND scratch.maxLength >= bucketTableSize
THEN scratch
ELSE NEW [BucketTableRec[bucketTableSize]];
bucketTable.length ← bucketTableSize;
FOR i:
NAT
IN [0..bucketTableSize)
DO
bucketTable.seq[i] ← 0;
ENDLOOP;
FOR s:
LIST
OF SegmentRep ← devicePath.segmentList, s.rest
UNTIL s =
NIL
DO
start: INTEGER ~ MAX[s.first.sFirstScan, smin] - smin;
end: INTEGER ~ MIN[s.first.sFirstScan+s.first.scanCount, smax] - smin;
IF end > start
THEN {
bucketTable.seq[start] ← bucketTable.seq[start] + 1;
bucketTable.seq[end] ← bucketTable.seq[end] - 1;
};
ENDLOOP;
FOR p:
LIST
OF PieceRep ← devicePath.pieceList, p.rest
UNTIL p =
NIL
DO
start: INTEGER ~ MAX[p.first.sFirstScan, smin] - smin;
end: INTEGER ~ MIN[p.first.sFirstScan+p.first.scanCount, smax] - smin;
IF end > start
THEN {
bucketTable.seq[start] ← bucketTable.seq[start] + 1;
bucketTable.seq[end] ← bucketTable.seq[end] - 1;
};
ENDLOOP;
{sum, sumSum:
NAT ← 0;
FOR i:
NAT
IN [0..bucketTable.length)
DO
sum ← sum + bucketTable.seq[i];
bucketTable.seq[i] ← sumSum;
IF sumSum > maxPointTableSize
THEN {
bucketTable.length ← i+1;
RETURN;
};
sumSum ← sumSum + sum;
ENDLOOP;
};
};
BoundingBox:
PUBLIC
PROC [devicePath: DevicePath]
RETURNS [DeviceRectangle] ~ {
RETURN [[devicePath.sMin, devicePath.fMin, devicePath.sMax-devicePath.sMin, devicePath.fMax-devicePath.fMin]]
};
NumberOfRuns:
PUBLIC
PROC [devicePath: DevicePath]
RETURNS [numberOfRuns:
INT] ~ {
numberOfRuns ← devicePath.scanLineCrossings/2;
};
maxBucketTableSize: NAT ← 808;
maxPointTableSize: NAT ← 808*4;
Convert:
PROC [
devicePath: DevicePath,
resultProc: PROC [devicePath: DevicePath, sStart, sEnd: INTEGER],
clipBox: DeviceRectangle
] ~ {
sStart: INTEGER ← MAX[clipBox.sMin, devicePath.sMin];
sFinal: INTEGER ~ MIN[INT[clipBox.sMin+clipBox.sSize], devicePath.sMax];
sEnd: INTEGER ← sFinal;
fOrigin: INTEGER ← devicePath.fMin;
bucketTable: BucketTable;
WHILE sStart < sFinal
DO
IF sEnd - sStart > maxBucketTableSize THEN sEnd ← sStart + maxBucketTableSize;
bucketTable ← devicePath.bucketTable ← InitialBucketTable[devicePath, sStart, sEnd, devicePath.bucketTable];
IF bucketTable.seq[bucketTable.length-1] > maxPointTableSize
THEN {
sEnd ← sStart;
WHILE bucketTable.seq[sEnd-sStart] < maxPointTableSize
DO
sEnd ← sEnd+1;
ENDLOOP;
IF sEnd > sStart+1 THEN sEnd ← sEnd - 1;
bucketTable ← devicePath.bucketTable ← InitialBucketTable[devicePath, sStart, sEnd, devicePath.bucketTable];
};
CHECKED {
scanLineCrossings: NAT ~ bucketTable.seq[bucketTable.length-1];
pointTable: PointTable ~ devicePath.pointTable
←
IF devicePath.pointTable # NIL
AND devicePath.pointTable.maxLength >= scanLineCrossings
THEN devicePath.pointTable
ELSE NEW[PointTableRec[scanLineCrossings]];
points: NAT ← 0;
FOR p:
LIST
OF SegmentRep ← devicePath.segmentList, p.rest
UNTIL p =
NIL
DO
firstScan: INTEGER ~ MAX[p.first.sFirstScan, sStart];
endScan: INTEGER ~ MIN[p.first.sFirstScan+p.first.scanCount, sEnd];
IF endScan > firstScan
THEN
TRUSTED {
direction: Direction ~ p.first.direction;
w:
REAL ~
MAX[
ABS[p.first.f1-p.first.f0],
ABS[p.first.s1-p.first.s0]];
w cannot be exactly zero, since otherwise endScan = firstScan.
sDelta: INTEGER ← Real.RoundI[16536*(p.first.s1-p.first.s0)/w];
fDelta: INTEGER ~ Real.RoundI[16536*(p.first.f1-p.first.f0)/w];
fAbsDelta: INTEGER ~ ABS[fDelta];
fSignDelta: INTEGER ~ IF fAbsDelta = fDelta THEN 1 ELSE -1;
sReal: REAL ~ firstScan + 0.5;
fReal: REAL ~ p.first.f0 + (sReal-p.first.s0)*(p.first.f1-p.first.f0)/(p.first.s1-p.first.s0);
f: INTEGER ← FloorI[fReal+0.5];
e:
INTEGER ←
IF fAbsDelta = fDelta
THEN Real.RoundI[(f+0.5-fReal)*sDelta]
ELSE Real.RoundI[(fReal-f+0.5)*sDelta];
bPtr: LONG POINTER TO INTEGER ← @(bucketTable.seq[firstScan-sStart]);
IF sDelta <= 0
THEN {
IF sDelta < 0 OR endScan # firstScan + 1 THEN ERROR;
sDelta ← fAbsDelta;
Only one scan line, so sDelta just needs to be positive to avoid an infinite loop.
};
FOR s:
INTEGER
IN [firstScan..endScan)
DO
pointTable[bPtr^] ← [fRel: MAX[f-fOrigin, 0], direction: direction];
bPtr^ ← bPtr^ + 1;
points ← points + 1;
bPtr ← bPtr + SIZE[INTEGER];
e ← e - fAbsDelta;
WHILE e<0
DO
f ← f + fSignDelta;
e ← e + sDelta;
ENDLOOP;
ENDLOOP;
};
ENDLOOP;
FOR p:
LIST
OF PieceRep ← devicePath.pieceList, p.rest
UNTIL p =
NIL
DO
firstScan: INTEGER ~ MAX[p.first.sFirstScan, sStart];
endScan: INTEGER ~ MIN[p.first.sFirstScan+p.first.scanCount, sEnd];
direction: Direction ← p.first.direction;
FOR s:
INTEGER
IN [firstScan..endScan)
DO
f: INTEGER ← FValueFor[p, s];
TRUSTED {
bPtr: LONG POINTER TO INTEGER ← @(bucketTable.seq[s-sStart]);
pointTable[bPtr^] ← [fRel: f-fOrigin, direction: direction];
bPtr^ ← bPtr^ + 1;
points ← points + 1;
};
ENDLOOP;
ENDLOOP;
IF points # scanLineCrossings THEN ERROR;
resultProc[devicePath, sStart, sEnd];
};
sStart ← sEnd;
sEnd ← sFinal;
ENDLOOP;
};
ConvertToRuns:
PUBLIC
PROC [
devicePath: DevicePath,
runProc: PROC [sMin, fMin: INTEGER, fSize: NAT],
clipBox: DeviceRectangle,
parityFill: BOOLEAN ← FALSE
] ~ {
Result:
PROC [devicePath: DevicePath,
sStart, sEnd:
INTEGER] ~ {
bucketTable: BucketTable ~ devicePath.bucketTable;
pointTable: PointTable ~ devicePath.pointTable;
parityMask: CARDINAL ~ IF parityFill THEN 1 ELSE LAST[CARDINAL];
scanLineCrossings: NAT ~ bucketTable.seq[bucketTable.length-1];
fOrigin: INTEGER ~ devicePath.fMin;
wrap: INTEGER ← 0;
pointNumber: NAT ← 0;
FOR line:
NAT
IN [0..bucketTable.length)
DO
s: INTEGER ~ sStart + line;
firstPointOnNextLine: NAT ~ bucketTable.seq[line];
numberOfPointsOnLine: NAT ~ firstPointOnNextLine - pointNumber;
fStart: INTEGER;
IF numberOfPointsOnLine = 2
THEN {
p1, p2: Point;
IF Key[p1 ← pointTable[pointNumber]] > Key[p2 ← pointTable[pointNumber+1]]
THEN
{pointTable[pointNumber] ← p2; pointTable[pointNumber+1] ← p1}
}
ELSE ShellSort[pointTable, pointNumber, numberOfPointsOnLine];
WHILE pointNumber < firstPointOnNextLine
DO
point: Point ~ pointTable[pointNumber];
pointNumber ← pointNumber + 1;
IF BITANDI[wrap, parityMask] = 0 THEN fStart ← point.fRel + fOrigin;
wrap ← wrap + deltaWrap[point.direction];
IF
BITANDI[wrap, parityMask] = 0
THEN {
fMin: INTEGER ← MAX[fStart, clipBox.fMin];
fMax: INTEGER ← MIN[point.fRel + fOrigin, clipBox.fMin+clipBox.fSize];
IF fMax > fMin THEN runProc[s, fMin, fMax-fMin];
};
ENDLOOP;
IF wrap # 0 THEN ERROR;
ENDLOOP;
};
Convert[devicePath, Result, clipBox];
};
ConvertToPixels:
PUBLIC
PROC [
devicePath: DevicePath,
pixelMap: PixelMap,
value: CARDINAL,
parityFill: BOOLEAN,
function: Function
] ~ {
clipBox: DeviceRectangle ← ImagerPixelMap.BoundedWindow[pixelMap];
lgBitsPerPixel: INTEGER ← pixelMap.refRep.lgBitsPerPixel;
rast: CARDINAL ← pixelMap.refRep.rast;
bbTableSpace: PrincOps.BBTableSpace;
bbPtr: PrincOps.BBptr ← InitBBTable[];
InitBBTable:
PROC
RETURNS [bb: PrincOps.BBptr] ~
TRUSTED
INLINE {
bb ← PrincOpsUtils.AlignedBBTable[@bbTableSpace];
bb^ ← [
dst: [word: NIL, bit: 0],
dstBpl: rast*Basics.bitsPerWord,
src: [word: @replicatedPixel, bit: 0],
srcDesc: [gray[[yOffset: 0, widthMinusOne: 0, heightMinusOne: 0]]],
height: 1,
width: 0,
flags: [direction: forward, disjoint: TRUE, disjointItems: TRUE, gray: TRUE, srcFunc: function.srcFunc, dstFunc: function.dstFunc]
];
};
replicatedPixel:
CARDINAL ←
BITAND[value, Shift[1, Shift[1, lgBitsPerPixel]]-1] * (
SELECT lgBitsPerPixel
FROM
0 => 0FFFFH,
1 => 05555H,
2 => 01111H,
3 => 00101H,
4 => 00001H,
ENDCASE => ERROR
);
pointer: LONG POINTER ~ pixelMap.refRep.pointer;
words: LONG CARDINAL ~ pixelMap.refRep.words;
fBase: INTEGER ~ pixelMap.fOrigin;
destLine: LONG POINTER ← pointer;
sDest: INTEGER ← pixelMap.sOrigin;
Run:
PROC [sMin, fMin:
INTEGER, fSize:
NAT] ~
TRUSTED {
bitIndex: CARDINAL ← Shift[fMin-fBase, lgBitsPerPixel];
bbPtr.width ← Shift[fSize, lgBitsPerPixel];
IF sMin = sDest + 1
THEN {
destLine ← destLine + rast;
sDest ← sMin;
}
ELSE
IF sMin # sDest
THEN {
destLine ← pointer + Basics.LongMult[sMin-pixelMap.sOrigin, rast];
sDest ← sMin;
};
bbPtr.dst.word ← destLine + bitIndex / Basics.bitsPerWord;
bbPtr.dst.bit ← bitIndex MOD Basics.bitsPerWord;
IF bbPtr.dst.word-pointer < 0 OR bbPtr.dst.word-pointer+NAT[bbPtr.width+15]/16 > words THEN ERROR;
PrincOpsUtils.BITBLT[bbPtr];
};
ConvertToRuns[devicePath, Run, clipBox, parityFill];
};
TryBox:
PROC [devicePath: DevicePath, clipBox: DeviceRectangle]
RETURNS [isBox:
BOOL ←
FALSE, box: DeviceRectangle ← [0,0,0,0]] ~ {
segList: LIST OF SegmentRep ← devicePath.segmentList;
IF devicePath.pieceList # NIL OR segList = NIL OR segList.rest = NIL OR segList.rest.rest # NIL THEN RETURN
ELSE {
seg0: SegmentRep ← segList.first;
seg1: SegmentRep ← segList.rest.first;
fMin: REAL ← MIN[seg0.f0, seg1.f0];
fMax: REAL ← MAX[seg0.f0, seg1.f0];
IF seg0.f0 # seg0.f1 THEN RETURN;
IF seg1.f0 # seg1.f1 THEN RETURN;
isBox ← TRUE;
box.sMin ← seg0.sFirstScan;
box.sSize ← seg0.scanCount;
box.fMin ← FloorI[fMin+0.5];
box.fSize ← FloorI[fMax+0.5]-box.fMin;
box ← ImagerPixelMap.Intersect[box, clipBox];
};
};
ConvertToManhattanPolygon:
PUBLIC
PROC [
devicePath: DevicePath,
clipBox: DeviceRectangle,
parityFill: BOOLEAN
] RETURNS [LIST OF DeviceRectangle] ~ {
Runs:
PROC [
run: PROC [sMin, fMin: INTEGER, fSize: NAT],
repeat: PROC [timesToRepeatScanline: NAT]] ~ {
ConvertToRuns[devicePath, run, clipBox, parityFill];
};
isBox: BOOL;
box: DeviceRectangle;
[isBox, box] ← TryBox[devicePath, clipBox];
IF isBox THEN RETURN [ImagerManhattan.CreateFromBox[box]]
ELSE RETURN [ImagerManhattan.CreateFromRuns[Runs]];
};