Compréhension Marching cubes

Version imprimable

13/12/2011, 17h16
on2101

Compréhension Marching cubes

Bonjour à tous et à toutes,

Je travaille actuellement sur l algorithme Marching Cubes et je coince sur la compréhension de l algorithme. Peut etre pourres vous m apporter votre aide ;)

Tout d abord, a quoi sert l algorithme. Cet algorithme permet d extraire une isosurface (f(x,y,z) = alpha). En sortie, on obtient des triangles (un mesh) représentant l objet 3D étudié.

Je ne comprend pas bien ce que l algo prend en entrée. Je pensais au départ qu il s agissait d un nuage de points 3D, est ce bien le cas ?

Des cubes sont utilisés dans la méthode, définis par leurs sommets. Les sommets ne peuvent correspondre aux points du nuage si ce dernier n a pas ses points uniformements repartis. Les cubes sont ils construits de manière régulière (une simple grille, ou les sommets des cubes ne sont pas des points du nuage) ou bien le nuage de points doit il absolument etre aligné (cad points = sommets des cubes) ?

Enfin, je ne vois pas quelle est la fonction dont on extrait l isosurface. Quel est le lien entre cette fonction, et les données de départ ? Autrement dit, comment affecter à un point (ou sommet des cubes) une valeur qui servira ensuite a extraire l isosurface ?

Je comprend la suite de l algorithme, avec les différentes configurations, ... mais je bloque vraiment la première partie.

Merci de m'avoir lu, et de me faire partager votre savoir ;)
13/12/2011, 18h11
pseudocode

Citation:

Envoyé par on2101

Je ne comprend pas bien ce que l algo prend en entrée. Je pensais au départ qu il s agissait d un nuage de points 3D, est ce bien le cas ?

Non, l'algo prend en entrée un champ scalaire.

En terme plus clair, pour le cas 2D l'algo prend en entrée un tableau 2D de valeurs = les valeurs de chaque pixels de l'image. Et en 3D, un tableau de 3D de valeurs = les valeurs dans chaque voxel du volume.
13/12/2011, 18h19
on2101

Merci de votre réponse.

En effet, dans les articles il est bien précisé que l algo prend en entrée une "regular scalar volumetric data set". Il s agit donc d un tableau 3D de voxels comme vous me l avez précisé.

Savez vous s il est possible d adapter cet algo a partir d un nuage de points 3D ? (avec des points qui ne sont pas positionnés sur une grille régulière).

Je pense par exemple a coller une grille 3D sur mon nuage points, et essayer d affecter à chaque sommet de voxels le point 3D le plus proche, ou quelque chose dans cet esprit la.
13/12/2011, 18h34
pseudocode
Citation:

Envoyé par on2101

Merci de votre réponse.

En effet, dans les articles il est bien précisé que l algo prend en entrée une "regular scalar volumetric data set". Il s agit donc d un tableau 3D de voxels comme vous me l avez précisé.

Savez vous s il est possible d adapter cet algo a partir d un nuage de points 3D ? (avec des points qui ne sont pas positionnés sur une grille régulière).

Je pense par exemple a coller une grille 3D sur mon nuage points, et essayer d affecter à chaque sommet de voxels le point 3D le plus proche, ou quelque chose dans cet esprit la.

Cet algo sert a déterminer des iso-surfaces, et plus particulièrement les contours d'un objet 2d/3d. Pour que cela ait du sens, il ne faut pas qu'il y a ait de 'trous" dans la grille de valeurs. Sinon on ne peut pas savoir ce qu'il y a dans les trous, et donc on ne peut pas définir le contour.

Dans le cas suivant, sans connaitre les valeurs "?" on ne peut pas savoir s'il y a un ou deux objets représentés. Et donc on ne peut pas définir le contour.
```
. . . . . . .
. X X X . . .
. X X ? ? ? .
. X ? ? ? X .
. X X ? ? ? .
. . . . . . .
```
14/12/2011, 10h45
math_lab

Il est tout de même possible d'avoir un champ scalaire a partir de la liste de points. Il suffit de retourner la distance au point le plus proche pour n'importe quel (x,y,z).
14/12/2011, 11h46
pseudocode

Citation:

Envoyé par math_lab

Il est tout de même possible d'avoir un champ scalaire a partir de la liste de points. Il suffit de retourner la distance au point le plus proche pour n'importe quel (x,y,z).

Tout dépend de la finalité de l'opération et de ce que représente le nuage de points.

Si le nuage de point est le résultat d'un scanner 3D et que le but est de reconstruire la surface scannée, alors il ne faut pas utiliser la distance aux points connus mais la distance à la surface...

Ce qui implique de créer une fonction implicite de "distance à la surface" à partir des points connus, puis d'évaluer cette fonction en chaque point de l'espace pour avoir un champ scalaire complet. Le marching-cubes pour la valeur zéro nous donnera au final la surface cherchée.

Cf thèse de Hugues Hoppe : "Surface reconstruction from unorganized points"
14/12/2011, 12h07
on2101

Effectivement, je souhaiterait utiliser les Marching Cubes dans le cadre d un nuage de points obtenu à partir d un scanner 3D.

Merci, je commence maintenant a y voir un peu plus clair.

Je superpose à mon nuage de points "non déjà organisé en grilles régulières" une grille 3D. Chaque point appartient alors a un cube (voxel). Les coins des voxels sont affectés d'une valeur, qui est en fait la distance a la surface recherchée. La distance doit être signée pour pouvoir ensuite trouver l isosurface de niveau 0.

La fonction dont on recherche l isosurface est donc la fonction de distance signée. On recherche l isosurface de niveau 0car on souhaite obtenir la surface "a une distance de zero" de la surface recherchée.

Ais je bien saisi les choses ? ;)

Dans le premier article sur les Marching Cubes, le but etait de reconstruire une surface a partir de plusieurs coupes, ce qui explique que les données de départ étaient déjà bien alignées pour former les cubes.

Enfin, dans le cas du scanner 3D, cela pourrait il suffire de rechercher le point 3D le plus proche des coins des voxels plutot qu a la surface ? (il faudrait alors approximer la surface pour trouver la distance?)

Merci beaucoup ;) Je vais regarder le lien !
14/12/2011, 12h19
pseudocode

Citation:

Envoyé par on2101

Ais je bien saisi les choses ? ;)

Oui, c'est tout a fait ça.

Citation:

Enfin, dans le cas du scanner 3D, cela pourrait il suffire de rechercher le point 3D le plus proche des coins des voxels plutot qu a la surface ? (il faudrait alors approximer la surface pour trouver la distance?)

Hum... utiliser la distance au point au lieu de la distance à la surface va donner des résultats curieux.

Tu auras au final des petits morceaux de surfaces englobant des paquets de points.
22/05/2013, 14h47
nana35600

Bonjour,

Je m'intéresse également à la mise en oeuvre du marching cube pour faire une reconstitution 3d d'un objet à partir d'un scan. Je voulais donc savoir si vous aviez trouver des documents intéressant sur le sujet, car actuellement, je patine un peu ...