Bezjeove krive

Oblik Bezjeove krive je definisan skupom od n + 1 kontrolnih tačaka (P₀, P₁,..., P_n), odnosno kontrolnim mnogouglom koji se dobija spajanjem susednih kontrolnih tačaka pravim linijama. Promenom položaja kontrolnih tačaka menja se oblik Bezjeove krive.

Stepen Bezjeove krive je uvek za jedan manji od broja kontrolnih tačaka. Krive mogu imati veliki broj kontrolnih tačaka, ali sa povećanjem njihovog broja raste složenost proračuna. 

Bezjeove krive mogu da budu dvodimenzionalne (2D) ili trodimenzionalne (3D).

Danas se ove krive sreću u raznim vrstama računarskih programa, a najčešće ih možemo sresti u programima za vektorsko crtanje gde služe za crtanje glatkih kontura nepravilnih oblika. Ako se od nacrtanih oblika pravi animacija pomoću njih se mogu crtati putanje kretanja. Zbog svoje jednostavnosti i osobine da skaliranjem ne menjaju oblik, koriste se za crtanje fontova. Bezjeove krive se danas retko sreću u CAD softverima jer su zamenjene naprednijim krivama slobodnog oblika, obično B-splajn ili NURBS krivama.

Bezjeove krive je prvi opisao Pier Bezje (Pierre Étienne Bézier) koji je bio šef razvoja u francuskom proizvođaču automobila Renault. Razvio ih je početkom 60-ih godina prošlog veka (oko 1962 godina) za CAD sistem UNISURF koji je ova kompanija u to vreme razvijala. Nezavisno od njega, nekoliko godina ranije (oko 1959. godine) je Paul de Casteljau osmislio De Casteljau algoritam koji je neka vrsta geometrijske konstrukcije za crtanje Bezjeovih kriva. Na njegovu žalost Citroen je njegov rad proglasio za tajnu tako da su sve zasluge otišle Bezje-u. Više o istoriji kriva slobodnog oblika možete pročitati na strani Istorija površinskog modeliranja.

Na sledećoj slici možete videti primere Bezjeovih kriva.

Bezjeove krive se mogu definisati pomoću De Casteljau algoritma (valjda po Vuku De Kastelžo algoritam) ili pomoću polinomskih funkcija. Probaću da objasnim oba načina, s tima da neću ulaziti suviše duboko u matematiku. Korisnike CAD softvera proračunski deo ove priče baš i ne zanima mnogo, a programeri i matematičari će na osnovu mog objašnjenja veoma lako pronaći opširnija objašnjenja i izvođenja.

Rekurzivna definicija pomoću De Casteljau algoritma

De Casteljau algoritam je u suštini neka vrsta geometrijske konstrukcije koja se zasniva na uzastopnoj primeni linearne interpolacije. Pomoću ovog algoritma je moguće odrediti tačke na Bezjeovoj krivi, odnosno konstruisati Bezjeovu krivu. Velika prednost ovog algoritma je što daje jasnu geometrijsku vizuelizaciju kako se određuju tačke krive.

Pojednostavljeno bi smo De Casteljau algoritam mogli objasniti na sledeći način: Dat je skup kontrolnih tačaka P₀, P₁, P₂,...,P_n na osnovu kojeg je potrebno konstruisati Bezjeovu krivu. Povezivanjem susednih kontrolnih tačaka dobija se kontrolni mnogougao koji nije gladak. Ako na ovom mnogouglu isečemo uglove, dobijamo novi kontrolni mnogougao koji je glatkiji od prethodnog. Ako bi se ovaj postupak ponavljao beskonačno mnogo puta dobila bi se Bezjeova kriva. Na sledećoj slici možete videti ovaj postupak na primeru 5 kontrolnih tačaka.

De Casteljau algoritam se može predstaviti i deljenjem Bezjeove krive na krive istog stepena. Što se više puta kriva deli, njen kontrolni mnogougao će biti sličniji krivi.

Koraci De Casteljau algoritma:

• dat je skup kontrolnih tačaka P₀, P₁, P₂,...,P_n na osnovu kojeg je potrebno konstruisati Bezjeovu krivu. Spajanjem susednih kontrolnih tačaka dobijamo kontrolni mnogougao.

