PEBezierImpl.mesa
Copyright (C) 1984 by Xerox Corporation. All rights reserved.
Written by Darlene Plebon on August 17, 1983 2:35 pm
Bezier routines for the Path Editor.
DIRECTORY
CGCubic USING [Bezier, Flat, Split],
PEAlgebra USING [DistanceSquared],
PEBezier,
PETrajectoryOps USING [VertexListLength, InsertVertex],
PETypes USING [VertexRec, Point, Segment, SegmentRec];
PEBezierImpl: CEDAR PROGRAM
IMPORTS PEAlgebra, CGCubic, PETrajectoryOps
EXPORTS PEBezier =
BEGIN OPEN PEAlgebra, PEBezier, PETrajectoryOps, PETypes;
BezierSubdivideUntilLines: PUBLIC PROCEDURE [bezier: Bezier, proc: BezierLineProc, depth: NAT ← 0, t0: REAL ← 0.0, t3: REAL ← 1.0] = {
This routine runs the bezier subdivision algorithm on a bezier cubic segment applying the specified client procedure to each straight line segment generated. The client procedure is passed the endpoints of the line segment and the value of the parameter t at the endpoints.
This routine uses flatness and maximum depth tests to control the recursion.
eps: REAL = 1.5;
maxDepth: NAT = 10;
IF depth >= maxDepth OR CGCubic.Flat[bezier, eps] THEN proc[t0: t0, t3: t3, bezier: bezier]
ELSE {
tMid: REAL ← (t0 + t3) / 2.0;
b1, b2: Bezier;
[b1, b2] ← CGCubic.Split[bezier];
BezierSubdivideUntilLines[bezier: b1, proc: proc, depth: depth+1, t0: t0, t3: tMid];
BezierSubdivideUntilLines[bezier: b2, proc: proc, depth: depth+1, t0: tMid, t3: t3];
};
};
BezierSubdivideUntilPoints: PUBLIC PROCEDURE [bezier: Bezier, proc: BezierPointProc, t0: REAL ← 0.0, t3: REAL ← 1.0] = {
This routine runs the bezier subdivision algorithm on a bezier cubic segment applying the specified client procedure to each point generated. The client procedure is passed the point and the value of the parameter t at that point. The subdivision is halted when we get down to pixel resolution.
DoBezierSubdivideUntilPoints[bezier: bezier, proc: proc, t0: t0, t3: t3];
Generate the last point since DoBezierSubdivideUntilPoints misses it.
proc[t: t3, p: bezier.b3];
};
DoBezierSubdivideUntilPoints: PROCEDURE [bezier: Bezier, proc: BezierPointProc, t0: REAL ← 0.0, t3: REAL ← 1.0] = {
This routine runs the bezier subdivision algorithm on a bezier cubic segment applying the specified client procedure to each point generated. The client procedure is passed the point and the value of the parameter t at that point. The subdivision is halted when we get down to pixel resolution. Note that this routine only calls the client procedure with the first of the two knots in a segment of fine enough resolution, thus missing the very last point in the bezier segment that the client called us with.
eps: REAL = 1.0;
IF DistanceSquared[bezier.b0, bezier.b3] < eps THEN proc[t: t0, p: bezier.b0]
ELSE {
tMid: REAL ← (t0 + t3) / 2.0;
b1, b2: Bezier;
[b1, b2] ← CGCubic.Split[bezier];
DoBezierSubdivideUntilPoints[bezier: b1, proc: proc, t0: t0, t3: tMid];
DoBezierSubdivideUntilPoints[bezier: b2, proc: proc, t0: tMid, t3: t3];
};
};
SegmentToBezier: PUBLIC PROCEDURE [segment: Segment] RETURNS [bezier: Bezier] = {
This routine converts a bezier spline segment from our segment representation to the bezier representation used by the CGCubic routines.
numberVertices: CARDINAL ← VertexListLength[segment.vertices];
bezier.b0 ← SELECT TRUE FROM
segment = NIL => [0.0, 0.0],
segment.fp # NIL => segment.fp.point,
numberVertices > 0 => segment.vertices.first.point,
ENDCASE => [0.0, 0.0];
SELECT numberVertices FROM
0 => {
bezier.b1 ← bezier.b0;
bezier.b2 ← bezier.b0;
bezier.b3 ← bezier.b0;
};
1 => {
bezier.b1 ← bezier.b0;
bezier.b2 ← segment.vertices.first.point;
bezier.b3 ← segment.vertices.first.point;
};
2 => {
bezier.b1 ← segment.vertices.first.point;
bezier.b2 ← segment.vertices.first.point;
bezier.b3 ← segment.vertices.rest.first.point;
};
ENDCASE => {
bezier.b1 ← segment.vertices.first.point;
bezier.b2 ← segment.vertices.rest.first.point;
bezier.b3 ← segment.vertices.rest.rest.first.point;
};
};
BezierToSegment: PUBLIC PROCEDURE [bezier: Bezier] RETURNS [segment: Segment] = {
This routine converts a bezier spline segment from the bezier representation used by the CGCubic routines to our segment representation. Two vertices within epsilon of each other are considered identical, and only one of the two is inserted in the segment, thus permitting lines and quadratics. This routine always generates a segment with at least one vertex in it. Note that the fp field of the segment is not initialized properly since this is a pointer back into another segment.
Identical: PROCEDURE [p0, p1: Point] RETURNS [equal: BOOLEAN] = {
eps: REAL = 0.05;
RETURN [DistanceSquared[p0, p1] < eps];
};
segment ← NEW[SegmentRec ← [type: curveTo]];
[segment.vertices,] ← InsertVertex[segment.vertices, NEW[VertexRec ← [point: bezier.b3]], NIL];
IF ~Identical[bezier.b1,bezier.b2] AND ~Identical[bezier.b2,bezier.b3] THEN [segment.vertices,] ← InsertVertex[segment.vertices, NEW[VertexRec ← [point: bezier.b2]], NIL];
IF ~Identical[bezier.b0,bezier.b1] THEN [segment.vertices,] ← InsertVertex[segment.vertices, NEW[VertexRec ← [point: bezier.b1]], NIL];
};
SplitBezier: PUBLIC PROCEDURE [originalBezier: Bezier, t: REAL] RETURNS [bezier1, bezier2: Bezier] = {
This routine splits a bezier spline segment into two segments at the specified point on the curve, recomputing the control points so that the two new segments form the original curve.
OneMinusT: REAL ← 1.0 - t;
temp: Point;
bezier1.b0 ← originalBezier.b0;
bezier1.b1.x ← OneMinusT*originalBezier.b0.x + t*originalBezier.b1.x;
bezier1.b1.y ← OneMinusT*originalBezier.b0.y + t*originalBezier.b1.y;
bezier2.b2.x ← OneMinusT*originalBezier.b2.x + t*originalBezier.b3.x;
bezier2.b2.y ← OneMinusT*originalBezier.b2.y + t*originalBezier.b3.y;
temp.x ← OneMinusT*originalBezier.b1.x + t*originalBezier.b2.x;
temp.y ← OneMinusT*originalBezier.b1.y + t*originalBezier.b2.y;
bezier1.b2.x ← OneMinusT*bezier1.b1.x + t*temp.x;
bezier1.b2.y ← OneMinusT*bezier1.b1.y + t*temp.y;
bezier2.b1.x ← OneMinusT*temp.x + t*bezier2.b2.x;
bezier2.b1.y ← OneMinusT*temp.y + t*bezier2.b2.y;
bezier1.b3.x ← OneMinusT*bezier1.b2.x + t*bezier2.b1.x;
bezier1.b3.y ← OneMinusT*bezier1.b2.y + t*bezier2.b1.y;
bezier2.b0 ← bezier1.b3;
bezier2.b3 ← originalBezier.b3;
};
END.