NURBS

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Nurbs)
Aller à : navigation, rechercher
Les surfaces NURBS en trois dimensions peuvent avoir des formes complexes et organiques. Les points de contrôle influent sur la direction que prend la surface. Le côté extérieur, post ci-dessous, décrit les extensions X / Y de la surface. Modélisation et rendu en Cobalt.

Les B-splines rationnelles non uniformes, plus communément désignées par leur acronyme anglais NURBS (pour Non-Uniform Rational Basis Splines), correspondent à une généralisation des B-splines car ces fonctions sont définies avec des points en coordonnées homogènes.

Intérêts des NURBS[modifier | modifier le code]

Le principal intérêt de ces courbes NURBS est qu'elles parviennent même à ajuster des courbes qui ne peuvent pas être représentées par des B-splines uniformes qui ne peuvent représenter exactement (quel que soit leur degré de définition, c’est-à-dire le nombre de coordonnées de points de contrôle en plus des coordonnées des sommets de chaque arc ou facette courbe) que des segments de droite et certaines courbes et surfaces (mais pas la plupart des courbes polynomiales de degré 2 ou supérieur).

Un exemple fameux est le tracé d'un quart de cercle, mais leur intérêt est de permettre une représentation exacte de la totalité des arcs coniques (dont le cercle et toutes les ellipses, même celle dont les foyers ne sont pas sur un axe horizontal ou vertical, les arcs paraboliques et hyperboliques, et bien sûr aussi les segments de droite), ainsi que la totalité des courbes et surfaces polynomiales, avec uniquement des paramètres entiers (ou rationnels sous la forme de paires d'entiers) si les NURBS passent par un nombre limité mais suffisant de points définis dans un maillage discret (à coordonnées entières ou rationnelles) de l'espace.

Cet intérêt s'étend aussi aux espaces à plus de 2 dimensions et permet aussi une représentation exacte des surfaces coniques dans un espace tri-dimensionnel (dont les cônes à base circulaire ou elliptique, la sphère et les elllipsoïdes avec un axe focal d'orientation quelconque, les paraboloïdes et hyperboloïdes, mais encore aussi les facettes planes). Les NURBS permettent également de définir des courbes ou surfaces d'ordre supérieur (par exemple les courbes ou surfaces polynomiales du troisième degré ou plus), selon le nombre de points de contrôle (et de poids affectés à chacun d'eux) définis entre les sommets d'un même arc (ou d'une même facette courbe).

L'utilisation des NURBS, dont les points de contrôle sont affectés de poids rationnels (et non seulement entiers avec les B-splines classiques) permet de réduire souvent considérablement le nombre de sommets et de points de contrôle dans l’approximation précise d'un arc ou d'une facette courbe quelconque, tout en améliorant la précision de cette approximation et en conservant un degré faible pour cette approximation (donc un rendu rapide).

Les NURBS conservent aussi leur propriétés via toutes les transformations affines de l'espace (translations, rotations, homothéties), mais aussi certaines transformations non isométriques comme les projections, y compris la perspective (qu'il est possible de réaliser en représentant cette transformation comme une projection simple dans un espace isométrique de degré immédiatement supérieur, c’est-à-dire par l'emploi de coordonnées homogènes avec une seule coordonnée rationnelle supplémentaire par sommet ou point de contrôle), tout en garantissant la conservation de certaines propriétés physiques essentielles comme la continuité, la préservation des tangentes ou angles aux sommets, mais aussi la monotonie des transitions graduelles de courbure le long de l'arc ou de la facette ainsi définie (y compris la préservation de la constance de cette courbure dans le cas des droites ou arcs de cercles et des facettes planes ou sphériques, mesurée dans l'espace homogène).

Les NURBS constituent alors une représentation intéressante pour réduire la complexité de modélisation d'objets et de scènes complexes (y compris animés), par exemple dans la modélisation 3D et au sein des accélérateurs de calcul de géométrie et de rendus graphiques, par une réduction souvent notable du nombre d'arcs nécessaires, tout en n'imposant pas plus d'arcs qu'avec les B-splines et arcs elliptiques seuls.

Leur utilisation récente est également importante dans de nouvelles applications cartographiques qui demandent une très grande précision des coordonnées calculées, car les NURBS sont compatibles avec la majorité des projections les plus utilisées dans ce domaine ; elles permettent des interpolations extrêmement précises (au niveau des distances/périmètres, angles et aires calculés) à partir d'un volume réduit de mesures géodésiques et d'un des modèles usuels (historiques ou standardisés) de géoïdes cartographiques, et un jeu de mesure par l'observateur, obtenu simplement par des instruments optiques simples (photographies aériennes ou satellitaires) ou radioélectriques (par exemple pour la géolocalisation par satellite, couplée à des horloges de grande précision mais avec un nombre réduit de satellites observés, pour le calcul des triangulations permettant de positionner ou ajuster précisément les coordonnées des photos aériennes ou satellitaires, ou encore pour les mesures précises de vitesse et l'optimisation de trajectoire dans les transports, la construction et les productions agricoles).

