Cours GPA445 Conception assistée par ordinateur Courbes complexes Par Antoine Brière-Côté, ing.jr, M.Ing. Génie de la production automatisée École de technologie

Cours GPA445

Conception assistée par ordinateur

Courbes complexes

Par Antoine Brière-Côté, ing.jr, M.Ing.Génie de la production automatisée

École de technologie supérieureadapté de Louis Rivest, ing., Ph.D.et de Roland Maranzana, Dr.Ing.

Été 2013

GPA445 - Conception Assistée par OrdinateurÉcole de technologie supérieure

Courbes complexes 2

Thèmes abordés• Rappel sur la représentation paramétrique• Points-clés et contraintes• Interpolation et approximation• Courbes polynomiales cubiques

• Interpolation de Lagrange• Interpolation de Hermite

• Courbes de Bézier• Algorithme de De Casteljau

• Courbe Spline• Courbe B-Spline (aperçu)

Chapitre 7notes de cours

©A.B.Côté, adapté de L.Rivest & R.Maranzana


• Forme paramétrique générale d’une courbe en 3D:

où x(u), y(u) et z(u) sont les composants de chaque point de la courbe évaluée en u dans l’intervalle [u0,u1].

• Forme réduite en 2D:

• Figure:a, b, c et d, des valeurs discrètes du paramètre u telles que

u0 < a < b < c < d < u1.

Courbes complexes 3

Représentation paramétrique


0 1( ) ( ) ( ) ( ) , ,u x u y u z u u u u P

0 1( ) ( ) ( ) , ,u x u y u u u u P

y

x

0( )uP ( )aP

1( )uP

( )bP

( )cP

( )dP

( )uP


0'( )uP

'( )aP'( )bP

'( )cP'( )dP

1'( )uP

• La dérivé première en u d’une courbe paramétrique donne l’ensemble des vecteurs tangents:

où x’(u), y’(u) et z’(u) sont les composants de chaque vecteurs tangents de la courbe évaluée en u dans l’intervalle [u0,u1].

Courbes complexes 4

Représentation paramétrique


0 1'( ) = '( ) '( ) '( ) , ,dx dy dz

u x u y u z u u u udu du du

P

y

x

0'( )uP

( )uP

'( )aP

'( )bP

'( )cP

'( )dP

1'( )uP


Courbes polynomiales• Les courbes analytiques sont insuffisantes pour répondre

aux exigences de conception géométrique des pièces mécaniques:• Carrosseries de voitures,• Coques de navire,• Fuselages et ailes d’aéronefs,

• On doit avoir recours aux courbes complexes ou « synthétiques » lorsqu’une courbe est d’abord représenté par une collection de points de contrôle.

• Objectif: construire une courbe lisse qui interpole ou approxime un ensemble ordonné de points de contrôle.


Courbes complexes 5

• Pales d’hélices,• Semelles de chaussures,• Bouteilles de toute sorte, etc.


Courbes polynomiales• La forme générale d’équation paramétrique des courbes

complexes est la forme polynomiale:

• ai sont des vecteurs de coefficients…• … de dimension 2 pour une courbe dans l’espace 2D,• … de dimension 3 pour une courbe dans l’espace 3D;

• ui sont les fonctions de base, définies sur un domaine limité;

• Une équation polynomiale de degré n (degré du monôme le plus élevé) représente une courbe de degré n.


Courbes complexes 6

20 1 2 0 1

0

( ) ... avec ,n

i ni n

i

P u a u a a u a u a u u u u


• Une courbe unique de degré n permet d’interpoler ou d’approximer n + 1 points de contrôle;

• Exemple: L’interpolation de 2 points donne une droite, représentée par un polynôme de degré 1;

Courbes polynomiales


Courbes complexes 7

y

x

0P

1P

1

0

0 1

0 1 0

( ) avec 0,1ii

i

P u a u u

a a u

P P P u


Courbes polynomiales• Pour construire une courbe à l’aide d’un ensemble

ordonné de N points de contrôle, on peut…• Construire une seule courbe utilisant tous les points; le degré de

la courbe est donc dépendant du nombre de points (N – 1).• Construire plusieurs segments consécutifs de courbes de degré

imposé n utilisant chacun un sous-ensemble de n + 1 points de contrôle.


Courbes complexes 8

0P

1P

4P

2P

3P

( )uP

1( )uQ

Courbe unique Courbe par segments

2( )uQ

3( )uQ

4 ( )uQ

0P

1P

4P

2P

3P


Courbes polynomiales• Les courbes (polynômes) de degré élevé ne sont

habituellement pas utilisés en CAO, car:• Elles ont tendance à osciller de manière indésirable au voisinage

des points de contrôle;• Elles accaparent énormément de ressources de calcul d’un

ordinateur;• Leurs représentations internes n’est pas concise; i.e., occupent

