Les courbes et
surfaces lissées
PARAMÉTRIQUES
CUBIQUES
Définition
Propriétés, applications
COURBES
DE BÉZIER
Définition
Propriétés
Algorithme
COURBES B-SPLINES
NON RATIONNELLES
UNIFORMES
Définition
Propriétés
Algorithme
B-SPLINES
DE CATMULL-ROM
Définition
Propriétés
B-SPLINES NON
UNIFORMES NON
RATIONNELLES
SURFACES
PARAMÉTRIQUES
BICUBIQUES
Définition
Propriétés
QUADRIQUES
Définition
Exemples
Les courbes paramétriques cubiques
Courbe paramétrique cubique de R3: Courbe définie par le système d'équations paramétriques cubiques suivant:
(1)
Pour obtenir des segments de courbe, on considère que t appartient à un intervalle [min,max] (fréquemment [0.0,1.0]).
Reformulation mathématique
Soit le vecteur T = (t3, t2, t, 1), (1) s’écrit sous la forme
Q(t) = (x(t),y(t),z(t)) = T.C avec C = 
et .
Les courbes de cette famille ont pour propriétés d'être:
- continues,
- de dérivés premières en t continues (dérivation de chaque composante de T),
- de dérivés secondes en t continues (double dérivation de chaque composante de T).
Quatre coefficients numériques constants sont nécessaires pour définir chacune des trois équations paramétriques.
-> Quatre contraintes mathématiques sont imposées pour définir l'équation selon chacun des trois axes.
On transforme la matrice C donnée précédemment en la matrice produit M.G où M est une matrice 4x4 (appelée matrice de base) et G est un vecteur colonne de quatre contraintes géométriques (appelé vecteur géométrie).
Q(t) = (x(t), y(t), z(t) ) = T.C = T.M.G =
(2)
La matrice G permet de représenter 4 contraintes géométriques s'appliquant à la courbe. Il s'agit habituellement de la position de 4 points dans l'espace de représentation. La courbe générée évoluera "entre" ces quatre points.
La matrice M permet d'attribuer des "poids" respectifs à chacun des coefficients ti s’appliquant à une contrainte géométrique, permettant ainsi de définir la "forme" de la courbe.
De bons choix de matrice M permettront d'obtenir des tracés de courbe approximant la ligne polygonale à 4 sommets définie par les quatre points présentant différentes caractéristiques.
| Trois types de courbes paramétriques cubiques |
|
|
| Tangente à une courbe paramétrique cubique |
|
|
Les courbes paramétriques cubiques sont souvent utilisées pour programmer des fonctions de lissage de lignes brisées.
Les propriétés de continuité, de continues dérivabilités première et seconde sont primordiales dans ce cadre car elles assurent la possibilité de se déplacer uniformément sur tous les points de la courbe.
Elles assurent une vitesse de déplacement continue (pas de déplacement instantané) et une accélération du déplacement continue (pas de saute de vitesse instantanée) quand on fait varier t uniformément.
Ces propriétés sont importantes en CFAO (domaine d'origine de ces outils mathématiques).
Les courbes paramétriques cubiques possèdent aussi la propriété de ne pas être déformées par translation et rotation de leurs sommets de définition.
En revanche, elles sont modifiées par changement des paramètres de mise en perspective.
Problème: Ces courbes sont définies sur 4 points de contrôle. Que faire si on en a moins (3) ou plus (5, 6, 7 ou encore plus)?
Si P0, P1, P2, P3, ..., Pn sont les n+1 points d’une ligne brisée. La courbe de Bézier définie par ces points est:
avec le coefficient t compris entre 0.0 et 1.0. On rappelle que 
.
Une telle courbe
- commence par le premier point, finit par le dernier point et ne passe pas obligatoirement par les autres points,
- est tangente au segment P0,P1 en P0 et au segment Pn,Pn-1 en Pn,
- n'est pas déformée par translation et rotation,
- est déformée par changement des paramètres de mise en perspective.
Problèmes
Quoique pouvant être optimisé, le calcul des Cin n'est pas économique en temps.
Les deux mises à la puissance en t et en 1-t ne sont pas économiques en temps.
La courbe est intégralement modifiée quand on modifie la position d'un seul point de contrôle. Ceci a pour conséquence l'obligation de la réévaluer intégralement. Il n'y a donc pas de contrôle local sur la forme de la courbe.
Lorsqu'une courbe de Bézier est tracée avec beaucoup de sommets, les sommets intermédiaires sont peu "attractifs". La courbe reste donc loin d'eux. Il n'y a donc pas de fort contrôle de la forme de la courbe.
struct coord_3D {
GLfloat x = 0.0F;
GLfloat y = 0.0F;
GLfloat z = 0.0F;
GLfloat w = 1.0F; };
struct polygone {
int n = 0;
coord_3D *p = NULL; };
void point(float x,float y,float z) {
glVertex3f(x,y,z);
}
double power(double v,int p) {
return(( v || p ) ? pow(v,(double) p) : 1.0);
}
void bezier(polygone *p,int n) {
int i,j;
float t,mt;
float *cn,x,y,z,fac;
cn =(float *) calloc(p->n,sizeof(float));
cn[0] = 1;
cn[1] =(float) (p->n-1);
for ( i = 2 ; i < p->n ; i++ )
cn[i] = cn[i-1] * (p->n - i) / i;
for ( i = 0 ; i < n ; i++ ) {
t =(float) i/(n-1);
mt = 1.0F-t;
x = y = z = 0.0F;
for ( j = 0 ; j < p->n ; j++ ) {
fac = cn[j]*(float) power(t,j)*
(float) power(mt,p->n-1-j);
x += fac * p->p[j].x;
y += fac * p->p[j].y;
z += fac * p->p[j].z; }
point(x,y,z); }
free(cn);
}
Cas particulier
Si n = 3 (4 sommets), C(t) peut être présentée sous la forme d'une courbe paramétrique cubique définie par les 4 points de contrôle. Les 4 contraintes géométriques G1, G2, G3 et G4 sont alors les positions de ces 4 points de contrôle.
On a alors:
C(t) = (x(t), y(t), z(t)) = 
Problème: Acquérir un contrôle local et obtenir un bon lissage avec beaucoup de points de contrôle.
Solution: Relier deux courbes de Bézier définies sur quatre sommets tels que le dernier sommet définissant la première courbe soit aussi le premier sommet de la seconde. C'est à dire tracer la courbe Pi avec 0 <= i <= 6 (soit au total 7 sommets différents).
Si P2, P3 et P4 sont sur la même droite alors il y a continue dérivabilité au point P3.
Si les distances entre P2 et P3 d'une part et P3 et P4 d'autre part sont identiques alors il y a continue dérivabilité seconde au point P3.
Avantage : Contrôle local, forme "bien" lissée et contrôlée, ajout possible de points de contrôle.
Application : Tracé de courbes lissées quand le nombre de points de contrôle n'est pas fortement imposé.
-> Utilisation dans les logiciels de dessin vectoriel et de modélisation géométrique
Inconvénient : Tous les points de contrôle ne sont pas "au même niveau".
Les courbes B-Splines non rationnelles uniformes
Problème
Lisser une ligne polygonale quelconque au moyen d'une courbe paramétrique cubique telle que la modification de la position d'un seul sommet ne modifie
pas l'intégralité de la courbe.
-> Seule la partie modifiée aura à être recalculée.
Soit une ligne polygonale de n+1 sommets Pi, 0 <= i <= n avec n >= 3.
On définit les n-2 vecteurs géométriques Gi = 
avec 0 <= i <= n-3.
Ces n-2 vecteurs géométriques permettent la génération de n-2 morceaux de courbe jointifs qui une fois réunis formeront une courbe lissée approximant la ligne polygonale P.
Pour chaque morceau la valeur de t variera obligatoirement uniformément entre 0.0 et 1.0
-> B-Spline uniforme.
La matrice de base utilisée est 
Les morceaux de courbe se joignent obligatoirement en leurs extrémités. En effet, soient les deux morceaux de courbe correspondant à Gi
et Gi+1, le premier se finit à t = 1.0, le second commence à t = 0.0. En ces points, on calcule que les coordonnées obtenues sont identiques
avec pour valeur 
. Cette position est quelque part dans le
triangle défini par les trois sommets, plus proche de Pi+2 que des 2 autres car il s'agit du barycentre des points Pi+1,
Pi+2 et pi+3 affectés des poids 1.0, 4.0 et 1.0.
Chaque morceau de spline dépend de 4 points de contrôle. Chaque point de contrôle intervient sur au maximum 4 morceaux de splines.
-> On n'a pas l'obligation de recalculer toute la courbe si un seul point est modifié, mais seulement 4 morceaux au maximum.
Les courbes B-Splines NRU:
- ne passent pas par les sommets de la ligne brisée, y compris le premier et le dernier,
- respectent la continuité, la continue dérivabilité première et la continue dérivabilité seconde.
Une solution simple pour passer par le premier et le dernier point consiste à tripler ces points.
struct coord_3D {
GLfloat x = 0.0F;
GLfloat y = 0.0F;
GLfloat z = 0.0F;
GLfloat w = 1.0F; };
struct polygone {
int n = 0;
coord_3D *p = NULL; };
typedef float matrice[4][4] ;
void point(float x,float y,float z) {
glVertex3f(x,y,z);
}
void morceauBSpline(coord_3D *p,int n,matrice m) {
int j,k ;
float tt[4],ttt[4],x,y,z ;
for ( int i = 0 ; i < n ; i++ ) {
float t =(float) i/(n-1) ;
tt[0] = t*t*t ;
tt[1] = t*t ;
tt[2] = t ;
tt[3] = 1.0F ;
for ( j = 0 ; j < 4 ; j++ ) {
ttt[j] = 0.0F ;
for ( k = 0 ; k < 4 ; k++ )
ttt[j] += tt[k] * m[k][j] ; }
x = y = z = 0.0F ;
for ( j = 0 ; j < 4 ; j++ ) {
x += ttt[j] * p[j].x ;
y += ttt[j] * p[j].y ;
z += ttt[j] * p[j].z ; }
point(x,y,z) ; }
}
void BSpline(struct polygone *p,matrice m,int n) {
for ( int i = 0 ; i < p->n-3 ; i++ )
morceauBSpline(&p->p[i],n,m) ;
}
Les courbes Splines de Catmull-Rom
Problème
Lisser une ligne polygonale par une courbe passant par chacun des sommets de cette ligne.
-> Utilisation des courbes Splines de Catmull-Rom.
On lisse une ligne polygonale de n+1 sommets Pi, 0 <= i <= n avec n >= 3. Soient les n-2 Gi = , 0 <= i <= n-3.
est la matrice de base utilisée.
Pour le vecteur géométrique Gi, la courbe commence pour t = 0.0 en Pi+1, et finit pour t = 1.0 en Pi+2.
-> Tous les morceaux se rejoignent en leurs extrémités pour des intervalles [0.0,1.0]. Ces extrémités sont les points de contrôle.
Les courbes splines ainsi définies:
- passent par tous les sommets de la ligne brisée, à l'exception du premier et du dernier,
- commencent au deuxième point et finissent à l'avant dernier,
- sont tangentes au point Pi à la direction donnée par le segment Pi-1,Pi+1,
- respectent la continuité, les continues dérivabilités première et seconde.
Une solution simple pour passer par le premier et le dernier point consiste à doubler ces points.
Les courbes B-Splines non uniformes non rationnelles
Ces courbes sont mathématiquement équivalentes aux B-Splines uniformes non rationnelles à la seule différence que les intervalles de variabilité pour les morceaux de courbe ne sont pas forcément tous [0.0,1.0].
Cette modification entraîne une plus grande complexité car il est plus difficile de s'assurer des propriétés caractéristiques qui nous sont nécessaires (dérivabilités). Obtenir cette assurance a fréquemment pour conséquence la duplication de points de contrôle ou l'apparition de nouveaux points de contrôle.
L'intérêt de ces B-Splines est par exemple la possibilité d'ajouter des points de contrôle sans modifier la courbe initiale.
Les courbes B-Splines non uniformes rationnelles: les NURBS
Une B-Spline non rationnelle est calculée au moyen de points de contrôle. Si elle est visualisée en perspective, la même courbe devra être modélisée
en cas de modification des paramètres de mise en perspective.
Il n'est pas possible de placer les points de contrôle en perspective et de calculer la B-Spline ensuite. On devra d'abord calculer la B-Spline
pour ensuite faire la mise en perspective sur l'ensemble des points obtenus.
Faute de cet ordre de manipulation, la B-Spline obtenue n'est pas invariante par modification des paramètres de mise en perspective avec pour
conséquence des problèmes de visualisation.
Cet ordre de calcul est inefficace en temps de calcul car le nombre de sommets de la courbe lissée est plus grand que le nombre de points de contrôle.
Solution: Utiliser les B-Splines non-uniformes rationnelles.
Définition mathématique
Courbe NURBS: 
avec x(t), y(t), z(t) et w(t) des équations paramétriques cubiques représentant des coordonnées homogènes.
Les surfaces paramétriques bicubiques
Les surfaces paramétriques bicubiques sont une généralisation aux surfaces des courbes paramétriques cubiques.
Soit une courbe cubique Q(s) = S.M.G (s et S sont équivalents à t et T). Le vecteur géométrique G est constant.
Si les composantes de ce vecteur sont elles-mêmes des cubiques. On obtient:
Q(s,t) = S.M.G(t) = S.M.
avec t compris entre 0.0 et 1.0.
Les Gi sont des cubiques.
-> Gi(t) = T.M'.Pi avec Pi = (Pi1,Pi2,Pi3,Pi4)T,
-> Gi(t) = (T.M'.Pi)T = PiT.M'T.TT
= (Pi1,Pi2,Pi3,Pi4).M'T.TT.
Chaque point Pij est un point de contrôle de Gi(t).
-> 16 points Pij
Q(s,t) = S.M.
.M'T.TT avec s et t compris
entre 0.0 et 1.0.
La modification d'un seul des 16 points de contrôle entraîne la modification de l'ensemble de la surface.
Le choix des matrices M et M' permet d'adapter les caractéristiques de la surface tracée aux spécifications désirées.
Ces matrices pourront être celles décrites précédemment dans le chapitre (Bézier, NRU, Catmull-Rom) ou d'autres matrices.
Elles pourront être identiques ou bien différentes l'une de l'autre pour obtenir certaines caractéristiques selon un axe et des caractéristiques
différentes selon l'autre axe.
Interprétation intuitive
Une interprétation intuitive de ces surfaces consiste à considérer qu'une telle surface est générée à partir d'une matrice carrée de 4x4 points de contrôle.
Les 4 lignes de cette matrice permettent de générer m séries de 4 points de contrôle, chacune de ces m séries permettant de générer n points modélisant la surface, soit donc au total m*n points. Ces m*n points définissent un maillage quadrangulaire traçable.
Surface obtenue avec M et M' matrices de Bézier.
On appelle surface quadrique une surface d'équation:
f(x,y,z) = ax2 + by2 + cz2 + dxy + eyz + fxz + gx + hy + iz + j = 0.0
Cette famille de surfaces est très vaste.
Il est possible de représenter des plans, des sphères, des paraboloïdes, des ellipsoïdes, …
Les raisons qui pourraient faire utiliser les surfaces quadriques sont multiples:
- Calcul facile de la normale en un point à la surface
- Test facile de la présence d'un point sur la surface
- Calcul facile d'une des coordonnées si les deux autres sont connues
- Calcul possible de l'intersection d'une surface quadrique avec une autre surface quadrique
-
Plans: a = b = c = d = e = f = 0.0
-> f(x,y,z) = gx + hy + iz + j = 0.0 -
Ellipsoïdes: d = e = f = g = h = i = 0, j <= 0.0
-> f(x,y,z) = ax2 + by2 + cz2 + j = 0.0
Les surfaces et courbes lissées ont été initialement conçues comme outils de CFAO pour la modélisation d'objets.
Plus récemment, l'informatique graphique s'est emparée de ces objets mathématiques comme outils de modélisation pour représenter les objets des scènes autrement que par ensembles de facettes ou en tant qu'objets canoniques volumiques de type sphère, cube, ...
Les outils de haut niveau en modélisation pour la synthèse d'images font appel aux NURBS (Non Uniform Rational B-Splines) qui sont une évolution des NRUBs pour permettre un affichage en perspective.