7
$\begingroup$

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

enter image description here

We duplicate each point (denoted by the grey area)

enter image description here

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

enter image description here

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

$\endgroup$

1 Answer 1

16
+50
$\begingroup$

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:

One duplication and one movement step

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):

Second movement step and new polygon

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:

Further refinements of the quadratic B-spline control polygon

Here's an animation of this process:

Animation of LR algorithm creating quadratic B-spline

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:

Cubic B-spline refinement by dup-move-move-move steps

An animation of this process:

Animation of LR algorithm creating cubic B-spline

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

EDIT: Added animations.

$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – joojaa
    Commented Nov 7, 2017 at 20:49
  • 1
    $\begingroup$ Also, what software did you use to draw/generate this? $\endgroup$
    – Makogan
    Commented Nov 8, 2017 at 1:22
  • $\begingroup$ @Makogan you may want to look at this post for ideas on how to draw. Though the choice is a highly personal one. $\endgroup$
    – joojaa
    Commented Nov 8, 2017 at 7:32
  • 1
    $\begingroup$ @Makogan I made the diagrams in asymptote, which is open-source. $\endgroup$
    – gilgamec
    Commented Nov 9, 2017 at 9:09
  • 1
    $\begingroup$ @joojaa I've added animations of quadratic and cubic B-spline generation. $\endgroup$
    – gilgamec
    Commented Nov 9, 2017 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.