
DIRECTORY IO, G2dSpline, G3dBasic, G3dMatrix;

G3dSpline: CEDAR DEFINITIONS
~ BEGIN
Spline:					TYPE ~ G3dMatrix.Matrix;
SplineRep:				TYPE ~ G3dMatrix.MatrixRep;

Bezier:					TYPE ~ RECORD [b0, b1, b2, b3: Triple м []];
Bspline:					TYPE ~ RECORD [b0, b1, b2, b3: Triple м []];
Hermite:					TYPE ~ RECORD [p0, p1, tan0, tan1: Triple м []];

SplinePlaneIntersect:	TYPE ~ RECORD [nRoots: NAT м 0, roots: ARRAY [0..3) OF REAL];

SplineSequence:			TYPE ~ REF SplineSequenceRep;
SplineSequenceRep:		TYPE ~ RECORD [
length:							CARDINAL м 0,
element:							SEQUENCE maxLength: CARDINAL OF Spline
];

NearSpline:				TYPE ~ RECORD [
point:								Triple м [0.0, 0.0, 0.0],	-- point on 3d spline
t:									REAL м 0.0,				-- parametric position
distance:							REAL м 0.0				-- distance to spline
];

PerPointProc:				TYPE ~ PROC [p: Triple] RETURNS [continue: BOOL м TRUE];

Pair:						TYPE ~ G3dBasic.Pair;
Triple:					TYPE ~ G3dBasic.Triple;
Quad:						TYPE ~ G3dBasic.Quad;
Ray:						TYPE ~ G3dBasic.Ray;
TripleSequence:			TYPE ~ G3dBasic.TripleSequence;
NearSpline2d:			TYPE ~ G2dSpline.NearSpline;
InterpolateCyclic: PROC [knots: TripleSequence, tension: REAL м 1.0]
RETURNS [SplineSequence];
Interpolate: PROC [
knots: TripleSequence,
tan0, tan1: Triple м [],
tension: REAL м 1.0,
c: SplineSequence м NIL]
RETURNS [SplineSequence]; 
SplineFromBezier: PROC [b: Bezier, out: Spline м NIL] RETURNS [Spline];

SplineFromBspline: PROC [b: Bspline, out: Spline м NIL] RETURNS [Spline];
SplineFromHermite: PROC [h: Hermite, out: Spline м NIL] RETURNS [Spline];
BezierFromSpline: PROC [s: Spline] RETURNS [Bezier];
BsplineFromSpline: PROC [s: Spline] RETURNS [Bspline];

HermiteFromSpline: PROC [s: Spline] RETURNS [Hermite];
BezierFromHermite: PROC [p0, p1, v0, v1: Triple] RETURNS [b: Bezier];
CopySpline: PROC [spline: Spline, out: Spline м NIL] RETURNS [Spline];
Position: PROC [s: Spline, t: REAL] RETURNS [Triple];

Velocity: PROC [s: Spline, t: REAL] RETURNS [Triple];

Tangent: PROC [s: Spline, t: REAL] RETURNS [Triple];
PositionAndVelocity: PROC [s: Spline, t: REAL] RETURNS [pos, vel: Triple];
Acceleration: PROC [s: Spline, t: REAL] RETURNS [Triple];

MinAcceleration: PROC [s: Spline] RETURNS [t: REAL];
Curvature: PROC [s: Spline, t: REAL] RETURNS [Triple];
CurvatureMag: PROC [s: Spline, t: REAL] RETURNS [REAL];
WalkBezier: PROC [b: Bezier, proc: PerPointProc, epsilon: REAL м 0.05, doLast: BOOL м TRUE];

ForwardDifference: PROC [in: Spline, nSegments: INTEGER, out: Spline м NIL]
RETURNS [Spline];

Samples: PROC [s: Spline, nPoints: NAT, points: TripleSequence м NIL]
RETURNS [TripleSequence];

RefVec: PROC [s: Spline, t: REAL] RETURNS [Triple]; 
IsStraight: PROC [s: Spline, epsilon: REAL м 0.01] RETURNS [BOOL];
Length: PROC [s: Spline, nSteps: NAT м 100] RETURNS [REAL];

ConvexHullArea: PROC [b: Bezier] RETURNS [REAL];

