James Coburn

02-25-2003, 02:48 PM

I want to thank everyone who responded to my posting asking for help

fitting B-Splines through a data set. Here is a somewhat brief but

detailed summary of the explanations I received with the suggested

references given at the bottom. I hope this is helpful to others who are

new to these methods.

First of all, it was pointed out that B-Splines are usually very well

suited to fitting between data points but not necessarily interpolating

_through_ each of those points. Basically, b-splines are associated with a

number of control points. For a cubic order b-spline, four control points

are necessary to describe each section of the curve. To crudely construct

a curve that will go through certain points, you must duplicate those

control points. The curve can also be forced through the endpoints by

using repeated values at the beginning and end of the knot vector. "If you

need interpolating endpoints your knot multiplicity at the ends must equal

the order of curve (= degree + 1). For a cubic curve this means that you

must have 4 identical knot values at the beginning and at the end."(RT)

A knot sequence defines the scope of each control point. Unlike

Bezier curves, b-splines are characterized by local control so moving one

control point will change a small region but doesn't affect the entire

curve. To define a basic knot sequence "you can use a uniform sequence of

numbers, 1, 2, 3, ..., or usually you can achieve a better curve by having

the knot sequence represent euclidean distance between points so that

U(n)-u(n-1) = distance between points n-1 and n." (GN) This line will go

through the endpoints (if the repeated knots described above are used) but

not necessarily through any of the intervening points.

To create a line that intersects all data points, a different type

of curve is more efficient. Both natural or Ferguson splines (JR) and

Hermite curves (VL) were suggested to fill this role. I settled on using

a subset of Hermite curves. There are several basic types of hermite

curves: Cardinal Splines, Catmull-Rom Splines, and Kochanek-Bartels (KB)

Splines. All these curves rely on locally fitting curves based on the

control points and tangents to those points either specified or derived

from the surrounding data. The most general of these being KB splines

which allow the user (or algorithm) to specify a tension, continuity and

bias coefficient for each tangent calculation. Catmull-Rom splines are

similar in form to the KB-spline but do not account for these three

specific coefficients. Rather , the coefficient is set at

1/2. Calculation of the intermediary points on the curve is trivial once

the algorithm is set up.

References:

"Curves and Surfaces for CAGD: A Practical Guide" by Gerald Farin (RT)

"The NURBS Book" by Les A. Piegl and Wayne Tiller (RT)

"Mathematical Elements of Computer Graphics" by Rogers and Adams (GN)

"Computer Graphics for Engineers" by Dewey Pub: Harper & Row, 1988 (AE)

Hermite Curve Interpolation by Nils Pipenbrinck (link below)

http://www.cubic.org/~submissive/sourcerer/hermite.htm

Cheers,

James

------------------------------------------------------------------------------------------

Brown University Orthopedic Research

Dept of Engineering Rhode Island Hospital

Providence, RI Providence, RI

---------------------------------------------------------------

To unsubscribe send SIGNOFF BIOMCH-L to LISTSERV@nic.surfnet.nl

For information and archives: http://isb.ri.ccf.org/biomch-l

---------------------------------------------------------------

fitting B-Splines through a data set. Here is a somewhat brief but

detailed summary of the explanations I received with the suggested

references given at the bottom. I hope this is helpful to others who are

new to these methods.

First of all, it was pointed out that B-Splines are usually very well

suited to fitting between data points but not necessarily interpolating

_through_ each of those points. Basically, b-splines are associated with a

number of control points. For a cubic order b-spline, four control points

are necessary to describe each section of the curve. To crudely construct

a curve that will go through certain points, you must duplicate those

control points. The curve can also be forced through the endpoints by

using repeated values at the beginning and end of the knot vector. "If you

need interpolating endpoints your knot multiplicity at the ends must equal

the order of curve (= degree + 1). For a cubic curve this means that you

must have 4 identical knot values at the beginning and at the end."(RT)

A knot sequence defines the scope of each control point. Unlike

Bezier curves, b-splines are characterized by local control so moving one

control point will change a small region but doesn't affect the entire

curve. To define a basic knot sequence "you can use a uniform sequence of

numbers, 1, 2, 3, ..., or usually you can achieve a better curve by having

the knot sequence represent euclidean distance between points so that

U(n)-u(n-1) = distance between points n-1 and n." (GN) This line will go

through the endpoints (if the repeated knots described above are used) but

not necessarily through any of the intervening points.

To create a line that intersects all data points, a different type

of curve is more efficient. Both natural or Ferguson splines (JR) and

Hermite curves (VL) were suggested to fill this role. I settled on using

a subset of Hermite curves. There are several basic types of hermite

curves: Cardinal Splines, Catmull-Rom Splines, and Kochanek-Bartels (KB)

Splines. All these curves rely on locally fitting curves based on the

control points and tangents to those points either specified or derived

from the surrounding data. The most general of these being KB splines

which allow the user (or algorithm) to specify a tension, continuity and

bias coefficient for each tangent calculation. Catmull-Rom splines are

similar in form to the KB-spline but do not account for these three

specific coefficients. Rather , the coefficient is set at

1/2. Calculation of the intermediary points on the curve is trivial once

the algorithm is set up.

References:

"Curves and Surfaces for CAGD: A Practical Guide" by Gerald Farin (RT)

"The NURBS Book" by Les A. Piegl and Wayne Tiller (RT)

"Mathematical Elements of Computer Graphics" by Rogers and Adams (GN)

"Computer Graphics for Engineers" by Dewey Pub: Harper & Row, 1988 (AE)

Hermite Curve Interpolation by Nils Pipenbrinck (link below)

http://www.cubic.org/~submissive/sourcerer/hermite.htm

Cheers,

James

------------------------------------------------------------------------------------------

Brown University Orthopedic Research

Dept of Engineering Rhode Island Hospital

Providence, RI Providence, RI

---------------------------------------------------------------

To unsubscribe send SIGNOFF BIOMCH-L to LISTSERV@nic.surfnet.nl

For information and archives: http://isb.ri.ccf.org/biomch-l

---------------------------------------------------------------