[컴선설] Lec 07 B-spline Curve

8. B-spline Property

• $d$: degree
• $D$: dimension

\[N_i^d(u), \qquad x(u)=\sum_{i=0}^{D-1}d_i^xN_i^d(u)\]

• Convex hull property
• Variation diminishing
• Local property

Support

\[N_i^d(u)\ge 0 \quad\Rightarrow\quad \text{degree}+2\text{ knots}, \qquad [u_{i-1},u_{i+d}]\]

9. End Point Interpolation

Example

\[\mathbf{s}(u)=\sum_{i=0}^{5}\mathbf{d}_iN_i^d(u), \qquad D=6, \qquad \text{degree}=3\] \[\mathbf{d}_0=\mathbf{p}_0, \qquad \mathbf{d}_5=\mathbf{p}_3\] \[u_0=u_1=u_2, \qquad u_3, \qquad u_4, \qquad u_5=u_6=u_7\] \[N_0^3(u),\quad u\in[u_0,u_3] \qquad (\text{degree}+1)\] \[N_1^3(u),\quad u\in[u_0,u_4] \qquad (\text{degree}+2)\] \[N_2^3(u),\quad u\in[u_1,u_5]\] \[N_3^3(u),\quad u\in[u_2,u_6]\] \[N_4^3(u),\quad u\in[u_3,u_7]\] \[N_5^3(u),\quad u\in[u_4,u_7] \qquad (\text{degree}+1)\]

10. End Point Derivative

At the beginning of the curve,

\[\mathbf{s}'(u) = d\sum_{i=1}^{L+d-1} \frac{\Delta\mathbf{d}_{i-1}}{u_d-u_{d-1}} N_i^{d-1}(u)\]

At the end of the curve,

\[\mathbf{s}'(u) = d\sum_{i=1}^{L+d-1} \frac{\Delta\mathbf{d}_{i-1}}{u_{K-d}-u_{K-d-1}} N_i^{d-1}(u)\]

• $K$: number of knots
• $d$: degree
• $L$: number of pieces

For degree $3$,

\[\mathbf{s}'(u_2) = 3\frac{\mathbf{d}_1-\mathbf{d}_0}{u_3-u_2}\] \[\mathbf{s}'(u_5) = 3\frac{\mathbf{d}_5-\mathbf{d}_4}{u_5-u_4}\]

Match with Bessel end condition

\[\mathbf{L}(u) = \mathbf{p}_0 \frac{(u-u_1)(u-u_2)}{(u_0-u_1)(u_0-u_2)} + \mathbf{p}_1 \frac{(u-u_0)(u-u_2)}{(u_1-u_0)(u_1-u_2)} + \mathbf{p}_2 \frac{(u-u_0)(u-u_1)}{(u_2-u_0)(u_2-u_1)}\] \[\mathbf{L}'(u_2) = \mathbf{s}'(u_2) = 3\frac{\mathbf{d}_1-\mathbf{d}_0}{u_3-u_2}\] \[\mathbf{M}'(u_5) = \mathbf{s}'(u_5) = 3\frac{\mathbf{d}_5-\mathbf{d}_4}{u_5-u_4}\]

• 2 constraints from Bessel end condition
• 4 POC conditions with parameter

\[\mathbf{x}(u_2)=\mathbf{p}_0, \qquad \mathbf{x}(u_3)=\mathbf{p}_1, \qquad \mathbf{x}(u_4)=\mathbf{p}_2, \qquad \mathbf{x}(u_5)=\mathbf{p}_3\]

Solve the $6\times6$ linear system.

11. de Boor Algorithm (Knot Insertion)

• Can compute POC or a certain basis-function value $N_i^d(u)$.

Example

\[[0,0,0,3,6,6,6], \qquad \#\text{ of points}=5\]

Insert knot

\[\hat{u}=4\] \[\zeta_0^0=0, \qquad \zeta_1^0=1, \qquad \zeta_2^0=3, \qquad \zeta_3^0=5, \qquad \zeta_4^0=6\] \[\zeta_i^k = \frac{u_{i+d-k}-u}{u_{i+d-k}-u_{i-1}}\zeta_{i-1}^{k-1} + \frac{u-u_{i-1}}{u_{i+d-k}-u_{i-1}}\zeta_i^{k-1}\]

Substitute $\zeta_i^0\leftarrow d_i$.

For a certain basis function,

\[d_i= \begin{cases} 1, & i=r,\\ 0, & i\ne r \end{cases} \quad\Rightarrow\quad N_r^d(\hat{u})\] \[\#\text{ of control points} = \#\text{ of knots}-(\text{degree}-1)\] \[\#\text{ of intervals} = \#\text{ of knots}-2(\text{degree})+1\]

• Degree $0$: dimension $6$
• Degree $1$: dimension $5$
• Degree $2$
• Degree $3$

\[N_1^3(u) = N_1^2(u)\frac{u-u_0}{u_3-u_0} + N_2^2(u)\frac{u_4-u}{u_4-u_1}\]

Therefore,

\[N_i^k(u) = \frac{u-u_{i-1}}{u_{i+k-1}-u_{i-1}}N_i^{k-1}(u) + \frac{u_{i+k}-u}{u_{i+k}-u_i}N_{i+1}^{k-1}(u)\]

13. B-spline to Piecewise Bézier Curve

• Insert a knot until its multiplicity becomes the degree.
• Then split the curve at the inserted knot.

Example

• degree $=3$
• number of points $=5$
• $L=2$

\[[0,0,0,3,6,6,6]\]

Insert the knot $3$ two more times.

\[[0,0,0,3,3,3,6,6,6]\]

• Two piecewise Bézier curves are obtained.
• Finding the first and second derivatives: same method as Bézier curves.