ConvexHullLength: PUBLIC PROC [b: Bezier] RETURNS [REAL];
FlatBezier: PROC [b: Bezier, epsilon: REAL м 0.05] RETURNS [BOOL];

Tiny: PROC [s: Spline, epsilon: REAL м 0.05] RETURNS [BOOL];

Resolution: PROC [s: Spline, epsilon: REAL] RETURNS [INTEGER];
InflectionPoint: PROC [s: Spline] RETURNS [REAL];
NearestPoint: PROC [p: Triple, s: Spline, t0: REAL м 0.0, t1: REAL м 1.0, epsilon: REAL м 0.01]
RETURNS [NearSpline];
PreciseNearestPoint: PUBLIC PROC [p: Triple, s: Spline] RETURNS [n: NearSpline];
NearestPair: PROC [p: Pair, s: Spline, persp: BOOL м FALSE, t0: REAL м 0.0, t1: REAL м 1.0]
RETURNS [NearSpline2d];
NearestLine: PROC [
line: Ray, s: Spline, t0: REAL м 0.0, t1: REAL м 1.0, epsilon: REAL м 0.01]
RETURNS [sPt, lPt: Triple, t, dist: REAL];
NearestSpline: PROC [s1, s2: Spline, epsilon: REAL м 0.01] RETURNS [t1, t2: REAL];
FurthestPoint: PROC [s: Spline] RETURNS [NearSpline];
SplitCurve: PROC [s: Spline, out1, out2: Spline м NIL] RETURNS [s1, s2: Spline];

SplitBezier: PROC [b: Bezier] RETURNS [b1, b2: Bezier];

Subdivide: PROC [s: Spline, t: REAL] RETURNS [s1, s2: Spline];

Reparameterize: PROC [in: Spline, t0, t1: REAL, out: Spline м NIL] RETURNS [Spline];
CopySplineSequence: PROC [splines: SplineSequence] RETURNS [SplineSequence];
AddToSplineSequence: PROC [splines: SplineSequence, spline: Spline]
RETURNS [SplineSequence];
LengthenSplineSequence: PROC [splines: SplineSequence, amount: REAL м 1.3]
RETURNS [SplineSequence];
SlowInOut: PROC [value0, value1, t: REAL] RETURNS [REAL];
TameType: TYPE ~ RECORD [loop, cusp: BOOL м TRUE, inflect, bulge: BOOL м FALSE];

Tame: PROC [in: Spline, tameType: TameType, out: Spline м NIL] RETURNS [Spline];

SplineFromPointsAndNormals: PROC [
point0, point1, normal0, normal1: Triple,
tension: REAL м 1.0,
spline: Spline м NIL]
RETURNS [Spline];

IntersectSplineAndPlane: PROC [spline: Spline, plane: Quad] RETURNS [SplinePlaneIntersect];
GetA: PROC [s: Spline] RETURNS [Triple];
GetB: PROC [s: Spline] RETURNS [Triple];
GetC: PROC [s: Spline] RETURNS [Triple];
GetD: PROC [s: Spline] RETURNS [Triple];
Same: PROC [s1, s2: Spline] RETURNS [BOOL];
END.
..

   Ц  
G3dSpline.mesa
Copyright ╙ 1985, 1992 by Xerox Corporation.  All rights reserved.
Bloomenthal, July 14, 1992 1:48 pm PDT
Type Declarations
The first column of the coeffs matrix contains the coefficients for t3, t2 and t
and the constant term of the x-coordinate; the second column for y, the third for z.
The first row contains the coefficients for the t3 terms, the second row for the t2 terms, etc.

Interpolation Procedures
The curve will interpolate from the last knot through the first knot,
the last knot need not replicate the first.

Creates three-dimensional natural interpolating spline with chord-length parametrization.
End tangents are set if specified tangent is non-zero.
Conversion Procedures
Convert Bezier control points to cubic coefficients; return out if non-NIL.
Convert Bspline control points to cubic coefficients; return out if non-NIL.

Convert Hermite control points to cubic coefficients; return out if non-NIL.

Convert cubic coefficients to Bezier control points.

Convert cubic coefficients to Bspline control points.
Convert cubic coefficients to Hermite control points.