inutilement beaucoup d’espace mémoire.

• En CAO, on utilise la définition de courbes par morceaux à l’aide de segments des courbes polynomiales de degré 3.


Courbes complexes 9


• Exemple: Construction d'une courbe par des arcs de cercle

• C'est le principe des courbes définies par morceaux;• Des conditions de tangence donne une pente continue et

dérivable en tout point;• Cette méthode est utilisée pour définir des trajectoires d'outils

en fabrication assistée par ordinateur (FAO).

Courbes polynomiales


Courbes complexes 10


Ordre de continuité des courbes• Différentes exigences de continuité des profils peuvent

être spécifiées dans la conception des pièces mécaniques:• Aérodynamisme d’un fuselage ou d’une aile;• Fluidité de mouvement d’un galet parcourant une came; etc.



http://img136.imageshack.us/img136/4224/fokkerdr1pre05ah1.jpg

https://upload.wikimedia.org/wikipedia/commons/d/d3/Came1.gif


Ordre de continuité des courbes• L’ordre de continuité prend de l’importance lorsque les

courbes complexes sont définies par segments;

• Le plus petit ordre de continuité spécifié à un point de jonctions de deux segments définit l’ordre de continuité de la courbe résultante;

• On distingue la continuité géométrique de la continuité paramétrique:• Continuité géométrique (Gx):

continuité ou « aspect lisse » de la courbe résultante;• Continuité paramétrique (Cx):

continuité dans le traçage de la courbe, dans le déplacement de la particule.




Ordre de continuité des courbes• G0: Continuité géométrique d’ordre 0

• Deux segments de courbes forment une courbe continue G0 si celle-ci est ininterrompue au point de jonction;

• Appelée aussi continuité de position;• Correspond à une courbe tracée sans lever le crayon…

• Soit P1(u) et P2(u) définies sur u [0,1]; P1(1) étant le point d’arrivée de P1, et P2(0) étant le point de départ de P2; P1 et P2 sont continues G0 si P1(1) = P2(0).



1( )uP

2( )uP

1 2(1) (0)P P

pentes ou tangentes



• Deux segments de courbes forment une courbe continue G1 si la pente au point de jonction est la même pour les deux segments;

• Appelée aussi continuité de pente ou tangence;• On fait correspondre la direction des vecteurs tangents.

• Soit P1(u) et P2(u) définies sur u [0,1]; P1‘(1) étant la tangente en P1(1) (départ), P2‘(0) étant la tangente en P2(0) (fin);

P1 et P2 sont continues G1 si



1( )uP

2( )uP

1 2'(1) '(0)kP P

pente

1 2'(1) '(0) , 0.k k P P


Ordre de continuité des courbes• C1: Continuité paramétrique d’ordre 1

• G1 correspond à la continuité de la direction du vecteur tangent;• C1 implique G1 ET la continuité de la grandeur du vecteur tangent;• Correspond au tracé d’une courbe lisse sans changement brusque

de vitesse;• On fait correspondre les dérivées premières au point de jonction.

• Soit P1(u) et P2(u) définies sur u [0,1]; P1‘(1) étant la tangente en P1(1) (départ), P2‘(0) étant la tangente en P2(0) (fin);

P1 et P2 sont continues C1 si



1( )uP

2( )uP

1 2'(1) '(0)P P

pente

1 2'(1) '(0).P P



• Deux segments de courbes forment une courbe continue G2 si le centre de courbure au point de jonction est le même pour les deux segments;

• Appelée aussi continuité de courbure;• Pour P(u) = [ x(u) y(u) ], le rayon de courbure ρ(u) est défini par

l’équation:



1( )uP

2( )uP

pente

32 2 2'( ) '( )

( )'( ) ''( ) '( ) ''( )

x u y uu

x u y u y u x u

centre de courbure

1 2(1) (0)


Ordre de continuité des courbes• C2: Continuité paramétrique d’ordre 2

• Deux segments de courbes forment une courbe continue C2 si leurs dérivées secondes respectives au point de jonction sont égales;

• Correspond au déplacement sans secousse d’un particule dont la vitesse et l’accélération (tangentielle et normale) varient graduellement.

• En somme…• En modélisation, on s’intéresse surtout à continuité géométrique.• En analyse, la continuité paramétrique peut être une condition

nécessaire aux calculs basés sur la géométrie.




Interpolation et approximation• Définition d'une courbe en fonction d'un ensemble de points:

• Interpolation• Approximation ou lissage

• Interpolation:• La courbe passe exactement par les points;• Le degré de la courbe dépend du nombre de points de contrôle

