LN11. Subdivision and Degree Elevation of Bézier Curve

1. Subdivision / Clipping Bézier Curve

Given a Bézier curve

\[\mathbf{C}(t) = \sum_{i=0}^{n}\mathbf{b}_{i}B_{i}^{n}(t), \qquad 0\le t\le1\]

subdivision at parameter $u$ divides it into

• a left curve over $[0,u]$,
• a right curve over $[u,1]$.

The two new curves have different control points but reproduce the original geometry exactly.

de Casteljau Construction

Set

\[\mathbf{b}_{i}^{0}=\mathbf{b}_{i}\]

and recursively compute

\[\mathbf{b}_{i}^{r} = (1-u)\mathbf{b}_{i}^{r-1} +u\mathbf{b}_{i+1}^{r-1}\]

for

\[r=1,2,\ldots,n\]

The point at the subdivision parameter is

\[\mathbf{C}(u)=\mathbf{b}_{0}^{n}\]

Left control points

\[\left\{ \mathbf{b}_{0}^{0}, \mathbf{b}_{0}^{1}, \ldots, \mathbf{b}_{0}^{n} \right\}\]

Right control points

\[\left\{ \mathbf{b}_{0}^{n}, \mathbf{b}_{1}^{n-1}, \ldots, \mathbf{b}_{n}^{0} \right\}\]

For a cubic curve,

\[\{\mathbf{b}^{*}\} = \{\mathbf{b}_{0}^{0},\mathbf{b}_{0}^{1},\mathbf{b}_{0}^{2},\mathbf{b}_{0}^{3}\}\] \[\{\mathbf{b}^{**}\} = \{\mathbf{b}_{0}^{3},\mathbf{b}_{1}^{2},\mathbf{b}_{2}^{1},\mathbf{b}_{3}^{0}\}\]

Reparameterization

Let $s\in[0,1]$.

Left curve

\[\mathbf{C}_{1}(s)=\mathbf{C}(us)\]

Right curve

\[\mathbf{C}_{2}(s)=\mathbf{C}\big(u+(1-u)s\big)\]

At the common endpoint,

\[\mathbf{C}_{1}(1)=\mathbf{C}(u)=\mathbf{C}_{2}(0)\]

Clipping

Clipping extracts an arbitrary parameter interval $[u_{1},u_{2}]$ from a curve. It can be performed by two subdivisions.

1. Subdivide at $u_2$ and keep the forward part.
2. Reparameterize the retained interval.
3. Subdivide again at $u_1/u_2$ and keep the after part.

\[\mathbf{C}(t)\big|_{\mathrm{clip}(u_1,u_2)} = \left[ \mathbf{C}(t)\big|_{\mathrm{subdivide}(u_2,\mathrm{fwd})} \right] \bigg|_{\mathrm{subdivide}(u_1/u_2,\mathrm{aft})}\]

2. Degree Elevation

Degree elevation increases the degree of a Bézier curve without changing its shape.

\[\mathbf{C}(t) = \sum_{i=0}^{n}\mathbf{b}_{i}B_{i}^{n}(t) = \sum_{i=0}^{n+1}\mathbf{b}_{i}'B_{i}^{n+1}(t)\]

Use

\[(1-t)+t=1\]

to express the degree-$n$ basis in the degree-$(n+1)$ basis.

The elevated control points are

\[\mathbf{b}_{0}'=\mathbf{b}_{0}\] \[\mathbf{b}_{i}' = \frac{i}{n+1}\mathbf{b}_{i-1} + \frac{n+1-i}{n+1}\mathbf{b}_{i}, \qquad 1\le i\le n\] \[\mathbf{b}_{n+1}'=\mathbf{b}_{n}\]

Degree $2$ to degree $3$

\[\mathbf{b}_{0}'=\mathbf{b}_{0}\] \[\mathbf{b}_{1}' = \frac{1}{3}\mathbf{b}_{0} + \frac{2}{3}\mathbf{b}_{1}\] \[\mathbf{b}_{2}' = \frac{2}{3}\mathbf{b}_{1} + \frac{1}{3}\mathbf{b}_{2}\] \[\mathbf{b}_{3}'=\mathbf{b}_{2}\]