Return the Bezier equivalent of the Hermite representation.

Return a copy of the input coefficients; use out if non-nil.
Evaluation Procedures
Return the point of the curve at position t.
Return the unnormalized tangent of the curve at position t.
An alias for Velocity[].

Optimized computation of both the position and velocity at t.

Return the unnormalized acceleration of the curve at position t.
Return parametric point of minimum acceleration.

Return the unnormalized curvature vector of the curve at position t.

Return the magnitude of the curvature vector.

Callback for each point on curve; e.g., WalkBezier[bezier, DrawTo];
the curve is subdivided such that each segment is flat within epsilon.
Only if doLast call proc for last point of curve.
Create the matrix of forward differences, use out if non-NIL.
Fill the PointSequence with nPoints number of points along the curve.
Return a reference vector for the curve at t.

Return TRUE iff the curve is along a straight line.
epsilon is the maximum deviation from 1.0 allowed the cosine of the
angle formed by adjacent edges of the bezier control polygon.
Size Procedures
Return (approximate) length of curve, derived by summing length of nSteps linear steps.
Return the area of the convex hull of b, approximate if convex hull is non-planar.
Return the sum of the lengths of the four sides of the bezier control polygon.

Because b is a three-dimensional curve with an unknown relation to image space, FlatBezier
does not test if the curve deviates from its straight line approximation by more than a pixel.
Instead, it returns TRUE iff the ratio of the combined lengths of the three sides of the control
shell to the distance between the curve endpoints is less than 1+epsilon, FALSE otherwise.
Return TRUE if distance between curve endpoints is less than epsilon; 
Return the number of segments needed to draw c such that each linear segment deviates
from the curve by at most epsilon.  s is presumed already transformed into image space.
Search Procedures
Analytically compute the parametric location of the inflection point.
If s is straight, return -2; if s has no inflection, return -1.

Using subdivision, find point on the curve between t0 and t1 that is closest to p.
epsilon is the greatest tolerated angular deviation from 90 degrees of the angle formed
between the line segment connecting p and the closest point and the tangent of curve at the
closest point.  The further p is from the curve, the greater the precision needed.
If epsilon = 0.0, PreciseNearestPoint is called.

Compute the nearest point analytically.  This is precise, not prone to error, but runs about
2-5 times slower than NearestPoint, depending on the position of p with respect to the curve.

As NearestPoint but only the first two components of the curve, considered as a Pair, are
tested against p; the distance returned is measured in the xy plane.  Set persp true iff c
has been transformed with perspective.

Using subdivision, examine s between t0 and t1 for point sPt closest to line.
lPt is the closest point on the line, t is sPt's parametric value, and dist is the
distance betwen sPt and lPt.

Using subdivision, return the closest approach of the two curves in terms of the
parameter t1 for the first curve and t2 for the second.  This procedure is unreliable.

Using subdivision, return the nearest point on curve c which is furthest from the straight
line connecting the curve endpoints; also return the distance from p to the straight line.
Subdivision Procedures
Subdivide the curve at the parametric midpoint.  curve1 is the curve that begins at t=0.
Use out1, out2 if non-NIL.
Subdivide the curve at the parametric midpoint.  b1 is the curve that begins at t=0.
Divide a curve at parametric point t into two new curves; s1 is the curve that begins at t=0.
Return a curve such that within the interval (t0, t1) it defines the same curve as did the
input curve within the interval (0,1).  Use out if non-NIL.  out may be equal to in.
Sequence Operations
Return a copy of the input sequence of coefficients.

Add spline to the sequence.

Return a copy of the input sequence whose maxLength is amount*input.maxLength.
Special Purpose
Return a value IN [value0..value1] given t IN [0..1] (no bounds checking),
such that the derivatives at t = 0 and t = 1 are 0.

Return a curve tamed according to tameType:
if tameType.loop, disallow any loops;
if tameType.cusp, disallow any cusps;
if tameType.inflect, disallow any inflections
if tameType.bulge, disallow any bulges.
Use out if non-NIL.
Return approximation to a circular arc given the chord from point0 to point1 and the
direction (normal) to the circle's center, as suggested by Frank Crow.  Previously, the curve
depended on the length of the normals, assuming a longer normal implied a flatter surface;
not only was this computationally awkward, but the length of the normal, which might be
computed from and related to a spatial function, may not have any deducible relation to the
surface geometry.
Return the roots (if any) of the intersection of plane with the spline.
Miscellaneous Procedures
Return the t3 term for x, y, and z.