(et d'autres conditions éventuellement);• Le nombre de points doit rester faible pour limiter le degré de la

courbe;

• Approximation:• Déterminer une courbe qui décrit au mieux un ensemble de points;• Ces points sont souvent de nature expérimentale (numérisation).




Interpolation et approximation• Approximation (suite)

• La courbe d'approximation peut être contrainte de diverses manières:• Limiter le degré de la courbe;• Limiter l'erreur maximale tolérée (ex.: moindre carré);

• Appropriée lorsque le nombre de points est élevé;• Remplacement d'une courbe dont l'équation est inconnue

ou mal adaptée au traitement numérique;• Exprimer différentes types de courbes sous une forme

unifiée;

• Passage points -> courbes ?





Interpolation et approximation• Influence des points sur la courbe:

• Cas 1: courbe interpole les points,• 2 pts: droites,• 3 pts: coniques (ex. arc de cercle),• 4 pts: polynôme cubique;

• Cas 2: • Courbe approxime les points,• Modifiable globalement;

• Cas 3• Courbe approxime les points,• Modifiable localement;

• Le comportement d’une courbe au déplacement d’un point dépend de son type de courbe.

Adapté du cours GMC405, Prof. Alain Desrochers

McMahon

p1

p0

p3

p2

p5

p0

p1

p2

p3

p4

p4’

p5

p0

p1

p2

p3

p4

p4’



Courbes polynomiales cubiques • Équation paramétrique polynomiale de degré 3:

(représentation algébrique)

(représentation vectorielle)

• 2 équations algébriques, u ϵ [0,1] (3 éq. en 3D),• 8 inconnus ai, bi, ci, di avec i = 1, 2;• Fixer ou modifier les valeurs des coefficients algébriques ai, bi, ci, di

ne permet pas de contrôler facilement la forme de la courbe;

• Contraintes géométriques, G, pour définir la courbe de degré 3: • Lagrange: 4 points interpolés correspondant à 4 valeurs de u;• Hermite: 2 points extrémités et 2 vecteurs tangents en ces

points.©A.B.Côté, adapté de L.Rivest & R.Maranzana


2 31 1 1 1

2 32 2 2 2

( )( )

x u a b u c u d uy u a b u c u d u

2 3( )u a bu cu du P


Courbes polynomiales cubiques • Interpolation de Lagrange (2D)

• Soit les équations du polynôme :

• L’interpolation de Lagrange utilise quatre points (P0 à P3);• On obtient donc un système de huit équations correspondant aux

coordonnées x et y de chaque point;• La résolution fournit les

valeurs des paramètresai , bi , ci et di . p1

p0

p3

p2



2 31 1 1 1

2 32 2 2 2

( )( )



• Interpolation de Lagrange (suite)• Exemple: Déterminer l'équation polynômiale cubique de la

courbe passant par les 4 points suivants:• u0 = 0; P0 = P(u0) = (0, 0)• u1 = 0,33; P1 = P(u1) = (1, 1)• u2 = 0,66; P2 = P(u2) = (2, 0)• u3 = 1; P3 = P(u3) = (3, 1)

• Trouver ax, bx, cx, dx et ay, by, cy, dy …

Courbes polynomiales cubiques

x

y

P1

P2

P3

P0

2 3( )u a bu cu du P




• Interpolation de Lagrange (suite)• Exemple en 2D: Expression matricielle…

• Résolution matricielle…


x

y

P1

P2

P3

P0

2 3

( ) ( ) ( )

1

x y

x y

x y

x y

u x u y u

a ab b

u u uc cd d

P

2 30 0 0 0

2 31 1 1 1

2 32 2 2 2

2 33 3 3 3

( ) 1( ) 1( ) 1( ) 1

u u u uu u u uu u u uu u u u

aPbPcP

P d

12 300 0 0

2 311 1 1

2 322 2 2

2 333 3 3

( )1( )1( )1( )1

uu u uuu u uuu u uuu u u

a Pb Pc P

Pd




• Interpolation de Lagrange (fin)• Inconvénients principaux:

• Le degré de la courbe est directement lié au nombre de points interpolés (n+1) points = degré n;

• Dans le cas d’une seule courbe, plus il y a de points, plus il y a des oscillations indésirables dans la courbe.

• Démo… (http://www.math.ucla.edu/~baker/java/hoefer/TwoDemos.htm)

• Dans le cas d’une courbe par segments, on contrôle difficilement les conditions aux limites des segments, donc la continuité de la courbe résultante.




http://www.math.ucla.edu/~baker/java/hoefer/TwoDemos.htm


Courbes polynomiales cubiques• Interpolation de Hermite (2D)

• Soit les équations du polynôme :

• L’interpolation de Hermite utilise deux points P0 et P1 et leurs pentes respectives P0’ et P1’ pour déterminer les 8 inconnues.

p0'

p1'

p0p1



2 31 1 1 1

2 32 2 2 2

( )( )



Courbes polynomiales cubiques • Interpolation de Hermite (suite)

• La pente de la courbe p s’obtient en dérivant l'équation p(u) par rapport à u:

• En appliquant les conditions frontières P0 , P1, P0’ et P1’, on obtient un système de quatre équations vectorielles et quatre vecteurs inconnus:

2 3

0 1 2 3

21 2 3

( ) ( ) ( )

'( ) '( ) '( ) 2 3

u x u y u u u u

u x u y u u u

P k k k k

P k k k

0 0

1 0 1 2 3

0 1

1 1 2 3

(0)

(1)

' '(0)

' '(1) 2 3

P P k

P P k k k k

P P k

P P k k k





• Le contrôle de la courbe est plus intuitif à partir des points limites P0 et P1, et des vecteurs tangents P0’ et P1’;

• Ce système est donc remanié pour extraire les ki, ce qui donne:

• L’équation originale de P(u) peut finalement être réécrite :

0 0

1 0

2 1 0 0 1

3 0 1 0 1

'

3( ) 2 ' '

2( ) ' '

k P

k P

k P P P P

k P P P P

2 3 2 3 2 3 2 3

0 1 0 1( ) (1 3 2 ) (3 2 ) '( 2 ) '( )u u u u u u u u u uP P P P P





• Sous forme matricielle…

• MH : Matrice des coefficients de Hermite;• GH : Vecteur des contraintes géométriques de Hermite.

MHGH

0

2 3 2 3 2 3 2 3 1

0

1

0

3 2 1

0

1

( ) 1 3 2 3 2 2''

2 2 1 13 3 2 1

( ) 10 0 1 0 '1 0 0 0 '

u u u u u u u u u u

u u u u

PP

PPP

PP

PPP




u10

Courbes polynomiales cubiques• Interpolation de Hermite (suite)

• L’équation obtenue est la somme de quatre fonctions en u multipliées par les conditions frontières P0 , P1, P0’ et P1’ :

• Ces fonctions s'appellent lesfonctions d’influence(blending functions)

• Leur représentation graphiqueest illustrée ici…

(P1) 3u2 - 2u3

(P0) 1 - 3u2 + 2u3

(P0’) u - 2u2 + u3

(P1’) -u2 + u3

2 3 2 3 2 3 2 3

0 1 0 1( ) (1 3 2 ) (3 2 ) '( 2 ) '( )u u u u u u u u u uP P P P P





• Les fonctions d’influence ou fonctions de base sont un concept fondamental en CAO;

• Elles seront appliquées à d’autres types de courbes;• Ces fonctions représentent le long de l’intervalle de u, l’influence

respective des conditions frontières :• Points de départ et d'arrivée,• Vecteurs tangents, ou pentes, aux points de départ et

d’arrivée.

• Exercice: Déterminer l'équation polynômiale cubique pour les contraintes de Hermite suivantes:P0 = (1,1) ; P1 = (2,3) ; P0’ = (1,1) ; P1’ = (1,1)

2 3 2 3 2 3 2 3

0 1 0 1

2 30 1 2 3

( ) (1 3 2 ) (3 2 ) '( 2 ) '( )u u u u u u u u u u

u u u

P P P P P

k k k k






• Effet de la variation de la grandeur du vecteur P0’:

Figure 11.14, Foley


P0'

P1'

y(u)

x(u)

P1P0




• Effet de la variation de direction du vecteur P0’:

Figure 11.15, Foley


y(u)

x(u)

P0'

P1'

P1P0



Courbes polynomiales cubiques • Jonction de deux courbes de l’Hermite

• Les deux courbes doivent avoir un point commun = G0 (C0):

Mortenson

P1(0)

P1(1)

P2(1)

P1u(0) P1

u(1)

P2u(0)

P2u(1)

1

2

G1 = [P1(0) P1(1) P1u(0) P1

u(1)]T

G2 = [P2(0) P2(1) P2u(0) P2

u(1)]T

= P2(0)




Courbes polynomiales cubiques • Jonction de deux courbes de l’Hermite (suite)

• Les vecteurs de tangence au point commun ont…• La même direction (G1);• Les mêmes direction et grandeur (C1);

Mortenson

P1u(0)

P2u(0)

P2u(1)

G1 = [P1(0) P1(1) P1u(0) P1

u(1)]T

G2 = [P2(0) P2(1) P2u(0) P2

u(1)]T

= P2(0) = P1u(1)

12

P1(0)

P1(1)

P2(1)





• Conditions de continuité G1 aux 2 extrémités du segment 2;

Mortenson

31

2 21 3

(0)(1)(0) (1)

(1) (0)

uuu u

u ua et b

PPP P

P P





• Vecteur géométrique du segment 2:

• Équation générale pour G1 au segment i:

Mortenson

312 1 3

1 3

(0)(1)(1) (0)

(1) (0)

Tuu

u ua b

PPG P P

P P

1 11 1

1 1

(1) (0)(1) (0)

(1) (0)

Tu ui i

i i i i iu ui i

a b

P PG P P

P P

Conditions requises pour continuité C1 ?




Courbes de Bézier• Introduction

• Pierre Bézier, ingénieur chez Renault;• Initialement pour la définition de panneaux de carrosserie;• Vise à fournir un moyen intuitif pour définir courbes 3D…

• Pas de tangente à spécifier, contrairement à l’Hermite;• Utilisation d’un polygone de contrôle;• Approximation du polygone par un polynôme dont le degré (n) est

un de moins que le nombre de sommets (n+1); • Ex: pour polygone à quatre sommets, polynôme cubique.




• Définition mathématique (courbe polynomiale cubique)• Courbe polynomiale cubique de Bézier -> Polygone à 4 points.• Correspondance des sommets du polygone de Bézier avec les

paramètres de la courbe de Hermite:• P0 et P3 de Bézier équivalent à P0 et P1 de Hermite;• P1 et P2 de Bézier sont définis comme étant au tiers de la

longueur des vecteurs de tangence P0’ et P1’ de Hermite;• Ici, la proportion du tiers correspond à l’inverse du degré du

polynôme (1/n).• Les vecteurs tangents en P0 et P3 peuvent alors s’écrire :

• P0’ = 3(P1 - P0)• P3’ = 3(P3 - P2)

Courbes de Bézier




• Définition mathématique (courbe polynomiale cubique)• Correspondance des sommets du polygone de Bézier avec les

paramètres de la courbe de Hermite (suite):

Courbes de Bézier

P0P1

P1’

P0’

P0

P1 P2

P3

Hermite Bézier




u10

Courbes de Bézier• Définition mathématique (courbe polynomiale cubique)

• Substitution dans la forme finale du polynôme de Hermite :

• On obtient:

• Fonctions d’influence correspondantes:

(P0) 1 - 3u + 3u2 - u3 (P3) u3

(P1) 3u - 6u2 + 3u3 (P2) 3u2 - 3u3

2 3 2 3 2 3 2 3

0 1 0 1

0 0 1 3 0 1 0 1 3 2

( ) (1 3 2 ) (3 2 ) '( 2 ) '( )

; ; ' 3( ) ; ' 3( )

u u u u u u u u u uP P P P P

P P P P P P P P P P

2 3 2 3 2 3 3

0 1 2 3( ) (1 3 3 ) (3 6 3 ) (3 3 ) ( )u u u u u u u u u uQ P P P P




Courbes de Bézier • Représentation matricielle (courbe polynomiale cubique)

• L’équation obtenue peut être exprimée sous forme matricielle:

MB : Matrice des coefficients de Bézier;GB : Vecteur des contraintes géométriques de Bézier.

0

3 2 1 1

2

3

( )

1 3 3 13 6 3 0

( ) 13 3 0 0

1 0 0 0

B Bu

u u u u

Q UM G

PP

QPP

2 3 2 3 2 3 3

0 1 2 3( ) (1 3 3 ) (3 6 3 ) (3 3 ) ( )u u u u u u u u u uQ P P P P



MBGB


• Formulation générale de Bézier-Bernstein (degré n)

• Fonction d’influence : fonction polynomiale de Bernstein:

• Ces fonctions peuvent être représentée graphiquement comme précédemment par (n + 1) courbes.

Courbes de Bézier

0

!( ) (1 )

!( )!

ni n i

ii

nu u u

i n iQ P

,

!( ) (1 ) avec [0,1]

!( )!i n i

i n

nB u u u u

i n i




Courbes de Bézier• Caractéristiques principales des courbes de Bézier

• La courbe passe par les premier et dernier points;• La dérivée nième de la courbe au point de départ ou d’arrivée

dépend des (n + 1) points voisins du polygone;• Dérivée première : La courbe est tangente aux vecteurs formés

par les 2 premiers et les 2 derniers points;• Propriété intéressante pour raccorder des courbes de Bézier

avec des contraintes de continuité;• Pour tous les autres points intermédiaires, la courbe adoucit la

forme du polygone en atténuant ses variations;• La courbe se situe toujours à l’intérieur de l’enveloppe convexe

formée par le polygone de contrôle.




• Caractéristiques principales des courbes de Bézier (suite)• La même courbe est générée en inversant l’ordre des points dans

le polynôme de contrôle• Exemple numérique:

Courbes de Bézier

P3(1,1)

P2(3,3) P1(5,3)

P0(6,2)

P0(1,1)

P1(3,3) P2(5,3)

P3(6,2)




Courbes de Bézier• Caractéristiques principales des courbes de Bézier (suite)

• Effet du déplacement d’un point du polygone de contrôle;• Courbe principalement affectée dans la région autour des

points où le paramètre u prend la valeur i/n;• Courbe à déformation globale:

P0(0,0)

P1(0,1) P2(1,1) P2(2,1)

P3(1,0)




1 point en Pi

2 points en Pi

3 points en Pi

n = 3

• Caractéristiques principales des courbes de Bézier (suite)• Un point du polygone de contrôle peut être un point double ou

triple ou même équivalent à n points;• Effet d’attirance lorsqu’un point

du polygone de contrôle est un…• Point simple,• Point double,• Point triple;

• Le degré du polynôme augmente!

Courbes de Bézier

n = 2

n = 4

Pn

P0

Pi




• Caractéristiques principales des courbes de Bézier (suite)• Courbe fermé:

• G0 : Premier et dernier points coïncidents;

• G1: ET points adjacents colinéaires;

• C1: …?

Courbes de Bézier

P0

P1

P2P3

P4

P5P6

P0

P1

P2

P3

P4

P5




Courbes de Bézier• Jonction des courbes de Bézier

• Lorsque plusieurs points sont approximés par plusieurs courbes de Bézier de degré(s) inférieur(s);

• On assure une continuité G1 à la jonction de deux segments de courbe de Bézier:• Dernier point du polygone j = 1er point du polygone j + 1;• Points précédent, commun et suivant colinéaires;

• 2 segments de courbe de Bézier consécutifs peuvent être de degrés différents.

5 pts Degré 4

4 pts Degré 3




Courbes de Bézier• Une courbe de Bézier est modifiable globalement.

Modification d'un point du polygoneCourbe modifiée globalement




• Caractéristiques principales des courbes de Bézier (fin)• Lorsque la courbe à représenter devient complexe (beaucoup de

points), le degré de la courbe augmente;• En modifiant un point de contrôle du polygone, toute la courbe

est affectée;• Lorsque le degré du polynôme augmente, la courbe peut osciller;• La charge de calcul augmente avec le degré de la courbe;• Compromis: courbes complexes représentées par plusieurs

courbes de Bézier de degré moindre;• Inconvénients: l'édition de la courbe par segments tout en

maintenant la continuité G1 aux jonctions est pénible;• Les limitations des courbes de Béziers proviennent de ses

fonctions d’influence (blending functions).

Courbes de Bézier




• Exercice:• Polygone de contrôle

• P0 (0, 0) P1 (0.3, 1) P2 (0.6, 0.8) P3 (1, 0)

1. Déterminer l’équation de la courbe de Bézier suivant la formulation de Bernstein.

2. Tracer la courbe de Bézier avec les points intermédiaires suivants:

2.1) u = 0.3 2.2) u = 0.6

