PolygonPenImpl.mesa
Michael Plass, May 11, 1984 10:16:35 am PDT
Beach, February 9, 1985 9:03:56 pm PST
DIRECTORY
Quadratic USING [RealRoots],
RealFns USING [SqRt],
PolygonPen;
This module provides for the conversion of pen-drawn spline curves to spline-bounded outlines. The simplest kind of pen handled here is the broad pen, which is just a line segment. Polygonal-pen strokes are built up by means of multiple broad-pen strokes.
PolygonPenImpl: CEDAR PROGRAM IMPORTS Quadratic, RealFns EXPORTS PolygonPen =
BEGIN
Bezier: TYPE = PolygonPen.Bezier;
Pen: TYPE = PolygonPen.Pen;
Vec: TYPE = PolygonPen.Vec; -- a broad pen is represented as a vector, with the reference point at the origin.
Add:
PROC[a: Vec, b: Vec]
RETURNS[Vec] =
INLINE {
RETURN[[a.x+b.x,a.y+b.y]]
};
Sub:
PROC[a: Vec, b: Vec]
RETURNS[Vec] =
INLINE {
RETURN[[a.x-b.x,a.y-b.y]]
};
Mul:
PROC[a: Vec, s:
REAL]
RETURNS[Vec] =
INLINE {
RETURN[[a.x*s,a.y*s]]
};
Coeffs: TYPE = RECORD[c0, c1, c2, c3: Vec];
BezierToCoeffs:
PROC[bezier: Bezier]
RETURNS [coeffs: Coeffs] = {
Compute the cubic coefficients from the Bezier points.
c0 ← b0;
c1 ← 3(b1-b0);
c2 ← 3(b0-2b1+b2); [ = 3(b2-b1) - c1 ]
c3 ← -b0 +3(b1-b2) + b3; [ = b3 - (b0 + 3(b2-b1)) ]
t: Vec ← Mul[Sub[bezier.b2,bezier.b1],3];
coeffs.c0 ← bezier.b0;
coeffs.c1 ← Mul[Sub[bezier.b1,bezier.b0],3];
coeffs.c2 ← Sub[t,coeffs.c1];
coeffs.c3 ← Sub[bezier.b3,Add[bezier.b0,t]];
RETURN[coeffs];
};
The results are sent by calling procedures of the following types:
MoveToProc: TYPE = PolygonPen.MoveToProc;
LineToProc: TYPE = PolygonPen.LineToProc;
CurveToProc:
TYPE = PolygonPen.CurveToProc;
SimpleStroke:
PUBLIC
PROCEDURE [pen: Vec, curve: Bezier, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc] =
BEGIN OPEN curve;
moveTo[b0];
lineTo[Add[b0, pen]];
curveTo[Add[b1, pen], Add[b2, pen], Add[b3, pen]];
lineTo[b3];
curveTo[b2, b1, b0]
END;
BroadStroke:
PUBLIC
PROCEDURE [pen: Vec, curve: Bezier, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc] =
BEGIN
c: Coeffs = BezierToCoeffs[curve];
Stroke:
PROC [t0, t1:
REAL] =
{SimpleStroke[pen, SubBezier[curve, t0, t1],
moveTo, lineTo, curveTo]};
q2: REAL = 3*(pen.x*c.c3.y - pen.y*c.c3.x);
q1: REAL = 2*(pen.x*c.c2.y - pen.y*c.c2.x);
q0: REAL = pen.x*c.c1.y - pen.y*c.c1.x;
dSqr: REAL = q1*q1 - 4*q0*q2;
d: REAL = IF dSqr<=0 THEN 0 ELSE RealFns.SqRt[dSqr];
t0, t1: REAL;
nRoots: [0..2];
[[nRoots, t0, t1]] ← Quadratic.RealRoots[q2, q1, q0];
IF nRoots>0
THEN {
IF t0 < 0
THEN t0 ← 0;
IF t0 > 1 THEN t0 ← 1}
ELSE t0 ← 0;
IF nRoots>1
THEN {
IF t1 < 0
THEN t1 ← 0;
IF t1 > 1 THEN t1 ← 1}
ELSE t1 ← 1;
IF 0 < t0 THEN Stroke[0.0, t0];
IF t0 < t1 THEN Stroke[t0, t1];
IF t1 < 1 THEN Stroke[t1, 1.0]
END;
SubBezier:
PROCEDURE [b: Bezier, t0, t1:
REAL]
RETURNS [Bezier] =
{RETURN [HighBezier[LowBezier[b, t1], t0/t1]]};
LowBezier:
PROCEDURE [b: Bezier, t:
REAL]
RETURNS [Bezier] =
BEGIN OPEN b;
q1, q2, q3, qp1, qp2, q: Vec;
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];
RETURN[[b0: b0, b1: q1, b2: qp1, b3: q]];
END;
HighBezier:
PROCEDURE [b: Bezier, t:
REAL]
RETURNS [Bezier] =
BEGIN OPEN b;
q1, q2, q3, qp1, qp2, q: Vec;
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];
RETURN[[b0: q, b1: qp2, b2: q3, b3: b3]];
END;
Interpolate:
PROCEDURE [t:
REAL, a, b: Vec]
RETURNS [r: Vec] =
BEGIN
r ← Add[Mul[b, t], Mul[a, 1-t]];
END;
Dot:
PUBLIC
PROCEDURE [pen: Pen, point: Vec, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc] =
BEGIN
n: NAT = pen.n;
IF n>0 THEN moveTo[Add[pen[0], point]];
FOR i: NAT IN (0..n) DO lineTo[Add[pen[i], point]] ENDLOOP;
END;
Line:
PUBLIC
PROCEDURE [pen: Pen, startPoint, endPoint: Vec, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc] =
{Stroke[pen, [startPoint, Interpolate[0.1, startPoint, endPoint], Interpolate[0.1, startPoint, endPoint], endPoint], moveTo, lineTo, curveTo]};
Stroke:
PUBLIC
PROCEDURE [pen: Pen, curve: Bezier, moveTo: MoveToProc, lineTo: LineToProc, curveTo: CurveToProc] =
BEGIN
Shifted:
PROC [v: Vec]
RETURNS [Bezier] =
BEGIN OPEN curve;
RETURN[[Add[b0, v], Add[b1, v], Add[b2, v], Add[b3, v]]]
END;
n: NAT = pen.n;
Dot[pen, curve.b0, moveTo, lineTo, curveTo];
FOR i:
NAT
IN [0..n)
DO
OPEN curve;
BroadStroke
[Sub[pen[(i+1)
MOD n], pen[i]],
Shifted[pen[i]],
moveTo, lineTo, curveTo]
ENDLOOP
END;
END.