Algorithmes du Marching Square et Marching Cube

De Physix.

Les algorithmes du Marching Square et Cube permettent de représenter une isovaleur d'une potentiel (un contour pour le Marching Square et une surface pour le Marching Cube).

Nous allons expliquer le fonctionnement du Marching Square, la généralisation en 3D pour le Marching Cube est facile. Nous verrons les résultats sur le Marching Cube.

Explication du Marching Square

Nous cherchons à approcher un contour par un ensemble de segments. Le contour est défini par un isopotentiel.

Pour l'exemple .

C'est donc le quart de cercle unité. Considérons tout d'abord le carré . Découpons-le en quatre carrés (les milieux des segments). Et ainsi de suite à partir de chaque carré on construit 4 autres plus petits carrés. On s'arrête un moment. Plus on voudra être précis, plus il faudra découper, mais hélàs plus on aura beaucoup de carrés (temps d'exécution plus lent).

Le carré initial

Première découpe

Deuxième découpe

Maintenant on va construire nos segments comme ceci : on joint les milieux des segments dont les extrémités sont de part et d'autre de l'isopotentiel.

Le carré initial

Première découpe

Deuxième découpe

Troisième découpe

Cependant nous allons améliorer un peu cet algorithme, l'idée est qu'au lieu de prendre le milieu on peut prendre les points d'intersection (Une simple dichotomie en plus). L'ensemble des carrés forment une grille, on lie les points d'intersection entre la grille et le contour. On voit très bien que plus on divise nos carrés plus on se rapporche du contour. Ceci nous permet d'être plus précis pour un niveau de récursion plus faible. Cela va accélérer l'algorithme.

Le carré initial

Première découpe

Deuxième découpe

N.B.: Pour calculer les points d'intersection, on fait une dichotomie le long de chaque coté des carrés. Ceci nous impose que sur l'isopotentiel, le potentiel doit changer de signe (pour les potentiels différentiables, il faut que le gradient soit non-nul aux points où le potentiel vaut notre isovaleur).

Vous trouverez sur internet bons nombres de sites internet expliquant qu'il y a 16 cas différents à traiter dans les algorithmes de Marching Square et Marching Cube. Il y a une autre façon de traiter cela : on découpe le carré en triangles et le cube en tétrahèdres ensuite pour le cas de l'intersection d'une ligne ou d'une surface d'isopotentiel avec un triangle ou un tétrahèdre est beaucoup plus simple puisqu'il y a moins de cas.

Résultats du Marching Cube

Voilà les résultats de l'algorithme du Marching Cube sur un potentiel d'une ellipse.

Comme pour le Marching Square, nous découpons chaque cube en 8 petits cubes :

A gauche l'algorithme standard du Marching Cube. A droite l'algorithme du Marching Cube avec notre petite amélioration de la dichotomie.

découpe #1

découpe #2

découpe #3

découpe #4

découpe #5

découpe #6

On voit immédiatement le gain de notre petite astuce.

Nous avons dit plus haut que pour des raisons de simplicité nous avons découpé chaque cube en tétrahèdres pour enfin calculer facilement les triangles approchant la surface.

Le gros cube => 5 tétrahèdres