Bézierova křivka

Tyto Bézierovy křivky jsou křivky polynom parametrický design, vyvinutý pro části těla automobilů . Navrhl je Paul de Casteljau v roce 1959 pro Citroën a samostatně Pierre Bézier v roce 1962 pro Renault (práce Paula de Casteljau byla důvěrná, jméno Bézier přešlo na potomky). Mají mnoho aplikací v syntéze obrázků a vykreslování písem . Porodili mnoho dalších matematických objektů .

Před Bézierem existovaly korekční křivky zvané splajny , ale vadou bylo změnit jejich vzhled během rotace souřadnic, což je v CADu zneužilo . Bézierova začal z geometrického přístup založený na linearitu z euklidovském prostoru a již existující teorie barycenter  : v případě, že definice je čistě geometrické, žádné referenční bod zasahuje od konstrukce je nezávislá na tom, který nebyl není případ drážek ( splajny splňující Bézierovy principy budou následně nazývány B-splajny ).

Obecná teorie

Bézierova křivka pro kontrolní body n +1 ( P 0 , ..., P n ) je množina bodů definovaná parametrickou reprezentací , pro t ∈ [0; 1] a kde BP(t)=∑i=0neBine(t)⋅Pi{\ displaystyle P (t) = \ součet _ {i = 0} ^ {n} B_ {i} ^ {n} (t) \ cdot \ mathbf {P} _ {i}}n
ijsou Bernsteinovy ​​polynomy .

Posloupnost bodů P 0 , ..., P n tvoří „  Bézierův kontrolní polygon “.

Příklady

• Pro n = 2 je Bernsteinův polynom

12=(1-t+t)2=((1-t)+t)2=(1-t)2+2(1-t)t+t2{\ displaystyle 1 ^ {2} = (1-t + t) ^ {2} = ((1-t) + t) ^ {2} = (1-t) ^ {2} +2 (1-t ) t + t ^ {2}}

Potom přidáme kontrolní body n +1 pro každý koeficient polynomu:

P(t)=(1-t)2P0+2(1-t)tP1+t2P2{\ displaystyle P (t) = (1-t) ^ {2} \ mathbf {P} _ {0} +2 (1-t) t \ mathbf {P} _ {1} + t ^ {2} \ mathbf {P} _ {2}}

s t ∈ [0; 1] . Jedná se tedy o Bézierovu křivku stupně 2.

• Pro n = 3 máme:

13=(1-t+t)3=((1-t)+t)3=(1-t)3+3(1-t)2t+3(1-t)t2+t3{\ displaystyle 1 ^ {3} = (1-t + t) ^ {3} = ((1-t) + t) ^ {3} = (1-t) ^ {3} +3 (1-t ) ^ {2} t + 3 (1-t) t ^ {2} + t ^ {3}}

Potom přidáme kontrolní body n +1 pro každý koeficient polynomu a získáme,

P(t)=(1-t)3P0+3(1-t)2tP1+3(1-t)t2P2+t3P3{\ displaystyle P (t) = (1-t) ^ {3} \ mathbf {P} _ {0} +3 (1-t) ^ {2} t \ mathbf {P} _ {1} +3 ( 1-t) t ^ {2} \ mathbf {P} _ {2} + t ^ {3} \ mathbf {P} _ {3}}

s t ∈ [0; 1] . Jedná se tedy o Bézierovu křivku stupně 3.

Poznámka Protože Bernsteinovy ​​polynomy tvoří rozdělení jednoty, máme . Součet koeficientů je tedy nenulový pro všechna t , proto jsou správně definovány všechny body P ( t ) křivky.∑i=0neBine(t)=1{\ displaystyle \ sum _ {i = 0} ^ {n} B_ {i} ^ {n} (t) = 1}

Vlastnosti

• Křivka je uvnitř konvexní obálky kontrolních bodů.
• Křivka začíná bodem P 0 a končí bodem P n , ale a priori neprochází dalšími kontrolními body, které však určují obecný tvar křivky.
• P0P1→{\ displaystyle {\ overrightarrow {P_ {0} P_ {1}}}}je tečný vektor ke křivce v P 0 a v bodě P n .Pne-1Pne→{\ displaystyle {\ overrightarrow {P_ {n-1} P_ {n}}}}
• Bézierova křivka je nekonečně diferencovatelná (třídy ).VS∞{\ displaystyle C ^ {\ infty}}
• Bézierova křivka je segment právě tehdy, jsou-li kontrolní body zarovnány.
• Každé omezení Bézierovy křivky je také Bézierovou křivkou.
• Kruhový oblouk nemůže být popsán Bézierovy křivky, bez ohledu na jeho stupeň.
• Bézierova křivka řádu 2 je fragment paraboly, pokud body, které ji definují, nejsou zarovnány.
• Ovládání křivky je globální: úpravou kontrolního bodu se upraví celá křivka, nikoli sousedství kontrolního bodu.
• Chcete-li provést afinní transformaci křivky, stačí provést transformaci ve všech řídicích bodech.