• na svakoj liniji kontrolnog mnogougla određujemo tačke Q proporcionalno vrednosti parametra t t.j. svaka linija kontrolnog mnogougla se deli u istom odnosu t:(1 - t). Promenom parametra od 0 do 1 vrši se linearna interpolacija između tačaka Q susednih segmenata. Ovo je prvi nivo interpolacije.

• kada tačke Q spojimo pravim linijama dobićemo novi kontrolni mnogougao. Broj kontrolnih tačaka ovog mnogougla je za jedan manji od prethodnog.

• na isti način kao tačke Q, na svakoj liniji novog kontrolnog mnogougla određujemo tačke R. Promenom parametra od 0 do 1 vrši se linearna interpolacija između tačaka R. Ovo je sledeći, t.j. drugi nivo interpolacije.

• ovaj postupak se ponavlja dok se ne dobije samo jedna linija kontrolnog mnogougla na kojoj se može odrediti tačka B proporcionalno vrednosti parametra t. Promenom vrednosti prametra t tačka B će opisivati Bezje-ovu krivu.

Ovaj postupak možemo primeniti na:

1. Linearne krive (prave linije) - Parametar t određuje gde se između kontrolnih tačaka P₀ i P₁ nalazi tačka B, odnosno vrednost funkcije B(t). Na primer, pri t = 0,75, vrednost funkcije B(t) odgovara tri četvrtine rastojanja između tačaka P₀ i P₁. Promenom parametra t  od 0 do 1, tačka B(t) će opisati pravu liniju između tačaka P₀ i P₁.

2. Kvadratne krive - Da bi se konstruisale kvadratne Bezijeove krive, potrebno je odrediti međutačke Q₀ i Q₁  tako što linije kontrolnog mnogougla podelimo u odnosu t:(1 - t). 

• U zavisnoti od t, tačka Q₀ se pomera između P₀ i P₁ i opisuje linearnu Bezijeovu krivu (pravu liniju).

• U zavisnoti od t, tačka Q₁ se pomera između P₁ i P₂ i takođe opisuje linearnu Bezijeovu krivu (pravu liniju).

• U zavisnoti od t tačka B se pomera između Q₀ i Q₁ i njena putanja opisuje kvadratnu Bezijeovu krivu.

3. Krive 3 i višeg stepena - Za konstruisanje krivih višeg stepena potrebno je postupak određivanja međutačaka ponavljati n puta. 

• Za kubnu krivu, prvo treba odrediti međutačke Q₀, Q₁ i Q₂ koje opisuju linearne krive, zatim tačke R₀ i R₁ koje opisuju kvadratne krive i na kraju tačku B čija putanja će opisivati kubnu Bezjeovu krivu.

• Za krive četvrtog stepena prvo treba odrediti međutačke Q₀, Q₁, Q₂ i Q₃ koje opisuju linearne krive, zatim tačke R₀, R₁ i R₂ koje opisuju kvadratne krive, zatim tačke tačke S₀ i S₁ koje opisuju kubne Bezjeove krive i na kraju tačku B čija putanja će opisivati Bezjeovu krivu četvrtog stepena.

De Casteljau algoritam je jasan na prvi pogled i nije potrebno mnogo objašnjenja da bi se shvatio. Ovaj algoritam se može opisati i jednačinama na osnovu kojih se mogu proračunati položaji tačke B (oblik Bezjeove krive), ali to je već suviše stručno i nepotrebno za nivo znanja koji nudi ovaj vebsajt.

Proračun Bezjeove krive pomoću polinomskih funkcija (Polinoma)

Bezijeova kriva je polinom stepena n. Ako Bezjeova kriva ima stepen n ona ima n+1 kontrolnih tačaka. Jednostavnije rečeno stepen Bezjeove krive je uvek za jedan manji od broja kontrolnih tačaka.

Neka su date kontrolne tačke P₀, P₁,..., P_n, (n≥1). Duži P₀P₁, P₁P₂,...,P_n-1P_n  su linije kontrolnog mnogougla. Oznaka i je oznaka iteracije, a t je parametar čije se oseg kreće od 0 do 1.

Opšta jednačina Bezjeovih kriva B(t) ima sledeći oblik:

Polinomi b_i,n(t) se zovu Bernštajnovi polinomi i definisani su jednačinom:

