Počítačová grafika 23/24

Coonsova kubika, Coonsův kubický B-spline
ukotvená B-spline kubika
interpolační křivky

Coonsova kubika

Steven Anson Coons (1912 - 1979)
Massachusetts Institute of Technology (MIT)

Coonsova kubika

aproximační křivka 3. stupně daná 4 řídicími body $P_0, P_1, P_2, P_3$

vektorová rovnice:

$$\mathscr{P}(t)=C_0(t)P_0 + C_1(t)P_1 + C_2(t)P_2 + C_3(t)P_3,\ t\in[0,1]$$
Coonsovy polynomy

$C_0(t)=\frac{1}{6}(1-t)^3$
$C_1(t)=\frac{1}{6}(3t^3-6t^2+4)$
$C_2(t)=\frac{1}{6}(-3t^3+3t^2+3t+1)$
$C_3(t)=\frac{1}{6}t^3$

Coonsova kubika

Coonsovy a Bernsteinovy polynomy - průběhy

Počáteční bod křivky

$$\mathscr{P}(0)=\frac{1}{6}P_0 + \frac{2}{3}P_1 + \frac{1}{6}P_2\\ \Downarrow\\ \mathscr{P}(0)=P_1 + \frac{1}{6}(P_0-P_1) + \frac{1}{6}(P_2-P_1)\\ \Downarrow\\ \mathscr{P}(0)=P_1 + \frac{1}{2}(\frac{1}{3}\vec{P_1P_0}+\frac{1}{3}\vec{P_1P_2})$$

Konstrukce počátečního bodu

Počáteční bod - vlastnosti

$\mathscr{P}(0)$ je tzv. antitěžiště trojúhelníka $P_0P_1P_2$

Koncový bod křivky

$$\mathscr{P}(1)=\frac{1}{6}P_1 + \frac{2}{3}P_2 + \frac{1}{6}P_3\\ \Downarrow\\ \mathscr{P}(1)=P_2 + \frac{1}{2}(\frac{1}{3}\vec{P_2P_1}+\frac{1}{3}\vec{P_2P_3})$$

Krajní body křivky

$\mathscr{P}(0)$ je "antitěžiště" trojúhelníka $P_0P_1P_2, \mathscr{P}(1)$ je "antitěžiště" trojúhelníka $P_1P_2P_3$

Počáteční a koncový tečný vektor

derivace Coonsových polynomů:
$C'_0(t)=-\frac{1}{2}(1-t)^2$
$C'_1(t)=\frac{1}{2}(3t^2-4t)$
$C'_2(t)=\frac{1}{2}(-3t^2+2t+1)$
$C'_3(t)=\frac{1}{2}t$

$$\mathscr{P}'(0)=-\frac{1}{2}P_0 + \frac{1}{2}P_2 = \frac{1}{2}\vec{P_0P_2}$$
$$\mathscr{P}'(1)=-\frac{1}{2}P_1 + \frac{1}{2}P_3 = \frac{1}{2}\vec{P_1P_3}$$

Počáteční a koncový tečný vektor

Vztah mezi Coonsovou a Bézierovou kubikou

Napojování Coonsových kubik

$C^2$ spojité napojení

řídicí polygon $P_0,P_1,P_2,P_3$ Coonsovy kubiky $\mathscr{P}(t)$
řídicí polygon $R_0,R_1,R_2,R_3$ Coonsovy kubiky $\mathscr{R}(s)$

$C^0 \iff \frac{1}{6}P_1 + \frac{2}{3}P_2 + \frac{1}{6}P_3 = \frac{1}{6}R_0 + \frac{2}{3}R_1 + \frac{1}{6}R_2$
$C^1 \iff C^0 \land -\frac{1}{2}P_1+\frac{1}{2}P_3=-\frac{1}{2}R_0+\frac{1}{2}R_2$
$C^2 \iff C^1 \land P_1-2P_2+P_3=R_0-2R_1+R_2$

soustava 3 rovnic pro neznámé $R_0,R_1,R_2$ $\Rightarrow$ jediné řešení $R_0=P_1$, $R_1=P_2$, $R_2=P_3$