Kubické Bézierovy křivky

Čtyři body P 0 , P 1 , P 2 a P 3 definují kubickou Bézierovu křivku. Křivka je nakreslena počínaje od bodu P 0 , směřujícího k P 1 a přicházejícího do bodu P 3 ve směru P 2 - P 3 . Křivka obecně neprochází ani P 1, ani P 2  : tyto body poskytují pouze informace o směru. Vzdálenost mezi P 0 a P 1 určuje rychlost pohybu ve směru P 1 před otočením na P 3 .

Z výše uvedeného je parametrický tvar křivky zapsán jako afinní kombinace kontrolních bodů

P(t)=P0(1-t)3+3P1t(1-t)2+3P2t2(1-t)+P3t3{\ displaystyle \ mathbf {P} (t) = \ mathbf {P} _ {0} (1-t) ^ {3} +3 \ mathbf {P} _ {1} t (1-t) ^ {2 } +3 \ mathbf {P} _ {2} t ^ {2} (1-t) + \ mathbf {P} _ {3} t ^ {3}}

pro 0 ≤ t ≤ 1 .
Můžeme zde jasně vidět vlastnost rozdělení jednotky Bernsteinových polynomů: podle Newtonova binomického vzorce řádu 3,

(1-t)3+3t(1-t)2+3t2(1-t)+t3=[t+(1-t)]3=13=1{\ displaystyle (1-t) ^ {3} + 3t (1-t) ^ {2} + 3t ^ {2} (1-t) + t ^ {3} = [t + (1-t)] ^ {3} = 1 ^ {3} = 1}

Součet koeficientů spojených s kontrolními body má hodnotu 1.

Bézierovy křivky jsou pro zpracování obrazu zajímavé ze dvou hlavních důvodů:

• Body lze rychle vypočítat pomocí rekurzivní procedury, která používá dělení dvěma a základní operace obchází všechny operace plovoucí aritmetiky reálného čísla.

(NA′B′VS′D′)=(1000121200142414018383818)⋅(NABVSD){\ displaystyle {\ begin {pmatrix} A '\\ B' \\ C '\\ D' \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 & 0 & 0 \\ {1 \ nad 2 } & {1 \ nad 2} & 0 & 0 \\ {1 \ nad 4} & {2 \ nad 4} & {1 \ nad 4} & 0 \\ {1 \ nad 8} & {3 \ nad 8 } & {3 \ over 8} & {1 \ over 8} \ end {pmatrix}} \ cdot {\ begin {pmatrix} A \\ B \\ C \\ D \ end {pmatrix}}}

nebo ekvivalent