gde su Cⁿ_i  binomni koeficijenti:

Ako opštu jednačinu pretvorimo u jednačine za svaku kordinatu x = B_x(t) i y = B_y (t) i ubacimo u njih jednačinu za Bernštajnov polinom dobićemo:

Izvođenjem (koje ću preskočiti) se mogu dobiti jednačine Bernštajnovih polinoma za razne stepene:

b_0,3(t) = (1-t)³

b_1,3(t) = 3t(1-t)²

b_2,3(t) = 3t²(1-t)

b_3,3(t) = t³

Ubacivanjem ovih jednačina u jednačinu za Bezjeove krive dobijamo:

• Za n=1 (2 kontrolne tačke) Bezjeova kriva će imati oblik duži, a kontrolne tačke P₀ i P₁ će biti njena početna i zadnja tačka.

B(t) = (1-t)P₀ + tP₁

• Za n=2 (3 kontrolne tačke) Bezjeova kriva će imati oblik kvadratne krive

B(t) = (1-t)²P₀ + 2t(1-t)P₁ + t²P₂

• Za n=3 (4 kontrolne tačke) Bezjeova kriva će imati oblik kubne krive 

B(t) = (1-t)³P₀ + 3t(1-t)²P₁ + 3t²(1-t)P₂ + t³P₃

Na internetu postoji baš mnogo kvalitetnog materijala o ovim krivama i na raspolaganju su Vam kvalitetna video uputstva, naučni radovi, veb stranice... Veoma lako ćete pronaći stranice koje na pojednostavljeni način CAD korisnicima objašnjavaju osnovu ovih kriva, ali i kvalitetne stranice posvećene matematičarima i programerima.

Osobine Bezjeovih kriva

• Oblik Bezjeove krive kontrolišu njene kontrolne tačke (P₀, P₁, P₂,…,P_n). Promena položaja kontrolnih tačaka promeniće oblik Bezjeove krive. U grafičkim softverima se kontrolne tačke zadaju klikanjem miša po radnoj površini programa.

• Bezjeove krive prolaze kroz prvu P₀ i zadnju P_n kontrolnu tačku. Prvoj tački odgovara parametar t=0, a zadnjoj t=1. Između početne i zadnje tačke se nalaze jedna ili više kontrolnih tačaka kroz koje kriva ne prolazi

• Bezijeove krive ne pružaju lokalnu kontrolu, tj. pomeranje bilo koje kontrolne tačke menja oblik cele krive.

• Spajanjem susednih kontrolnih tačaka dobijamo izlomljenu liniju koja se naziva kontrolni mnogougao. Bezjeove krive prate oblik kontrolnog mnogougla.

• Tangenta u prvoj i zadnjoj tački Bezjeove krive se poklapa sa prvom i zadnjom linijom kontrolnog mnogougla. Drugim rečima pravac tangente u početnoj tački (t = 0) se poklapa sa pravcem prave  linije koja spaja tačke P₀ i P₁, a pravac tangente u zadnjoj tački (t = 1)  se poklapa sa pravcom prave  linije koja spaja tačke P_n-1 i P_n.

• Stepen Bezjeove krive je uvek za jedan manji od broja kontrolnih tačaka. Stepen Bezjeove krive se može menjati dodavanjem ili oduzimanjem kontrolnih tačaka. Povećanje stepena usložnjava numeričke proračune i troši više resursa računara. Problem sa proračunom Bezjeovih kriva sa visokim stepenom se rešava konstruisanjem kriva od glatkih segmenata u obliki Bezjeovih kriva manjeg stepena. Ovakve krive se nazivaju Splajn krive.

• Povećavanjem stepena Bezjeove krive, kriva se približava kontrolnom mnogouglu

• Bezjeova kriva se uvek nalazi unutar konveksnog omotača kontrolnog mnogougla. Konveksni omotač predstavlja najmanji konveksni mnogougao takav da sve kontrolne tačke pripadaju njegovoj unutrašnjosti ili leže na njegovim ivicama. Na sledećoj slici možete videti nekoliko primera Bezjeovih kriva sa njihovim konveksnim omotačima. Konveksni omotač možete sebi slikovito predstaviti ako zamislite da su u kontrolne tačke zabijeni ekseri, a oko njih je rastegnuta gumica tako da obuhvati sve eksere. Svojstvo da se Bezjeove krive nalaze unutar konveksnog omotača je izuzetno korisno jer garantuje da će se kriva nalaziti unutar područia koje je lako matematički odrediti što pojednostavljuje rad mnogih algoritama u CAD/CAM softverima.

