DIRECTORY
GraphicsBasic,
Graphics,
CGVector,
CGCubic,
CGPath,
UFCubicScan,
Inline,
Mopcodes,
Real,
Scaled
;
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] = {
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
=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: 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] = {
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] = {
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 xStart THEN
LineProc[xStart, a.sortKey, y];
nonZeroWrapCount _ nonZeroWrapCount - 1;
};
wrap[k] _ w;
ENDLOOP;
ENDLOOP;
FreeActivePieceTable[active];
FreeWrapTable[wrap];
};
END.
UFCubicScanImpl.mesa
Created February 16, 1983
Edited by Michael Plass, March 2, 1983 2:00 pm
Returns LAST[INTEGER] if y is below the piece, FIRST[INTEGER] if it is above, otherwise the x-intercept rounded to the nearest integer.
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.
Useful for debugging the DevicePath building code
Κ
JJJ.unitΟk JJ J JJJJJ JJJJ18JJ
JWJUJWJΟn
RJ
ZK+K$
$TJ KJJJ
2J
1J (6J GJ HJ
=JJJ$$J$$J$$J))J))J,,J
@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 .LJ9LJATJ9LJATJJ(kJJ$$J$$JJ 5TJ<>J 6J<<QrJ**JJ ]J11J JJ'J!!JPJL J0GJ15J
JJ**J
BJ
CJ
Οc,dJe|JeiJJK1$J)JJ JJK%)
OJ
$+tJ'J:*JJJ 3J)JJJJ&TJ
JJK#J"JK
AJ
XJ J
,
#