GGCubic2.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Last edited by Bier on December 1, 1986 4:42:55 pm PST
Contents: The routines in Cubic2 and CubicPaths are inadequate for Gargoyle purposes. The Closest Point routine is too slow and doesn't properly document its accuracy. There is also a need for routines that are slow but very accurate so we can test how good our fast routines are (maybe using rational arithmetic?). Hopefully, these routines will eventually find their way back into Cubic2, and CubicPaths.
DIRECTORY
Cubic2, CubicPaths, Polynomial, Vector2;
GGCubic2: CEDAR DEFINITIONS =
BEGIN
Bezier: TYPE = Cubic2.Bezier;
Path: TYPE = CubicPaths.Path;
ShortRealRootRec: TYPE = Polynomial.ShortRealRootRec;
VEC: TYPE = Vector2.VEC;
Flat:
PROC [bezier: Bezier, epsilon:
REAL]
RETURNS[
BOOL];
A Bezier segment is considered flat if it can be approximated by a straight line from its first control point to its last with a guaranteed maximum error less than epsilon.
ClosestPointSubdivide:
PROC[pt:
VEC, path: Path, epsilon:
REAL, tolerance:
REAL ← 9999.0]
RETURNS [closest:
VEC, success:
BOOL];
Finds the closest point on bezier to pt. If success = TRUE, the point returned is guaranteed to be no farther than epsilon from bezier, and no farther than epsilon from the actual closest point. If no point on the curve is within tolerance then ClosestPoint has the option of returning success = FALSE, leaving closest uninitialized. This can save time, since we can throw away all parts of the curve that are outside tolerance, right from the beginning.
ClosestPointAnalytic:
PROC[pt:
VEC, path: Path, tolerance:
REAL ← 9999.0]
RETURNS [closest:
VEC, success:
BOOL];
Faster than ClosestPointSubdivide, more accurate, and almost as robust. If success = TRUE, the point returned is guaranteed to be quite close to the Bezier path. The point is quite close because it results from plugging in a value of the parameter. The point returned is also quite close to the actual closest point, since the parameter chosen is within a floating point round-off error of being a root of the "closest point" polynomials. IF success = FALSE, no point on path is within tolerance of pt. In this case, closest is not valid data.
CheapRealRootsInInterval:
PROC [poly: Polynomial.Ref, lo, hi:
REAL]
RETURNS [roots: ShortRealRootRec];
Like CheapRealRoots, but it only finds those roots that are in the closed interval [lo..hi]. As a result, it runs 2 or 3 times faster for many cases. It is also more robust since it only evaluates poly in the range [lo..hi], whereas CheapRealRoots may evaluate poly at very large numbers, resulting in floating point errors.
AlphaSplit:
PROC [bezier: Bezier, alpha:
REAL]
RETURNS[Bezier, Bezier];
Split the bezier curve into the two pieces generated by parameter values [0..alpha] and [alpha..1], respectively.
GetParam:
PROC [bezier: Bezier, pt:
VEC]
RETURNS [u:
REAL];
Given a bezier curve, and a point on the curve, find the parameter value u that generates pt.
END.