Toutefois, les NURBS trouvent aujourd'hui leur utilisation dans la productique de matériels de très haute précision (par exemple la microélectronique et le tracé des routages au sein des composants, ou la fabrication d'instruments de mesures comme les miroirs et lentilles utilisés en astronomie), car elles permettent une réduction des contraintes physiques appliquées aux systèmes de pilotage des instruments de fabrication, et la réduction de l'usure de ces instruments (ce qui permet l’augmentation et stabilisation des vitesses de pilotage sans dépasser les contraintes d'accélération, par le respect de contraintes dont les limites basses de curvature, ces contraintes influant directement sur les accélérations physiques subies et donc aussi sur la vitesse maximale et le temps et le coût minimum de fabrication). Elles permettent aussi l'augmentation de la résistance physique et de la fiabilité des éléments fabriqués à partir de telles modélisations devant répondre à des contraintes physiques importantes (par exemple pour réduire les arcs parasites émetteurs de perturbations radioélectriques ou de diffusion électrochimique dans les micro-composants fabriqués, ou dans la construction nautique et aéronautique et les superstructures porteuses de charge lourde, par exemple pour augmenter la résistance des ponts, bâtiments et navires de transport, mais aussi la conception de moteurs et systèmes de transmission pour réduire leur consommation d'énergie), tout en simplifiant le jeu de données précalculées à concevoir et optimiser dans les modélisations et en simplifiant aussi la conception et le coût des outils devant aussi les fabriquer (notamment par la réduction notable du nombre de pièces et de degrés de libertés de ces outils).

De fait, les NURBS sont devenues aujourd'hui incontournables dans les systèmes de CAO les plus avancés, au-delà des seuls besoins de l'imagerie informatique créative (elle aussi de plus en gourmande en calculs et pour lesquels les optimisations offertes par les NURBS sont devenues très intéressantes, car elles sont supportées maintenant par des moyens bon marché d'accélération matérielle, par exemple dans les actuels processeurs d'accélération graphique pour ordinateurs et consoles de jeu), même si de nombreux outils et normes graphiques (formats de fichiers et langages de programmation, polices vectorielles, etc.) ne les supportent pas encore nativement autrement que par des extensions spécifiques pour certaines applications.

Définitions[modifier | modifier le code]

Définition étendue[modifier | modifier le code]

Les NURBS sont utilisées pour représenter mathématiquement des objets géométriques. Elles généralisent la représentation par les B-splines des courbes et des surfaces en ajoutant un dénominateur. Elles sont en fait définies avec des points en coordonnées homogènes. Une B-spline ressemble à une représentation polynomiale par morceaux, alors qu'une NURBS est une représentation par fractions rationnelles par morceaux. Notamment utilisées dans les logiciels d'édition 3D, ces fonctions d'ajustement sont particulièrement utilisées dans le domaine de l'informatique, plus précisément dans la compression d'images et dans le design assisté par ordinateur, afin de générer et représenter des formes douces et ergonomiques. Du fait qu'elle présentent de nombreux avantages, leur utilisation est largement répandue :

  • facilité et précision pour évaluer une forme
  • capacité pour approximer des formes complexes
  • simplicité de construction et d'implémentation
  • faible complexité des algorithmes utilisés

