DIRECTORY Quadratic USING [RealRoots], RealFns USING [SqRt], PolygonPen; 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] = { 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]; }; 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. ^PolygonPenImpl.mesa Michael Plass, May 11, 1984 10:16:35 am PDT Beach, February 9, 1985 9:03:56 pm PST 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. 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)) ] The results are sent by calling procedures of the following types: Êü˜Jšœ™šœ,™,J™&—J˜šÏk ˜ Jšœ œ˜Jšœœ ˜J˜ J˜—Jšœ™J˜Jšœ œœœ ˜MJ˜Jš˜J˜Jšœœ˜!J˜Jšœœ˜J˜JšœœÏcR˜nšÏnœœœœ˜1Jšœ˜J˜—šŸœœœœ˜1Jšœ˜J˜—š Ÿœœ œœœ˜2Jšœ˜J˜—Jšœœœ˜+šŸœœœ˜AJšœ6™6Jšœ™Jšœ™Jšœ&™&Jšœ3™3J˜)J˜J˜,J˜J˜,Jšœ ˜J˜J˜—JšœC™CJšœ œ˜)Jšœ œ˜)šœ œ˜+J˜—šŸ œœ œZ˜xJšœœ˜J˜ J˜J˜2J˜ J˜Jšœ˜J˜—šŸ œœ œZ˜wJš˜Jšœ"˜"šŸœœ œ˜˜-J˜——Jšœœ#˜+Jšœœ#˜+Jšœœ"˜*Jšœœ˜Jš œœœ œœ˜4Jšœœ˜ J˜J˜5šœ œœœ˜(Jšœœ˜—Jšœ˜ šœ œœœ˜(Jšœœ˜—Jšœ˜ Jšœœ˜Jšœ œ˜Jšœœ˜Jšœ˜J˜—šŸ œ œœœ ˜AJšœœ(˜/J˜—šŸ œ œœœ ˜Jš˜J˜ Jšœ˜J˜—šŸœœ œW˜lJš˜Jšœœ ˜Jšœœ˜'Jš œœœœœ˜;Jšœ˜J˜—šŸœœ œf˜|J˜J˜—šŸœœ œZ˜rJš˜šŸœœ œ ˜)Jšœœ˜Jšœ2˜8Jšœ˜—Jšœœ ˜J˜,š œœœœœ˜#˜ šœœ˜ J˜J˜——Jš˜—Jšœ˜J˜—Jšœ˜J˜—…—`º