4. B-Spline görbék

Bases Spline

Lásd még

4.1. Normalizált B-spline alapfüggvény

Tekintsük az \(u_i \in \mathbb{R}, i \in \mathbb{Z}\) értékeket, amelyekre teljesül, hogy \(u_i \leq u_{i+1}\)! A B-spline alapfüggvényt az alábbi rekurzív formában definiálhatjuk:

\[\begin{split}N_i^1(u) = \begin{cases} 1, & \text{ha } u_i \leq u < u_{i+1}, \\ 0, & \text{egyébként}, \end{cases}\end{split}\]
\[N_i^k(u) = \dfrac{u - u_i}{u_{i+k-1} - u_i} N_i^{k-1}(u) + \dfrac{u_{i+k} - u}{u_{i+k} - u_{i+1}} N_{i+1}^{k-1}(u).\]

  • Az \(\{u_i\}_{i \in \mathbb{Z}}\) értékeket csomóértékeknek (knot values) hívjuk.

  • A komponenseikből képzett vektor a csomóvektor (knot vector).

  • Ahol 0-val való osztás fordulna elő, ott az eredményt 0-nak tekintjük.

\(\rhd\) Írjuk fel és ábrázoljuk a másod- és harmadfokú B-spline alapfüggvényeket!

Az \(u_i\) értékek megválasztására itt is alkalmazhatunk egyenközű (vagy másnéven uniform) felosztást, például \(u_i = i\).

Az azonos fokszámú görbék eltolással származtathatók egymásból, vagyis

\[N_i^k(u) = N_0^k(u - i), \quad \forall i \in \mathbb{Z}.\]

Megjegyzés

  • A \(k\)-adrendű B-spline alapfüggvények (legfeljebb) \((k-1)\)-edfokú polinomokat tartalmaznak.

  • Az \(N_i^k\) csak az \((u_i, u_{i+k})\) intervallumon lehet 0-tól különböző.

  • Tekintsük az \([u_i, u_{i+1})\) intervallumot! Ennek azon \(N_j^k\) normalizált B-spline alapfüggvényekre van hatása, ahol \((i - k + 1) \leq j \leq i\).

4.1.1. Lokalitási tétel

\[N_i^k(u) = 0, \text{ha } u \notin [u_i, u_{i+k}).\]

Bizonyítás (indukciós)

\(k = 1\) esetén az állítás definíció szerint teljesül.

Helyettesítsük vissza a \((k-1)\) értéket, és vegyük észre, hogy

\[\begin{split}\begin{align} &N_i^{k-1}(u) = 0, \text{ha } u \notin [u_i, u_{i+k-1}), \\ &N_{i+1}^{k-1}(u) = 0, \text{ha } u \notin [u_{i+1}, u_{i+k}). \\ \end{align}\end{split}\]

Mivel \(u \notin [u_i, u_{i+k})\) esetén ezeknek a lineáris kombinációját kellene venni (az \(u\) érték és a csomóértékek függvényében), ezért biztosan 0 lesz az értéke. \(\square\)

4.1.2. Nemnegativitási tétel

A normalizált B-spline alapfüggvények nemnegatívak, vagyis

\[N_i^k(u) \geq 0, \forall u \in \mathbb{R}, i \in \mathbb{Z}, k \geq 1.\]

4.1.3. Egységfelbontási tétel

A \(k\)-adrendű normalizált B-spline alapfüggvények egységfelbontást alkotnak, azaz

\[\sum_j N_j^k (u) = 1, \quad \forall u \in \mathbb{R}, \forall k \geq 1.\]

4.1.4. Többszörös csomóértékek

A definíció lehetővé teszi, hogy ugyanazon \(u_i\) értékeket többször is szerepeltessünk. Vizsgáljuk meg harmadfokú B-spline alapfüggvény esetén a hatását!

A harmadfokú B-spline alapfüggvény a következőképpen írható föl:

