Bézier-kurve

De Bezier-kurver er kurvene polynom med parametre utviklet teknisk felt for kroppsdeler fra biler . De ble designet av Paul de Casteljau i 1959 for Citroën, og uavhengig av Pierre Bézier i 1962 for Renault (Paul de Casteljaus verk var konfidensielt, det er navnet Bézier som har gått til ettertiden). De har mange programmer i bildesyntese og skriftgjengivelse . De fødte mange andre matematiske objekter .

Før Bézier var det justeringskurver kalt splines , men feilen var å endre utseendet under en koordinatrotasjon, noe som gjorde dem ubrukelige i CAD . Bézier startet fra en geometrisk tilnærming basert på lineariteten til det euklidiske rommet og den allerede eksisterende teorien om barycenter  : hvis definisjonen er rent geometrisk, griper ikke noe referansepunkt inn siden konstruksjonen er uavhengig av den, noe som ikke var tilfelle for splines ( splines i samsvar med Bézier-prinsippene vil senere bli kalt B-splines ).

Generell teori

Bézier-kurven for n +1 kontrollpunktene ( P 0 , ..., P n ) , er settet med punkter definert av den parametriske representasjonen , for t ∈ [0; 1] og hvor BP(t)=∑Jeg=0ikkeBJegikke(t)⋅PJeg{\ displaystyle P (t) = \ sum _ {i = 0} ^ {n} B_ {i} ^ {n} (t) \ cdot \ mathbf {P} _ {i}}n
ier Bernstein-polynomene .

Punktserien P 0 , ..., P n danner "  Bézier control polygon ".

Eksempler

• For n = 2 er Bernstein-polynomet

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}}

Deretter legger vi til n +1 kontrollpunktene for hver polynomkoeffisient:

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}}

med t ∈ [0; 1] . Det er derfor Bézier-kurven av grad 2.

• For n = 3 har vi:

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}}

Deretter legger vi til n +1 kontrollpunktene for hver polynomkoeffisient, og vi får,

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}}

med t ∈ [0; 1] . Det er derfor Bézier-kurven av grad 3.

Merk Siden Bernstein-polynomene danner en partisjon av enhet, har vi gjort det . Summen av koeffisientene er derfor ikke null for alle t , derfor er alle punktene P ( t ) i kurven riktig definert.∑Jeg=0ikkeBJegikke(t)=1{\ displaystyle \ sum _ {i = 0} ^ {n} B_ {i} ^ {n} (t) = 1}

Eiendommer

• Kurven er inne i den konvekse konvolutten til kontrollpunktene.
• Kurven begynner med punkt P 0 og ender med punktet P n , men ikke a priori pasning gjennom de andre kontrollpunktene, som imidlertid bestemmer den generelle form av kurven.
• P0P1→{\ displaystyle {\ overrightarrow {P_ {0} P_ {1}}}}er tangensvektoren til kurven ved P 0 og ved punktet P n .Pikke-1Pikke→{\ displaystyle {\ overrightarrow {P_ {n-1} P_ {n}}}}
• En Bézier-kurve er uendelig differensierbar (av klasse ).VS∞{\ displaystyle C ^ {\ infty}}
• Bézier-kurven er et segment hvis og bare hvis kontrollpunktene er justert.
• Hver begrensning av en Bézier-kurve er også en Bézier-kurve.
• En sirkelbue kan ikke beskrives av en Bézier-kurve, uavhengig av graden.
• En Bézier-kurve av rekkefølge 2 er et fragment av en parabel hvis punktene som definerer den ikke er justert.
• Kontrollen av kurven er global: endring av et kontrollpunkt endrer hele kurven, og ikke et nabolag for kontrollpunktet.
• For å utføre en affinert transformasjon av kurven, er det tilstrekkelig å utføre transformasjonen på alle kontrollpunktene.

Kubiske Bézier-kurver

Fire punkter P 0 , P 1 , P 2 og P 3 definerer en kubisk Bézier-kurve. Kurven tegnes fra punkt P 0 , retning P 1 og ankommer punkt P 3 i retning P 2- P 3 . Generelt går ikke kurven verken gjennom P 1 eller gjennom P 2  : disse punktene gir bare retningsinformasjon. Avstanden mellom P 0 og P 1 bestemmer bevegelseshastigheten i retning P 1 før du svinger til P 3 .