D←(VS+D)/2{\ displaystyle D \ leftarrow (C + D) / 2}, VS←(B+VS)/2, D←(VS+D)/2{\ displaystyle C \ leftarrow (B + C) / 2, \ D \ leftarrow (C + D) / 2}, B′: =B←(NA+B)/2, VS′: =VS←(B+VS)/2, D′: =D←(VS+D)/2{\ displaystyle B ': = B \ leftarrow (A + B) / 2, \ C': = C \ leftarrow (B + C) / 2, \ D ': = D \ leftarrow (C + D) / 2}

Pozor  : na rozdíl od použití v matematice jsou zde body (přesněji vektory) a ne komponenty vektoru. Kromě toho ve druhé formulaci musí být uvedené operace provedeny v pořadí, shora dolů, zleva doprava a opakovat operace, i když se objeví několikrát shodně, to s novými hodnotami kvůli předchozímu operace. (matematicky je to jako rozbití matice 4 × 4 jako součin 6 matic 4 × 4 se dvěma jinde 1 , 2 ½ a 0 všude jinde). NA,B,VS,D,NA′,B′,VS′,D′{\ displaystyle A, B, C, D, A ', B', C ', D'}

Přesněji můžeme křivku P ( t ) rozložit na dvě křivky P L a P R, jejichž kontrolní body jsou příslušně ( L 1 , L 2 , L 3 , L 4 ) a ( R 1 , R 2 , R 3 , R 4 ) s

(L1′L2′L3′L4′)=(1000121200142414018383818)⋅(NABVSD){\ displaystyle {\ begin {pmatrix} L_ {1} '\\ L_ {2}' \\ L_ {3} '\\ L_ {4}' \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 a 0 a 0 \ \ {1 \ nad 2} a {1 \ nad 2} a 0 a 0 \\ {1 \ nad 4} a {2 \ nad 4} a {1 \ nad 4} & 0 \\ {1 \ nad 8} & {3 \ nad 8} & {3 \ nad 8} & {1 \ nad 8} \ konec {pmatrix}} \ cdot {\ begin {pmatrix} A \\ B \\ C \\ D \ end {pmatrix}}} a (R1′R2′R3′R4′)=(1838381801424140012120001)⋅(NABVSD){\ displaystyle {\ begin {pmatrix} R_ {1} '\\ R_ {2}' \\ R_ {3} '\\ R_ {4}' \ end {pmatrix}} = {\ begin {pmatrix} {1 \ nad 8} & {3 \ nad 8} & {3 \ nad 8} & {1 \ nad 8} \\ 0 & {1 \ nad 4} & {2 \ nad 4} & {1 \ nad 4} \ \ 0 & 0 & {1 \ nad 2} & {1 \ nad 2} \\ 0 & 0 & 0 & 1 \ end {pmatrix}} \ cdot {\ begin {pmatrix} A \\ B \\ C \\ D \ end {pmatrix}}}

Během tohoto rekurzivního volání vykreslení P ( t ) , protože Bézierova křivka prochází prvním a posledním kontrolním bodem, je známa poloha konců každého kusu ( L 1 , L 4 = R 1 a R 4 ) . Když je takový graf implementován, může být kritérium pro zastavení opakování spojeno se vzdáleností mezi dílčí křivkou, která má být vynesena, a segmentem [ L 1 , L 4 ] .

Poznámka  : Plovoucí aritmetika reálného čísla, která je k dispozici přímo na moderních procesorech, se stala mnohem rychlejší než alokace paměti potřebná pro rekurzi. Metoda, která poskytuje pixely křivky, které se mají vykreslit, aniž by postupovala krok za krokem, navíc neumožňuje vyhlazování . Rekurze proto již není správnou metodou k vykreslení Bézierových křivek; výhodně se použije metoda, která prochází pixely krok za krokem, zatímco v každém kroku vypočítává „tečnou vadu“, kterou lze použít pro vyhlazování .

Výpočet bodu Bézierovy křivky lze také provést pomocí Hornerovy metody nejprve výpočtem vektorových koeficientů a i polynomu:

nai=(mi)∑j=0i(-1)i-j(ij)Pjproi=0 ...m{\ displaystyle \ mathbf {a_ {i}} = {\ začátek {pmatrix} m \\ i \ konec {pmatrix}} \ součet _ {j = 0} ^ {i} (- 1) ^ {ij} {\ začátek {pmatrix} i \\ j \ konec {pmatrix}} \ mathbf {P_ {j}} \ qquad {\ mbox {for}} \ qquad i = 0 ... m}

Příklady

Lineární Bézierova křivka (stupně 1) Kontrolní body P 0 a P 1 definují Bézierovu křivku danou rovnicí: B(t)=P0(1-t)+P1t , t∈[0,1].{\ displaystyle \ mathbf {B} (t) = \ mathbf {P} _ {0} (1-t) + \ mathbf {P} _ {1} t {\ mbox {,}} t \ v [0, 1].} Jedná se tedy o segment [P0, P1]. Kvadratická Bézierova křivka (stupně 2) Kvadratická Bézierova křivka je křivka B ( t ) definovaná kontrolními body P 0 , P 1 a P 2 . B(t)=P0(1-t)2+2P1t(1-t)+P2t2 , t∈[0,1].{\ displaystyle \ mathbf {B} (t) = \ mathbf {P} _ {0} (1-t) ^ {2} +2 \ mathbf {P} _ {1} t (1-t) + \ mathbf {P} _ {2} t ^ {2} {\ mbox {,}} t \ in [0,1].} Tyto kvadratické křivky jsou dnes široce používány (například v definicích glyfů písem ve formátu TrueType a písem OpenType v jejich odrůdě kompatibilní s TrueType). Pokud však umožňují zajistit kontinuitu v tečnosti dvou spojených křivek, neumožňují (obecně) zachovat kontinuitu zakřivení v bodech propojení. K překonání této nevýhody je pak nutné zvýšit počet vzájemně propojených oblouků, aby se snížily zlomy zakřivení mezi každým z nich, což omezuje jejich hodnotu a může vést ke složitějšímu návrhu křivek (s více vrcholy a kontrolou body do polohy). Kubická Bézierova křivka (stupně 3) Kubická Bézierova křivka je křivka B ( t ) definovaná kontrolními body P 0 , P 1 , P 2 a P 3 . Jeho parametrická forma je: B(t)=P0(1-t)3+3P1t(1-t)2+3P2t2(1-t)+P3t3 , t∈[0,1].{\ displaystyle \ mathbf {B} (t) = \ mathbf {P} _ {0} (1-t) ^ {3} +3 \ mathbf {P} _ {1} t (1-t) ^ {2 } +3 \ mathbf {P} _ {2} t ^ {2} (1-t) + \ mathbf {P} _ {3} t ^ {3} {\ mbox {,}} t \ in [0, 1].} Toto jsou Bézierovy křivky nejpoužívanější v grafickém designu (protože umožňují zajistit nejen kontinuitu v tečnosti dvou spojených křivek, ale také kontinuitu jejich zakřivení, aniž by bylo nutné umisťovat mnoho vrcholů a bodů. Ovládání). Používají se například v jazyce PostScript a při definici glyfů písem typu „typ 1“, stejně jako u písem OpenType v jejich rozmanitosti CFF ( Compact Font Format ), která používá stejné definice vrcholů a řídicích bodů.

• Kubická Bézierova křivka přibližující oblouk kruhu Chcete-li nakreslit Bézierovu křivku přibližující se 90 ° oblouku kružnice o poloměru r , musíte mít 4 body definované 2 segmenty kolmými na osy X a Y procházející středem kružnice. Délka každého segmentu musí být rk s (viz Složená Bézierova křivka (cs) ).k: =4(2-1)3≈0,5522847498{\ displaystyle k: = {\ frac {4 \ vlevo ({\ sqrt {2}} - 1 \ vpravo)} {3}} \ přibližně 0 {,} 5522847498} 

Bézierova křivka stupně větší než 3 Jsou zřídka používány. Raději se omezujeme na použití kubických křivek, které jsou spojeny, aby se zachovala výhoda kontinuity zakřivení. K tomu je nutné a dostačující, aby poslední bod křivky byl prvním z ostatních. Takto se získá spojitá křivka. Například pro křivku definovanou body A , B , C , D , E , F a G použijeme kubické křivky definované A , B , C a D a D , E , F a G a je tak zajištěna kontinuita. Abychom měli křivku C 1 v D , potřebujeme [ C , D ] = [ D , E ], a pokud navíc chceme, aby to byla C 2 v D , pak [ B , D ] = [ D , F ], a totéž pro následné deriváty. Tato transformace však ztrácí kontinuitu C 3 v D (a jediný způsob, jak to překonat, je vložit další kontrolní body (aby se zvýšil počet kubických oblouků, aby se dosáhlo lepší aproximace a alespoň aby ​​se zajistila kontinuita C 3 v počáteční body, ale ne kolem přidaných kontrolních bodů). Zájem Bézierových křivek stupně 4 a více je však dnes omezenější z důvodu pokroku a integrace podpory nejednotných B-splajnů v moderních grafických knihovnách, zejména NURBS , na racionální koeficienty, ekvivalentní uniformní B-splajny (ale s celou váhou v průběhu nemusí být nutně aritmetické, jako je tomu u Bézierových křivek), tyto B-splajny se však počítají nejprve v projektivním prostoru s homogenními souřadnicemi , což umožňuje zachovat všechny výhody B-splajnů stupně 3 nebo vyššího, a to i v případě kónických (nelineárních) křivek, které nelze přesně reprezentovat jinými Bézierovými křivkami než aproximací velkým počtem vrcholů a řídicích bodů.

Aplikace

Syntéza obrázků

• Bézierovy křivky tvoří základní nástroj vektorového kreslení, který se opírá o matematický přepis objektů. Formát Scalable Vector Graphics (SVG) umožňuje kreslit kvadratické a kubické Bézierovy křivky. Kubické Bézierovy křivky používá také následující software pro vektorové kreslení:
  • Ve svobodném softwaru JPicEdt existuje nástroj pro vytváření a úpravy řetězců Bézierových křivek řádu 3.
  • Ve svobodném softwaru Inkscape .

• Nejpoužívanější kubické Bézierovy křivky se nacházejí v grafice a v různých systémech syntézy obrázků, jako jsou PostScript , Metafont a GIMP , pro kreslení „hladkých“ křivek spojujících body nebo Bézierovy polygony.

• Bézierovy křivky se objevují v prohlížečích kompatibilních s HTML5 v prvku plátna.
• Bézierovy křivky se také objevují ve 3D renderovacím softwaru, jako je Blender .

• V tažení maticového softwaru , barva , je možné vytvářet Bézierových křivek s „Curve“ nástroj. To se provádí nakreslením čáry od P 0 do P 3 a následným kliknutím v místech P 1 a P 2 .

Animace

• Některé kubické Bézierovy křivky lze použít k definování průběhu animace CSS3 nebo přechodu v čase. Konce křivky jsou předdefinovány v (0; 0) a (1; 1) a úsečky dvou zbývajících řídicích bodů musí být mezi 0 a 1.

Vykreslování písem

• Texty jsou také definovány Bézierovými křivkami v rámci funkcí DTP, jako je komplexní rozložení , správa textových bloků, skiny .
• Písma TrueType používají Bézierovy křivky jednodušší.

Hudební rytina

• V hudební rytině jsou legato linky tradičně reprezentovány kubickými Bézierovými křivkami. Tato metoda umožňuje reprodukovat jak klasické křivky, tak ty vzácnější s inflexními body.

Racionální Bézierova křivka

Abychom velmi přesně popsali křivky jako kruhy (i když v praxi jsou aproximace pomocí Bézierových křivek dostatečné), jsou zapotřebí další stupně volnosti.

Myšlenkou je přidání závaží do kontrolních bodů (to jsou ). Jmenovatel je zde pouze k normalizaci součtu přídavných vah, takže křivka je definována jako konvexní kombinace kontrolních bodů. ωi{\ displaystyle \ omega _ {i}}

Racionální Bézierova křivka má následující obecnou podobu:

B(t)=∑i=0neBine(t)ωiPi∑i=0neBine(t)ωi{\ displaystyle \ mathbf {B} (t) = {\ dfrac {\ displaystyle \ sum _ {i = 0} ^ {n} B_ {i} ^ {n} (t) \ omega _ {i} \ mathbf { P} _ {i}} {\ displaystyle \ sum _ {i = 0} ^ {n} B_ {i} ^ {n} (t) \ omega _ {i}}}}

Bibliografie

• Křivky a povrchy , Pierre Bézier, Hermès, 1986
• Bézierovy modely, B-splajny a NURBS , G Demengel, JP Pouget, Éditions Ellipses (Vzdělávací přístup k odhalení černé skříňky těchto modelů používaných v CAD pro modelování křivek a povrchů.)
• Příloha G knihy Yannisa Haralambouse , Fonty a kódování: Glyfy a postavy v digitálním věku , O'Reilly ,2004, 990  s. ( ISBN  978-2-84177-273-5 )písmo: Program , Addison-Wesley 1986, str. 123-131. Vynikající diskuse o podrobnostech implementace; k dispozici zdarma jako součást distribuce TeX.

Poznámky a odkazy

1. (in) „The curve commands“ SVG 1.1 (druhé vydání) - 16. srpna 2011 ( neoficiální francouzský překlad )

Podívejte se také

Související články

• Spline a B-spline , další parametrické křivky. Tyto NURBS jsou zobecnění.
• Bézierův povrch , zobecnění na povrchy (toto je nejužitečnější forma v CAD ).
• Algoritmus De Casteljau , který se používá k zobrazení Bézierových křivek.
• Unisurf

externí odkazy

• Bézierovy křivky a plochy s implementací Na webu nonifier.ovh.org
• Kurz matematiky BTS na křivkách střední školy Bézier, Aymar v Saint Seine na webu http://lyceeenligne.free.fr .

• (en) Living Math Bezier applet Na webových stránkách sunsite.ubc.ca
• (en) Zásuvka Bezierovy křivky pomocí C / Opengl Na webu jppanaget.com
• (en) Bitmapové / Bézierovy křivky / Kubické a (en) Bitmapové / Bézierovy křivky / Kvadratické na webu rosettacode.org
• (fr) LECYGN software pro kreslení Software využívající Bézierovy křivky jako základny pro kreslení a jako podporu textů s konfigurovatelným formátováním: euraldic.com.
• (en) Interaktivní aplikace ilustrující konstrukci Bézierovy křivky
• (en) Jak generovat obrazová prostředí LaTeX pomocí metody GaPFilL Konstanta kruhového oblouku používaná Herbertem Möllerem