3.9. 3.9. Bézier-görbe közelítése töröttvonallal

Gyakran szükség van arra, hogy a Bézier-görbét adott pontossággal, töröttvonallal közelítsük. Ilyen feladat például a görbe megrajzolása, vagy ívhosszának kiszámítása.

A görbéket általában a görbébe írt töröttvonal segítségével jelenítjük meg, vagyis az görbe paraméterértékeihez tartozó pontjait kiszámítjuk, és ezeket kötjük össze egyenes szakaszokkal. Fontos kérdés azonban a paraméterértékek megválasztása.

Kézenfekvő, egyszerű megoldás a , vagyis az értelmezési tartomány egyenlő részre osztása. Kétségtelen, hogy növelésével előbb-utóbb kielégítő eredményt kapunk, azonban az esetek többségében túl sok szakaszt használunk, ami lassítja a kirajzolás műveletét. Ezzel az eljárással ugyanis a görbe olyan részeit is több szakasszal közelítjük, amelyek majdnem egyenes szakaszok, mivel a legnagyobb görbületű részhez kell megválasztani a felosztást. Tehát a jó kirajzoló algoritmusnak a görbület változását is figyelembe kell vennie. Az értelmezési tartomány egyenlő részekre osztása csak azoknál a görbéknél optimális, melyek görbületének változása nulla, vagyis a konstans görbületűeknél. Ilyen síkgörbe azonban, mint tudjuk, csak az egyenes és a kör, tehát minden más esetben ettől eltérő megoldást célszerű keresni. A Bézier-görbék esetén az alább ismertetendő algoritmus optimális eredményt biztosít.

Tekintsük a kontrollpontokkal adott Bézier-görbét, és legyen adott az pontosság, ami a közelítő egyenes szakaszoknak (a húroknak) az általuk helyettesített ívtől mért távolságának a felső korlátja.

  1. Ha , azaz a görbe zárt, akkor vágjuk ketté a görbét a de Casteljau-algoritmussal a paraméterértéknél, és az így kapott két darab -edfokú Bézier-görbére hajtsuk végre az algoritmus további lépéseit.

  2. Vegyük a és kontrollpontokat összekötő egyenest, és keressük meg a tőle legtávolabb fekvő kontrollpontot. Ennek a távolságát -vel jelöljük.

  3. Ha , akkor a görbét a szakasszal helyettesítjük. Egyébként osszuk fel a görbét a paraméterértéknél a de Casteljau-algoritmussal két -edfokú Bézier-görbére, és mindkét görbére a 2. lépéstől folytassuk a feldolgozást.

Jelöljük -vel a pontok által meghatározott Bézier-görbét, , illetve -el az első felosztás után kapott Bézier-görbéket, , illetve -el a következő felosztás után kapottakat. Ezt az eljárást folytatva egy bináris fát építünk fel, melynek levelein balról jobbra végighaladva, az ott lévő Bézier-görbék kezdő- és végpontját összekötve, az eredeti Bézier-görbét adott pontossággal közelítő töröttvonalat kapjuk.

Ez a módszer konvergens és gyors. A 3. lépésnél tulajdonképpen bármely értéknél kettévághatnánk a görbét, azonban, ha van legtávolabb az egyenestől, akkor ő húzza el tőle leginkább a görbét. Mivel -nek a paraméterértéknél van legnagyobb hatása a görbe alakjára, ezért az algoritmust gyorsítjuk, ha ennél az értéknél vágjuk ketté a görbét.

Ezt az algoritmust célszerű használni a Bézier-görbe kirajzolásához. Ha például pixeles megjelenítőt használunk, akkor az pixel garantáltan sima, folytonos, esztétikus eredményt ad, és mindezt viszonylag kevés egyenes szakasszal éri el, mivel az algoritmus a görbület változását figyelembe véve állítja elő a közelítő töröttvonalat.