Browse Prior Art Database

Recursive Spline Curve Fitting

IP.com Disclosure Number: IPCOM000106798D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 135K

Publishing Venue

IBM

Related People

Thornton, AT: AUTHOR

Abstract

Disclosed is a recursive technique for converting a polyline, consisting of a list of vertices, into a spline curve. It addresses issues involved in producing an interactive 3-D sketching tool for car body stylists and other free-form objects. Although described for a B-spline curve, the same technique is applicable to other members of the family of spline curves.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 40% of the total text.

Recursive Spline Curve Fitting

      Disclosed is a recursive technique for converting a polyline,
consisting of a list of vertices, into a spline curve.  It addresses
issues involved in producing an interactive 3-D sketching tool for
car body stylists and other free-form objects.  Although described
for a B-spline curve, the same technique is applicable to other
members of the family of spline curves.

      Spline curves are used for representing lines in geometric
modelling systems.  They possess useful properties including the
ability to represent most geometric forms accurately with significant
data reduction compared with polylines and well defined geometric
properties over the length of the curve.  However, where the user can
interactively draw a line, the mouse or pen device returns a list of
vertices, resulting in a large amount of data, and a line that is
undefined between vertices.  The application may have to make some
assumptions such as linear or quadratic segments to reduce the data
load.  In addition to the curve representation, the list of points
read off the input device contain noise which must be filtered and
smoothed using standard techniques.  Existing approaches to
conversion of a polyline to some form of spline and their drawbacks,
are described below.

      "Direct Curve Fitting" takes the list of vertices from the
input device, and fits a spline that passes through every single
point by the simple technique of creating a sufficient number of
control points and knots.  Although the curve is precisely defined,
there is no data reduction which can be a major benefit of using
spline curves [1].  "Least Squares Approximation" is a technique
where the number of knots and degree of the spline is predetermined
by the application, and the error function (found by taking the
differences between the vertices and the fitted curve, and summing
over the curve) is minimised by the least squares technique [2].  The
problem is that the degree of the curve and, more significantly, the
number of knots in the resultant spline, have to be decided in
advance by the application.  Automatic determination of the location
and quantity of knots is the real need.  "Least Squares Approximation
with Variable Knots" is a technique [2]  which modifies the knot
placement to obtain a solution that is locally optimal.  The
technique is computationally expensive and only useful in the region
of discontinuities.  It is too expensive for an interactive
line-drawing application.  "On the fly evaluation" [3]  fits a spline
curve on the fly by fitting the curve to a localised, moving window;
smoothing and filtering must also be performed on the fly so there is
only the possibility to smooth using historical data.  To perform the
best smoothing and filtering, a global analysis is required, not
available with this approach.

Requirements for a solution to the various problems in the
application domain are:

1.  Performance high...