\[\begin{split}N_i^3(u) = \begin{cases} \dfrac{(u-u_i)^2}{(u_{i+2}-u_i)(u_{i+1}-u_i)}, & \text{ha } u \in [u_i, u_{i+1}), \\ \dfrac{(u-u_i)(u_{i+2}-u)}{(u_{i+2}-u_i)(u_{i+2}-u_{i+1})} + \dfrac{(u_{i+3}-u)(u-u_{i+1})}{(u_{i+3}-u_{i+1})(u_{i+2}-u_{i+1})}, & \text{ha } u \in [u_{i+1}, u_{i+2}), \\ \dfrac{(u_{i+3}-u)^2}{(u_{i+3}-u_{i+1})(u_{i+3}-u_{i+2})}, & \text{ha } u \in [u_{i+2}, u_{i+3}), \\ 0, & \text{egyébként}. \end{cases}\end{split}\]

Tegyük fel, hogy \(u_{i+1} = u_{i+2}\) teljesül! Ekkor azt kapjuk, hogy

\[\begin{split}N_i^3(u) = \begin{cases} \dfrac{(u - u_i)^2}{(u_{i+1} - u_i)^2}, & \text{ha } u \in [u_i, u_{i+1}), \\ \dfrac{(u_{i+3} - u)^2}{(u_{i+3} - u_{i+1})^2}, & \text{ha } u \in [u_{i+1}, u_{i+3}), \\ 0, & \text{egyébként}. \end{cases}\end{split}\]

Szemléletesen tulajdonképpen egymáshoz toltuk az \(u_{i+1}\) és \(u_{i+2}\) értékeket. Az alapfüggvény így az adott pontban folytonos maradt, viszont már nem differenciálható.

Több csomóérték egybeesését mint csomóérték multiplicitást definiálhatjuk.

Egy csomóérték multiplicitása \(m\), hogy ha \(m\) darab egymás utáni csomóérték esik egybe, vagyis

\[u_{i-1} < u_i = u_{i+1} = \cdots = u_{i+m-1} < u_{i+m}.\]

4.1.5. Kapcsolat a Bernstein polinomokkal

Az

\[u_0, u_1 = u_2 = \ldots = u_{k-1}, u_k = u_{k+1} = \ldots = u_{2k-2} = 1, u_{2k-1}\]

csomóértékek esetében teljesül, hogy

\[N_i^{k-j}(u) = B_{i-j}^{k-1-j}(u), \forall u \in [u_{k-1}, u_k], i = 0, 1, \ldots, k - 1, j = 0, 1, \ldots, i.\]

4.1.6. Multiplicitásra vonatkozó tétel

Hogy ha az \(u_i\) csomóérték multiplicitása \(k\), akkor \(N_i^k(u_i) = 1\).

4.1.7. Derivált

Az \(N_i^k(u)\) normalizált B-spline alapfüggvény deriváltja:

\[\dfrac{\mathrm{d}}{\mathrm{d}u} N_i^k(u) = (k - 1) \left( \dfrac{1}{u_{i+k-1}-u_i}N_i^{k-1}(u) - \dfrac{1}{u_{i+k} - u_{i+1}}N_{i+1}^{k-1}(u) \right),\]

ahol \([u_i, u_{i+k})\).

4.1.8. Lineáris függetlenség

Az \(\{N_j^k\}_{j=i-k+1}^i\) normalizált B-spline alapfüggvények lineárisan függetlenek az \([u_i, u_{i+1})\) intervallumon, hogy ha \(u_i < u_{i+1}\).

4.2. B-spline görbe

Legyenek adottak a \(\textbf{d}_0, \textbf{d}_1, \ldots, \textbf{d}_n\) kontrollpontok és az \(\{u_j\}_{j=0}^{n+k}\) csomóértékek! Az

\[\textbf{s}(u) = \sum_{i=0}^n N_i^k(u) \textbf{d}_i, u \in [u_{k-1}, u_{n+1}], 1 < k < n + 1\]

