ImagerStrokeImpl.mesa
Last changed by:
Michael Plass, February 16, 1984 10:34:32 am PST
Doug Wyatt, April 6, 1984 5:14:34 pm PST
DIRECTORY
ImagerBasic USING [Bezier, Pair, PathMapType, StrokeEnd, Transformation],
ImagerConic USING [ToCurves],
ImagerScanConverter USING [CreatePath, DevicePath, DeviceRectangle],
ImagerTransform USING [Contents, SingularValues, TransformationRec],
ImagerStroke USING [],
Real USING [SqRt];
ImagerStrokeImpl: CEDAR PROGRAM
IMPORTS ImagerConic, ImagerScanConverter, ImagerTransform, Real
EXPORTS ImagerStroke
= BEGIN
StrokeEnd: TYPE = ImagerBasic.StrokeEnd;
Pair: TYPE = ImagerBasic.Pair;
Bezier: TYPE = ImagerBasic.Bezier;
DevicePath: TYPE ~ ImagerScanConverter.DevicePath;
DeviceRectangle: TYPE ~ ImagerScanConverter.DeviceRectangle;
maxdepth: NAT ← 10; -- Used in Subdivide
tolerance: REAL ← 0.5; -- Used in GenerateStroke, GenerateThinStroke
Split:
PUBLIC
PROC [bezier: Bezier]
RETURNS [firstHalf, secondHalf: Bezier] ~ {
a,b,c,ab,bc,p: Pair;
Mid: PROC[u,v: Pair] RETURNS[Pair] = INLINE { RETURN[[(u.x+v.x)/2,(u.y+v.y)/2]] };
a ← Mid[bezier.b0,bezier.b1];
b ← Mid[bezier.b1,bezier.b2];
c ← Mid[bezier.b2,bezier.b3];
ab ← Mid[a,b];
bc ← Mid[b,c];
p ← Mid[ab,bc];
RETURN[[bezier.b0, a, ab, p],[p, bc, c, bezier.b3]];
};
Add: PROC[a: Pair, b: Pair] RETURNS[Pair] = INLINE { RETURN[[a.x+b.x,a.y+b.y]] };
Sub: PROC[a: Pair, b: Pair] RETURNS[Pair] = INLINE { RETURN[[a.x-b.x,a.y-b.y]] };
In: PROC[a: Pair, b: Pair, c: Pair] RETURNS[BOOLEAN] = INLINE { RETURN[a.x IN[b.x..c.x] AND a.y IN[b.y..c.y]] };
Min: PROC[a: Pair, b: Pair] RETURNS[Pair] = INLINE { RETURN[[MIN[a.x,b.x],MIN[a.y,b.y]]] };
Max: PROC[a: Pair, b: Pair] RETURNS[Pair] = INLINE { RETURN[[MAX[a.x,b.x],MAX[a.y,b.y]]] };
Dot: PROC[a: Pair, b: Pair] RETURNS[REAL] = INLINE { RETURN[a.x*b.x+a.y*b.y] };
FlatBezier:
PUBLIC
PROC[bezier: Bezier, epsilon:
REAL]
RETURNS[
BOOLEAN] ~ {
dx,dy: REAL;
d1,d2,d,bl,bh: Pair;
oh: Pair=[0.5,0.5];
bh ← Add[Max[bezier.b0,bezier.b3],oh];
bl ← Sub[Min[bezier.b0,bezier.b3],oh];
IF NOT In[bezier.b1,bl,bh] OR NOT In[bezier.b2,bl,bh] THEN RETURN[FALSE];
d1 ← Sub[bezier.b1,bezier.b0];
d2 ← Sub[bezier.b2,bezier.b0];
d ← Sub[bezier.b3,bezier.b0];
dx ← ABS[d.x]; dy ← ABS[d.y];
IF dx+dy < 1 THEN RETURN[TRUE];
IF dy < dx
THEN {
dydx: REAL ← d.y/d.x;
RETURN[ABS[d2.y-d2.x*dydx]<epsilon AND ABS[d1.y-d1.x*dydx]<epsilon]
}
ELSE {
dxdy: REAL ← d.x/d.y;
RETURN[ABS[d2.x-d2.y*dxdy]<epsilon AND ABS[d1.x-d1.y*dxdy]<epsilon]
}
};
Subdivide:
PUBLIC
PROC [bezier: Bezier, vertex:
PROC[Pair], tolerance:
REAL] ~ {
depth: CARDINAL ← 0;
Subdiv:
PROC [b: Bezier] ~ {
IF depth>=maxdepth OR FlatBezier[b, tolerance] THEN vertex[b.b3]
ELSE { b1, b2: Bezier;
[b1, b2] ← Split[b];
depth ← depth + 1;
Subdiv[b1]; -- first half
Subdiv[b2]; -- second half
depth ← depth - 1;
};
};
Subdiv[bezier];
};
DevicePathFromStroke:
PUBLIC
PROC [pathMap: ImagerBasic.PathMapType, pathData:
REF, clientToDevice: ImagerBasic.Transformation, width:
REAL, strokeEnd: StrokeEnd, closed:
BOOLEAN,
clipBox: DeviceRectangle, scratch: DevicePath]
RETURNS [devicePath: DevicePath] = {
cToD: ImagerTransform.TransformationRec ← ImagerTransform.Contents[clientToDevice];
FilterPath: ImagerBasic.PathMapType ~ {
data: REF,
move: PROC[p: Pair],
line: PROC[p: Pair],
curve: PROC[p1, p2, p3: Pair],
conic: PROC[p1, p2: Pair, r: REAL]
lp: Pair;
FilterMove:
PROC[p: Pair] ~ {
move[lp ← p];
};
FilterLine:
PROC[p: Pair] ~ {
IF p#lp THEN line[lp ← p];
};
FilterCurve:
PROC[p1, p2, p3: Pair] ~ {
n: NAT ← 3; -- count position changes
IF lp=p1 THEN n ← n-1; IF p1=p2 THEN n ← n-1; IF p2=p3 THEN n ← n-1;
SELECT n FROM 0 => NULL; 1 => line[lp ← p3]; ENDCASE => curve[p1, p2, lp ← p3];
};
FilterConic:
PROC[p1, p2: Pair, r:
REAL] ~ {
n: NAT ← 2; -- count position changes
IF lp=p1 THEN n ← n-1; IF p1=p2 THEN n ← n-1;
SELECT n FROM 0 => NULL; 1 => line[lp ← p2]; ENDCASE => conic[p1, lp ← p2, r];
};
pathMap[pathData, FilterMove, FilterLine, FilterCurve, FilterConic];
};
Xform:
PROC [p: Pair]
RETURNS [Pair] ~ {
RETURN[[
Transforms (x, y) to (s, f)
cToD.a * p.x + cToD.b * p.y + cToD.c,
cToD.d * p.x + cToD.e * p.y + cToD.f
]]};
GenPath:
PROC [move:
PROC[s, f:
REAL], line:
PROC[s, f:
REAL], curve:
PROC[s1, f1, s2, f2, s3, f3:
REAL]] = {
sv: Pair ~ ImagerTransform.SingularValues[clientToDevice];
AlmostCircular:
PROC[p: Pair]
RETURNS[
BOOL] ~ {
min: REAL ~ MIN[p.x, p.y]; max: REAL ~ MAX[p.x, p.y];
epsilon: REAL ~ 0.1;
RETURN[ABS[min/max-1]<epsilon];
};
IF AlmostCircular[sv]
AND sv.y * width < 1.0
THEN GenerateThinStroke[
pathMap: FilterPath, pathData: NIL,
closed: closed, map: Xform, clipBox: clipBox,
move: move, line: line, curve: curve]
ELSE GenerateStroke[
pathMap: FilterPath, pathData: NIL,
width: width, closed: closed, ends: strokeEnd, map: Xform,
moveTo: move, lineTo: line];
};
devicePath ← ImagerScanConverter.CreatePath[GenPath, clipBox, scratch];
};
GenerateThinStroke:
PUBLIC
PROC[pathMap: ImagerBasic.PathMapType, pathData:
REF, closed:
BOOLEAN, map:
PROC[Pair]
RETURNS[Pair], clipBox: DeviceRectangle, move:
PROC[s, f:
REAL], line:
PROC[s, f:
REAL], curve:
PROC[s1, f1, s2, f2, s3, f3:
REAL]] = {
first: BOOLEAN ← TRUE;
sp: Pair; -- map[first point of trajectory]
mp: Pair; -- map[last point];
xMin: REAL ← clipBox.sMin;
xMax: REAL ← clipBox.sMin+clipBox.sSize;
yMin: REAL ← clipBox.fMin;
yMax: REAL ← clipBox.fMin+clipBox.fSize;
Move: PROC[p: Pair] = {IF first THEN first ← FALSE ELSE Close[]; sp ← mp ← map[p]};
Line: PROC[p: Pair] = {MappedLine[map[p]]};
Curve:
PROC[p1, p2, p3: Pair] = {
MappedCurve[map[p1], map[p2], map[p3]];
};
Conic:
PROC[p1, p2: Pair, r:
REAL] = {
ImagerConic.ToCurves[mp, map[p1], map[p2], r, MappedCurve];
};
MappedLine:
PROC[p1: Pair] = {
p0: Pair ← mp;
mp ← p1;
IF MAX[p0.x, p1.x] < xMin THEN RETURN;
IF MAX[p0.y, p1.y] < yMin THEN RETURN;
IF MIN[p0.y, p1.y] > yMax THEN RETURN;
IF MIN[p0.x, p1.x] > xMax THEN RETURN;
IF p1.x < p0.x THEN {t: Pair ← p0; p0 ← p1; p1 ← t};
IF p1.x-p0.x >=
ABS[p1.y-p0.y]
THEN {
move[p0.x-0.5, p0.y];
line[p0.x, p0.y+0.5];
line[p1.x, p1.y+0.5];
line[p1.x+0.5, p1.y];
line[p1.x, p1.y-0.5];
line[p0.x, p0.y-0.5];
}
ELSE {
IF p1.y < p0.y THEN {t: Pair ← p0; p0 ← p1; p1 ← t};
move[p0.x, p0.y-0.5];
line[p0.x-0.5, p0.y];
line[p1.x-0.5, p1.y];
line[p1.x, p1.y+0.5];
line[p1.x+0.5, p1.y];
line[p0.x+0.5, p0.y];
};
};
MappedCurve:
PROC[p1, p2, p3: Pair] = {
IF MAX[mp.x, p1.x, p2.x, p3.x] < xMin THEN {mp ← p3; RETURN};
IF MAX[mp.y, p1.y, p2.y, p3.y] < yMin THEN {mp ← p3; RETURN};
IF MIN[mp.y, p1.y, p2.y, p3.y] > yMax THEN {mp ← p3; RETURN};
IF MIN[mp.x, p1.x, p2.x, p3.x] > xMax THEN {mp ← p3; RETURN};
Subdivide[bezier: [mp, p1, p2, p3], vertex: MappedLine, tolerance: tolerance];
};
Close:
PROC = {
IF closed THEN MappedLine[sp];
};
pathMap[pathData, Move, Line, Curve, Conic];
IF NOT first THEN Close[];
};
Mag:
PROC[v: Pair]
RETURNS [
REAL] =
INLINE {
RETURN [Real.SqRt[v.x * v.x + v.y * v.y]]
};
Normalize:
PROC[v: Pair]
RETURNS [Pair] =
INLINE {
m: REAL ← Mag[v];
IF m = 0 THEN RETURN[v] ELSE RETURN[[v.x/m, v.y/m]]
};
Midpoint:
PROC[a, b: Pair]
RETURNS[Pair] =
INLINE {
RETURN[[(a.x+b.x)/2, (a.y+b.y)/2]] };
Miter:
PROC[v1, v2: Pair]
RETURNS[
REAL] = {
s, a: REAL; v3: Pair;
v3 ← Normalize[Add[v1, v2]];
s ← Dot[[v1.y, -v1.x], v3]; -- compute sin of angle
a ← s / Real.SqRt[1 - s*s]; -- compute horz vec for angle between v1 & v3
RETURN[a];
};
Three point flatness test:
Flat:
PROC[v1, v2, v3: Pair, epsilon:
REAL]
RETURNS[b:
BOOL] = {
dx, dy: REAL;
d1, d, bl, bh: Pair;
oh: Pair = [0.5, 0.5];
bh ← Add[Max[v1, v3], oh];
bl ← Sub[Min[v1, v3], oh];
IF NOT In[v2, bl, bh] THEN RETURN[FALSE];
d1 ← Sub[v2, v1];
d ← Sub[v3, v1];
dx ← ABS[d.x]; dy ← ABS[d.y];
IF dx + dy < 1 THEN RETURN[TRUE];
IF dy < dx THEN { dydx: REAL ← d.y / d.x; RETURN[ABS[d1.y - d1.x * dydx] < epsilon] }
ELSE { dxdy: REAL ← d.x / d.y; RETURN[ABS[d1.x - d1.y * dxdy] < epsilon] };
};
GenerateStroke:
PUBLIC
PROC[pathMap: ImagerBasic.PathMapType, pathData:
REF, width:
REAL, closed:
BOOLEAN, ends: StrokeEnd,
map: PROC[Pair] RETURNS[Pair], moveTo, lineTo: PROC[s, f: REAL]] = {
h: REAL ← ABS[width]/2; -- half width
hsq: REAL ← h*h;
smallSin: REAL ← 0.001*hsq;
line: BOOLEAN; -- is current segment a line?
b0, b1, b2, b3: Pair; -- control points for current segment
u0, u3: Pair; -- half width normal vectors at b0, b3
p0, q0, p3, q3: Pair; -- corners of stroke boundary for current segment
MiterFlags: TYPE = RECORD[p, q: BOOLEAN];
m0, m3: MiterFlags;
fb0, fb1, fb2, fb3, fu0, fu3, fp3, fq3: Pair; -- saved values for deferred segment
fline: BOOLEAN; fm3: MiterFlags; -- ditto
begin: BOOLEAN;
defer: BOOLEAN;
firstVertex: BOOLEAN ← TRUE;
vertex: PROC[p: Pair] ~ {IF firstVertex THEN {firstVertex ← FALSE; moveTo[p.x, p.y]} ELSE lineTo[p.x, p.y]};
close: PROC ~ INLINE {firstVertex ← TRUE};
Cap:
PROC[b, d, p, q: Pair] = {
SELECT ends
FROM
butt => { };
square => {
v0: Pair ← [b.x-d.y, b.y+d.x];
v3: Pair ← [b.x+d.y, b.y-d.x];
v1: Pair ← [v0.x+d.x, v0.y+d.y];
v2: Pair ← [v3.x+d.x, v3.y+d.y];
vertex[p]; vertex[map[v1]]; vertex[map[v2]]; vertex[q]; close[];
};
round => {
bz: Bezier;
v0, v1, v2, v3: Pair;
f: REAL = 0.5522848; -- 4*(sqrt2-1)/3
a: Pair ← [f*d.x, f*d.y];
v0 ← [b.x-d.y, b.y+d.x];
v3 ← [b.x+d.x, b.y+d.y];
v1 ← [v0.x+a.x, v0.y+a.y];
v2 ← [v3.x-a.y, v3.y+a.x];
bz.b0 ← p; bz.b1 ← map[v1]; bz.b2 ← map[v2]; bz.b3 ← map[v3];
vertex[p]; Subdivide[bz, vertex, tolerance];
v0 ← v3;
v3 ← [b.x+d.y, b.y-d.x];
v1 ← [v0.x+a.y, v0.y-a.x];
v2 ← [v3.x+a.x, v3.y+a.y];
bz.b0 ← bz.b3; bz.b1 ← map[v1]; bz.b2 ← map[v2]; bz.b3 ← q;
Subdivide[bz, vertex, tolerance]; close[];
};
ENDCASE => ERROR;
};
HNormal:
PROC[a, b: Pair]
RETURNS[Pair] = {
returns a vector of length halfWidth normal to the direction from a to b
d: Pair ← Sub[b, a];
u: Pair ← Normalize[d];
RETURN[[-u.y*h, u.x*h]];
};
ComputeP: PROC[b, u: Pair] RETURNS[Pair] = INLINE { RETURN[map[[b.x+u.x, b.y+u.y]]] };
ComputeQ: PROC[b, u: Pair] RETURNS[Pair] = INLINE { RETURN[map[[b.x-u.x, b.y-u.y]]] };
DoCurve:
PROC[b0, b1, b2, b3: Pair, p0, p3: Pair, depth:
NAT ← 0] = {
b01: Pair ← Midpoint[b0, b1];
b12: Pair ← Midpoint[b1, b2];
b23: Pair ← Midpoint[b2, b3];
b11: Pair ← Midpoint[b01, b12];
b22: Pair ← Midpoint[b12, b23];
bm: Pair ← Midpoint[b11, b22]; -- middle point on curve (at t=1/2)
um: Pair ← HNormal[b11, b22]; -- half width normal at bm
pm: Pair ← map[Add[bm, um]]; -- point on stroke edge
IF depth>0
-- always divide at least once --
AND Flat[p0, pm, p3, tolerance] THEN vertex[p3]
ELSE {
DoCurve[b0, b01, b11, bm, p0, pm, depth+1]; -- first half
DoCurve[bm, b22, b23, b3, pm, p3, depth+1]; -- second half
};
};
EmitSegment:
PROC = {
IF NOT m0.p THEN p0 ← ComputeP[b0, u0];
IF NOT m0.q THEN q0 ← ComputeQ[b0, u0];
IF NOT m3.p THEN p3 ← ComputeP[b3, u3];
IF NOT m3.q THEN q3 ← ComputeQ[b3, u3];
vertex[p0];
IF line THEN vertex[p3] ELSE DoCurve[b0, b1, b2, b3, p0, p3];
vertex[q3];
IF line THEN vertex[q0] ELSE DoCurve[b3, b2, b1, b0, q3, q0];
close[];
};
EmitPreviousSegment:
PROC[u4: Pair, miter:
BOOLEAN ←
TRUE] = {
IF begin
THEN {
IF closed
THEN {
fb0 ← b3; fu0 ← u4;
defer ← TRUE }
ELSE {
u3 ← u4;
p3 ← ComputeP[b3, u3]; q3 ← ComputeQ[b3, u3];
m3 ← [TRUE,TRUE];
Cap[b3, [-u3.y, u3.x], q3, p3];
defer ← FALSE };
begin ← FALSE }
ELSE {
IF miter
THEN {
sin: REAL ← u3.x*u4.y-u3.y*u4.x;
IF
ABS[sin]<smallSin
THEN {
cos: REAL ← u3.x*u4.x+u3.y*u4.y;
IF cos>0
THEN {
p3 ← ComputeP[b3, u3]; q3 ← ComputeQ[b3, u3];
m3 ← [TRUE,TRUE] }
ELSE m3 ← [FALSE,FALSE];
}
ELSE {
f: REAL ← hsq/sin;
r: Pair ← [f*(u4.y-u3.y), f*(u3.x-u4.x)];
IF sin<0 THEN { p3 ← map[[b3.x+r.x, b3.y+r.y]]; m3 ← [p: TRUE, q: FALSE] }
ELSE { q3 ← map[[b3.x-r.x, b3.y-r.y]]; m3 ← [p: FALSE, q: TRUE] };
};
}
ELSE m3 ← [FALSE,FALSE];
IF defer
THEN {
fb1 ← b1; fb2 ← b2; fb3 ← b3; fline ← line;
fu3 ← u3; fp3 ← p3; fq3 ← q3; fm3 ← m3;
defer ← FALSE }
ELSE EmitSegment[];
};
b0 ← b3; u0 ← u4; p0 ← p3; q0 ← q3; m0 ← m3;
};
first: BOOLEAN ← TRUE;
Move: PROC[p: Pair] = {IF first THEN first ← FALSE ELSE Close[]; b3 ← p; begin ← TRUE };
Line:
PROC[p: Pair] = {
u0: Pair ← HNormal[b3, p];
EmitPreviousSegment[u0];
b3 ← p; u3 ← u0; line ← TRUE;
};
Curve:
PROC[p1, p2, p3: Pair] = {
u0: Pair ← (IF p1#b3 THEN HNormal[b3, p1] ELSE HNormal[b3, p2]);
EmitPreviousSegment[u0];
b1 ← p1; b2 ← p2; b3 ← p3; line ← FALSE;
u3 ← (IF b2#b3 THEN HNormal[b2, b3] ELSE HNormal[b1, b2]);
};
Conic:
PROC[p1, p2: Pair, r:
REAL] = {
ImagerConic.ToCurves[b3, p1, p2, r, Curve];
};
Close:
PROC = {
IF begin
THEN {
trajectory is a single point
IF closed THEN { --ignore-- }
ELSE {
just pick an arbitrary direction for end caps
u3 ← [0, h];
p3 ← ComputeP[b3, u3];
q3 ← ComputeQ[b3, u3];
Cap[b3, [-h, 0], q3, p3];
Cap[b3, [h, 0], p3, q3];
};
}
ELSE
IF closed
THEN {
IF b3#fb0 THEN Line[fb0]; -- if necessary, extend a line to the first point
EmitPreviousSegment[fu0]; -- emit the segment ending at the first point
b1 ← fb1; b2 ← fb2; b3 ← fb3; line ← fline;
u3 ← fu3; p3 ← fp3; q3 ← fq3; m3 ← fm3;
EmitSegment[]; -- emit the deferred first segment
}
ELSE { EmitPreviousSegment[u3, FALSE]; Cap[b3, [u3.y, -u3.x], p3, q3] };
};
pathMap[pathData, Move, Line, Curve, Conic];
IF NOT first THEN Close[];
};
END.