Return the t2 term for x, y, and z.

Return the t term for x, y, and z.

Return the constant term for x, y, and z.

Return TRUE iff the curves are identical.

TPos:					TYPE ~ RECORD [t: REAL, p: Triple];
TPosSequence:		TYPE ~ REF TPosSequenceRep;
TPosSequenceRep:	TYPE ~ RECORD [element: SEQUENCE maxLength: NAT OF TPos];

TPosFromSpline: PROC [
c: Spline, num: NAT, t0: REAL _ 0.0, t1: REAL _ 1.0, tpos: TPosSequence _ NIL]
RETURNS [TPosSequence];
Return t parameters and positions at approximately optimal spacings; use tPos if non-nil.

Э╩
  ХNewlineDelimiter
Ц"cedarcode" styleЩ ЩJЪЬ	╧eЬ6ЩBJЩ&JШ ЧЪ╧k	ЬЮЬ!Ш-JШ ЧJЪ╨bl	ЬЮЬЮШJЪЬЮШheadЪ╧lЩJЪЬE╧uЬбЬЩPJЩTЪЬ1бЬ бЬЩ_JЩ ЧJЪЬЮЬШ$ЪЬЮЬШ)JШ ЧJЪЬЮЬЮЬШ8JЪЬЮЬЮЬШ9ЪЬЮЬЮЬ#Ш=JШ ЧЪЬЮЬЮЬ
ЮЬЮЬЮЬЮЬШSJШ ЧJЪЬЮЬЮЬШ/ЪЬЮЬЮЬШ#JЪЬЮЬШJЪЬЮЬЮЬЮЬШ5ШJШ ЧЧЪЬЮЬЮЬШJЪЬ(╧cШ=JЪЬЮЬвШ0JЪЬЮЬ
вШ3JШJШ ЧЪЬЮЬЮЬЮЬЮЬЮЬШIJШ ЧJЪЬЮ	ЬШ JЪЬЮЬШ#JЪЬЮ	ЬШ JЪЬЮ	ЬШJЪЬЮЬШ1JЪЬЮЬШ,ЧЪаЩЪ╧nЬЮЬ"ЮЬШDJЪЮЬШJЩEJЩ+JЩ ЧЪгЬЮЬШJШJШJЪЬ	ЮЬШJЪЬЮЬШJЪЮЬШJЩYJЩ6ЧЧЪаЩЪгЬЮЬЮЬЮЬ
ШGJЪЬG╧sЬЩKJШ ЧЪгЬЮЬЮЬЮЬ
ШIJЪЬHдЬЩLJЩ ЧЪгЬЮЬЮЬЮЬ
ШIJЪЬHдЬЩLJЩ ЧЪгЬЮЬЮЬ
Ш4JЩ4JЩ ЧЪгЬЮЬЮЬШ6JЩ5JШ ЧЪгЬЮЬЮЬШ6JЩ5JЩ ЧЪгЬЮЬЮЬШEJЩ;JЩ ЧЪг
ЬЮЬ ЮЬЮЬ
ШFJЩ<ЧЧЪаЩЪгЬЮЬЮЬЮЬ
Ш5JЩ,JШ ЧЪгЬЮЬЮЬЮЬ
Ш5JЩ;JШ ЧЪгЬЮЬЮЬЮЬ
Ш4JЩJЩ ЧЪгЬЮЬЮЬЮЬШJJЩ=JЩ ЧЪгЬЮЬЮЬЮЬ
Ш9JЩ@JШ ЧЪгЬЮЬЮЬЮЬШ4JЩ0JЩ ЧЪг	ЬЮЬЮЬЮЬ
Ш6JЩDJЩ ЧЪ
гЬЮЬЮЬЮЬЮЬШ7JЩ-JЩ ЧЪ
г
ЬЮЬ*ЮЬЮЬЮЬШ\JЩCJЩFJЩ1JШ ЧЪгЬЮЬЮЬЮЬШKJЪЮЬ
ШJЪЬ9дЬЩ=JШ ЧЪ	╨bn╧bЮжЬЮЬЮЬШEJЪЮжЬШJЩEJШ ЧЪгЬЮЬЮЬЮЬШ4JЩ-JЩ ЧЪ
г
ЬЮЬЮЬ	ЮЬЮЬШBJЪЬдЬ(Щ3JЩCJЩ=ЧЧЪаЩЪ
гЬЮЬЮЬЮЬЮЬШ;JЩWJШ ЧЪгЬЮЬЮЬЮЬШ0JЩRJШ ЧЪ
гЬЮЬЮЬЮЬЮЬШ9JЩNJЩ ЧЪ
г
ЬЮЬЮЬ	ЮЬЮЬШBJЩZJЩ^JЪЬЮЬHЩ`JЪЬJЮЬЩZJШ ЧЪ
гЬЮЬЮЬ	ЮЬЮЬШ<JЪЬЮЬ;ЩFJШ ЧЪ
г
ЬЮЬЮЬЮЬЮЬШ>JЩUJЩWЧЧЪаЩЪгЬЮЬЮЬЮЬШ1JЩEJЩ?JЩ ЧЪ
гЬЮЬЮЬЮЬЮЬШ_JЪЮЬШJЩRJЩWJЩ[JЩRJЩ0JЩ ЧЪгЬЮЬЮЬЮЬШPJЩ\JЩ]JЩ ЧЪгЬЮЬЮЬЮЬЮЬЮЬШ[JЪЮЬШJЩYJЩZJЩ&JЩ ЧЪгЬЮЬШJЪЬЮЬЮЬЮЬШKJЪЮЬЮЬШ*JЩMJЩRJЩJЩ ЧЪ
гЬЮЬЮЬЮЬ
ЮЬШRJЩPJЩVJЩ ЧЪгЬЮЬЮЬШ5JЩZJЩZЧЧЪаЩЪг
ЬЮЬ"ЮЬЮЬШPJЩXJЪЬдЬЩJШ ЧЪгЬЮЬЮЬШ7JЩTJШ ЧЪг	ЬЮЬЮЬЮЬШ>JЩ]JШ ЧЪ
гЬЮЬЮЬЮЬЮЬ
ШTJЩZJЪЬ7дЬЩTЧЧЪаЩЪгЬЮЬЮЬШLЩ4JЩ ЧЧЪгЬдЮЬ
дЬдЬдЬШCJЪЮдЬШЪЬЩJЩ ЧЧЪгЬЮЬ#ЮЬШJJЪЮЬШJЩNЧЧЪаЩЪ
г	ЬЮЬЮЬЮЬЮЬШ9JЪЬдЬдЬЩJJЩ3JЩ ЧJЪЬ
ЮЬЮЬЮЬЮЬЮЬЮЬШPJШ ЪгЬЮЬ0ЮЬЮЬ
ШPЩ+JЩ%JЩ%JЩ-JЩ'ЧJЪЬдЬЩJШ ЧЪгЬЮЬШ"JШ)JЪЬ	ЮЬШJЪЬЮЬШJЪЮЬ
ШJЩTJЩ]JЩZJЩWJЩ[JЩJШ ЧЪгЬЮЬЮЬШ[JЩGЧЧЪаЩЪгЬЮЬЮЬ
Ш(JЪЬбЬЩ#JЩ ЧЪгЬЮЬЮЬ
Ш(JЪЬбЬЩ#JЩ ЧЪгЬЮЬЮЬ
Ш(JЩ"JЩ ЧЪгЬЮЬЮЬ
Ш(JЩ)JЩ ЧЪгЬЮЬЮЬЮЬШ+JЪЬЮЬЩ)ЧJЩ ЧJЪЮЬШJШШ JЪЬ
ЮЬЮЬЮЬЩ-JЪЬЮЬЮЬЩ*JЪЬЮЬЮЬЮЬЮЬЮЬЩJJЩ ЪгЬЮЬЩJЪ	ЬЮЬЮЬЮЬЮЬЩNJЪЮЬЩJЩYЧЧJЩ Ч ЕЧ    b  8  