• Nijedna prava linija ne seče Bezjeovu krivu više puta nego što seče kontrolni mnogougao. Ovo nam govori da je oblik kontrolnog mnogougla uvek složeniji od krive koju određuje.

• Zatvorena Bezijeova kriva se može konstruisati tako što se prva i poslednja kontrolna tačka poklope.

• Bezijerove krive su afino invarijantne. Drugim rečima, kriva ne menja oblik ako se sve njene kontrolne tačke transliraju ili rotiraju. Ovo je veoma korisna osobina jer umesto tranformacije Bezjeove krive, dovoljno je trasformisati njene kontrolne tačke što je u suštini veoma lako.

• Bezjeove krive nisu projektivno invarijantne.

• Ako su kontrolne tačke Bezjeove krive kolinearne ili ih ima samo dve, kriva će imati oblik prave linije.

• Bezjeova kriva se može podeliti na proizvoljno mnogo segmenata od kojih je svaki Bezjeova kriva. Na sledećoj slici možete videti primer podele na krive istog stepena pomoću tangente. Ova osobina je osnova De Casteljau algoritma. Deljenjem Bezjeove krive kontrolni mnogougao konvergira obliku krive. Iz ove osobine sledi da je jedan od načina konstruisanja Bezjeove krive njena podela određeni broj puta.

• Pošto su Bezjeove krive polinomske funkcije, one se lako izračunavaju i beskonačno su diferencijabilne. 

• Bezijeove krive su parametarske krive koje koriste Bernštajnove polinome kao osnovu.

• Kvadratne Bezjeove krive su delovi parabole. Za predstavljanje kružnice, elipse ili hiperbole potrebna je kubna Bezjeova kriva.

• Nije moguće da dve Bezjeove krive imaju isti oblik, a različite položaje kontrolnih tačaka.

Bezjeove splajn krive

Bezjeove krive imaju dve veoma problematične osobine koje ih čine nepodobnim za korišćenje u CAD programima. Prva je da se sa povećanjem broja kontrolnih tačaka povećava stepen krive što usložnjava proraračune, a druga je nemogućnost promene oblika samo na nekom delu krive (lokalno). Rešenje je pronađeno u upotrebi splajn kriva.

Bezjeove splajn krive su vrsta kriva slobodnog oblika koje se sastoje od delova, odnosno međusobno spojenih segmenata (raspona) Bezjeovih kriva manjeg stepena. Da bi kriva bila glatka u krajnjim tačkama raspona su zadovoljeni uslovi kontinuiteta. Drugim rečima kriva se sastoji od više jednostavnijih kriva, a da bi one ostajale glatke, odnosno ponašale se kao jedna kriva, na njihovim spojevima se poštuje neki od kontinuiteta.

Racionalne Bezjeove krive

Bezjeove krive su polinomijalne krive te su afino invarijantne, ali ne i projektivno invarijantne. Ovo je glavni razlog zašto je uvedena nova vrsta Bezjeovih kriva koja ispunjava ovaj uslov, a to su racionalne Bezjeove krive.

Za date n+1 kontrolne tačke (P₀, P₁,...P_n) jednačina koja opisuje racionalne Bezjeove krive izgleda na sledeći način:

gde su tačke P_i kontrolne tačke, brojevi ω_i su težine, a b_i,n Bernštajnovi polinomi.

Za racionalne Bezjeove krive je bitno napomenuti da se kod njih mogu menjati težine kontrolnih tačaka. Težina omogućava dodatnu kontrolu oblika krive, tako da je sa njima moguće opisati konusne preseke. Sa druge strane proračun racionalnih Bezjeovih kriva zahteva više resursa računara.

Ne bi da zalazim dublje u ovu problematiku, spomenuo sam ovu vrstu kriva samo da nagovestim šta znači slovo R u skraćenici NURBS. Svako koga ovo zanima dublje verovatno zna matematiku bolje od mene i sigurno je više nego sposoban da samostalno nađe više materijala koji obrađuju ovu tematiku.