Discussion :

[PierroVsf]

Bonjour,

Je présente une méthode de triangulation plus récente que la triangulation de Delaunay ou que le marching cube.
C'est un algorithme simple et efficace capable de fonctionner en temps réel.

Je vous laisse découvrir le fonctionnement et les jolis maillages obtenus par la triangulation de surfaces implicites par contour dual.

N'hésitez pas à me laisser des retours.

[N_I_C_S]

C'est intéressant d'avoir un article sur ce type d'algo en francais ^^.

Par contre je suis un peu perplexe sur l'appellation contour dual, l'algo traditionnellement appelé dual contouring est différent.
C'est plus une variation du marching cube où le point du maillage est dans le cube et les arêtes stockent une normale à l'isosurface (on retrouve le point par intersection des plans).

L'algo que vous présentez est plus celui des surface nets...
Vous écrivez sûrement contour dual dans un sens large mais ça peut créer la confusion...

[PierroVsf]

Je suis content que vous trouvez cela interressant

Effectivement j'utilise le terme contour dual au sens général des méthodes duales par opposition aux méthodes primaires comme le marching cube. Je suis désolé si cela peut prêter à confusion, mais je ne présente pas la méthode traditionnelle du dual contouring.

L'algorithme traditionnel appelé dual contouring est un algorithme complet de triangulation de surface capable de faire des maillages adaptatifs et de gérer les bords coupants. Son gros avantage est d'utiliser des erreurs quadratiques pour placer les sommets. De même la méthode initiale du surface nets est un algorithme pour traiter les données d'un scanner par exemple, celui-ci lisse les contour et utilise des contraintes élastiques pour placer les sommets.

Ce que je présente ici est surtout la base de ces méthodes, à savoir avoir un premier maillage dual. Ensuite il y a de nombreuses façons pour pouvoir placer les points au mieux sur la surface à partir d'un premier maillage dual, la méthode traditionnelle du dual contouring en donne une grâce aux erreurs quadratiques. J'en donne une autre grâce à une projection et un barycentre. Mais cette méthode n'a pas de rapport avec le marching cube.

[N_I_C_S]

Mais cette méthode n'a pas de rapport avec le marching cube.

Oui en effet, justement le marching cube n'est pas dual (le plus confus ce fut moi...)

[mermich]

Bon je presume que c'est un bon article de qualite, mais j'ai a peu pres rien compris (et je pense que le probleme vient de moi).

Cette phrase m'a tuer:

L'isosurface est alors approximée par le maillage de quadrangles(1) formés par les faces des voxels : il suffit alors de projeter les points qui forment les sommets des quadrangles sur l'isosurface en suivant le gradient, et c'est terminé.

Du coup PierroVsf, pourrais-tu m'indiquer un lien ou je pourrai aquerir le vocabulaire necessaire a la comprehension de l'article ?

[PierroVsf]

bonjour,

En fait cette phrase résume les parties III-A et IV-C

Sur la partie III-A, on réalise le maillage d'une sphère:
on voit le maillage formé des faces carrées des voxels sur une première figure. Ensuite, les sommets qui forment ce maillage sont projetés en suivant le gradient pour former la deuxième figure à côté, et cette étape est décrite dans la partie IV-C.

Après le vocabulaire:
un quadrangle est un quadrilatère en 3D
les voxels sont des pixels en trois dimension, soit des cubes.
pour le gradient tu peux aller voir wikipedia: https://fr.wikipedia.org/wiki/Gradient
On utilise la méthode de newton pour projeter le point: https://fr.wikipedia.org/wiki/M%C3%A9thode_de_Newton
Une isosurface est une surface définie par une équation de la forme f(x,y,z) = 0

En fait il est important de comprendre l'étape de projection: elle nécessite de résoudre une équation non linéaire. Il faut trouver le point qui est à l'intersection de [ la droite définie par le point initial et le gradient de la fonction potentielle en ce point] et [ l'isosurface ].
Pour cela on utilise une méthode qui se rapproche de la méthode de newton décrite dans IV-C.

la méthode de newton est au départ pour trouver le zéro d'une fonction:

x_k+1 = x_k - f(x_k)/f'(x_k)

On la modifie un peut pour qu'elle fonctionne dans notre cas avec une fonction de trois variable et en notant f' le gradient de notre fonction on a:

x_k+1 = x_k - f(x_k)f'(x_k)/(f'(x_k).f'(x_k))

[neiji]

Bonjour,

j'ai moi-même développer un programme c++ avec DirectX qui permet l'affichage de forme 3D comme des blob et des sphères avec l'algorithme du marching cube. Dans mon programme, j'utilise aussi l'isolevel et des champs scalaires, et donc des fonctions en entré. Je me permet de poster ce message pour savoir s'il éxiste une méthode permettant de produire des mesh avec des voxel sans passer par des fonctions comme le gradient que vous utilisez.
J'avais trouvé un algorithme qui utilise les surface nets et apperement, il n'utilise pas de fonction en entré pour définir les mesh que le programme fournit. C'est un programme de sculpt 3D et les voxel sont utilisé comme structure intermédiaire.

[PierroVsf]

Bonjour,

Je ne comprend pas quel problème pose ce gradient vu que tu as aussi des champs scalaires.

Peut être que c'est un problème si tu utilise des unions de sphères où il n'y a pas de champs scalaire, et seulement un champ binaire (intérieur ou extérieur). Alors tu peux plaquer les vecteurs du contour des voxels sur la sphère la plus proche.

Sinon tu peux aussi utiliser la méthode du contour dual initial qui est dans l'article en anglais, qui est de calculer les intersections des côtés du voxel qui entourent le sommet avec la surface, de calculer les normales à cette position (pour cela il faut renormer le gradient de la fonction en ce point sauf si tu connaît la normale de la surface autrement).

Et il faut trouver le point qui minimise l'erreur quadratique qui est dans l'article (qui dépend des points et normales trouvées). Cela revient seulement à inverser une matrice 3*3.
J'ai testé cette méthode et elle est un peu moins stable que celle que je présente dans mon cas, mais permet d'approximer les angles coupant.

J'espère que ma réponse va t'aider