Modélisation 3D – Tour d’horizon

Les types de modélisation

Par nuage de points

Pas grand chose à dire sur cette méthode, elle relie 3 points afin de former un triangle, et fait une sorte de maillage en procédant ainsi et en formant une multitude de triangles reliés par leur sommet. Au final on obtient une forme en 3D. A noter que c’est la méthode de modélisation qu’utilise la Kinect de Microsoft pour vous modéliser dans les jeux !

Par polygône

C’est la même chose sauf le le maillage de triangles va être fait à la main, et non pas en reliant des points dans un nuage de points. Dans ces principes, plus il y a de triangles, plus la forme est bien définie, mais plus le calcul est long (logique Captain Obvious !). Les triangles peuvent être générés de 2 façons :

Soit en « Strip« , c’est à dire en « bande », on fait un ruban en ajoutant les triangles côte à côte :

strip

Source : https://karczmarczuk.users.greyc.fr/TEACH/InfoGeo/Images/strip.png

Soit en ‘Fan‘, en éventail, et dans ce cas, un point central servira de sommet commun aux triangles :

fan

Source : http://jc-tchang.philohome.com/manuel/Images_LD_fileF/LDrawPoly2.jpg

Au niveau de la programmation, ces données sont stockées dans 3 tableaux :

  • Sommets : [1, 5] index 1 , [8, 5 ] index 2, … : les deux chiffres pour chaque sommet représentent les coordonnées
  • Arrêtes : [1,2], [3, 4 ], … : les chiffres contenus dans ce tableau représentent les index des sommets.
  • Polygônes : [AB,BC,AC], … : les polygônes générés par les arrêtes et sommets sont stockés dans un tableau à part.

B-Rep (Boundary representation)

Il existe plusieurs méthodes que je ne vais détailler : NURBS, B-Splines, ou les fameuses courbes de Bézier ! ( Note : SI en fait je vais détailler ces dernières, un peu plus loin dans l’article)

Extrusion

Cette méthode consiste à prendre une forme de base 2D, et à s’en servir comme moule pour créer une forme 3D. Bien sûr n’oubliez pas que je vulgarise toutes mes définitions :p

Par exemple, si on prend un cercle de base et qu’on va l’étirer en hauteur cela va nous donner un cylindre. C’est cela que l’on appelle l’extrusion. Cette méthode est très utilisée dans les logiciels de CAO/DAO (dessin industriel, plans 3D, …)

Géométrie de construction de solides (CSG)

On assemble des formes de bases, (comme des sphères, cylindres, parallélépipèdes rectangles, cônes, tores, …) de façon à former une forme plus complexe.

Pour assembler ces formes on utilise 3 symboles qui sont :

  • l’intersection : conserve uniquement les volumes qui sont confondus (l’équivalent d’un ET )
  • l’union U : conserve tout (c’est l’équivalent d’un OU)
  • et la différence : on soustrait un volume à un autre (retire la forme du volume, lorsque deux volumes sont confondus)

csg

Par exemple, si on veut modéliser une bouteille d’eau (grossièrement) on pose sur un cylindre un cone, puis on va faire l’union d’une sphère sur le dessus du cône pour faire le bouchon de la bouteille.

Surface de subdivision

On insère des polygones dans d’autres afin de polir les bords (Note : l’algorithme utilisé est celui de Catmull Clark). Cette technique est utilisée en différé et non en temps réel. Pourquoi ?

Car elle demande de long calcul et n’est donc pas optimisée pour un traitement en temps réel d’un moteur 3D, mais l’est pour le différé, c’est à dire pour les animations calculées et compilées à l’avance puis rendues.

Par exemple sur un bloc de pierre modélisé par une sphère, on va supprimer une partie des sommet, et le remplacer par des polygones, pour augmenter la précision de notre forme :

subdivision

Source http://perso.esiee.fr/~perrotol/TheRedBook-1.0/chapter02.html

Modélisation explicite de volume