spline křivka

- interpolační vícesegmentová polynomiální křivka

B-spline křivka

- aproximační vícesegmentová křivka

  • B (basis) - bázové funkce
  • všechny segmenty napojeny se spojitostí min. $C^2$ (např. segmenty Bézierových kubik napojené s $C^2$ spojitostí)
  • zobecněním B-spline křivky je NeUniformní Racionální B-Spline (NURBS)

Coonsův kubický B-spline

- aproximační vícesegmentová křivka třetího stupně, jejíž segmenty jsou Coonsovy kubiky napojené s $C^2$ spojitostí

v terminologii NURBS $\Rightarrow$ Uniformní neRacionální B-Spline 3. stupně

Coonsův kubický B-spline

Dáno: $P_0, P_1, ..., P_n$

jednotlivé segmenty $k_i$ jsou Coonsovy kubiky s řídicími polygony:

$k_1 : (P_0P_1P_2P_3)$

$k_1 : (P_1P_2P_3P_4)$

$\dots$

$k_{n-3} : (P_{n-3}P_{n-2}P_{n-1}P_n)$

počet segmentů: $n-2$

Coonsův kubický B-spline otevřený

řídicí polygon $P_0,P_1,P_2,P_3,P_4$

Coonsův kubický B-spline uzavřený

řídící polygon $P_0,P_1,P_2,P_3,P_4(,P_5=P_0,P_6=P_1,P_7=P_2)$

Ukotvená uniformní B-spline kubika

Dáno: $P_0, P_1, ..., P_n$

vícesegmentová B-spline křivka třetího stupně, prochází krajními řídícími body, ostatní body aproximuje

počet segmentů: n-2

Ukotvená kubika - 4 body

Ukotvená kubika - 5 bodů

Ukotvená kubika - 6 bodů

Ukotvená kubika - 10 bodů

Ukotvená kubika - Coonsův kubický B-spline

Interpolační křivky

  • Fergusonova (Hermitova) kubika - jednosegmentová
  • interpolace jedním polynomem ($n$ definičních bodů $\Rightarrow$ stupeň křivky $n-1$)
  • definiční body interpolované po částech $C^2$ spojitě napojenými kubikami

Příklad - 4 definiční body

Obecný postup

každý segment mezi dvěma po sobě jdoucími $Q$ body má být křivka 3. stupně
$$\Downarrow$$
$4$ neznámé koeficienty $\alpha,\beta,\gamma,\delta$ pro rovnici segmentu ve tvaru $\mathscr{P}(t)=\alpha t^3+\beta t^2+\gamma t+\delta$
$$\Downarrow$$
$4$ body $\rightarrow$ $3$ segmenty $\rightarrow$ $12$ neznámých
$$\Downarrow$$
$\mathscr{P}_0(0)=Q_0, \mathscr{P}_0(1)=Q_1=\mathscr{P}_1(0), \mathscr{P}_1(1)=Q_2=\mathscr{P}_2(0), \mathscr{P}_2(1)=Q_3$
$\mathscr{P}'_0(1)=\mathscr{P}'_1(0), \mathscr{P}'_1(1)=\mathscr{P}'_2(0)$
$\mathscr{P}''_0(1)=\mathscr{P}''_1(0), \mathscr{P}''_1(1)=\mathscr{P}''_2(0)$
$$\Downarrow$$
$10$ rovnic pro $12$ neznámých
$$\Downarrow$$
dodat další $2$ (okrajové) podmínky
(např.$\mathscr{P}''_0(0)=0=\mathscr{P}''_2(1)$)

Soustava rovnic pro určení $\mathscr{P}_i(t)$

$$\begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 3 & 2 & 1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 2 & 1 & 0 & 0 & 0 & -1 & 0\\ 3 & 1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & -1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0\\ \end{pmatrix}\cdot\begin{pmatrix} \alpha_0\\ \beta_0\\ \gamma_0\\ \delta_0\\ \alpha_1\\ \beta_1\\ \gamma_1\\ \delta_1\\ \alpha_2\\ \beta_2\\ \gamma_2\\ \delta_2\\ \end{pmatrix}= \begin{pmatrix} Q_0\\ Q_1\\ Q_1\\ Q_2\\ Q_2\\ Q_3\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{pmatrix}$$