formában definiált görbét \(k\)-adrendű (vagy \((k-1)\)-edfokú) B-spline görbének nevezzük.

  • A \(\textbf{d}_i\) pontokat kontrollpontoknak (vagy de Boor pontoknak) nevezzük.

  • Az \(N_i^k\) az \(i\)-edik \((k-1)\)-edfokú normalizált B-spline görbét jelöli.

A B-spline görbe általános esetben approximációs görbe. Kivételt képezhetnek például az alábbi esetek.

  • Hogy ha \(k = 2\), akkor a kontrollpoligont kapjuk vissza.

  • Áthaladhat a kontrollpontokon, hogy ha a pontok kollineárisak.

  • Hogy ha a kezdő és a végpontban a multiplicitás \(k\), akkor a Bézier görbéhez hasonlóan interpolál a végpontokban.

Megjegyzés

Utóbbit egyszerűen beláthatjuk. Tegyük fel, hogy \(u_1 = u_2 = \cdots = u_{k-1}\)! A görbe pontját az \(u_{k-1}\) paraméternél a következőképpen számíthatjuk ki:

\[\textbf{s}(u_{k-1}) = \sum_{i=0}^{k-1} N_i^k(u_{k-1}) \textbf{d}_i.\]

Tudjuk, hogy \(N_i^k(u_{k-1}) = 0\), hogy ha \(i \in [1, k-2]\). A tétel alapján az \(N_0^k(u_{k-1}) = 1\) összefüggést kihasználva adódik, hogy

\[\textbf{s}(u_{k-1}) = \textbf{d}_0.\]

Hasonlóképpen kikövetkeztethető, hogy a \(\textbf{d}_n\) pontban szintén interpolálni fog a görbe a megfelelő multiplicitást megadva.

4.2.1. A görbe tulajdonságai

A B-spline görbe lokálisan változtatható, vagyis egy kontrollpont megváltoztatása csak a görbe egy adott részére van hatással, nem az egészre.

Egy \((k-1)\)-edfokú B-spline görbe bármely íve a \(k\) darab egymást követő kontrollpontjának konvex burkában van.

4.2.2. A de Boor-algoritmus

A de Boor-algoritmus, egy, a de Castejau algoritmushoz hasonló rekurzív eljárást segítségével is képes meghatározni a B-spline görbe egy adott, \(u\) paraméterhez tartozó pontját. Egy numerikusan stabil eljárásról van szó.

Vezessük be a következő jelöléseket:

\[\begin{split}\alpha_j^l(u) = \begin{cases} 1, & \text{ha } l = 0, \\ \dfrac{u - u_j}{u_{j+k-l} - u_j}, & \text{ha } l > 0, \end{cases}\end{split}\]
\[\begin{split}\textbf{d}_j^l(u) = \begin{cases} \textbf{d}_j, & \text{ha } l = 0, \\ \alpha_j^l(u)\textbf{d}_j^{l-1}(u) + (1 - \alpha_j^l(u)) \textbf{d}_{j-1}^{l-1}(u), & \text{ha } l > 0, \end{cases}\end{split}\]

ahol

\[l = 0, 1, \ldots, k - 1, j = i - k + 1 + l, \ldots, i.\]

Az \(l\) érték a kitevőben az iteráció számát jelöli. Segédpontokat számolunk az \(\alpha\) értékekből számolt arányokkal.

Az \(l < (k - 1)\) lépésekben:

\[\textbf{s}(u) = \sum_{j=i-k+l+1}^i \textbf{d}_j^l(u) N_j^{k-l}(u),\]

az \(l = (k - 1)\) lépésben:

\[\textbf{s}(u) = \textbf{d}_i^{k-1},\]

mivel

\[\begin{split}N_i^1(u) = \begin{cases} 1, & \text{ha } u \in [u_i, u_{i+1}), \\ 0, & \text{egyébként}. \end{cases}\end{split}\]

