G3dSpline.mesa
Copyright Ó 1985, 1992 by Xerox Corporation. All rights reserved.
Bloomenthal, July 14, 1992 1:48 pm PDT
DIRECTORY IO, G2dSpline, G3dBasic, G3dMatrix;
G3dSpline: CEDAR DEFINITIONS
~ BEGIN
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.
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;
Interpolation Procedures
InterpolateCyclic: PROC [knots: TripleSequence, tension: REAL ¬ 1.0]
RETURNS [SplineSequence];
The curve will interpolate from the last knot through the first knot,
the last knot need not replicate the first.
Interpolate: PROC [
knots: TripleSequence,
tan0, tan1: Triple ¬ [],
tension: REAL ¬ 1.0,
c: SplineSequence ¬ NIL]
RETURNS [SplineSequence];
Creates three-dimensional natural interpolating spline with chord-length parametrization.
End tangents are set if specified tangent is non-zero.
Conversion Procedures
SplineFromBezier: PROC [b: Bezier, out: Spline ¬ NIL] RETURNS [Spline];
Convert Bezier control points to cubic coefficients; return out if non-NIL.
SplineFromBspline: PROC [b: Bspline, out: Spline ¬ NIL] RETURNS [Spline];
Convert Bspline control points to cubic coefficients; return out if non-NIL.
SplineFromHermite: PROC [h: Hermite, out: Spline ¬ NIL] RETURNS [Spline];
Convert Hermite control points to cubic coefficients; return out if non-NIL.
BezierFromSpline: PROC [s: Spline] RETURNS [Bezier];
Convert cubic coefficients to Bezier control points.
BsplineFromSpline: PROC [s: Spline] RETURNS [Bspline];
Convert cubic coefficients to Bspline control points.
HermiteFromSpline: PROC [s: Spline] RETURNS [Hermite];
Convert cubic coefficients to Hermite control points.
BezierFromHermite: PROC [p0, p1, v0, v1: Triple] RETURNS [b: Bezier];
Return the Bezier equivalent of the Hermite representation.
CopySpline: PROC [spline: Spline, out: Spline ¬ NIL] RETURNS [Spline];
Return a copy of the input coefficients; use out if non-nil.
Evaluation Procedures
Position: PROC [s: Spline, t: REAL] RETURNS [Triple];
Return the point of the curve at position t.
Velocity: PROC [s: Spline, t: REAL] RETURNS [Triple];
Return the unnormalized tangent of the curve at position t.
Tangent: PROC [s: Spline, t: REAL] RETURNS [Triple];
An alias for Velocity[].
PositionAndVelocity: PROC [s: Spline, t: REAL] RETURNS [pos, vel: Triple];
Optimized computation of both the position and velocity at t.
Acceleration: PROC [s: Spline, t: REAL] RETURNS [Triple];
Return the unnormalized acceleration of the curve at position t.
MinAcceleration: PROC [s: Spline] RETURNS [t: REAL];
Return parametric point of minimum acceleration.
Curvature: PROC [s: Spline, t: REAL] RETURNS [Triple];
Return the unnormalized curvature vector of the curve at position t.
CurvatureMag: PROC [s: Spline, t: REAL] RETURNS [REAL];
Return the magnitude of the curvature vector.
WalkBezier: PROC [b: Bezier, proc: PerPointProc, epsilon: REAL ¬ 0.05, doLast: BOOL ¬ TRUE];
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.
ForwardDifference: PROC [in: Spline, nSegments: INTEGER, out: Spline ¬ NIL]
RETURNS [Spline];
Create the matrix of forward differences, use out if non-NIL.
Samples: PROC [s: Spline, nPoints: NAT, points: TripleSequence ¬ NIL]
RETURNS [TripleSequence];
Fill the PointSequence with nPoints number of points along the curve.
RefVec: PROC [s: Spline, t: REAL] RETURNS [Triple];
Return a reference vector for the curve at t.
IsStraight: PROC [s: Spline, epsilon: REAL ¬ 0.01] RETURNS [BOOL];
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
Length: PROC [s: Spline, nSteps: NAT ¬ 100] RETURNS [REAL];
Return (approximate) length of curve, derived by summing length of nSteps linear steps.
ConvexHullArea: PROC [b: Bezier] RETURNS [REAL];
Return the area of the convex hull of b, approximate if convex hull is non-planar.
ConvexHullLength: PUBLIC PROC [b: Bezier] RETURNS [REAL];
Return the sum of the lengths of the four sides of the bezier control polygon.
FlatBezier: PROC [b: Bezier, epsilon: REAL ¬ 0.05] RETURNS [BOOL];
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.
Tiny: PROC [s: Spline, epsilon: REAL ¬ 0.05] RETURNS [BOOL];
Return TRUE if distance between curve endpoints is less than epsilon;
Resolution: PROC [s: Spline, epsilon: REAL] RETURNS [INTEGER];
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
InflectionPoint: PROC [s: Spline] RETURNS [REAL];
Analytically compute the parametric location of the inflection point.
If s is straight, return -2; if s has no inflection, return -1.
NearestPoint: PROC [p: Triple, s: Spline, t0: REAL ¬ 0.0, t1: REAL ¬ 1.0, epsilon: REAL ¬ 0.01]
RETURNS [NearSpline];
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.
PreciseNearestPoint: PUBLIC PROC [p: Triple, s: Spline] RETURNS [n: NearSpline];
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.
NearestPair: PROC [p: Pair, s: Spline, persp: BOOL ¬ FALSE, t0: REAL ¬ 0.0, t1: REAL ¬ 1.0]
RETURNS [NearSpline2d];
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.
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];
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.
NearestSpline: PROC [s1, s2: Spline, epsilon: REAL ¬ 0.01] RETURNS [t1, t2: REAL];
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.
FurthestPoint: PROC [s: Spline] RETURNS [NearSpline];
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
SplitCurve: PROC [s: Spline, out1, out2: Spline ¬ NIL] RETURNS [s1, s2: Spline];
Subdivide the curve at the parametric midpoint. curve1 is the curve that begins at t=0.
Use out1, out2 if non-NIL.
SplitBezier: PROC [b: Bezier] RETURNS [b1, b2: Bezier];
Subdivide the curve at the parametric midpoint. b1 is the curve that begins at t=0.
Subdivide: PROC [s: Spline, t: REAL] RETURNS [s1, s2: Spline];
Divide a curve at parametric point t into two new curves; s1 is the curve that begins at t=0.
Reparameterize: PROC [in: Spline, t0, t1: REAL, out: Spline ¬ NIL] RETURNS [Spline];
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
CopySplineSequence: PROC [splines: SplineSequence] RETURNS [SplineSequence];
Return a copy of the input sequence of coefficients.
AddToSplineSequence: PROC [splines: SplineSequence, spline: Spline]
RETURNS [SplineSequence];
Add spline to the sequence.
LengthenSplineSequence: PROC [splines: SplineSequence, amount: REAL ¬ 1.3]
RETURNS [SplineSequence];
Return a copy of the input sequence whose maxLength is amount*input.maxLength.
Special Purpose
SlowInOut: PROC [value0, value1, t: REAL] RETURNS [REAL];
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.
TameType: TYPE ~ RECORD [loop, cusp: BOOL ¬ TRUE, inflect, bulge: BOOL ¬ FALSE];
Tame: PROC [in: Spline, tameType: TameType, out: Spline ¬ NIL] RETURNS [Spline];
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.
SplineFromPointsAndNormals: PROC [
point0, point1, normal0, normal1: Triple,
tension: REAL ¬ 1.0,
spline: Spline ¬ NIL]
RETURNS [Spline];
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.
IntersectSplineAndPlane: PROC [spline: Spline, plane: Quad] RETURNS [SplinePlaneIntersect];
Return the roots (if any) of the intersection of plane with the spline.
Miscellaneous Procedures
GetA: PROC [s: Spline] RETURNS [Triple];
Return the t3 term for x, y, and z.
GetB: PROC [s: Spline] RETURNS [Triple];
Return the t2 term for x, y, and z.
GetC: PROC [s: Spline] RETURNS [Triple];
Return the t term for x, y, and z.
GetD: PROC [s: Spline] RETURNS [Triple];
Return the constant term for x, y, and z.
Same: PROC [s1, s2: Spline] RETURNS [BOOL];
Return TRUE iff the curves are identical.
END.
..
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.