Courbes de Bézier




• Solution1. Formulation de Bernstein: trouver les fonctions d’influence…

Courbe de Bézier passant par 4 points Degré n = 3.

Courbes de Bézier

,

!( ) (1 ) avec [0,1]

!( )!i n i

i n

nB u u u u

i n i

0 3 0 3 2 30,3

1 3 1 2 3 21,3

2 3 2 2 2 32,3

3 3 3 33,3

3!0) ( ) (1 ) (1 ) 1 3 3

0!(3 0)!3! 3!

1) ( ) (1 ) (1 ) 3 6 31!(3 1)! 2!

3! 3!2) ( ) (1 ) (1 ) 3 3

2!(3 2)! 2!3!

3) ( ) (1 )3!(3 3)!

i B u u u u u u u

i B u u u u u u u u

i B u u u u u u u

i B u u u u




• Solution1. Équation de Bézier-Bernstein:

Équations algébriques paramétriques:

Courbes de Bézier

,

0

2 3 2 3 2 3 30 1 2 3

( ) avec [0,1]

(1 3 3 ) (3 6 3 ) (3 3 ) ( )

( ) ( )

n

i n ii

u B u

u u u u u u u u u

x u y u

Q P

P P P P

2 3 2 3 2 3 3

3

2 3 2 3 2 3 3

