-- PolygonPenImpl.mesa
-- Michael Plass,  9-Nov-81 14:47:38

DIRECTORY
	Cubic USING [Bezier,Coeffs,BezierToCoeffs],
	Quadratic USING [RealRoots],
	RealFns USING [SqRt],
	Vector USING [Add,Mul,Sub,Vec],
	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: PROGRAM IMPORTS Cubic, Quadratic, RealFns, Vector 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.

-- 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[Vector.Add[b0, pen]];
    curveTo[Vector.Add[b1, pen],Vector.Add[b2, pen],Vector.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: Cubic.Coeffs = Cubic.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:Cubic.Bezier, t0,t1:REAL] RETURNS [Bezier] =
    {RETURN [HighBezier[LowBezier[b,t1],t0*t1]]};

LowBezier: PROCEDURE [b:Cubic.Bezier, t:REAL] RETURNS [Bezier] =
    BEGIN OPEN b;
    q1,q2,q3,qp1,qp2,q: Vector.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:Cubic.Bezier, t:REAL] RETURNS [Bezier] =
    BEGIN OPEN b;
    q1,q2,q3,qp1,qp2,q: Vector.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: Vector.Vec] RETURNS [r:Vector.Vec] =
    BEGIN OPEN Vector;
    r ← Add[Mul[b,t],Mul[a,1-t]];
    END;

Dot: PUBLIC PROCEDURE [pen: Pen, point: Vector.Vec, moveTo: MoveToProc, lineTo:LineToProc, curveTo:CurveToProc] =
    BEGIN
    n: NAT = pen.n;
    IF n>0 THEN moveTo[Vector.Add[pen[0],point]];
    FOR i:NAT IN (0..n) DO lineTo[Vector.Add[pen[i],point]] ENDLOOP;
    END;

Line: PUBLIC PROCEDURE [pen: Pen, startPoint,endPoint: Vector.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, Vector;
	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,Vector;
        BroadStroke
	   [Vector.Sub[pen[(i+1) MOD n],pen[i]],
	    Shifted[pen[i]],
	    moveTo, lineTo, curveTo]
	ENDLOOP
    END;

END.