Types and Constants
RealSequence: TYPE ~ Vector3d.RealSequence;
RealSequenceRep: TYPE ~ Vector3d.RealSequenceRep;
Triple: TYPE ~ Vector3d.Triple;
TripleSequence: TYPE ~ Vector3d.TripleSequence;
TripleSequenceRep: TYPE ~ Vector3d.TripleSequenceRep;
Pair: TYPE ~ Vector3d.Pair;
Line: TYPE ~ Vector3d.Line;
Matrix: TYPE ~ Matrix3d.Matrix;
MatrixRep: TYPE ~ Matrix3d.MatrixRep;
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.
Coeffs: TYPE ~ Matrix;
CoeffsRep: TYPE ~ Matrix3d.MatrixRep;
CoeffsSequence: TYPE ~ REF CoeffsSequenceRep;
CoeffsSequenceRep:
TYPE ~
RECORD [
length: CARDINAL ← 0,
element: SEQUENCE maxLength: CARDINAL OF Coeffs
];
Bezier: TYPE ~ RECORD [b0, b1, b2, b3: Triple];
Bspline: TYPE ~ RECORD [b0, b1, b2, b3: Triple];
Hermite: TYPE ~ RECORD [p0, p1, tan0, tan1: Triple];
Near3d: TYPE ~ RECORD [point: Triple, t, distance: REAL];
Near2d: TYPE ~ RECORD [point: Pair, t, distance: REAL];
origin: Triple ~ Vector3d.origin;
Interpolation Procedures
InterpolateCyclic:
PUBLIC
PROC [knots: TripleSequence, tension:
REAL ← 1.0]
RETURNS [CoeffsSequence];
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 ← origin,
tension: REAL ← 1.0,
c: CoeffsSequence ← NIL]
RETURNS [CoeffsSequence];
Implements three-dimensional natural interpolating spline with chord-length parametrization.
End tangents are set if specified tangent is non-zero.
Conversion Procedures
CoeffsFromBezier:
PROC [b: Bezier, out: Coeffs ←
NIL]
RETURNS [Coeffs];
Convert Bezier control points to cubic coefficients; return out if non-nil
CoeffsFromBspline:
PROC [b: Bspline, out: Coeffs ←
NIL]
RETURNS [Coeffs];
Convert Bspline control points to cubic coefficients; return out if non-nil
CoeffsFromHermite:
PROC [h: Hermite, out: Coeffs ←
NIL]
RETURNS [Coeffs];
Convert Hermite control points to cubic coefficients; return out if non-nil
BezierFromCoeffs:
PROC [c: Coeffs]
RETURNS [Bezier];
Convert cubic coefficients to Bezier control points.
BsplineFromCoeffs:
PROC [c: Coeffs]
RETURNS [Bspline];
Convert cubic coefficients to Bspline control points.
HermiteFromCoeffs:
PROC [c: Coeffs]
RETURNS [Hermite];
Convert cubic coefficients to Hermite control points.
Evaluation Procedures
PerPointProc: TYPE = PROC [p: Triple];
WalkBezier:
PROC [b: Bezier, proc: PerPointProc, epsilon:
REAL ← 0.05, doLast:
BOOL ←
TRUE];
Callback for each point on curve; ie.: WalkBezier[bezier, DrawTo];
the curve is subdivided such that each segment is flat within epsilon.
If doLast is FALSE, don't call proc for last point of curve.
FwdDif:
PROC [in: Coeffs, nSegments:
INTEGER, out: Coeffs ←
NIL]
RETURNS [Coeffs];
Create the matrix of forward differences.
Samples:
PROC
[c: Coeffs, nPoints:
NAT, points: TripleSequence ←
NIL]
RETURNS [TripleSequence];
Fill the PointSequence with nPoints number of points along the curve.
Position:
PROC [c: Coeffs, t:
REAL]
RETURNS [Triple];
Return the point of the curve at position t.
Velocity:
PROC [c: Coeffs, t:
REAL]
RETURNS [Triple];
Return the unnormalized tangent of the curve at position t.
Acceleration:
PROC [c: Coeffs, t:
REAL]
RETURNS [Triple];
Return the unnormalized acceleration of the curve at position t.
Tangent:
PROC [c: Coeffs, t:
REAL]
RETURNS [Triple];
A renamimg of Velocity[].
MinAcceleration:
PROC [c: Coeffs]
RETURNS [t:
REAL];
Return parametric point of minimum acceleration.
CurvatureMag:
PROC [c: Coeffs, t:
REAL]
RETURNS [
REAL];
Return the magnitude of the curvature vector.
Curvature:
PROC [c: Coeffs, t:
REAL]
RETURNS [Triple];
Return the unnormalized curvature vector of the curve at position t.
RefVec:
PROC [c: Coeffs, t:
REAL]
RETURNS [Triple];
Return a reference vector for the curve at t.
IsStraight:
PROC [c: Coeffs, 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 [c: Coeffs]
RETURNS [
REAL];
Return the (approximate) length of the curve.
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 [c: Coeffs, epsilon:
REAL ← 0.05]
RETURNS [
BOOL];
Return TRUE if distance between curve endpoints is less than epsilon;
Resolution:
PROC [c: Coeffs, 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. c is presumed already transformed into image space.
Search Procedures
InflectionPoint:
PROC [c: Coeffs]
RETURNS [
REAL];
Analytically compute the parametric location of the inflection point.
If c is straight, return -2; if c has no inflection, return -1.
NearestPoint:
PROC [
p: Triple, c: Coeffs, t0: REAL ← 0.0, t1: REAL ← 1.0, epsilon: REAL ← 0.01]
RETURNS [Near3d];
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, c: Coeffs]
RETURNS [n: Near3d];
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, c: Coeffs, persp:
BOOL ←
FALSE, t0:
REAL ← 0.0, t1:
REAL ← 1.0]
RETURNS [Near2d];
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: Line, c: Coeffs, t0: REAL ← 0.0, t1: REAL ← 1.0, epsilon: REAL ← 0.01]
RETURNS [cPt, lPt: Triple, t, dist: REAL];
Using subdivision, examine c between t0 and t1 for point cPt closest to line.
lPt is the closest point on the line, t is cPt's parametric value, and dist is the
distance betwen cPt and lPt.
NearestSpline:
PROC [c1, c2: Coeffs, 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 [c: Coeffs]
RETURNS [Near3d];
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 [c: Coeffs, out1, out2: Coeffs ←
NIL]
RETURNS [c1, c2: Coeffs];
Subdivide the curve at the parametric midpoint. curve1 is the curve that begins at t=0.
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 [c: Coeffs, t:
REAL]
RETURNS [c1, c2: Coeffs];
Divide a curve at parametric point t into two new curves; c1 is the curve that begins at t=0.
Reparameterize:
PROC [in: Coeffs, t0, t1:
REAL, out: Coeffs ←
NIL]
RETURNS [Coeffs];
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). out may be equal to in.
Miscellaneous Procedures
GetA:
PROC [c: Coeffs]
RETURNS [Triple];
Return the t3 term for x, y, and z.
GetB:
PROC [c: Coeffs]
RETURNS [Triple];
Return the t2 term for x, y, and z.
GetC:
PROC [c: Coeffs]
RETURNS [Triple];
Return the t term for x, y, and z.
GetD:
PROC [c: Coeffs]
RETURNS [Triple];
Return the constant term for x, y, and z.
Tame:
PROC [in: Coeffs, out: Coeffs ←
NIL]
RETURNS [Coeffs];
Return a curve eliminating initial or terminating bulges, inflections or loops.
Same:
PROC [c1, c2: Coeffs]
RETURNS [
BOOL];
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];
TPosFromCoeffs:
PROC [
c: Coeffs, 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.