# TP5 : Lane-Riesenfeld algorithm

## Code

## Uniform B-splines

In TP3, you have implemented the De Boor’s algorithm for evaluation of general B-splines. Now, let’s have a look at a particular subclass of B-spline curves, characterized by the uniform knot vector $t_i = i \; \; \forall i \in \mathbb Z$; have a look at the basis induced by such vector.

Your today’s task will be to implement these uniform B-splines as subdivision curves.

## Lane-Riesenfeld algorithm

For a given `degree`

, the following constitutes one subdivision step
of the Lane-Riesenfeld algorithm.
From initial polygon $\mathbf P_0, \mathbf P_1, \dots, \mathbf P_{n-1}$ with $n$ vertices,
we compute subdivided polygon $\mathbf S_0, \mathbf S_1, \dots, \mathbf S_{2n-1}$ with $2n$ vertices.

### Double the points (refining) :

### Average multiple times (smoothing) :

($i$-indices are taken modulo $2n$)

### Replace :

With increasing `degree`

, the Stanford bunny becomes smoother and smoother. Here, the `degree`

runs from 2 to 20 and back.

## Variations on the Lane-Riesenfeld algorithm

Since the introduction of the algorithm by Lane and Riesenfeld in 1980, multiple variations of the original scheme were introduced.
We will implement two of them, replacing the *midpoint averaging* with **four-point** and **six-point averaging**.
You already know the four-point averaging from the previous TP.

For brevity, I’m only including the modified parts of the original algorithm.

Don’t forget the indices are taken **modulo** $2n$ in the smoothing step!

### Four-point

In the refining step, vertices are no longer doubled: the new ones are already computed via four-point averaging.
Then, we perform additional `degree`

averagings on all vertices.

#### Refine :

#### Smooth :

### Six-point

Very similar to the four-point scheme.

#### Refine :

#### Smooth :

## ToDo

- Implement the three subdivision schemes (for closed polygons). Test with the provided datasets.
- Try varying the
`degree`

parameter. How do the curves change? - What differences between the three schemes do you observe? In your opinion, which scheme gives better results? Why?
- Simplify the original Lane-Riesenfeld scheme for
`degree=2`

. What do you observe?

## Resources

- Subdivision curves on Numerical Tours by Gabriel Peyré
- Subdivision spline curves
- Generalized Lane–Riesenfeld algorithms, paper by Cashman et al. (CAGD 2013)
- A Six-Point Variant on the Lane-Riesenfeld Algorithm, paper by Ashraf et al. (JAM 2014)