DIRECTORY
Basics USING [BITAND, BITOR, BITSHIFT, BITXOR, LongDiv, LongMult],
ImagerManhattan USING [CreateFromBox, CreateFromBoxes],
ImagerPath USING [PathProc, Transform],
ImagerScanConverter USING [],
ImagerScanConverterPrivate USING [BucketTable, BucketTableRec, DevicePathRep, Direction, PieceRep, Point, PointTable, PointTableRec, SegmentRep],
ImagerTransformation USING [Transformation],
Real USING [FixC, FScale, RoundC, RoundI],
RealFns USING [ArcTan, Cos, Sin, SqRt],
SF USING [Box, BoxAction, BoxGenerator, Intersect, maxBox],
Vector2 USING [VEC];

ImagerScanConverterImpl: CEDAR PROGRAM
IMPORTS Basics, ImagerManhattan, ImagerPath, Real, RealFns, SF
EXPORTS ImagerScanConverter
~ BEGIN

Bezier: TYPE ~ RECORD [s0, f0, s1, f1, s2, f2, s3, f3: REAL];
Pair: TYPE ~ RECORD [s, f: REAL];
Box: TYPE ~ SF.Box;
maxBox: Box ~ SF.maxBox;
BoxAction: TYPE ~ SF.BoxAction;
BoxGenerator: TYPE ~ SF.BoxGenerator;
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;
VEC: TYPE ~ Vector2.VEC;

lgFScale: NAT ~ 6;
fScale: NAT ~ 64; -- must be a power of two.
flatness: REAL _ 4; -- 1/max allowed error in pixels.

retainScratch: INT _ 30;
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 {
deltaX: REAL ~ b.s3 - b.s0;
deltaY: REAL ~ b.f3 - b.f0;
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 {
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: Box,
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 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 - segment.sFirstScan - 0.5];
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 - piece.sFirstScan - 0.5];
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.min.s]];
sInnerMax: REAL _ MIN[REAL[LAST[NAT]-2], REAL[clipBox.max.s]];
fInnerMin: REAL _ MAX[-REAL[LAST[NAT]-2], REAL[clipBox.min.f]];
fInnerMax: REAL _ MIN[REAL[LAST[NAT]-2], REAL[clipBox.max.f]];
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[sMinRegion], ABS[fMinRegion]] <= 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] ~ {
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;
d0: REAL ~ c1;
d1: REAL ~ 2*c2;
d2: REAL ~ 3*c3;
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;
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];
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];
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;
};
};

Bounds: PROC [devicePath: DevicePath] RETURNS [Box] ~ INLINE {
RETURN[[
min: [s: devicePath.sMin, f: devicePath.fMin], 
max: [s: devicePath.sMax, f: devicePath.fMax]
]];
};

BoundingBox: PUBLIC PROC [devicePath: DevicePath, clipBox: Box _ maxBox] 
RETURNS [Box] ~ {
RETURN[Bounds[devicePath].Intersect[clipBox]];
};

NumberOfBoxes: PUBLIC PROC [devicePath: DevicePath] RETURNS [INT] ~ {
RETURN[IF IsBox[devicePath] THEN 1 ELSE devicePath.scanLineCrossings/2];
};

maxBucketTableSize: NAT _ 808;
maxPointTableSize: NAT _ 808*4;
Convert: PROC [
devicePath: DevicePath,
resultProc: PROC [devicePath: DevicePath, sStart, sEnd: INTEGER],
clipBox: Box
] ~ {
sStart: INTEGER _ MAX[clipBox.min.s, devicePath.sMin];
sFinal: INTEGER ~ MIN[clipBox.max.s, 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]];
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;
};
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;
};

IsBox: PROC [devicePath: DevicePath] RETURNS [BOOL] ~ {
IF devicePath.pieceList=NIL AND devicePath.segmentList#NIL THEN {
seg0: LIST OF SegmentRep ~ devicePath.segmentList;
seg1: LIST OF SegmentRep ~ seg0.rest;
IF seg1#NIL AND seg1.rest=NIL THEN 
RETURN[seg0.first.f0=seg0.first.f1 AND seg1.first.f0=seg1.first.f1];
};
RETURN[FALSE];
};