2 3

( ) (0)(1 3 3 ) (0.3)(3 6 3 ) (0.6)(3 3 ) (1)( )

0.9 0.1

( ) (0)(1 3 3 ) (1)(3 6 3 ) (0.8)(3 3 ) (0)( )

3 3.6 0.6

x u u u u u u u u u u

u u

y u u u u u u u u u u

u u u




y(u)

x(u)

• Solution:2.1)• x(0.3) = 0.2727• y(0.3) = 0.5922

2.2)• x(0.6) = 0.5616• y(0.6) = 0.6336

Courbes de Bézier

P0(0,0)

P1(0.3,1)

P2(0.6,0.8)

P3(1,0)

Q(0.3)

Q(0.6)




• Astuce pour le tracé des courbes de Bézier: Algorithme de De Casteljau1. Découpe des segments de droites du polygone selon le rapport

u/(umax-umin);

2. Tracé de nouveaux segmentsde droite reliant les nouveauxpoints obtenus sous le polygonede contrôle;

3. Découpe des nouveaux segments…

4. Répéter jusqu’à obtention dudernier point.

Exemple: Déterminer le point sur la courbe pour u = 0.5…

Courbes de Bézier




• Algorithme de De Casteljau

Courbes de Bézier

Découpe du polygone de contrôle

