Marching cubes
Le marching cubes est un algorithme d'infographie publié à la conférence SIGGRAPH 1987 par Lorensen et Cline. Il permet de créer un maillage polygonal à partir d'un champ scalaire en trois dimensions (son unité élémentaire est souvent appelée voxel), en principe créé par approximation d'une isosurface.
Il est le pendant 3D de l'algorithme marching squares.
Principe de fonctionnement
[modifier | modifier le code]Cet algorithme parcourt le champ scalaire, prenant huit points à la fois (définissant ainsi un cube imaginaire), et détermine les polygones à créer (si polygone à créer il y a) pour représenter une partie de l'isosurface contenue dans ce cube.
Ceci fonctionne en créant un index dans un tableau précalculé des 256 configurations de polygones possibles () dans un cube, en traitant chacune des 8 valeurs scalaires comme un bit dans un nombre entier de 8 bits. Si la valeur scalaire est supérieure à la valeur de l'isosurface (i.e., est à l'intérieur de la surface), alors le bit correspondant est mis à 1, sinon il est mis à 0. La valeur finale après le test des 8 points est l'index de la bonne configuration polygonale dans le tableau précalculé.
Finalement, chaque sommet des polygones créés est placé à sa position finale le long de l'arête du cube, en interpolant linéairement les deux valeurs scalaires connectés par cette arête.
Les 256 valeurs du tableau de configuration des polygones sont précalculées par réflexion et symétrie à partir de 15 cas possibles.
La valeur à chaque point du champ scalaire est aussi utilisée pour calculer le vecteur normal de l'isosurface passant en ce point. Ce calcul est basé sur le gradient du champ. Il est donc possible d'interpoler ces valeurs le long de chaque arête de chaque cube de façon à obtenir la normale des points sur la surface. L'interpolation permet d'éviter un calcul analytique du gradient pour une position quelconque. Le calcul des normales permet l'ombrage de l'objet par la suite.
Applications
[modifier | modifier le code]Les applications principales de cet algorithme sont du domaine de la visualisation médicale, comme la reconstruction de surfaces à partir des images issues de scanners ou d'IRM. L'algorithme peut également être mis en œuvre pour des effets spéciaux et des outils infographiques comme la modélisation 3D d'objets organiques (metaballs et toutes autres isosurfaces).
Brevets
[modifier | modifier le code]Cet algorithme est le premier exemple de brevet logiciel dans le domaine de l'infographie. Un algorithme similaire, appelé « Marching Tetrahedrons », a été développé de façon à contourner ce brevet et quelques problèmes topologiques mineurs liés à l'utilisation de cubes. Le brevet couvrant les Marching cubes a expiré : il a été déposé le au Bureau des brevets des États-Unis, le délai de 20 ans ayant expiré, son implémentation et son utilisation sont désormais libres de droit.
Le problème du brevet ne se posait pas pour les utilisations à l'intérieur d'un pays ne couvrant pas les brevets logiciels, comme la France, ou la majorité des pays d'Europe.
Références
[modifier | modifier le code]
Voir aussi
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- "The Marching Cubes Algorithm", voir crédits sur la page
