Bézier-kurve

De Bezier kurver er kurver polynomisk parametrisk design udviklet til karosseridele af biler . De blev designet af Paul de Casteljau i 1959 for Citroën og uafhængigt af Pierre Bézier i 1962 for Renault (Paul de Casteljaus arbejde var fortroligt, det er navnet på Bézier, der er gået til eftertiden). De har mange anvendelser i billedet syntese og skrifttype rendering . De fødte mange andre matematiske objekter .

Før Bézier var der justeringskurver kaldet splines , men fejlen var at ændre deres udseende under en koordinatrotation, hvilket gjorde dem ubrugelige i CAD . Bézier startede fra en geometrisk tilgang baseret på lineariteten af det euklidiske rum og den allerede eksisterende teori om barycenteret : hvis definitionen er rent geometrisk, griber intet referencepunkt ind, da konstruktionen er uafhængig af den, hvilket ikke var tilfældet for splines ( splines, der overholder Bézier-principperne, vil efterfølgende blive kaldt B-splines ).

Generel teori

Bézier-kurven for de n +1 kontrolpunkter $( P 0 , ..., P n )$ , er det sæt af punkter defineret af parametriske repræsentation , for $t$ $\in [0;$ $1]$ og hvor $B$ ${\ displaystyle P (t) = \ sum _ {i = 0} ^ {n} B_ {i} ^ {n} (t) \ cdot \ mathbf {P} _ {i}}$ $n i$ er Bernstein-polynomierne .

Sekvensen af punkterne $P 0 , ..., P n$ danner " Bézier- kontrolpolygonen ".

Eksempler

For n = 2 er Bernstein-polynomet

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

Derefter tilføjer vi n +1 kontrolpunkterne for hver polynomkoefficient:

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

med $t \in [0; 1]$ . Det er derfor Bézier-kurven for grad 2.

For n = 3 har vi:

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

Derefter tilføjer vi n +1 kontrolpunkterne for hver polynomkoefficient, og vi får,

