DIRECTORY
IGScanConverter,
Imager,
Inline,
Mopcodes,
Real,
Scaled
;
IGScanConverterImpl: CEDAR MONITOR
IMPORTS Inline, Real, Scaled
EXPORTS IGScanConverter
= BEGIN OPEN IGScanConverter;
xLimit: NAT _ 60;
yLimit: NAT _ 60;
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];
ShortVec: TYPE = RECORD [x, y: CARDINAL];
XValueFor: PUBLIC PROCEDURE [cubic: CubicRec, y: Scaled.Value] RETURNS [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 -- Required to guarantee termination.
AND 0 #
BITAND[
BITOR[BITXOR[x0, x1], BITOR[BITXOR[x1, x2], BITXOR[x2, x3]]],
LAST[CARDINAL]-255
]
DO
a: ShortVec _ [Mid[x0, x1], Mid[y0, y1]];
b: ShortVec _ [Mid[x1, x2], Mid[y1, y2]];
c: ShortVec _ [Mid[x2, x3], Mid[y2, y3]];
ab: ShortVec _ [Mid[a.x, b.x], Mid[a.y, b.y]];
bc: ShortVec _ [Mid[b.x, c.x], Mid[b.y, c.y]];
p: ShortVec _ [Mid[ab.x, bc.x], Mid[ab.y, bc.y]];
IF yRel
=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: Imager.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: Imager.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] = {
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: Imager.Path,
transformation: Imager.Transformation
] = {
firstPoint, lastPoint: Imager.Vec;
started: BOOLEAN _ FALSE;
outlineStart: NAT _ devicePath.length;
Move: PROC [v: Imager.Vec] = {
IF started THEN Close[];
outlineStart _ devicePath.length;
started _ TRUE;
firstPoint _ lastPoint _ v;
};
Line: PROC [v: Imager.Vec] = {
started _ TRUE;
AppendBezier[devicePath, [lastPoint, Interpolate[0.3333333, lastPoint, v], Interpolate[0.6666667, lastPoint, v], v]];
lastPoint _ v;
};
Curve: PROC [v1, v2, v3: Imager.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;
};
path.generateProc[path, transformation, 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;
};
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
};
shellD: ARRAY [1..11] OF CARDINAL = [1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 65535];
ShellSort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] = TRUSTED {
length: NAT _ startPlusLength - start;
passesPlusOne: [1..11] _ 1;
startPtr: LONG POINTER TO ActivePieceRec _ @(table[start]);
endPtr: LONG POINTER TO ActivePieceRec _ @(table[startPlusLength-1]) + SIZE[ActivePieceRec];
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[ActivePieceRec];
iPtr: LONG POINTER TO ActivePieceRec _ startPtr;
FOR iPtr: LONG POINTER TO ActivePieceRec _ startPtr, iPtr + SIZE[ActivePieceRec] UNTIL iPtr = endPtr DO
a: ActivePieceRec _ iPtr^;
jPtr: LONG POINTER TO ActivePieceRec _ iPtr;
b: LONG POINTER TO ActivePieceRec;
WHILE LOOPHOLE[(b _ jPtr-hTimesSize), LONG CARDINAL] >= LOOPHOLE[startPtr, LONG CARDINAL] AND a.sortKey < b^.sortKey DO
jPtr^ _ b^;
jPtr _ b;
ENDLOOP;
jPtr^ _ a;
ENDLOOP;
ENDLOOP;
};
InsertionSort: 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;
};
Sort: PROCEDURE [table: ActivePieceTable, start, startPlusLength: NAT] _ ShellSort;
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 xStart THEN
LineProc[xStart, a.sortKey, y];
nonZeroWrapCount _ nonZeroWrapCount - 1;
};
wrap[k] _ w;
ENDLOOP;
ENDLOOP;
FreeActivePieceTable[active];
FreeWrapTable[wrap];
};
END.
า IGScanConverterImpl.mesa
Created March 11, 1983
Edited by Michael Plass, March 11, 1983 1:50 pm
These parameters limit the extent of the pieces in either the x or y directions. Decreasing these paramters will use more devicepath storage, but will lead to fewer subdivisions in the inner loop. Tune them to minimize the overall time.
Some inlines for basic bit-hacking operations.
Returns LAST[INTEGER] if y is below the piece, FIRST[INTEGER] if it is above, otherwise the x-intercept rounded to the nearest integer.
-- The following quantity is zero iff x0, x1, x2, and x3 match in their high-order bits.
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.
ส JJJ/unitฯk JJJJ JJJ"JJJ๎JJJ .JWJUJWJฯn
RJ
ZK1K
)
$TJ KJJJ
2J
1J (6J GJ Hฯc%8JXXJ
=JJJJ))J))J))J..J..J11J
@PJ
/J@DJJJK
!uวK0K !PJ.JlJFFJFFJFFJ//J//J22JqwJ ?J
JJ J+J *HJ 4JJ J 3VJJ .#oJ *-6 J.KJ'JJJJJJ**J**JJNNJJJ22J
1AJJJSJSJSJSJ.AJ.AJ.AJ.AJ+FJ .LJ9LJATJ9LJATJJJ9J''JJ$$J$$JJ 4SJ<>J 6J<<QrJ**JJK1$J)JJ JJK%)
OJ
$+tJ'J:*JJJK <] 3WJ&JJ
";J 0\J3H
1JJ.J0"gJJ,J"wJJ JJ
JJJ
3S)JJJJ&TJ
JJK 3SK#J"JK
AJ
XJ J
,
#