Cette méthode va être utilisée pour modéliser principalement des objets souples, déformables ou dissociables. Comme différentes couches d’affichages, ou la représentation d’un liquide, d’un élastique … On simule le volume plein, par une multitude d’éléments soumis aux même lois. Chaque élément peut faire partie d’une « famille » qu’on décide d’afficher ou non.

Par exemple pour afficher des parties de couleurs sur un scan d’un cerveau humain (miam ! bel exemple tiens !), les pixels rouges auront une catégorie, les orange une autre et les jaune encore une … de cette façon on peut décider d’afficher ou non, telle ou telle zone représentée par une couleur.

 

Les courbes de Bézier

Je l’avais promis, voici la petite introduction aux courbes de Bézier. Bézier, qui soit dit en passant, était un ingénieur français, de chez Renault ! Il lui avait été demandé de modéliser facilement des courbes pour le tracé des carrosseries de l’époque. De Casteljau, ingénieur de chez Citröen et lui-même ont donc travaillé sur cette méthode.

John Warnock (qui n’est rien d’autre que le fondateur d’Adobe) avait à l’époque eu l’idée d’utiliser cette méthode révolutionnaire afin de modéliser des jolies polices de caractères pour les imprimantes.

Ces courbes sont utilisées a peu près partout. Dans les images vectorielles (type SVG, PNG, …) dans les canvas (HTML5, …) dans une tonne de logiciel de graphisme et de modélisation 3D (Blender, Photoshop, GIMP, …)

Le barycentre

Bon pour comprendre comment cela fonctionne, il faut assimiler les barycentres. Rien de plus simple, un barycentre est un point d’équilibre à une forme. Il est relatif au poids que l’on applique sur ses deux côtés :

barycentreEn admettant dans ce schéma qu’une barre relie deux poids : un de 3 kilos et l’autre de 1 kilo. Le barycentre est ici situé à 1 quart de la distance par rapport au poids le plus lourd, et on comprend avec logique qu’il correspond au point d’équilibre pour maintenir la barre horizontale. En admettant que le centre du poids de gauche s’appelle A, le point d’équilibre O et le centre du poids de droite B; on peut poser la formule suivante :

Poids gauche * OA = Poids droite * OB

Les courbes de degré 1

Maintenant que l’on sait ce qu’est un barycentre, nous allons attaquer le tracé des courbes de Bézier. Une courbe de Bézier de degré 1 est une courbe tracée à l’aide de deux points.

curb_first_degreeAvec t appartenant à [0,1] le barycentre est donc ici caractérisé par le point N(0.5) => A(1, – t) (B, t)

Les courbes de degré 2

C’est ici que vous allez commencer à comprendre et voir que ce sont de vraies courbes ;) Car sur l’exemple du dessus, la courbe est confondue sur le segment [AB]. Ici nous allons prendre 3 points (A,B et C) et les disposer, puis nous allons tracer la courbe.

Note : Vous avez remarqué que lorsque l’on prend x points, le degré de la courbe de Bézier associée est x-1.

courbes_bezier_d2Ici pour trouver le barycentre de cette forme, on va prendre la moitié de chaque segment, puis tracer un trait qui relie les deux points de milieu. Puis on reprend la moitié du segment tracé, et on obtient le barycentre de la figure ABC !

La figure suivante peut s’exprimer ainsi :

  • P1   (A, 1 -t ) (B, t)
  • P2  (B, 1 -t ) (C, t)
  • N    (P1, 1- t) (P2, t)

La courbe se trace en partant du premier point et en finissant sur le dernier (pour toutes les figures, quelques soit leur nombre de points).

Plus le degré d’une courbe est grand, plus elle est précise, nous allons voir cela de nos propres yeux en traçant une courbe de 3ème degré (avec 4 points donc !)

Courbes de 3ème degré