Rovnice + vykreslení (Maple)


Využití $C^2$ napojení Bézierových kubik

soustava rovnic pro určení dvou vnitřních řídicích bodů každého segmentu
$$\Downarrow$$
$3$ Bézierovy kubiky $\rightarrow$ $6$ neznámých bodů $N_i$, $i=0,\dots,5$
$$\Downarrow$$
$C^1$ napojení Bézierových kubik ve vnitřních definičních bodech $Q_1$ a $Q_2$ $\rightarrow$ $N_1+N_2=2Q_1, N_3+N_4=2Q_2$
$C^2$ napojení Bézierových kubik ve vnitřních definičních bodech $Q_1$ a $Q_2$ $\rightarrow$ $-N_0+4N_1+N_3=4Q_1, -N_2+4N_3+N_5=4Q_2$
$$\Downarrow$$
$4$ rovnice pro $6$ neznámých
$$\Downarrow$$
dodat $2$ okrajové podmínky (např. nulový vektor druhé derivace v bodech $Q_0$ a $Q_3$)

Soustava rovnic pro určení bodů $N_i$

$$\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0\\ -1 & 4 & 0 & 1 & 0 & 0\\ 0 & 0 & -1 & 4 & 0 & 1\\ 2 & -1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & -1 & 2\\ \end{pmatrix}\cdot\begin{pmatrix} N_0\\ N_1\\ N_2\\ N_3\\ N_4\\ N_5\\ \end{pmatrix}=\begin{pmatrix} 2Q_1\\ 2Q_2\\ 4Q_1\\ 4Q_2\\ Q_0\\ Q_3\\ \end{pmatrix}$$

segmenty jako Bézierovy kubiky

Využití $C^2$ napojení Fergusonových kubik

soustava rovnic pro určení vnitřních tečných vektorů
$$\Downarrow$$
$3$ Fergusonovy kubiky $\rightarrow$ $6$ neznámých vektorů $\vec{a}_i$, $\vec{b}_i$, $i=0,\dots,2$
$$\Downarrow$$
$C^1$ napojení Fergusonových kubik ve vnitřních definičních bodech $Q_1$ a $Q_2$ $\rightarrow$ $\vec{b}_0=\vec{a}_1, \vec{b}_1=\vec{a}_2$
$C^2$ napojení Fergusonových kubik ve vnitřních definičních bodech $Q_1$ a $Q_2$ $\rightarrow$ $\vec{a}_0+2\vec{b}_0+2\vec{a}_1+\vec{b}_1=3Q_2-3Q_0, \vec{a}_1+2\vec{b}_1+2\vec{a}_2+\vec{b}_2=3Q_3-3Q_1$
$$\Downarrow$$
$4$ rovnice pro $6$ neznámých
$$\Downarrow$$
dodat $2$ okrajové podmínky (např. nulový vektor druhé derivace v bodech $Q_0$ a $Q_3$)

Soustava rovnic pro určení vektorů $\vec{a}_i, \vec{b}_i$

$$\begin{pmatrix} 0 & 1 & -1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & -1 & 0\\ 1 & 2 & 2 & 1 & 0 & 0\\ 0 & 0 & 1 & 2 & 2 & 1\\ 2 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 2\\ \end{pmatrix}\cdot\begin{pmatrix} \vec{a}_0\\ \vec{b}_0\\ \vec{a}_1\\ \vec{b}_1\\ \vec{a}_2\\ \vec{b}_2\\ \end{pmatrix}=\begin{pmatrix} 0\\ 0\\ 3Q_2-3Q_0\\ 3Q_3-3Q_1\\ -3Q_0+3Q_1\\ -3Q_2+3Q_3\\ \end{pmatrix}$$

Segmenty jako Fergusonovy kubiky

Interpolační kubika - Rhino

Příště: Plochy