s
19 708 Pages

marching cubes (Littéralement: cubes de marche) est un algorithme de infographie, publié au SIGGRAPH la 1987 par Lorensen et Cline[1] pour extraire une maillage de polygones un isosurface par un champ scalaire 3D (Parfois appelé voxel). L'algorithme est principalement utilisé dans le domaine de la radiologie par l'imagerie diagnostique, par exemple CT et l 'IRM, mais aussi dans la création d'effets spéciaux de nell'amibito modélisation 3D, avec metaball ou metasuperfici. Un procédé analogue à deux dimensions est appelé carrés de marche.

marching cubes
des structures de tête et le cerveau (caché) extraites de 150 IRM découper à l'aide des marche-cubes (environ 150 000 triangles)

histoire

L'algorithme a été développé par William E. Lorensen et Harvey E. Cline à la suite de leurs recherches au General Electric. General Electric, ils ont travaillé si efficacement les données visuallizzare à partir d'appareils TDM et d'IRM.

marching cubes
15 configurations uniques

Leur première version publiée a exploité une symétrie de rotation et de réflexion ainsi que des changements particuliers dans la construction d'une table avec 15 configurations uniques. Cependant, le traitement des visages, il y a des cas ambigus.[2] Ces cas ambigus peuvent conduire à engrener avec des trous. topologiquement parlant, isosurfaces corrects peuvent impliquer un effort supplémentaire.[3]

Le problème est créé pour les cas en présence de double signe, que l'on trouve au moins deux bons choix dont le profil est valide. Le choix réel n'a pas d'importance, mais doit être topologiquement cohérente. Les principaux cas conduisent à des choix cohérents, mais le changement de signe peut entraîner des erreurs. Le tableau étendu en[3] 33 montre les configurations.

Les ambiguïtés ont été améliorées avec le développement de nouveaux algorithmes comme en 1991 decider asymptotique Nielson et Hamann[4] qui corrige ces anomalies.[5][6] Plusieurs autres de l'analyse des ambiguïtés et des améliorations ont été proposées depuis lors; voir l'enquête de Lopes 2005 et Bordlie, par exemple.[6]

Description de l'algorithme

L'algorithme passe à travers le champ scalaire, en prenant à la fois huit emplacements adjacents (formant ainsi un cube imaginaire), à ​​déterminer par conséquent le polygone ou polygones nécessaires pour représenter la partie de l'isosurface en passant par ce cube. Les polygones individuels sont ensuite fusionnés à la surface souhaitée.

Cela se fait en créant un index dans un tableau précalculée de 256 polygones de configurations possibles () A l'intérieur du cube, en traitant chacune des 8 valeurs scalaires en tant que bit dans un plein de 8 bits. Si la valeur du scalaire est supérieure à la valeur-iso (qui est à l'intérieur de la surface), alors le bit correspondant est mis à un, alors que si elle est plus faible (externe) est mis à zéro. La valeur finale après les 8 scalaires sont contrôlés, est l'indice de matrice de la configuration de polygone.

Enfin, chaque sommet polygones générés est mis dans la position appropriée le long du côté du cube interpolation linéaire les valeurs des deux scalaire qui sont connectés à ce côté.

La matrice précalculée de 256 configurations peuvent être obtenues par réflexion et rotations symétrique de seulement 15 cas.

Le gradient de champ scalaire à chaque point de la grille est aussi le vecteur normal d'une isosurface hypothétique à partir de ce point. Par conséquent, nous devons interpoler ces Normales le long des charnières de chaque cube pour trouver les Normales des sommets générés qui sont essentiels à l'ombre du maillage résultant avec un certain modèle d'éclairage.

Les questions relatives aux brevets

L'algorithme de cubes de marche de l'algorithme est considéré par les partisans de logiciel libre un boîtier principal dans le domaine de infographie les maux de logiciel propriétaire [citation nécessaire]. Ils font valoir que la mise en œuvre exclusive (brevet 4710876[7]) Est relativement évidente au problème de la génération de surface. Il a été développé un algorithme similaire tétraèdres appelé Marching afin d'éviter le brevet, en plus de résoudre certains cas d'ambiguïté avec une partie de la configuration du cube. La licence de l'algorithme de marching cubes a expiré en 2005 et est maintenant légal pour la communauté dans le domaine de l'infographie utiliser l'algorithme libre de droits depuis plus de 18 ans à compter de sa date d'émission (1 Décembre, 1987[7]).

notes

  1. ^ William E. Lorensen, Harvey E. Cline: Marching Cubes: Un algorithme de construction de surface 3D à haute résolution. dans: Computer Graphics, Vol. 21, Nr. 4, Juillet 1987
  2. ^ Les cubes Marching.
  3. ^ à b Marching Cubes 33: Construction de topologiquement Corriger Isosurfaces.
  4. ^ Gregory M. Nielson et B. Hamann, Le decider asymptotique: résoudre l'ambiguïté dans les cubes de marche, en VIS '91 Compte rendu de procéder de la 2ème conférence sur la visualisation '91, 1991.
  5. ^ Charles D. Hansen et Chris R. Johnson, Manuel de visualisation, Academic Press, 2004, p. 9 ISBN 978-0-12-387582-2.
  6. ^ à b A. Lopes et K. Bordlie, approches interactives et de contournage isosurfaces pour géovisualisation, dans Jason Dykes, Alan M. MacEachren Kraak et M. J. (eds), explorer Géovisualisation, Elsevier, 2005, pp. 352-353, ISBN 978-0-08-044531-1.
  7. ^ à b (FR) United States Patent 4710876, États-Unis des brevets et des marques Office.

Articles connexes

  • algorithme
  • Infographie 3D