au paramètre u = 0.5





Courbes de Bézier

Nouveaux segments sous

polygone de contrôle





Courbes de Bézier

Découpe du sous polygone de contrôle

au paramètre u =0.5





Courbes de Bézier

Nouveau segment sous polygone de

contrôle





Courbes de Bézier

Q(0.5)




• Algorithme de De Casteljau2. Déterminer et tracer les points de la courbe pour

u = 0.3 et u = 0.6…

Courbes de Bézier

u = 0.5u = 0.3 u = 0.6




• Exercice (à vous de le faire!)• Points de contrôle

• P0(1,1) P1(3,4) P2(4,2) P3(5,3) P4(6,0)

• Quel est le degré de la courbe?• Calculer l’équation de la courbe de Bézier;• Tracer la courbe de Bézier en utilisant l’algorithme de

De Casteljau en prenant le point intermédiaire u = 0.5.

Courbes de Bézier




Courbes de Bézier

• Solution1) Degré 42) B0,4 = (1 - u)4

B1,4 = 4u(1-u)3

B2,4 = 6u2(1-u)2

B3,4 = 4u3(1-u)

B4,4 = u4

P(u) = (1-u)4*P0 + 4u*(1-u)3*P1 + 6u2*(1-u)2*P2 + 4u3*(1-u)*P3 + u4*P4




