Marching Cubes

Marching Cubes

Marching cubes

Tête et structures cérébrales (cachées) obtenues par l'application des marching-cubes sur 150 tranches provenant d'un IRM (env. 150'000 triangles)

Les « marching cubes » désignent un algorithme d'infographie publié à la conférence SIGGRAPH 1987 par Lorensen et Cline. Ils permettent de générer un objet polygonal à partir d'un champ scalaire en trois dimensions (son unité élémentaire est souvent appelée voxel), en principe généré par approximation d'une isosurface.

Il est le pendant 3D de l'algorithme des « marching squares ».

Sommaire

Principe de fonctionnement

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 (28 = 256) 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 généré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.

Les 15 cas possibles de configuration des polygones

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

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

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 5 juin 1985 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[1].

Voir aussi

Références

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Marching cubes ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Marching Cubes de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Marching cubes — Head and cerebral structures (hidden) extracted from 150 MRI slices using marching cubes (about 150,000 triangles) Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline,[1] …   Wikipedia

  • Marching Cubes — Polygonmodell eines Kopfes, der mittels Marching Cube aus 150 MRT Schichten extrahiert wurde ( 150.000 Dreiecke) Marching Cubes ist ein Algorithmus zur Berechnung von Isoflächen in der 3D Computergrafik. Er nähert eine Voxelgrafik durch eine… …   Deutsch Wikipedia

  • Marching cubes — Модель, построенная из 150 слоев с МРТ с использованием алгоритма marching cubes. Под поверхностью находятся около 150 000 полигонов и скрытых объектов. Размер сетки составляет 64 × 64 × 150 вокселей, кодированных 8 ю… …   Википедия

  • Marching cubes — Tête et structures cérébrales (cachées) obtenues par l application des marching cubes sur 150 tranches provenant d un IRM (env. 150 000 triangles) Les « marching cubes » désignent un algorithme d infographie publié à la conférence… …   Wikipédia en Français

  • Marching Tetrahedra — Introduction Cette méthode est destinée à représenter la surface définie par , avec f une fonction définie sur l espace. Le principe de base est identique au marching cubes. On notera alors que le marching cubes est une technique ayant fait… …   Wikipédia en Français

  • Marching Squares — Les Marching squares designent un algorithme de reconstruction de surface implicites (ou isosurfaces) en deux dimensions. Le principe est le même que pour les Marching cubes, mais fonctionnant sur un plan, utilisant donc des carrés au lieux de… …   Wikipédia en Français

  • Marching squares — is a computer graphics algorithm that generates contours for a two dimensional scalar field (rectangular array of individual numerical values). A similar method can be used to contour 2D triangle meshes. The contours can be of two kinds: Isolines …   Wikipedia

  • Marching Cube — Polygonmodell eines Kopfes, der mittels Marching Cube aus 150 MRT Schichten extrahiert wurde ( 150.000 Dreiecke) Marching Cubes ist ein Algorithmus zur Berechnung von Isoflächen in der 3D Computergrafik. Er nähert eine Voxelgrafik durch eine… …   Deutsch Wikipedia

  • Marching tetrahedrons — A cube divided into six tetrahedrons, with one tetrahedron shaded Marching tetrahedrons is an algorithm in the field of computer graphics to render implicit surfaces. It clarifies a minor ambiguity problem of marching cubes with some cube… …   Wikipedia

  • Marching tetrahedra — Cette méthode est destinée à représenter la surface définie par , avec f une fonction définie sur l espace. Le principe de base est identique au marching cubes. On notera alors que le marching cubes est une technique ayant fait l’objet d’un… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”