Marching tetrahedra
Le marching tetrahedra est un algorithme alternatif et similaire au marching cubes, permettant d'approcher une isosurface d'une fonction réelle en 3D, dont les valeurs sont uniquement disponibles aux sommets de cubes décomposant l'espace. Il a été proposé pour la première fois en 1991[1].
Contexte
[modifier | modifier le code]La méthode permet de représenter l'isosurface définie par , avec f une fonction définie sur l'espace. Le principe de base est identique au marching cubes.
Le marching cubes est une technique ayant fait l’objet d’un brevet, alors que la technique du marching tetrahedra a été créé pour contourner ce brevet[réf. nécessaire].
Algorithme
[modifier | modifier le code]L'espace tridimensionnel est décomposé en cubes. Chaque cube qui possède à la fois des sommets où la fonction f prend des valeurs supérieures et des valeurs inférieures au seuil contient un bout de l'isosurface. Chacun de ces cubes traversés par l'isosurface est alors décomposé en six tétraèdres.
Dans le tétraèdre, en fonction du nombre et de la position des sommets qui ont une valeur supérieure ou inférieure au seuil, huit configurations différentes peuvent être observées.
Pour chaque arête dont un sommet a une valeur supérieure et l'autre une valeur inférieure au seuil, la position de l'intersection avec l'isosurface est calculée par interpolation linéaire.
Pour chaque tétraèdre concerné, un ou deux triangles approximant l'isosurface sont alors créés.
Pour le reste, la méthode est la même que pour le marching cubes.
Notes et références
[modifier | modifier le code]- Akio Doi et Akio Koide, « An Efficient Method of Triangulating Equi-Valued Surfaces by Using Tetrahedral Cells », IEICE Transactions of Information and Systems, vol. E74-D, no 1, (lire en ligne)