ConvertToBoxes: PUBLIC PROC [devicePath: DevicePath, oddWrap: BOOL _ FALSE, 
clipBox: Box _ maxBox, boxAction: BoxAction] ~ {
IF IsBox[devicePath] THEN boxAction[Bounds[devicePath].Intersect[clipBox]]
ELSE {
Result: PROC [devicePath: DevicePath, sStart, sEnd: INTEGER] ~ {
bucketTable: BucketTable ~ devicePath.bucketTable;
pointTable: PointTable ~ devicePath.pointTable;
parityMask: CARDINAL ~ IF oddWrap 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: Point ~ pointTable[pointNumber];
p2: Point ~ pointTable[pointNumber+1];
IF Key[p1] > Key[p2] 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: NAT ~ MAX[fStart, clipBox.min.f];
fMax: NAT ~ MIN[point.fRel + fOrigin, clipBox.max.f];
IF fMax > fMin THEN boxAction[[min: [s: s, f: fMin], max: [s: s+1, f: fMax]]];
};
ENDLOOP;
IF wrap # 0 THEN ERROR;
ENDLOOP;
};
Convert[devicePath, Result, clipBox];
};
};

ConvertToManhattanPolygon: PUBLIC PROC [
devicePath: DevicePath, oddWrap: BOOL, clipBox: Box] RETURNS [LIST OF Box] ~ {
IF IsBox[devicePath] THEN {
box: Box ~ BoundingBox[devicePath, clipBox];
RETURN[ImagerManhattan.CreateFromBox[box]];
}
ELSE {
boxes: BoxGenerator ~ {
ConvertToBoxes[devicePath: devicePath, oddWrap: oddWrap, 
clipBox: clipBox, boxAction: boxAction];
};
RETURN[ImagerManhattan.CreateFromBoxes[boxes]];
};
};

END.
ΒImagerScanConverterImpl.mesa
Copyright c 1984, 1985, 1986 by Xerox Corporation.  All rights reserved.
Michael Plass, November 26, 1985 11:13:00 am PST
Doug Wyatt, March 7, 1986 2:05:22 pm PST
-- These parameters control the precision with which the inner loop b subdivision is done. 
-- This parameter controls how much scratch storage a devicePath retains. 