Fra ovenstående er den parametriske formen på kurven skrevet som en affinert kombinasjon av kontrollpunktene

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}}

for 0 ≤ t ≤ 1 .
Vi kan tydelig se her delingsegenskapen til enheten av Bernstein-polynomer: i henhold til Newtons binomiale formel av ordre 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}

Summen av koeffisientene knyttet til kontrollpunktene er verdt 1.

Bézier-kurver er interessante for bildebehandling av to hovedårsaker:

• Poeng kan raskt beregnes ved hjelp av en rekursiv prosedyre som bruker divisjon av to og grunnleggende operasjoner, og unngår alle operasjonene med flytende punkt-reeltall-aritmetikk.

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

eller tilsvarende

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←(PÅ+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}

Oppmerksomhet  : i motsetning til bruk i matematikk, er her punkter (strengere vektorer) og ikke komponentene i en vektor. I tillegg, i den andre formuleringen, må de angitte operasjonene utføres i rekkefølge, fra topp til bunn, fra venstre til høyre og gjenta operasjonene selv om de vises flere ganger identisk, dette med de nye verdiene på grunn av forrige (matematisk, dette er som å bryte ned 4 × 4-matrisen som et produkt av 6 4 × 4-matriser med to 1-er , to ½-er og 0-er overalt ellers). PÅ,B,VS,D,PÅ′,B′,VS′,D′{\ displaystyle A, B, C, D, A ', B', C ', D'}

Mer presist, kan vi dekomponere kurve P ( t ) inn i to kurver P l og P R hvis styrepunkter er henholdsvis ( L 1 , L 2 , L 3 , l 4 ) og ( R 1 , R 2 , R 3 , R 4 ) med

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

I løpet av dette rekursive anropet til å plotte P ( t ) , siden Bézier-kurven passerer gjennom det første og siste kontrollpunktet, er posisjonen til endene på hvert stykke ( L 1 , L 4 = R 1 og R 4 ) kjent. Når et slikt plott er implementert, kan kriteriet for å stoppe gjentakelsen knyttes til avstanden mellom underkurven som skal plottes og segmentet [ L 1 , L 4 ] for eksempel.

Merk  : Flytende reeltall-aritmetikk er tilgjengelig direkte på moderne prosessorer, det har blitt mye raskere enn minnetildelingen som er nødvendig for en rekursjon. Videre tillater ikke en metode som gir piksler i kurven som skal tegnes uten å gå trinn for trinn, antialiasing . Rekursjon er derfor ikke lenger den riktige metoden for å tegne Bézier-kurver; metoden vil fordelaktig bli brukt som krysser pikslene trinn for trinn, og beregner i hvert trinn en "tangentfeil" som kan brukes til antialiasing .

Beregningen av et punkt i en Bézier-kurve kan også utføres ved hjelp av Horner-metoden ved først å beregne vektorkoeffisientene a i polynomet:

påJeg=(mJeg)∑j=0Jeg(-1)Jeg-j(Jegj)PjtilJeg=0 ...m{\ displaystyle \ mathbf {a_ {i}} = {\ begynn {pmatrix} m \\ i \ end {pmatrix}} \ sum _ {j = 0} ^ {i} (- 1) ^ {ij} {\ begynn {pmatrix} i \\ j \ end {pmatrix}} \ mathbf {P_ {j}} \ qquad {\ mbox {for}} \ qquad i = 0 ... m}

Eksempler

