# TP4 : Subdivision curves

## Code

## Subdivision Curves

A subdivision curve is defined as the limit of *recursive refinement* of the input polyline $\mathbf x_i = \mathbf x_i^0$.
Your today’s task is to implement three curve subdivision schemes from the lecture.
For the sake of simplicity, we’ll be working with closed curves only.

Generally, one iteration of curve subdivision has the following form:

**Topological step**: curve is upsampled by inserting a new vertex between each two adjacent vertices. This doubles the number of vertices: if there were $n$ vertices, now there is $2n$ of them.**Geometric step**: new positions are computed for all vertices.

There are two kinds of schemes: *approximating* schemes change the positions of old vertices,
while the *interpolating* schemes don’t.

### Chaikin’s scheme

Introduced in 1974 by George Chaikin, this algorithm revolutionized the world of numerical geometry. Limit curve is a uniform quadratic B-spline.

\[\left\lbrace \begin{align} \mathbf x_{2i }^{k+1} & = \tfrac34 \mathbf x_i^k + \tfrac14 \mathbf x_{i+1}^k \\ \mathbf x_{2i+1}^{k+1} & = \tfrac14 \mathbf x_i^k + \tfrac34 \mathbf x_{i+1}^k \end{align} \right.\]### Corner-cutting

Generalization of Chaikin’s algorithm with two parameters $ 0 < a < b < 1 $.

\[\left\lbrace \begin{align} \mathbf x_{2i }^{k+1} & = (1-a) \mathbf x_i^k + a \mathbf x_{i+1}^k \\ \mathbf x_{2i+1}^{k+1} & = (1-b) \mathbf x_i^k + b \mathbf x_{i+1}^k \end{align} \right.\]Setting $a=0.25, b=0.75$ gives Chaikin. The following example uses $a = 0.1, b = 0.6$:

### Four-point

Unlike corner cutting, the four-point scheme is interpolatory.

\[\left\lbrace \begin{align} \mathbf x_{2i }^{k+1} & = \mathbf x_i^k \\ \mathbf x_{2i+1}^{k+1} & = \tfrac1{16} \left( - \mathbf x_{i-1}^k + 9 \mathbf x_{i}^k + 9 \mathbf x_{i+1}^k - \mathbf x_{i+2}^k \right) \end{align} \right.\]## ToDo

- Implement the three subdivision schemes.
- Experiment with different values of $a,b$ in corner cutting. Specifically, try using
- $b=a+\frac12$
- $b \neq a+\frac12$

What do you observe?

*Generalized four-point*uses the mask $[-\omega,\frac12+\omega,\frac12+\omega,-\omega].$

($\omega=\frac1{16}$ in the original scheme.) Modify your implementation of this algorithm to account for the tension parameter $\omega$ and try varying its value. You should get $\mathcal C^1$ limit curves for $\omega \in \left[0,(\sqrt 5 - 1)/8 \approx 0.154 \right]$.

## Resources

- Subdivision curves on Numerical Tours by Gabriel Peyré
- Lecture on subdivision curves by Don Fussell