courbes_bezier_d3Bon pour cette courbe je n’ai pas tracé toutes les lignes, seulement les tracés de N(0.25), mais il faut aussi passer par N(0.5) et N(0.75) pour pouvoir placer correctement les 3 points. On voit que la courbe ici est plus dessinée (en gris). Le procédé est le même que précédemment mais on va ajouter des étapes.

  1. Je découpe [AB] aux 1/4 (P1)
  2. Je découpe [BC] aux 1/4 (P2)
  3. Je relie P1 et P2
  4. Je découpe [CD] aux 1/4 (P3)
  5. Je relie P2 et P3
  6. sur [P1 P2] je découpe aux 1/4 (P4)
  7. sur [P2 P3] je découpe aux 1/4 (P5)
  8. Je prend 1/4 de [P4 P5], j’obtiens mon point en N(0.25) ou passe la courbe !
  9. Et je répète les même opérations en prenant 1/2 et enfin 3/4.
  10. Et il suffit de partir de A, passer par les points N et finir en D.

Les étapes sont les mêmes pour les degrés suivant mais je ne les décrirais pas car ça devient long :)

La formule de Bernstein

Il existe un polynôme déniché par Sergeï Bernstein (Captain Obvious a encore frappé ! en fait non, je me suis renseigné il existe plusieurs mathématiciens du nom de Bernstein !) qui permet de formuler des courbes de Bézier de degré n. L’avantage des méthodes vues ci-dessus réside dans leur simplicité pour les petits degrés (1,2,3) et dans leur facilité de compréhension, l’avantage du théorème de Bernstein se trouve lui, dans la facilité de calcul pour des des degrés qui dépassent 3, 4. Cette formule se présente sous la forme suivante :

Source Wikipédia

Source Wikipédia

Avec le valeurs suivantes : m et i sont les coefficients binomiaux et u est l’inconnue ! (on le sait on la met en argument dans la fonction !!!) Les parenthèses représentent bien sûr la somme de la partie de droite, avec i+1 jusqu’à i=m (∑).

Le coefficient multiplicateur de chaque itération est défini selon le degré de la courbe en question selon la règle suivante :

Degré 1 : 1 1

Degré 2 : 1 2 1

Degré 3 : 1 3 3 1

Degré 4 : 1 4 4 4 1

… etc vous aurez probablement saisi la suite ;)

A chaque itération dans le calcul, on utilise donc la valeur suivante  dans la ligne correspondante.

Et pour les coefficients binomiaux rien de plus simple : i est égal à 0 puis est incrémenté de 1 à chaque itération (c’est le compteur), et m est égal au degré de la courbe.

Typiquement voici un exemple de calcul que l’on pourrait faire avec cette formule, pour modéliser une courbe de Bézier de degré 2 avec les points suivants A(1,1), B(3, 4) et C(7, 0) :

Vecteur OM = 1 u^0 (1 – u) ^2 * Vecteur OA + 2u^1 (1-u)^1 * Vecteur OB + 1u^2 (1 – u)^0 * Vecteur OC

Avant de continuer avec le détail du calcul, j’aimerais expliquer le code couleur  : les valeurs en bleu représentent les constantes sur la ligne correspondante au degré de la courbe (comme dans l’exemple au dessus, à la ligne du degré 2), les valeurs en vert sont le coefficient binomial i, qui est incrémenté à chaque itération du calcul et les valeur en rouge représentent m – i

Vecteur OM = (1 – u)^2 * Vecteur OA + 2u (1 – u) * Vecteur OB + t^2 * Vecteur OC

On découpe ensuite le calcul en deux parties : l’un avec les valeurs en X des vecteurs, et l’autre avec les valeur en Y :

xn = 1 * 1 (1 – u)^2 + 2 * 3 (1 – u) + 1 * 7u^2

yn = 1 * 1 (1 – u)^2 + 2 * 4 (1 – u)  + 1 * 0*u^2

Au final on a donc un xn =  (1 – u)^2 + 6 (1 – u) + 7u^2 et un yn =  (1 – u)^2 + 8(1 – u) .

J’ai essayé d’expliquer avec des termes qui ne sont pas toujours juste, n’étant pas spécialisé en mathématiques, j’aime à vulgariser les connaissances en mathématiques pour mieux les appréhender.

Pages: 1 2 3

Laisser un commentaire