Az algoritmus ugyan hasonló a de Casteljau algoritmushoz, de van néhány lényegi különbség ahhoz képest.

  • A felosztás során nem \(u:(1-u)\) arányban osztjuk fel a szakaszt.

  • Egy pont előállításához nincs szükség az összes kontrollpontra. (Ebből adódik a görbe lokális vezérelhetősége.)

  • Az algoritmus nem alkalmas a görbe kettévágására.

Lásd még

4.2.3. A görbe deriváltja

A B-spline görbe deriváltja az \(u \in [u_i, u_{i+1})\) helyen az alábbi alakban írható föl:

\[\dfrac{\mathrm{d}}{\mathrm{d}u} \textbf{s}(u) = (k - 1)\sum_{j=i-k+2}^i \dfrac{\textbf{d}_j - \textbf{d}_{j-1}}{u_{j+k-1} - u_j} N_j^{k-1}(u).\]

Ez tehát azt jelenti, hogy egy \((k - 1)\)-edfokú B-spline görbe hodográfja egy \((k - 2)\)-edfokú B-spline görbe.

A derivált a de Boor algoritmus pontjai segítségével is felírható:

\[\dfrac{k-1}{u_{i+1} - u_i} (\textbf{d}_i^{k-2}(u) - \textbf{d}_{i-1}^{k-2}(u)).\]

4.3. Kérdések

  • Hogyan definiáljuk a normalizált B-spline alapfüggvényt?

  • Mondja ki a normalizált B-spline alapfüggvényre vonatkozó lokalitási tételt!

  • Mondja ki a normalizált B-spline alapfüggvényre vonatkozó nemnegativitási tételt!

  • Mondja ki a normalizált B-spline alapfüggvényre vonatkozó egységfelbontási tételt!

  • Definiálja a B-spline görbét!

  • Milyen tulajdonságai vannak a B-spline görbének?

4.4. Programozási feladatok

4.4.1. Görbe megjelenítése, vizsgálata

  • Készítsünk egy programot, amely 8 kontrollpontra képes megjeleníteni a B-spline görbét!

  • Oldjuk meg, hogy a görbe rendjét lehessen változtatni!

  • Jelenítsük meg egy mozgatott kontrollpont esetén, hogy annak hatására a görbe mely része tud csak változni!

  • Oldjuk meg, hogy meg lehessen adni a kontrollpontok multiplicitását!

  • Jelenítsük meg a görbék szakaszait és a hozzájuk tartozó konvex burkokat (például váltogatva közöttük), amelyek esetében a görbe semmiképpen sem léphet ki azokon.

  • Implementálja a de Boor algoritmust!

  • Számítsa ki és jelenítse meg a görbe adott pontjához tartozó irányvektort és normálvektort!

4.4.2. Elérhető implementációk

Vizsgáljuk meg, hogy milyen elérhető implementáció vannak a B-spline függvényeknek és görbéknek! Például:

4.5. További feladatok

  • Implementálja a B-spline görbével történő interpolációt!

  • Vizsgálja meg, hogy nagy számú (enyhén zajos) ponthalmaz esetén hogyan lehet közelítést adni egy \(k\)-adrendű B-spline görbével!

  • Vizsgálja meg és hasonlítsa össze azokat az algoritmusokat, amelyre (azonos megjelenítési pontosságot feltételezve) minimializálni lehet a kirajzolandó szakaszok számát!

  • Határozza meg tetszőleges görbe esetén azon különböző \(u_i\) értékeket, amelyeknél a görbe saját magát metszi!

  • Adjon közelítést egy zárt, B-spline görbékkel határolt alakzat területére!

  • Dolgozzon ki egy eljárást, amellyel adott B-spline görbéhez alacsonyabb rendű B-spline görbe közelítést lehet adni! Vizsgálja meg a közelítés pontosságát!