Courbes de Bézier

• Solution

P0(1,1)

P1(3,4)

P2(4,2)

P3(5,3)

P4(6,0)

Découpe du sous polygone de contrôle au

paramètre u = 0.5




• Courbes par morceaux:• Une solution aux inconvénients des courbes de Bézier:

• Les fonctions de base ne doivent pas dépendre du nombre de points de contrôle;

• La courbe doit être modifiable localement;• Principes des courbes par morceaux:

• Remplacer un polynôme de degré élevé qui passe, ou est contrôlé, par de nombreux points, par plusieurs courbes de degré plus faible, plus faciles à manipuler par l'opérateur et aussi d'un point de vue numérique;

• Exemple: • Au lieu d'une courbe contrainte par 10 points…• 9 segments de courbes polynômiales cubiques passant

chacune par 2 points et respectant des contraintes de continuité en ces points .

Courbe Spline




• Exemple: Courbe par morceaux

• Problème: • L'attribution de la valeur du paramètre u au point Pi;• La valeur de u devrait être proportionnelle à la longueur parcourue

(Au moment de la construction, la courbe est inconnue!).

Courbe Spline

Segment1

Segmenti+1

u=u0

u=u1

u=ui

u=ui+1

u=un

Segmentn

u=un-1

S1(u); u ϵ [u0,u1]

Si+1(u); u ϵ [ui,ui+1]Sn(u); u ϵ [un-1,un]

Si(u); u ϵ [ui,ui+1]: Une fonction polynômiale de degré m

P0

P1

Pi

Pi+1

Pn-1

Pn




• Principes des courbes par morceaux (suite):• Les fonctions de base doivent être non nulles uniquement sur

une partie limitée de l'espace paramétrique;• La partie non nulle de chaque fonction de base est différente;• La courbe résultante n'est affectée que par un nombre réduit de

points; modifiable localement• Courbe composite qui a l'apparence d'une courbe unique;• Les segments de courbe ainsi reliés doivent au minimum être

des courbes polynomiales cubiques (le plus petit degré qui permet de décrire une courbe en 3D);

• Le nom Spline est utilisé pour nommer ces courbes:• Spline désigne un instrument utilisé historiquement par

plusieurs corps de métier pour tracer les courbes complexes (latte ou cerce, en français).

Courbe Spline





Courbe Spline• Courbe polynômiale par intervalles;• Pour chaque morceau on définit:

• Ordre ou degré des polynômes,• Plage du paramètre,• Ordre de continuité aux jonctions;

• Chaque morceau réuni peut s’écrire sous la forme:

Avec: u le paramètre de la courbe,f(u) la fonction polynômiale,Gi la ième information géométrique,

Ni la ième fonction de base ou d’influence.

( ) i ii

f u G N




Courbe Spline• Une fonction spline de degré m et d’ordre de continuité r est une

fonction polynomiale par intervalles de degré m, définie par exemple sur n intervalles :

• L’ordre de continuité d’une fonction est r si ses (r-1) premières dérivées sont continues;

• Elle satisfait les conditions de continuité de la jième dérivée de f aux valeurs nodales:

Soit la continuité de f et de ses r-1 premières dérivées aux frontières des intervalles.

1( ) ( ) si pour 0, ..., 1i i if u f u u u u i n

( ) ( )1( ) ( ) pour 1,2,..., 1 et 0,1,..., 1j j

