Multi-Res Modeling Group People Research Demos
Publications Software
Multi-Res Modeling Group Multi-Res Modeling Group

Drawing Smooth Interpolating Curves Given some set of points in the plane there are a number of different ways to draw curves which interpolate or approximate the points.

For an example of approximation see Chaikin's Algorithm, or so called corner cutting. Here we'll consider one of the simplest "nice" interpolating subdivision schemes.

Perhaps the most simple scheme would connect the points to be interpolated with straight lines, i.e., interpolate them piecewise linearly. This is often not smooth enough. In order to see how we might generalize this simple idea think of the piecewise linear approximation as a subdivision that inserts new points between old ones by averaging the neighbor on the left and on the right. If you keep repeating this process you will get in the limit a piecewise linear approximation. How about we take two neighbors on either side of the new point to be inserted. With a total of 4 old points we can construct an interpolating polynomial of degree 3 and define the new midpoint as the value this polynomial takes on at the parametric midpoint. This is the so called 4pt scheme.

If we assume that the old points sit at integer parameter values it turns out we get fixed weights of (-1, 9, 9, -1)/16. I.e., the new midpoint inbetween 2 old ones on the left and 2 old ones on the right is given by the above affine combination.

If this process is repeated ad infinitum we get a limit curve which is not a cubic polynomial (why?), but still very nice. It belongs to the smoothness class Cα for α < 2. It also has the property that it reproduces cubic polynomials. I.e., if the original points that we want to interpolate happen to lie on a common cubic polynomial the limit curve will be that same cubic polynomial.

Below is a little applet that implements this algorithm. You can choose open and closed boundary conditions. You can also choose whether the weights should be fixed or whether they should be adjusted taking the distance of the points into account. In the latter case every subdivision step requires the construction of a cubic polynomial for which the parameter values are chosen to reflect the distance between neighboring points. In many cases this leads to "nicer" curves. The controls at the top influence the editing behavior. Clicking the mouse button in the drawing area will allow you to add, delete or move points. Since we need at least 4 points to get anything you'll see the first curve after the insertion of the 4th point. The level control will set the number of subdivision steps. Level 0 corresponds to no subdivision at all. Finally the weight controls a parameter in the subdivision mask (this only works int the uniform case), which interpolates the subdivision scheme itself between cubic interpolation (weight=0) and linear interpolation (weight=1).

Copyright © 1997 Peter Schröder Last modified: Wed Oct 1 18:14:33 PDT 1997