{\ 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 \in [0; 1]$ . Det er derfor Bézier-kurven for grad 3.

Bemærk Da Bernstein-polynomerne udgør en skillevæg af enhed, har vi gjort det . Summen af koefficienterne er derfor ikke-nul for alle

t

, derfor er alle punkterne

P

(

t

)

i kurven defineret korrekt.

\ sum _ {{i = 0}} ^ {n} B_ {i} ^ {n} (t) = 1

Ejendomme

Kurven er inde i den konvekse konvolut af kontrolpunkterne.
Kurven begynder med punkt $P 0$ og enderne med punkt $P n$ , men ikke a priori aflevering gennem de andre kontrolpunkter, som dog bestemmer den generelle form af kurven.
$\ overrightarrow {P_ {0} P_ {1}}$ er tangent vektor til kurven ved $P 0$ og ved punkt $P$ $n$ . $\ overrightarrow {P _ {{n-1}} P_ {n}}$
En Bézier-kurve er uendelig differentierbar (af klasse ). $C ^ {{\ infty}}$
Bézier-kurven er et segment, hvis og kun hvis kontrolpunkterne er justeret.
Hver begrænsning af en Bézier-kurve er også en Bézier-kurve.
En cirkelbue kan ikke beskrives med en Bézier-kurve, uanset dens grad.
En Bézier-kurve af rækkefølge 2 er et fragment af en parabel, hvis de punkter, der definerer den, ikke er justeret.
Styringen af kurven er global: ændring af et kontrolpunkt ændrer hele kurven og ikke et kvarter af kontrolpunktet.
For at udføre en affin transformation af kurven er det tilstrækkeligt at udføre transformationen på alle kontrolpunkter.

Kubiske Bézier-kurver

Fire punkter P 0 , P 1 , P 2 og P 3 definerer en kubisk Bézier-kurve. Kurven tegnes med start fra punkt P 0 , retning P 1 og ankommer til punkt P 3 i retning P 2- P 3 . Generelt betyder kurven ikke passerer enten gennem P 1 eller via P 2 : disse punkter kun give retningsinformation. Afstanden mellem P 0 og P 1 bestemmer bevægelseshastigheden i retning af P 1, inden den drejes til P 3 .

Fra ovenstående skrives den parametriske form af kurven som en affin kombination af kontrolpunkterne

{\ 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 \leq t \leq 1$ .
Vi kan her tydeligt se delingsegenskaben for enheden af Bernstein-polynomer: ifølge Newtons binomiale formel af rækkefølge 3,

(1-t) ^ {3} + 3t (1-t) ^ {2} + 3t ^ {2} (1-t) + t ^ {3} = [t + (1-t)] ^ {3 } = 1 ^ {3} = 1

Summen af koefficienterne forbundet med kontrolpunkterne er værd 1.

Bézier-kurver er interessante til billedbehandling af to hovedårsager:

Points kan hurtigt beregnes ved hjælp af en rekursiv procedure, der bruger division med to og grundlæggende operationer, der omgår alle operationer med flydende reelt tal-aritmetik.

{\ 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} & {3 \ over 8} & { 3 \ over 8} & {1 \ over 8} \ end {pmatrix}} \ cdot {\ begin {pmatrix} A \\ B \\ C \\ D \ end {pmatrix}}

eller tilsvarende

D \ venstrepil (C + D) / 2

{\ displaystyle C \ leftarrow (B + C) / 2, \ D \ leftarrow (C + D) / 2}

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

Opmærksomhed : i modsætning til anvendelsen i matematik er her punkter (strengere vektorer) og ikke komponenterne i en vektor. Derudover skal de angivne operationer i den anden formulering udføres i rækkefølge fra top til bund, fra venstre mod højre og gentager operationerne, selvom de vises flere gange identisk, dette med de nye værdier på grund af det foregående (matematisk er dette som at nedbryde 4 × 4-matrixen som et produkt af 6 4 × 4-matricer med to 1'er , to ½'er og 0'er overalt). ${\ displaystyle A, B, C, D, A ', B', C ', D'}$

Mere præcist kan vi nedbryde kurven $P ( t )$ i to kurver $P L$ og $P R$ hvis kontrol punkter er henholdsvis $( L 1 , L 2 , L 3 , L 4 )$ og $( R 1 , R 2 , R 3 , R 4 )$ med

${\ begin {pmatrix} L_ {1} '\\ L_ {2}' \\ L_ {3} '\\ L_ {4}' \ end {pmatrix}} = {\ start {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} & {3 \ over 8} & {3 \ over 8} & {1 \ over 8} \ end {pmatrix}} \ cdot {\ begin {pmatrix} A \\ B \\ C \\ D \ end {pmatrix}}$ og ${\ begin {pmatrix} R_ {1} '\\ R_ {2}' \\ R_ {3} '\\ R_ {4}' \ end {pmatrix}} = {\ begynder {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}}$

Under dette rekursive opkald til plot $P ( t )$ , da Bézier-kurven passerer gennem det første og det sidste kontrolpunkt, er placeringen af enderne af hvert stykke kendt $( L 1 , L 4 = R 1 og R 4 )$ kendt. Når en sådan afbildning er implementeret, kan kriteriet til standsning af tilbagefald være knyttet til afstanden mellem sub-kurven, der skal afsættes, og segmentet $[ L 1 , L 4 ]$ f.eks.

Bemærk : Flydende reelt tal-aritmetik er tilgængeligt direkte på moderne processorer, det er blevet meget hurtigere end den hukommelsesallokering, der er nødvendig for en rekursion. Desuden tillader en metode, der tilvejebringer pixelerne i kurven, der skal tegnes uden at gå trin for trin, ikke antialiasing . Rekursion er derfor ikke længere den rigtige metode til at tegne Bézier-kurver; metoden vil med fordel blive anvendt, som krydser pixel trin for trin, mens der ved hvert trin beregnes en "tangentfejl", som kan anvendes til antialiasing .

Beregningen af et punkt i en Bézier-kurve kan også udføres ved hjælp af Horner-metoden ved først at beregne vektorkoefficienterne $a i$ polynomet:

{\ mathbf {a_ {i}}} = {\ begin {pmatrix} m \\ i \ end {pmatrix}} \ sum _ {{j = 0}} ^ {{i}} (- 1) ^ {{ ij}} {\ begin {pmatrix} i \\ j \ end {pmatrix}} {\ mathbf {P_ {j}}} \ qquad {\ mbox {for}} \ qquad i = 0 ... m

Eksempler

Lineær Bézier-kurve (grad 1) Styrepunkterne P 0 og P 1 definerer Bézier kurve givet ved ligningen:

{\ 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 (grad 2) En kvadratisk Bézier-kurve er kurven B ( t ) defineret af kontrolpunkterne P 0 , P 1 og P 2 .

{\ 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 kurver bruges stadig i vid udstrækning i dag (for eksempel i glyf-definitioner af skrifttyper i TrueType- format og OpenType- skrifttyper i deres TrueType-kompatible sort). Men hvis de gør det muligt at sikre kontinuiteten i tangensen af to forbundne kurver, gør de det ikke (generelt) muligt at bevare kontinuiteten i krumningen ved sammenkoblingspunkterne. For at overvinde denne ulempe er det derefter nødvendigt at øge antallet af indbyrdes forbundne buer for at reducere krumningsbrudene mellem hver af dem, hvilket begrænser deres værdi og kan føre til et mere komplekst design af kurverne (med flere hjørner og kontrol peger på position). Kubisk Bézier-kurve (grad 3) En kubisk Bézier kurve er kurven B ( t ) defineret af kontrolpunkterne P 0 , P 1 , P 2, og P 3 . Dens parametriske form er:

{\ 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 de Bézier-kurver, der er mest anvendte i grafisk design (fordi de gør det muligt at sikre ikke kun kontinuiteten i tangens af to tilsluttede kurver, men også deres krumning, samtidig med at man undgår at skulle placere mange hjørner og punkter. Kontrol). De bruges for eksempel i PostScript- sproget og definitionen af glyffer af "type 1" -skrifttyper såvel som i OpenType-skrifttyper i deres sort CFF ( Compact Font Format ), der bruger de samme definitioner af hjørner og kontrolpunkter.

Kubisk Bézier-kurve tilnærmende en cirkelbue For at tegne en Bézier-kurve, der tilnærmer sig 90 ° -buen for en cirkel med radius r , skal du have 4 punkter defineret af 2 segmenter vinkelret på X- og Y-akserne, der passerer gennem midten af cirklen. Længden af hvert segment skal være rk med (se Composite Bézier-kurve (en) ). ${\ displaystyle k: = {\ frac {4 \ left ({\ sqrt {2}} - 1 \ right)} {3}} \ approx 0 {,} 5522847498}$

Bézier-kurve med en grad større end 3 De bruges sjældent. Vi foretrækker at reducere os til brugen af kubiske kurver, der er forbundet for at bevare fordelen ved krumningens kontinuitet. Til dette er det nødvendigt og tilstrækkeligt, at det sidste punkt i en kurve er det første af et andet. Der opnås således en kontinuerlig kurve. For eksempel for en kurve defineret af punkterne A , B , C , D , E , F og G bruger vi de kubiske kurver defineret af A , B , C og D og af D , E , F og G og kontinuitet er således sikret. At have en kurve C 1 i D , vi behøver [ C , D ] = [ D , E ], og hvis der ud vi ønsker at være C 2 i D , derefter [ B , D ] = [ D , F ], og det samme for successive derivater. Men denne transformation mister kontinuitet C 3 i D (og den eneste måde at overvinde dette er at indsætte flere kontrolpunkter (for at øge antallet af kubiske buer for at opnå en bedre tilnærmelse og i det mindste at sikre kontinuitet C 3 i indledende punkter, men ikke omkring de tilføjede kontrolpunkter). Interessen for Bézier-kurver i grad 4 eller mere er dog mere begrænset i dag på grund af fremskridt og integration af understøttelsen af ikke-ensartede B-splines i moderne grafikbiblioteker og især NURBS til rationelle koefficienter svarende til ikke- ensartede B-splines (men med hele vægte i progression ikke nødvendigvis aritmetiske, som det er tilfældet med Bézier-kurver), men disse B-splines beregnes dog først i et projektivt rum med homogene koordinater , og som gør det muligt at bevare alle fordelene af B-splines med grad 3 eller højere, herunder i tilfælde af koniske (ikke-lineære) kurver, som det er umuligt at repræsentere nøjagtigt med andre Bézier-kurver end med en tilnærmelse af et stort antal hjørner og kontrolpunkter.

Ansøgninger

Syntese af billeder

Bézier-kurver udgør det grundlæggende værktøj til vektortegning, der er afhængig af matematisk transkription af objekter. SVG- format ( Scalable Vector Graphics ) giver dig mulighed for at tegne kvadratiske og kubiske Bézier-kurver. Kubiske Bézier-kurver bruges også af følgende vektortegningssoftware:
- I den gratis software JPicEdt er der et værktøj til at oprette og redigere kæder af Bézier-kurver i rækkefølge 3.
- I den gratis software Inkscape .

Kubiske Bézier-kurver, de mest udbredte, findes i grafik og i flere billedsyntese-systemer, såsom PostScript , Metafont og GIMP , til at tegne "glatte" kurver, der forbinder punkter eller Bézier-polygoner.

Bézier-kurver vises i HTML5-kompatible browsere i lærredselementet.
Bézier-kurver vises også i 3D-gengivelsessoftware som Blender .

I matrixtegningssoftwaren , Paint , er det muligt at oprette Bézier-kurver med værktøjet “Curve”. Dette gøres ved at trække en linie fra P 0 til P 3 derefter klikke successivt ved placeringerne af P 1 og P 2 .

Animation

Nogle kubiske Bézier-kurver kan bruges til at definere forløbet af en CSS3-animation eller overgang over tid. Enderne af kurven er foruddefineret i (0; 0) og (1; 1), og abscissas af de to resterende kontrolpunkter skal være mellem 0 og 1.

Gengivelser af skrifttyper

Teksterne er også defineret af Bézier-kurver inden for rammerne af DTP- funktioner såsom komplekst layout , tekstblokstyring, skind .
Skrifttyperne TrueType bruger Bezier-kurver enklere.

Musikalsk gravering

I musikalsk gravering er legato-linjer traditionelt repræsenteret af kubiske Bézier-kurver. Denne metode gør det muligt at gengive både klassiske kurver og dem, mere sjældne, med bøjningspunkter.

Rationel Bézier-kurve

For at beskrive kurver som cirkler meget nøjagtigt (selvom det i praksis er tilnærmelser med Bézier-kurver, der er tilstrækkelige), er der behov for yderligere frihedsgrader.

Ideen er at tilføje vægte til kontrolpunkterne (disse er ). Nævneren er kun der for at normalisere summen af de yderligere vægte, så kurven defineres som en konveks kombination af kontrolpunkterne. $\ omega _ {i}$

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

{\ 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 overflader , Pierre Bézier, Hermès, 1986
Bézier-modeller, B-splines og NURBS , G Demengel, JP Pouget, Éditions Ellipses (Pædagogisk tilgang til at afsløre den sorte boks af disse modeller, der anvendes i CAD til modellering af kurver og overflader.)
Appendiks G af bogen af Yannis Haralambous , Fonts & encodings: Glyffer og tegn i den digitale tidsalder , O'Reilly ,2004, 990 s. ( ISBN 978-2-84177-273-5 )skrifttype: Programmet , Addison-Wesley 1986, s. 123-131. Fremragende diskussion af detaljerne i implementeringen; tilgængelig gratis som en del af TeX-distributionen.

Noter og referencer

(in) "The curve commands" SVG 1.1 (Anden udgave) - 16. august 2011 ( uofficiel fransk oversættelse )

Se også

Relaterede artikler

Spline og B-spline , andre parametriske kurver. De NURBS er en generalisering.
Bézier overflade , generalisering til overflader (dette er den mest nyttige form i CAD ).
De Casteljau-algoritme , der bruges til at vise Bézier-kurver.
Unisurf

eksterne links

Bézier kurver og overflader med implementering På webstedet nonifier.ovh.org
BTS matematik kursus om kurverne på Bézier, Aymar gymnasium i Saint Seine på webstedet http://lyceeenligne.free.fr .

(da) Living Math Bezier-applet På hjemmesiden sunsite.ubc.ca
(da) Bezier Curves-skuffe ved hjælp af C / Opengl På jppanaget.com-siden
(en) Bitmap / Bézier-kurver / Kubiske og (en) Bitmap / Bézier-kurver / Kvadratisk på rosettacode.org-siden
(fr) LECYGN-tegnesoftware, der bruger Bézier-kurver som tegnebaser og som understøtter tekster med konfigurerbar formatering: euraldic.com.
(en) Interaktiv applikation, der illustrerer konstruktionen af en Bézier-kurve
(da) Sådan genereres LaTeX-billedmiljøer ved hjælp af GaPFilL-metoden Konstanten af buen i en cirkel, der bruges af Herbert Möller