Marching squares

Le marching squares désigne un algorithme d'infographie qui permet la construction de courbes de niveau ou courbes isovaleurs d'un champ scalaire sur une surface maillée par des quadrangles. Un algorithme tout à fait identique permet de tracer les isovaleurs sur une surface maillée par des triangles.

Les quatre différentes teintes grisées des cellules représentent les valeurs prises par un champ de température sur un maillage. La ligne en rouge est la courbe de niveau délimitant les carrés noirs : elle peut être obtenue par marching squares.

L'algorithme des marching squares procède, comme l’algorithme 3D marching cubes, en quatre étapes successives :

• traitement individuel de chaque quadrangle du maillage.
• Calcul d'un indice d'élément par comparaison de l'échelle d'isovaleurs choisie aux valeurs connues aux sommets (coins) de l'élément quadrangulaire. Il existe 16 configurations possibles de découpage d'un carré par une ligne, ce qui permet de coder l'indice sur 4 bits.
• Détermination par cet indice des côtés du quadrangle auxquels aboutit la ligne isovaleur (par consultation d'une table).
• Calcul de la position des extrémités de l'isovaleur le long de ces côtés par interpolation linéaire.

Cet algorithme, bien que rapide et totalement parallélisable, présente des problèmes de précision dans certains cas particuliers, difficiles à résoudre de manière automatique.