Dealer Notes
Copyright (C) 1984 by Xerox Corporation. All rights reserved.
Written by Pauline Ts'o on August 7, 1984 4:11:06 pm PDT
I. BACKGROUND
A. Splines in general
1. Piece-wise polynomial functions whose shapes are usually defined by a set of points called control points.
2. Two types of splines
a. Interpolating - spline must go through or interpolate control points
b. Approximating - spline doesn't necessarily interpolate control points, but goes close to them, where closeness is define by weighting functions.
3. #1 ← b1 = 1.0, b2 = 0.0, point out:
a. Control points
b. Spline segments - 4 control points defines one spline segment
c. Approximating
B. Beta-splines by Barsky
1. An approximating spline that is a generalization of the more common B-spline
2. Beta-splines have two additional parameters that control the shape of the spline. Intuitive overview:
a. Bias
1. Pulls the spline to one side or the other
#2 ← b1 = 2.0, b2 = 0.0
Reciprocal of bias pulls spline to the other side by an equal amount
#3 ← b1 = 0.5, b2 = 0.0
2. Two more examples
#4 ← b1 = 5.0, b2 = 0.0
#5 ← b1 = 0.2, b2 = 0.0
b. Tension
1. Pulls spline close to control points for positive values of tension
#6 ← b1 = 1.0, b2 = 0.0
#7 ← b1 = 1.0, b2 = 10.0
#8 ← b1 = 1.0, b2 = 50.0
c. Combining the two shape parameters
#9 ← b1 = 3.0, b2 = 150.0
d. Uniformly vs continuously shaped Beta-splines
Previous transparencies illustrated the effects of bias and tension when applied to the entire spline curve. It is possible to apply these shape parameters to only parts of the spline curve.
#10 ← 3rd vertex => vvb1 = 5.0, b2 = 0.0
4th vertex => vvb1 = 10.0, b2 = 0.0
rest => vvb1 = 1.0, b2 = 0.0
#11 ← 3rd vertex => vvb1 = 1.0, b2 = 25.0
4th vertex => vvb1 = 1.0, b2 = -5.0
rest => vvb1 = 1.0, b2 = 0.0
C. Uses of splines
1. CAD/CAM, #12 ← Local tension at some points, wheel well area
2. Illustrations (Griffin), #13 ← bwknight, plume and tail done with splines
3. Animation (motion paths)


II. PATHTOOL
A. All the splines shown were generated by a tool that I worked on this summer. I cannibalized a great deal of code from Darlene Plebon's Pathtool. In fact, my tool bears the same name, though I should change that. Her tool manipulated Bezier curves - a different type of spline.
B. Basically, my tool allows the user to interactively
1. Edit sets of control points
2. Specify global and local bias and tension
3. Use a grid constraint to aid in specifying control points.
C. I used it also to test heuristics that allow for simplification of Beta-splines
III. SIMPLIFICATION OF BETA-SPLINES
A. First, what do I mean? Two parts of definition
1. Filtering spline to smooth shape
2. Deleting control points so that fewer points specify the curve
B. Motivation
1. Database simplification - deals with observation that when camera zooms out, image gets smaller. High frequency details become indiscernable, so why draw them?
a. First seen by me in an article by Frank Crow for Siggraph '82
1. Objects had several descriptions associated to them. Each description differed in amount of detail and was used at different scales.
b. Related issue is scale independence in fractals
c. Importance
1. Saves on storage
2. Saves on computation time in rendering ← less points => less time spent on hidden line/surface removal, shading, anti-aliasing, etc.
2. Minor motivation - correcting user overspecification. The final solution is not really geared to this problem, but might provide some ideas
C. Objectives
1. Maintain general shape of curve for as long as possible while deleting control points
D. Solution
1. Noted that collinear points could be taken out with little change to the shape of the spline
2. Noted that areas of equal curvature could be approximated well by fewer control points
#13 ← 9 control points, #14 ← 8 control points
3. General algorithm
(1) Test for areas of ~equal curvature and sets of at least three approximately collinear points
(2) If an area of equal curvature exists
(a) If there are n points in this area, distribute n-1 points around the osculating circle leaving the first and last points unchanged. Refer to transparencies #13 and #14
(3) Else if a set of three collinear points exists, just delete the middle one.
(4) Else, use filtering technique (neighborhood averaging) to dampen high frequency changes. This allows collinear and equicurvature points to arise.
(5) Go to step 1.

Show rest of transparencies
IV. FUTURE WORK
A. Three-dimensions, obviously
B. Relate spline sampling to spline simplification
C. Integrate with spline subdivision techniques so one can zoom in and out.