i i i if u f u i n j r




Courbe Spline cubique• Les splines cubiques sont des courbes polynômiales par morceaux

dont chaque segment est représenté par un polynôme de degré 3;• Une façon de représenter un segment de spline cubique est d’utiliser

comme informations géométriques:• La position des points aux deux extrémités,• Le vecteur tangent à chaque extrémité;…• … L’Hermite!

p0’

p1’p0p1



• Cette courbe est connue sous le nom de courbe spline cubique à dérivée seconde continue (degré m = 3, ordre r = 3);

• Soit (n+1) points à interpoler, donc n segments sont nécessaires:• Chaque segment possède 4 inconnues, donc 4(n) inconnues à résoudre;• Chaque segment passe par le point de départ et d'arrivée, donc 2(n)

premières contraintes géométriques (continuité de position, C0);• Respecter les pentes en chaque point de connexion, donc (n-1) autres

contraintes géométriques (continuité en tangence, C1);• Respecter les courbures (en fait simplifié en respectant les dérivés

secondes), donc (n-1) autres contraintes (continuité en courbure, C2);• Il manquent encore 2 contraintes. Plusieurs solutions sont proposées:

• Pentes paramétriques nulles aux extrémités (P1'(u0) = 0 et Pn'(un) = 0)• Courbures nulles aux extrémités (P1''(u0) =0 et Pn''(un) = 0)• Les pentes aux extrémités explicitement données

(dy/dx: pente géométrique; dy/du et dx/du: pentes paramétriques).

Courbe Spline cubique




• Modification globale « atténuée » …• En s'éloignant du point modifié, les effets deviennent minimes;

• Spline cubique: pas de continuité C3 (r = 3);• Continuité C3: utilisée pour les profils de came ou des analyses

aérodynamiques;• Solution: utiliser un polynôme de degré n > 3;• Pour un polynôme de degré n, une continuité à la dérivée n-1

servira de contrainte en chaque point.

Courbe Spline cubique

[McMahon et Browne]

Point déplacé





Courbe B-spline• Caractéristiques:

• Généralisation par segment de l’approche de Bézier;• Courbe approximative à variation locale;• Pas de limitation sur le nombre de points de contrôle;• Le degré de la courbe est indépendant du nombre de points de

contrôle;• Chaque segment de la courbe possède ses propres fonctions

d’influence («blending functions») dont les valeurs sont non-nulles uniquement pour l’intervalle correspondant;

• La courbe B-spline est contenue à l’intérieur de son polygone de contrôle;

• Elle peut ou non passer par les points aux extrémités.




Courbe B-spline• Une courbe de Bézier par segment, ou B-spline, est

modifiable localement ?

Modification d'un point du polygoneCourbe modifiée localement





Courbe B-spline• Exemple:

Expression matricielle de la forme B-Spline uniforme non-rationnelle d’ordre K = 4 (degré m = 3):

Expression polynômiale de la forme B-Spline uniforme non-rationnelle d’ordre K = 4 (degré m = 3):


3

3 2 2

1

1 3 3 13 6 3 01

( ) 1 pour 3,3 0 3 06

1 4 1 0

i

ii

i

i

u u u u i n

PP

QPP

3 3 2 3 2 3

3 2 1

(1 ) 3 6 4 3 3 3 1( )

6 6 6 6i i i i i

u u u u u u uuQ P P P P




Courbe B-spline• Exemple: B-Spline uniforme non-rationnelle d’ordre 4, sur (n+1) = 10

points, donc composée de 7 segments (Q3 à Q9);

Foley

y(u)

x(u)P0

P1

P2

P3 P4

P5

P6

P7

P8

P9

Q3

Q4

Q5

Q6 Q7

Q8

Q9

Point de contrôleNœud

u3

u4

u5

u6

u7

u8

u9

u10




Courbe B-spline• Exemple: Contrôle local d’une B-Spline uniforme non-rationnelle

d’ordre 4, sur (n+1) = 9 points, composée de 6 segments (Q3 à Q8);

Foley

y(u)

x(u)

P0

P1

P2

P3

P5 P6

P7

P8

Q3

Q4

Q5 Q6

Q7

Q8

Point de contrôleNœud

P4’’

P4

P4’

Courbe avec P4’’

Courbe avec P4’

Courbe avec P4

u3

u4

u9

u8



• Exemple• Courbe B-spline non-uniforme non-rationnelle pour n = 5 et K = 3;• Fonctions de base (n=5 et K=3).

Courbes B-spline

p0

p1

p2

p3

p4

p5

p4'

N0,3 (u) N3,3 (u)

N4,3 (u)

N5,3 (u)N2,3 (u)

N1,3 (u)



Documents

Cours GPA445 Conception assistée par ordinateur Courbes complexes Par Antoine Brière-Côté, ing.jr, M.Ing. Génie de la production automatisée École de technologie