Knot Vector Generation for B-Spline Interpolation

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

This Demonstration is concerned with the problem of interpolating a given point set by a B-spline curve. We illustrate the influence of different choices for the curve's knot vector and parameter vector. The quality of the interpolation varies dramatically depending on these choices, and certain combinations lead to highly oscillating interpolants. A uniform knot vector combined with a chordal parameter vector often yields oscillations or erratic behavior (red curve). Combining a uniform knot vector with a centripetal parameter vector improves the result a bit (blue curve), but the best result is obtained for an average knot vector combined with a chordal (or centripetal) parameter vector (green curve).

Contributed by: Isabelle Cattiaux-Huillard and Gudrun Albrecht (August 2011)
Open content licensed under CC BY-NC-SA


Snapshots


Details

One of the basic tasks in reverse engineering is curve reconstruction from a set of measured points. A frequently used tool for this purpose is B-spline interpolation.

A degree B-spline curve defined by its control polygon reads

,

where , are the B-spline basis functions (see B-Spline (Wolfram MathWorld)). They depend on the knot vector

, where and .

Given a point set , , …, and an associated parameter vector , where , the interpolation problem thus consists of determining the control polygon as the solution of the following system of linear equations,

, for .

This polygon and thus the curve depend on the knot and parameter vectors. Well-known choices for the parameter vector are:

• the chordal distribution:

• the centripetal distribution:

where and is often chosen equal to .

A common choice for the knot vector is obtained by uniformly spacing the internal knots, for example on the interval :

(The knot vector generated by the Mathematica option SplineKnotsAutomatic is uniformly spaced.)

But for numerical reasons, it is not recommended to combine a uniform knot vector with a chordal parameter vector because that could generate an unstable or singular system of linear equations (see "Knot Vector Generation" in [1]). To avoid this problem, it is better to adapt the knot vector to the parameter vector, for example by using the average method:

Reference

[1] C.-K. Shene, Introduction to Computing with Geometry Notes. (Aug 22, 2011) http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/notes.html.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send