Vecteur nodal[modifier | modifier le code]

Le vecteur nodal est une séquence de valeur de paramètre qui détermine où et comment les points de contrôle vont affecter la forme. Le nombre de nœuds est toujours égal au nombre de point de contrôle plus le degré de la forme plus 1, i.e. étant donné un vecteur nodal T, n points de contrôles et un degré d,

alors \#T = n + d + 1.

Le vecteur nodal divise l'espace paramétrique dans des intervalles mentionnés précédemment.

A chaque fois que le paramètre entre dans un nouvel intervalle nodal, un nouveau point de contrôle devient actif tandis qu'un plus ancien devient inactif.

Ceci garanti donc l'influence locale des points de contrôles.

Un vecteur nodal est défini par une séquence de nœud où

les nœuds ont des valeurs comprises entre 0 et 1 (i.e. t_i \leq t_{i+1}$).

Par exemple en considérant m+1 nœuds le vecteur va se présenter sous la forme: U = (t_0, t_1, \cdots, t_m).

Des nœuds consécutifs peuvent avoir des valeurs identiques,

ceci est définit par la multiplicité d'un nœud et permet d'accentuer l'influence d'un point sur la courbe.

Par exemple, le premiers et le dernier point du polygone de contrôle sont par convention multiple. Les d+1 premiers nœuds sont nuls et les d+1 derniers nœuds sont égaux à 1, i.e. T=(\underbrace{0, \cdots, 0}_{d+1}, t_{d+1}, t_{d+2}, \cdots, t_{m-d-1}, t_{m-d}, \underbrace{1, \cdots ,1}_{d+1}).

Courbes possédant le même polygone de contrôle et des vecteurs nodaux différents (a) T = \big(0,0,0,0,\frac{1}{4},\frac{1}{2},\frac{3}{4},1,1,1,1\big), (b) T = \big(0,\frac{1}{10},\frac{1}{5},\frac{3}{10},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{7}{10},\frac{4}{5},\frac{9}{10},1\big).

Ceci oblige alors la courbe à passer par le premier ainsi que par le dernier point du polygone de contrôle

De plus, lorsque que l'écart entre chaque nœud consécutifs du sous-ensemble t_{d+1}, \cdots, t_{m-d} est identique,

i.e. t_{i} = \frac{i - d - 1}{m - 2d - 1} | i \in [d+1, m-d] , le vecteur est uniforme est la courbe l'utilisant est dite uniforme.

Définition formelle[modifier | modifier le code]

Fonction de base[modifier | modifier le code]

Les fonctions de base des NURBS de degré d sont définies par la formule doublement récursive de Cox-De Boor :

