Ugrás a tartalomhoz

Komputergrafika -- Matematikai alapok

Dr. Kovács Emőd

Kempelen Farkas Hallgatói Információs Központ

B-spline görbe előállítása

B-spline görbe előállítása

A görbe alőállítására – az előbbi fejezet alapján – már tudunk készíteni programot. Mivel a polinominális alakban megadott rekurzív függvény számítása rosszul kondicionált, ezért javallott  a Bézier görbénél tanult lineáris műveleteket tartalmazó de Casteljau algoritmushoz hasonló Cox de Boor algoritmus használata.

Cox-de Boor algoritmus

de Boor javasolt egy algoritmust arra, hogy B-spline görbe pontot állítsunk elő rekurzívan, lineáris műveletek segítségével. A (9.1) egyenletben definiált rekurzív formula átalakításával kezdjük:

Indextranszformációt hajtunk végre a második tagon, ,amely a következőt eredményezi

ahol, és . Az újraindexelést folytatva kapjuk

ha

akkor

konvex lineáris kombináció, ahol

Ha az algoritmust folytatjuk addig, hogy feltétel teljesül, akkor megkapjuk az bázisfüggvényt, azaz esetén a függvényértéket

Ezt a felosztási algoritmust Cox-de Boor algoritmusnak nevezzük. Ha az és multiplicitása , azaz

akkor speciális esetként a de Casteljau-algoritmust kapjuk, következésképpen a B-spline görbe speciális eseteként a Bézier görbét. Bizonyítást a [48]-ban találjuk meg.

Figyelembe véve azt a tényt, hogy adott paraméter esetén minden eltűnik kivéve azon bázisfüggvényt, ahol az indexekre igaz, hogy A Cox- de Boor algoritmus a következő sémával adható meg:

Ez alapján a szerkesztés is könnyen elvégezhető, csak itt a szakaszok osztási aránya függ a csomóértékektől.

9.6. ábra. B-spline görbepont szerkesztése de Boor algoritmussal,

Mivel programozási szempontból nagyon fontos a Cox-de Boor algoritmus, ezért részletesen megadjuk az algoritmust:

Adatok:

  • ahol de Boor pont , a B-spline görbe rendje (fokszám

  • Zárt görbe esetén, a (9.3) szerint megadott csomóértékeket érdemes kiterjeszteni jobbra és balra is, azaz bevezetni az

    értékeket

  • Nyílt görbe esetén, a csomóértékek megadása legyen

A számítás menete:

Határozzuk meg a paraméter értékhez tartozó görbe pontot.

  1. Keressünk olyan értéket, amelyre igaz

  2. Legyen , for to do

  3. Ismételten alkalmazzuk a formulát: for to do for to do

    Ha uniform módon adjuk meg a csomóértékeket és a lépésköz 1, akkor

  4. Számítsuk ki a görbepontot .