<p>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:</p>

<p><a href="https://i.sstatic.net/d7Dfn.png" rel="noreferrer"><img src="https://i.sstatic.net/d7Dfn.png" alt="One duplication and one movement step"></a></p>

<p>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.</p>

<p>Now, we can do a second movement step (without another duplication):</p>

<p><a href="https://i.sstatic.net/gjIca.png" rel="noreferrer"><img src="https://i.sstatic.net/gjIca.png" alt="Second movement step and new polygon"></a></p>

<p>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 <em>quadratic</em> 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.</p>

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

<p><a href="https://i.sstatic.net/AXVhV.png" rel="noreferrer"><img src="https://i.sstatic.net/AXVhV.png" alt="Further refinements of the quadratic B-spline control polygon"></a></p>

<p>Here's an animation of this process:</p>

<p><a href="https://i.sstatic.net/Q29mn.gif" rel="noreferrer"><img src="https://i.sstatic.net/Q29mn.gif" alt="Animation of LR algorithm creating quadratic B-spline"></a></p>

<p>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 <em>cubic</em> B-spline defined by the initial four vertices:</p>

<p><a href="https://i.sstatic.net/HaIxE.png" rel="noreferrer"><img src="https://i.sstatic.net/HaIxE.png" alt="Cubic B-spline refinement by dup-move-move-move steps"></a></p>

<p>An animation of this process:</p>

<p><a href="https://i.sstatic.net/94Um1.gif" rel="noreferrer"><img src="https://i.sstatic.net/94Um1.gif" alt="Animation of LR algorithm creating cubic B-spline"></a></p>

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

<p><strong>EDIT</strong>: Added animations.</p>

CC BY-SA 3.0
2017-11-07T20:49:34.520Z
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.
joojaa
CC BY-SA 3.0
2017-11-08T01:22:29.563Z
Also, what software did you use to draw/generate this?
Makogan
CC BY-SA 3.0
2017-11-08T07:32:45.383Z
@Makogan you may want to look at [this post](https://computergraphics.stackexchange.com/questions/405/how-to-produce-simple-2d-illustrations-to-accompany-geometry-answers/) for ideas on how to draw. Though the choice is a highly personal one.
joojaa
CC BY-SA 3.0
2017-11-08T08:32:39.480Z
Most of the software recommended there is payed software, I have a thing for free software :p
Makogan
CC BY-SA 3.0
2017-11-09T09:09:45.870Z
@Makogan I made the diagrams in [asymptote](http://asymptote.sourceforge.net/), which is open-source.
gilgamec
CC BY-SA 3.0
2017-11-09T12:37:33.663Z
@joojaa I've added animations of quadratic and cubic B-spline generation.
gilgamec
CC BY-SA 3.0
2017-11-09T14:56:45.187Z
@gilgamec yeah that meskes it easier to follow
joojaa
CC BY-SA 3.0
2017-11-09T14:58:41.900Z
@Makogan atleast half of all the suggested tools are free, its just that if you want nice sofdtware that do all you need quickly you need to pay. But obviously a researcher has access to even nonfree software for free.
joojaa
CC BY-SA 3.0
2017-11-07T10:08:34.453Z
2017-11-09T12:36:49.520Z
2017-11-09T12:36:49.520Z
gilgamec
<p>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.</p>

<p>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. </p>

<p>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. </p>

<p>Currently my very, very poor understanding is producing this:</p>

<p>Starting with the following 4 points</p>

<p><a href="https://i.sstatic.net/pOMeL.png" rel="noreferrer"><img src="https://i.sstatic.net/pOMeL.png" alt="enter image description here"></a></p>

<p>We duplicate each point (denoted by the grey area)</p>

<p><a href="https://i.sstatic.net/7Yn07.png" rel="noreferrer"><img src="https://i.sstatic.net/7Yn07.png" alt="enter image description here"></a></p>

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

<p><a href="https://i.sstatic.net/FR93Q.png" rel="noreferrer"><img src="https://i.sstatic.net/FR93Q.png" alt="enter image description here"></a></p>

<p>What do I do now? From here on I am just completely lost</p>

<algorithm><geometry><subdivision>
Visualizing the Lane-Riesenfeld Algorithm
Makogan
# Visualizing the Lane-Riesenfeld Algorithm

(Asked by: username_0 on 2017-11-03)

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](https://i.sstatic.net/pOMeL.png)](https://i.sstatic.net/pOMeL.png)

We duplicate each point (denoted by the grey area)

[![enter image description here](https://i.sstatic.net/7Yn07.png)](https://i.sstatic.net/7Yn07.png)

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](https://i.sstatic.net/FR93Q.png)](https://i.sstatic.net/FR93Q.png)

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

**Tags:** algorithm, geometry, subdivision


---

## 1 answers

### Answer by username_1 on 2017-11-07. Score: 16 | Accepted 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:

[![One duplication and one movement step](https://i.sstatic.net/d7Dfn.png)](https://i.sstatic.net/d7Dfn.png)

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](https://i.sstatic.net/gjIca.png)](https://i.sstatic.net/gjIca.png)

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](https://i.sstatic.net/AXVhV.png)](https://i.sstatic.net/AXVhV.png)

Here's an animation of this process:

[![Animation of LR algorithm creating quadratic B-spline](https://i.sstatic.net/Q29mn.gif)](https://i.sstatic.net/Q29mn.gif)

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](https://i.sstatic.net/HaIxE.png)](https://i.sstatic.net/HaIxE.png)

An animation of this process:

[![Animation of LR algorithm creating cubic B-spline](https://i.sstatic.net/94Um1.gif)](https://i.sstatic.net/94Um1.gif)

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

**EDIT**: Added animations.

> **Comments:**
> **username_2**: 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.  
> **username_0**: Also, what software did you use to draw/generate this?  
> **username_2**: @username_0 you may want to look at [this post](https://computergraphics.stackexchange.com/questions/405/how-to-produce-simple-2d-illustrations-to-accompany-geometry-answers/) for ideas on how to draw. Though the choice is a highly personal one.  
> **username_0**: Most of the software recommended there is payed software, I have a thing for free software :p  
> **username_1**: @username_0 I made the diagrams in [asymptote](http://asymptote.sourceforge.net/), which is open-source.  
> **username_1**: @username_2 I've added animations of quadratic and cubic B-spline generation.  
> **username_2**: @username_1 yeah that meskes it easier to follow  
> **username_2**: @username_0 atleast half of all the suggested tools are free, its just that if you want nice sofdtware that do all you need quickly you need to pay. But obviously a researcher has access to even nonfree software for free.  

---