Lineær Bézier-kurve (av grad 1) Kontrollpunktene P 0 og P 1 definerer Bézier-kurven gitt av ligningen: B(t)=P0(1-t)+P1t , t∈[0,1].{\ displaystyle \ mathbf {B} (t) = \ mathbf {P} _ {0} (1-t) + \ mathbf {P} _ {1} t {\ mbox {,}} t \ in [0, 1].} Det er derfor segmentet [P0, P1]. Kvadratisk Bézier-kurve (av grad 2) En kvadratisk Bézier-kurve er kurven B ( t ) definert av kontrollpunktene P 0 , P 1 og 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].} Disse kvadratiske kurvene brukes fortsatt mye i dag (for eksempel i definisjoner av skrifter i TrueType- format og OpenType- skrifter i deres TrueType-kompatible utvalg). Imidlertid, hvis de gjør det mulig å sikre kontinuiteten i tangens av to tilkoblede kurver, gjør de ikke (generelt) det mulig å bevare kontinuiteten i krumningen ved punktene for samtrafikk. For å overvinne denne ulempen er det da nødvendig å øke antall sammenkoblede buer for å redusere krumningsbruddene mellom hver av dem, noe som begrenser verdien og kan føre til en mer kompleks utforming av kurvene (med flere hjørner og kontroll peker på posisjon). Kubisk Bézier-kurve (av grad 3) En kubisk Bézier-kurve er kurven B ( t ) definert av kontrollpunktene P 0 , P 1 , P 2 og P 3 . Dens parametriske form er: 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].} Dette er Bézier-kurvene som er mest brukt i grafisk design (fordi de gjør det mulig å sikre ikke bare kontinuiteten i tangens av to tilkoblede kurver, men også kurvaturen, samtidig som man unngår å måtte plassere mange hjørner og punkter. Kontroll). De brukes for eksempel i PostScript- språket og definisjonen av tegnene for "type 1" -skrifttyper, så vel som i OpenType-skriftene i deres utvalg CFF ( Compact Font Format ) som bruker de samme definisjonene av hjørner og kontrollpunkter.

• Kubisk Bézier-kurve tilnærmet en sirkelbue For å tegne en Bézier-kurve som tilnærmer seg 90 ° buen til en sirkel med radius r , må du ha 4 punkter definert av to segmenter vinkelrett på X- og Y-aksene som går gjennom sentrum av sirkelen. Lengden på hvert segment må være rk med (se Composite Bézier curve (en) ).k: =4(2-1)3≈0,5522847498{\ displaystyle k: = {\ frac {4 \ left ({\ sqrt {2}} - 1 \ right)} {3}} \ approx 0 {,} 5522847498} 

Bézier-kurve av grad større enn 3 De brukes sjelden. Vi foretrekker å redusere oss til bruk av kubiske kurver som er koblet sammen for å bevare fordelen av krumningens kontinuitet. For dette er det nødvendig og tilstrekkelig at det siste punktet i en kurve er det første av en annen. En kontinuerlig kurve oppnås således. For eksempel, for en kurve definert av punktene A , B , C , D , E , F og G , bruker vi de kubiske kurvene definert av A , B , C og D , og av D , E , F og G og kontinuitet er dermed sikret. For å ha en kurve C 1 i D trenger vi [ C , D ] = [ D , E ], og hvis vi i tillegg vil at den skal være C 2 i D , så [ B , D ] = [ D , F ], og det samme for påfølgende derivater. Imidlertid mister denne transformasjonen kontinuiteten C 3 i D (og den eneste måten å løse dette på er å sette inn flere kontrollpunkter (for å øke antall kubikk buer for å oppnå en bedre tilnærmelse og i det minste for å sikre kontinuitet C 3 i innledende poeng, men ikke rundt de ekstra kontrollpunktene). Interessen for Bézier-kurver av grad 4 eller mer er imidlertid mer begrenset i dag på grunn av fremgang og integrering av støtten til ikke-ensartede B-splines i moderne grafikkbiblioteker, og spesielt NURBS , til rasjonelle koeffisienter, tilsvarende ikke- ensartede B-splines (men med hele vekter i progresjon ikke nødvendigvis aritmetiske, slik tilfellet er med Bézier-kurver), men disse B-splines blir imidlertid beregnet først i et prosjektivt rom med koordinater homogene , og som gjør det mulig å beholde alle fordelene av B-splines av grad 3 eller høyere, inkludert når det gjelder koniske (ikke-lineære) kurver som er umulige å representere nøyaktig med Bézier-kurver enn med en tilnærming av et stort antall hjørner og kontrollpunkter.

applikasjoner

Syntese av bilder

• Bézier-kurver utgjør det grunnleggende verktøyet for vektortegning som er avhengig av matematisk transkripsjon av objekter. SVG- formatet ( Scalable Vector Graphics ) lar deg tegne kvadratiske og kubiske Bézier-kurver. Kubiske Bézier-kurver brukes også av følgende vektortegningsprogramvare:
  • I den gratis programvaren JPicEdt er det et verktøy for å lage og redigere kjeder av Bézier-kurver av ordre 3.
  • I den gratis programvaren Inkscape .

• Kubiske Bézier-kurver, de mest brukte, finnes i grafikk og i flere bildesyntesesystemer, for eksempel PostScript , Metafont og GIMP , for å tegne "glatte" kurver som forbinder punkter eller Bézier-polygoner.

• Bézier-kurver vises i HTML5-kompatible nettlesere i lerretelementet.
• Bézier-kurver vises også i 3D-gjengivelsesprogramvare som Blender .

• I matriksetegningsprogrammet , Paint , er det mulig å lage Bézier-kurver med "Curve" -verktøyet. Dette blir gjort ved å trekke en linje fra P 0 til P 3 deretter suksessivt på stedene med P- 1 og P- 2 .

Animasjon

• Noen kubiske Bézier-kurver kan brukes til å definere fremdriften til en CSS3-animasjon eller overgang over tid. Endene på kurven er forhåndsdefinert i (0; 0) og (1; 1), og abscissas av de to gjenværende kontrollpunktene må være mellom 0 og 1.

Gjengivelse av skrift

• Tekstene er også definert av Bézier-kurver innenfor rammene av DTP- funksjonene som kompleks layout , tekstblokkadministrasjon, skins .
• Fontene TrueType bruker Bezier-kurver enklere.

Musikalsk gravering

• I musikalsk gravering er legato-linjer tradisjonelt representert av kubiske Bézier-kurver. Denne metoden gjør det mulig å reprodusere både klassiske kurver og de, mer sjeldne, med bøyepunkter.

Rasjonell Bézier-kurve

For å beskrive kurver som sirkler veldig nøyaktig (selv om det i praksis er tilnærminger med Bézier-kurver, er det behov for ytterligere frihetsgrader.

Ideen er å legge til vekter på kontrollpunktene (disse er ). Nevneren er bare der for å normalisere summen av tilleggsvektene, slik at kurven er definert som en konveks kombinasjon av kontrollpunktene. ωJeg{\ displaystyle \ omega _ {i}}

En rasjonell Bézier-kurve har følgende generelle form:

B(t)=∑Jeg=0ikkeBJegikke(t)ωJegPJeg∑Jeg=0ikkeBJegikke(t)ωJeg{\ 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}}}}