\left\{\begin{array}{ll}N_{j}^0(t)= \left\{
    \begin{array}{ll}
        1 & si\; t_j \leq t < t_{j+1} \\
        0 & sinon
    \end{array}
\right.\\
N_{j}^d(t)= \frac{t-t_j}{t_{j+d}-t_j} N_{j}^{d-1}(t)+\frac{t_{j+d+1}-t}{t_{j+d+1}-t_{j+1}}N_{j+1}^{d-1}(t)\end{array}\right.

où les t_j sont des nœuds appartenant au vecteur nodal, et d le degré de la NURBS.

Lorsque plusieurs nœuds t_j sont confondus, on pose \frac{0}{0}=0.

Les courbes NURBS[modifier | modifier le code]

La formule des courbes NURBS possède de grandes correspondances avec celle des B-splines. Elle est simplement généralisée afin d'être appliquée à des coordonnées homogènes.

Ainsi la formule d'une courbe NURBS est illustré de la manière suivante:

C(t)=\frac{\sum_{i=1}^{m-n-1}\omega_iP_iN_{i}^{n}(t)}{\sum_{i=1}^{m-n-1}\omega_iN_{i}^{n}(t)} où les w_i sont les coordonnées homogènes des points de contrôle donnés P_i, m le nombre de nœuds, n le degré de la NURBS, N_{i}^{n} les coefficients calculés selon l'algorithme de Cox-de Boor, et t \in [0,1] le paramètre.

Courbe NURBS
Courbe NURBS avec variation de la coordonnée homogène de P_1. Lorsque la coordonnée homogène est nulle, le point P_1 n'a aucune influence sur la courbe.

La dérivée d'une courbe NURBS en un point représente le vecteur tangent à la courbe en ce point.

La formation de la dérivée est un peu plus complexe et s'exprime de la manière suivante:

\frac{\partial C(u)}{\partial u} = C'(u) = 
				\frac{\sum_{i=0}^{m-n-1} \omega_i P_i N_i^n(u)'  \sum_{i=0}^{m-n-1} \omega_i N_i^n(u)}{(\sum_{i=0}^{m-n-1} \omega_i N_i^n(u) )^2}
				-
				\frac{\sum_{i=0}^{m-n-1} \omega_i P_i N_i^n(u)  \sum_{i=0}^{m-n-1} \omega_i N_i^n(u)'}{(\sum_{i=0}^{m-n-1} \omega_i N_i^n(u) )^2}

où:

N_i^n(t)' = \frac{n}{t_{i+n} - t_i}N_i^{n-1}(t) - \frac{n}{t_{i+n+1} - t_{i+1}}N_{i+1}^{n-1}(t)

Les surfaces NURBS[modifier | modifier le code]

Les surfaces NURBS dépendent de deux degrés n_u et n_v ainsi que de deux vecteur nodaux (resp. pour u et v).

Elles ne sont plus contrôlées par un polygone mais par un réseau de contrôle comprenant les point P_{i,j}.

SurfaceNURBS
Surface NURBS definie par un réseau de contrôle.

Ainsi la formule générale d'une surface NURBS s'exprime de la manière suivante:

	S(u,v) =  \frac{\sum_{i=0}^{m_u-n_u-1}  \sum_{i=0}^{m_v-n_v-1} N_i^{n_u}(u) N_i^{n_v}(v) \omega_{i,j} p_{i,j} }{\sum_{i=0}^{m_u-n_u-1} \sum_{i=0}^{m_v-n_v-1} N_i^{n_u}(u) N_i^{n_v}(v) \omega_{i,j} }, avec (u,v) \in [0,1]^2

La dérivée partiel de la surface en un point représente la tangence en ce point selon une direction (u et v).

Pour u elle s'exprime de la manière suivante:

\frac{\partial S(u,v)}{\partial u} = 
S_u(u,v) = \frac{R_u(u,v)\Omega(u,v) - R(u,v)\Omega_u(u,v)}{\Omega(u,v)^2}

où :

R(u,v) = \sum_{i=0}^{p_u} \sum_{j=0}^{p_v} N_i^{n_u}(u) N_j^{n_v}(v) P_{i,j}\omega_{i,j}
,

R_u(u,v) = \sum_{i=0}^{p_u} \sum_{j=0}^{p_v} N_i^{n_u}(u)' N_j^{n_v}(v)P_{i,j}\omega_{i,j}
,

\Omega(u,v) = \sum_{i=0}^{p_u} \sum_{j=0}^{p_v} N_i^{n_u}(u) N_j^{n_v}(v)\omega_{i,j}
,

et \Omega_u(u,v) =\sum_{i=0}^{p_u} \sum_{j=0}^{p_v} N_i^{n_u}(u)' N_j^{n_v}(v)\omega_{i,j}
.

La formulation est similaire pour \frac{\partial S(u,v)}{\partial v}.

Exemples[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Les Piegl & Wayne Tiller The Nurbs Book éditeur Springer ISBN 3-540-61545-8