Visualizing the Lane-Riesenfeld Algorithm

Ok so, I keep reading papers about this and non of them have pictures. The lane Riesenfeld algorithm provides a way to subdivide set of points with B-spline conversion.

The quesiton is simple HOW? If you can give me a set of pictures with the explanation that's be the best explanation, more than the math.

The first step (i.e duplication of the original vertices) seems clear enough, but I do not fully understand how the mid point averaging works.

Currently my very, very poor understanding is producing this:

Starting with the following 4 points

We duplicate each point (denoted by the grey area)

We take all odd points in our new set, and move them to the middle of the line connecting 2 consecutive points:

What do I do now? From here on I am just completely lost

1 Answer

The Lane-Riesenfeld algorithm subdivides the control polygon of a B-spline to create a new control polygon with the same limit spline. It's made up of two steps: first, duplicating all of the control points $P_i$ into $P^\prime_{2i}$ and $P^\prime_{2i+1}$; then, moving each point to the midpoint between it and the next point, so $P^\prime_i \rightarrow \frac{1}{2} P^\prime_i + \frac{1}{2}P^\prime_{i+1}$. These steps are illustrated in the figure:

On the left is an initial control polygon. In the middle, I've duplicated the vertices. On the right, the vertices have moved halfway to the next vertex. Notice that only half of the vertices move in the first movement step: this is because $P^\prime_{2i} = P^\prime_{2i+1},$ but $P^\prime_{2i+1} \neq P^\prime_{2i+2}.$ These eight vertices are a refined control polygon for the linear B-spline defined by the initial four vertices.

Now, we can do a second movement step (without another duplication):

On the left, we've moved each vertex to the midpoint between it and its neighbour; note that all of the vertices move this time (since none are in the same position). On the right, we have drawn the polygon with these eight vertices. This is a refined control polygon for the quadratic B-spline defined by the initial four vertices. You may also recognize this as the same polygon you get by Chaikin corner-cutting, which also gets you the quadratic B-spline.

Now we can perform more duplicate-move-move steps to further refine the polygon, and thus more closely approximate the quadratic B-spline curve:

Here's an animation of this process:

If, instead, we do a third movement step without a duplication step (that is, one duplication followed by three successive movements) we get a refined control polygon for the cubic B-spline defined by the initial four vertices:

An animation of this process:

In general, doing $k$ movement steps after each duplicate gives us the refined polygon for the $C^k$ B-spline.

EDIT: Added animations.

• Although this is a clear answer i would really like to see the process animated. But hey we are graphics programmers that shouldn't be too hard. Ill try tomorrow. Nov 7, 2017 at 20:49
• Also, what software did you use to draw/generate this? Nov 8, 2017 at 1:22
• @Makogan you may want to look at this post for ideas on how to draw. Though the choice is a highly personal one. Nov 8, 2017 at 7:32
• @Makogan I made the diagrams in asymptote, which is open-source. Nov 9, 2017 at 9:09
• @joojaa I've added animations of quadratic and cubic B-spline generation. Nov 9, 2017 at 12:37