Bibliografi

• Kurver og overflater , Pierre Bézier, Hermès, 1986
• Bézier-modeller, B-splines og NURBS , G Demengel, JP Pouget, Éditions Ellipses (Pedagogisk tilnærming for å avsløre den svarte boksen til disse modellene som brukes i CAD for modellering av kurver og overflater.)
• Vedlegg G til boka av Yannis Haralambous , Fonts & encodings: Glyfer og tegn i den digitale tidsalderen , O'Reilly ,2004, 990  s. ( ISBN  978-2-84177-273-5 )font: Programmet , Addison-Wesley 1986, s. 123-131. Utmerket diskusjon av detaljene i implementeringen; tilgjengelig gratis som en del av TeX-distribusjonen.

Merknader og referanser

1. (in) "The curve commands" SVG 1.1 (Second Edition) - 16. august 2011 ( uoffisiell fransk oversettelse )

Se også

Relaterte artikler

• Spline og B-spline , andre parametriske kurver. De NURBS er en generalisering.
• Bézier overflate , generalisering til overflater (dette er den mest nyttige formen i CAD ).
• De Casteljau-algoritmen , brukt til å vise Bézier-kurver.
• Unisurf

Eksterne linker

• Bézier kurver og overflater med implementering På nettstedet nonifier.ovh.org
• BTS matematikkurs på kurvene til Bézier, Aymar videregående skole i Saint Seine på nettstedet http://lyceeenligne.free.fr .

• (no) Living Math Bezier-applet På nettstedet sunsite.ubc.ca
• (no) Bezier Curves skuff med C / Opengl På jppanaget.com-siden
• (en) Bitmap / Bézier curves / Cubic and (en) Bitmap / Bézier curves / Quadratic on the rosettacode.org site
• (fr) LECYGN-tegningsprogramvare Programvare som bruker Bézier-kurver som tegningsbaser og som støtte for tekster med konfigurerbar formatering: euraldic.com.
• (en) Interaktiv applikasjon som illustrerer konstruksjonen av en Bézier-kurve
• (no) Hvordan lage LaTeX-bildemiljøer ved hjelp av GaPFilL-metoden Konstanten til buen til en sirkel som brukes av Herbert Möller