-- Some inlines for basic bit-hacking operations.
Not used now, but a little easier to uderstand than the real one below.
this could be speeded up, if necessary
In this case, the convergence is faster.
First find the coefficients of the s projection.
Now find the coefficients of the derivative.
Find where the derivative vanishes.
Now break it up as needed
force monotonicity, in case of roundoff error
force monotonicity, in case of roundoff error
w cannot be exactly zero, since otherwise endScan = firstScan.
Only one scan line, so sDelta just needs to be positive to avoid an infinite loop.
Κ σ˜
codeš
œ™Kšœ
Οm
œ=™HK™0K™(—K˜š
Οk	˜	Kšœžœžœžœžœžœ˜BKšœžœ"˜7Kšœžœ˜'Kšœžœ˜Kšœžœq˜‘
Kšœžœ˜,Kšœžœ ˜*Kšœžœ˜'Kšžœ
žœ3˜;Kšœžœžœ˜—K˜KšΠblœž
˜&Kšžœ5ž˜>Kšžœ˜šœž˜K˜Kšœžœžœ"žœ˜=Kšœžœžœžœ˜!Kšœžœžœ˜Kšœžœ˜Kšœžœžœ˜Kšœžœžœ˜%Kšœžœžœ˜%Kšœžœ
žœ,˜FKšœ
žœ*˜;Kšœžœ-˜AKšœžœ(˜7Kšœ
žœ'˜5Kšœžœ$˜/Kšœžœ)˜9Kšœžœ,˜?Kšœžœ)˜9šžœžœžœ
˜K˜—š
œ[™[Kšœ
žœ˜KšœžœΟc˜,Kšœ
žœ !˜5K˜—š
œJ™JKšœžœ˜K™—™1š
Πknœžœžœžœ
žœ
˜/Kšœžœžœžœ	˜'K˜—š
‘œžœžœžœ
žœ
˜.Kš
œžœžœ
žœžœ
žœžœ˜EK˜—š
‘œžœžœžœ
žœ
˜.Kšœžœžœžœ	˜&K˜—š
‘œžœžœžœ
žœ
˜/Kšœžœ
žœžœ	˜'K˜—šΟnœžœžœžœžœžœ
˜8Kšœžœ
žœžœ	˜)K˜—š
’œžœžœžœžœ
˜6Kšœžœžœžœ˜1K˜—š
’œžœžœžœ
žœ
˜,Kšœžœžœžœ
˜-K˜—š
’œžœžœžœžœ
˜+Kšœžœžœžœ
˜5K˜—š
’œžœžœžœžœ
˜-Kšœžœžœžœ
˜5K˜——Kšœžœžœ
žœ˜0š’	œžœ	žœ
žœžœžœžœ˜YKšœžœžœžœ˜*Kš
œ˜KšœžœžœE˜YKšžœ
žœ
žœ!˜;šžœž˜%Kšœžœ
˜šžœžœ
žœžœ˜!Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜šžœžœ˜"Kš
œE˜EKš
œ;˜;Kš
œ˜Kš
œ˜Kš
œ
˜
—šžœ˜Kšœžœ˜(Kš
œ˜Kš
œD˜DKš
œC˜CKš
œ˜Kš
œ˜Kš
œ˜—Kšžœ
˜—Kšžœ
žœ
žœ
˜šžœžœ
žœ
žœ
žœ
žœ˜FKšžœ&˜*—šžœ
žœ
˜Kšžœ_˜cKšžœe˜i—Kš
œ˜K˜—š
’œžœ
žœžœžœ˜WK™GKšœžœ˜Kšœžœ˜K™&Kšœžœ"˜-Kšœžœ˜Kšœžœ˜Kšœžœ%˜-Kšœžœ%˜-Kšœžœžœ
žœ	žœžœ˜.Kš	œžœžœ
žœžœ˜)Kš
œ˜šžœž˜Kš
œ,˜,Kš
œ˜Kšžœ
˜—Kšžœžœžœ?˜VKš
œ˜J˜—š’œžœ
žœžœ˜LKšœžœ˜Kšœžœ˜Kšœžœ!˜+Kšœžœ+˜4Kšœžœ+˜4Kš	œžœžœ
žœžœ˜,Kšœžœ	˜Kš
œ˜šžœž˜Kš
œ,˜,Kš
œ˜Kšžœ
˜—šžœžœžœ
žœžœžœžœžœ˜
J™(Jš
œ>˜>Jš
œ˜—Kš
œ˜J˜—Kšœžœ˜š’œžœžœžœ˜;Kšœ
žœ'˜.K˜—š’	œžœžœžœ˜DK˜K˜K˜K˜K˜K˜K˜K˜K˜K˜K˜Kš
œ7˜7Kš
œ8˜8Kš
œ˜K˜—š
’œžœžœžœ
žœ˜UKš
žœžœ
žœ
žœžœ˜#Kš
œ˜Kšœžœ
˜šžœžœ
žœ˜*Kšžœžœ
žœ˜.šžœ˜Kšœžœ
žœ˜šžœ
žœ
ž˜Jš
œ˜Jšžœ
˜—Jš
œ$˜$Jš
œ˜—Jšœžœ
˜!Jš
œ˜—Kš
œ˜K˜—š
’œžœžœžœ
žœ˜QKš
žœžœ
žœ
žœžœ˜#Kš
œ˜Kšœžœ
˜šžœžœ
žœ˜(Kšžœžœ
žœ˜,šžœ˜Kšœžœ
žœ˜šžœ
žœ
ž˜Jš
œ˜Jšžœ
˜—Jš
œ"˜"Jš
œ˜—Jšœžœ
˜Jš
œ˜—Kš
œ˜K˜—š’œžœžœ
žœ
žœžœ
žœ˜^Kš
œ˜šžœžœ
žœžœ˜'Kšœžœ
žœ˜šžœžœ
žœžœžœ
ž˜4Jš
œ˜Jšžœ
˜—šžœžœ
žœ˜Jš
œ˜Jšœžœ
˜Jš
œ
˜
—Jšžœžœ
˜
Jš
œ˜—šžœžœ
ž˜Kšœžœ
žœ˜Kš
œ˜Kšœ	žœ
˜
Kšžœ
˜—Kš
œ˜K˜—š’œžœžœ
žœžœžœ
žœ˜XKš
œ˜šžœžœ
žœžœ˜'Kšœžœ
žœ˜šžœžœ
žœžœžœ
ž˜4Jš
œ˜Jšžœ
˜—šžœžœ
žœ˜Jš
œ˜Jšœžœ
˜Jš
œ
˜
—Jšžœžœ
˜
Jš
œ˜—šžœžœ
ž˜Kšœžœ
žœ˜Kš
œ˜Kšœ	žœ
˜
Kšžœ
˜—Kš
œ˜K˜—š’
œžœ
žœ˜Kš
œ˜K˜4Kš
œ
˜
Kšœžœ
 ˜2Kšœžœ˜Kš
œ˜Kšœžœ
žœ-˜HKšœžœ
žœ)˜Bš’
œžœžœ˜.Kš
œ˜šžœ	žœ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ
˜
—šžœ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ.˜.Kšœž
œ<˜Dšžœžœ˜Kš
œP˜PKšžœ&žœ&˜RKšžœžœ&žœ:˜ƒ
Kšœžœ:˜OKšœžœ>˜Sšžœžœ
ž˜ Kšœžœ!˜>—šžœ˜Kšœžœ
žœ!˜+Kš
œ˜Kš
œ ˜ Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ˜—Kš
œ˜—š’œžœžœ˜:Kšœžœ˜2Kšžœžœ&˜Ešžœ˜Kš
œ˜Kšœžœ#˜-Kšœžœžœ˜Kšœžœ
˜Kšœ
žœ˜Kš
œ˜š
žœžœ
žœžœ
žœ
žœž˜EKš
œ˜Kš
œ˜Kš
œ ˜ Kšžœ
˜—šžœ
žœ˜Kš
œ=˜=Kš
œ˜Kš
œ˜—Kšžœ˜"Kš
œ˜Kš
œ!˜!Kš
œ9˜9Kš
œ9˜9Kš
œ9˜9Kš
œ9˜9Kš
œ<˜<Kš
œ9˜9Kš
œ9˜9Kš
œ9˜9Kš
œ0˜0Kš
œ&˜&Kšœž
œ4˜:šžœžœ˜Kš
œN˜NKšžœ$žœ$˜NKšžœžœ$žœ6˜{Kšžœžœ˜BKšœžœ0žœ-˜ušžœžœ
ž˜Kšœžœ˜8—šžœ˜Kšœžœ
žœ˜'Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ˜—K˜—Kš
œ˜—Kš
œžœžœžœ
žœ
žœžœ˜?Kš
œžœžœ
žœ
žœ
žœžœ˜>Kš
œžœžœžœ
žœ
žœžœ˜?Kš
œžœžœ
žœ
žœ
žœžœ˜>Kšœžœžœžœ
žœ
žœ˜BKšœžœžœ
žœ
žœ
žœ˜AKšœžœžœžœ
žœ
žœ˜BKšœžœžœ
žœ
žœ
žœ˜AKš’œžœžœžœžœžœ
žœ
žœ˜SKš’œžœžœžœžœžœ
žœ
žœ˜Sš’œžœ˜/š’	œžœ˜Kš’œžœžœžœ
žœžœžœ˜MKš
œA˜AKš
œA˜AKš
œA˜AKš
œ*˜*Kš
œ*˜*Kš
œ/˜/Kš
œQ˜QKš
œQ˜QK˜—Kšœžœžœ-˜=Kšœžœžœ-˜=Kšœ	žœžœ˜*Kšœžœžœ ˜0Kšœžœžœ-˜=šœžœžœž˜&K˜K˜K˜K˜Kšžœ˜
—šœžœžœž˜&K˜K˜K˜K˜Kšžœ˜
—šœžœžœž˜&K˜K˜K˜K˜Kšžœ˜
—šœžœžœž˜&K˜K˜K˜K˜Kšžœ˜
—Kšžœ
žœ
žœžœžœžœ˜Ošžœ˜Kšžœžœ
žœžœžœžœžœ
žœ
žœ'˜©
Kšžœ
˜Kš
œ
˜
—šžœ
žœžœžœžœž˜Qš
œ˜Kš
œ#˜#Kš
œ#˜#Kš
œ#˜#Kš
œ"˜"Kš
œ˜——Kšžœ
˜K˜—š’œžœ˜"™0Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ
˜Kšœžœ˜—™,Kšœžœ˜Kšœžœ˜Kšœžœ˜—™#Kšœžœ˜Kšœ
žœ˜šžœ
žœ	žœ˜Kšœžœ	˜Kšœžœ	˜Kšœžœ˜šžœžœ˜Kšœžœ˜Kšœ
žœžœžœ
˜,Kš	œžœ
žœ	žœžœ˜'Kš
œ˜—Kš
œ
˜
—Kšžœ
žœ
žœ	žœ
˜%—™Kšœžœžœ˜Kšœžœžœ˜Kšžœ	žœžœ˜0šžœ
žœ	žœ
žœ˜+Kš
œ˜Kš
œ"˜"Kš
œ)˜)™-Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜—Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ
˜
—šžœ
žœžœžœžœžœ˜3Kš
œ˜Kš	œžœžœžœžœ˜@™-Kš
œ˜Kš
œ˜—Kš
œ˜Kš
œ˜Kš
œ
˜
—Kšžœ˜—Kš
œ˜—Kš
œ˜Kšœ	žœžœ
˜š’œžœžœ˜Kš
œ$˜$Kš
œ˜—š’œžœžœ˜Kšœžœžœ˜K˜
Kšžœ
žœžœ
žœ˜RKšžœžœžœžœ˜?Kšžœ.˜2šžœ˜Kš
œ.˜.Kš
œ.˜.Kš
œG˜GK˜—Kš
œ˜Kš
œ˜—š’œžœ
žœ˜ Kš
œM˜MKš
œ˜Kš
œ˜—š’œžœ˜Kšžœžœ$˜BKš
œ˜—Kš
œ!˜!Kšœžœ
žœ˜ Kšœžœ
žœ˜!Kšœžœ
žœ˜ Kšœžœ
žœ˜!š
œ3˜3Kš
œ:˜:—šžœ#ž˜)Kš
œJ˜J—šžœžœ
žœ˜Kš
œ+˜+Kš
œ-˜-Kš
œK˜KKš
œE˜EKš
œ˜Kšžœ
˜Kš
œ˜—Kšžœžœ˜)Kš
œ˜K˜—Kšœžœ	žœ
žœ<˜]Kš’œžœžœžœžœ
žœžœ
žœ
˜Wš’	œžœ$žœžœ˜Cšžœ	žœ˜Kš
œ˜Kšœ
žœ
žœ
žœ˜2Kš	œžœ
žœ
žœ$žœ˜GKšžœ3žœ
žœ
žœ
˜Hš	žœžœ
ž
œ
žœž˜1Kšœžœ˜Kšœžœžœ˜%šžœžœ
žœžœžœž˜UKš
œ˜Kšœžœ
žœ
žœ˜#Kšœžœ
žœ
žœ˜šžœ
žœžœ
žœžœžœ
žœžœž˜qKš
œ˜Kš
œ	˜	Kšžœ
˜—Kš
œ
˜
Kšžœ
˜—Kšžœ
˜—Kš
œ˜—Kš
œ˜—š
’œžœ žœžœžœ˜Œ
Kšœžœ˜'š	œžœžœ
žœ&žœ˜TKšžœ
žœ#˜+—Kš
œ%˜%šžœžœ
žœž˜%Kš
œ˜Kšžœ
˜—šžœžœ
žœ-žœžœ
ž˜KKšœžœžœ"˜6Kšœžœžœ4˜Fšžœ
žœ˜Kš
œ4˜4Kš
œ0˜0Kš
œ˜—Kšžœ
˜—šžœžœ
žœ)žœžœ
ž˜GKšœžœžœ"˜6Kšœžœžœ4˜Fšžœ
žœ˜Kš
œ4˜4Kš
œ0˜0Kš
œ˜—Kšžœ
˜—šœžœ˜šžœžœ
žœž˜(Kš
œ˜Kš
œ˜šžœžœ˜$Jš
œ˜Jšžœ
˜Jš
œ˜—Kš
œ˜Kšžœ
˜—K˜—Kš
œ˜K˜—š’œžœžœ	žœ˜>šžœ˜Kš
œ/˜/Kš
œ-˜-Kš
œ˜—K˜K˜—š’œžœ
žœ1žœ
˜[Kšžœ(˜.Kš
œ˜K˜—š
’
œžœ
žœžœžœ˜EKšžœ
žœžœžœ!˜HKš
œ˜K˜—Kšœžœ˜Kšœžœ	˜š’œžœ
˜Kš
œ˜Kšœžœž
œžœ˜AKš
œ˜Kš
œ˜Kšœžœžœ!˜6Kšœžœžœ!˜6Kšœžœ
˜Kšœ	žœ˜#Kš
œ˜šžœž˜Kšžœ$žœ$˜NKš
œl˜lšžœ;žœ˜CKš
œ˜šžœ2ž˜9Kš
œ˜Kšžœ
˜—Kšžœžœ˜(Kš
œl˜lKš
œ˜—šžœ˜	Kšœžœ)˜?šœ.ž˜0Kšžœž˜Kšžœ5˜8Kšžœ˜Kšžœ
žœ#˜+—Kšœžœ˜šžœžœ
žœ-žœžœ
ž˜KKšœžœžœ˜5Kšœ	žœžœ-˜Cšžœžœ
žœ˜%Kš
œ)˜)š	œžœžœ
žœžœ˜FKš
œ>™>—Kšœžœ0˜?Kšœžœ0˜?Kšœžœžœ	˜!Kš	œžœžœžœžœ˜;Kšœžœ˜KšœžœS˜^Kšœžœ˜šœžœ˜Kšžœ˜Kšžœ"˜&Kšžœ#˜'—Kš	œžœ
žœ
žœ
žœ(˜Ešžœ
žœ˜Kšžœžœžœ
žœ
˜4š
œ˜Kš
œR™R—Kš
œ˜—šžœžœ
žœž˜)Kšœžœ&˜DKš
œ˜K˜Kšœžœ
žœ˜Kš
œ˜šžœž˜Kš
œ˜Kš
œ˜Kšžœ
˜—Kšžœ
˜—Kš
œ˜—Kšžœ
˜—šžœžœ
žœ)žœžœ
ž˜GKšœžœžœ˜5Kšœ	žœžœ-˜CKš
œ)˜)šžœžœ
žœž˜)Kšœžœ˜šžœ˜	Kš	œžœ
žœ
žœ
žœ ˜=Kš
œ<˜<Kš
œ˜K˜Kš
œ˜—Kšžœ
˜—Kšžœ
˜—Kšžœžœ
žœ
˜)Kš
œ%˜%Kš
œ˜—Kš
œ˜Kš
œ˜Kšžœ
˜—Kš
œ˜K˜—š’œžœžœžœ˜7š
žœžœ
žœžœ
žœ˜AKšœžœ
žœ%˜2Kšœžœ
žœ˜%š
žœžœ
žœžœ
žœ
˜#Kšžœžœ˜D—K˜—Kšžœ
žœ˜K˜K˜—š
’œžœ
žœ#žœžœ3˜}Kšžœžœ1˜Jšžœ˜š’œžœž
œžœ˜@Kš
œ2˜2Kš
œ/˜/Kš
œžœžœ	žœžœ
žœ
žœ˜=Kšœžœ)˜?Kšœ	žœ˜#Kšœžœ˜Kšœ
žœ˜šžœžœ
žœž˜+Kšœžœ˜Kšœžœ˜2Kšœžœ&˜?Kšœžœ
˜šžœžœ˜"Kš
œ$˜$Kš
œ&˜&šžœžœ˜Kš
œ˜Kš
œ˜Kš
œ
˜
—K˜
—Kšžœ:˜>šžœ$ž˜+Kš
œ'˜'Kš
œ˜Kšžœ
žœžœ˜DKš
œ)˜)šžœ
žœžœ˜'Kšœžœžœ˜'Kšœžœžœ&˜5Kšžœ
žœ;˜NK˜—Kšžœ
˜—Kšžœ
žœ
žœ
˜Kšžœ
˜—Kš
œ˜—Kš
œ%˜%K˜—Kš
œ˜K˜—š’œžœ
žœ$žœžœžœ
žœ	˜wšžœžœ˜Kš
œ,˜,Kšžœ%˜+K˜
—šžœ˜š
œ˜Kš
œb˜bKš
œ˜—Kšžœ)˜/K˜—Kš
œ˜K˜——Kšžœ
˜—…—a0…ε