+ Répondre à la discussion Actualité déjà publiée
  1. #1
    Membre averti

    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2011
    Messages
    79
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : mars 2011
    Messages : 79
    Points : 391
    Points
    391

    Par défaut Triangulation de surface par contour dual

    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.
    Mes tutoriels avancés sur la triangulation par filet à surface et sur les octree - N'hésitez pas à consulter les tutoriels et FAQ 2D/3D/jeux.

  2. #2
    Membre confirmé
    Avatar de N_I_C_S
    Profil pro
    Inscrit en
    septembre 2006
    Messages
    434
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2006
    Messages : 434
    Points : 622
    Points
    622

    Par défaut

    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...
    Mes projets :
    Isotröma : FPS futuriste ( dernière démo )
    Flesh Snatcher : FPS/Survival ( téléchargement )
    JavaGL : Bibliothèque 3D software ( téléchargement )
    Page Developpez

  3. #3
    Membre averti

    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2011
    Messages
    79
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : mars 2011
    Messages : 79
    Points : 391
    Points
    391

    Par défaut

    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.
    Mes tutoriels avancés sur la triangulation par filet à surface et sur les octree - N'hésitez pas à consulter les tutoriels et FAQ 2D/3D/jeux.

  4. #4
    Membre confirmé
    Avatar de N_I_C_S
    Profil pro
    Inscrit en
    septembre 2006
    Messages
    434
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2006
    Messages : 434
    Points : 622
    Points
    622

    Par défaut

    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...)
    Mes projets :
    Isotröma : FPS futuriste ( dernière démo )
    Flesh Snatcher : FPS/Survival ( téléchargement )
    JavaGL : Bibliothèque 3D software ( téléchargement )
    Page Developpez

  5. #5
    Membre expérimenté
    Homme Profil pro
    Développeur .NET
    Inscrit en
    février 2007
    Messages
    758
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Canada

    Informations professionnelles :
    Activité : Développeur .NET

    Informations forums :
    Inscription : février 2007
    Messages : 758
    Points : 1 334
    Points
    1 334

    Par défaut

    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 ?

  6. #6
    Membre averti

    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2011
    Messages
    79
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : mars 2011
    Messages : 79
    Points : 391
    Points
    391

    Par défaut

    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:

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

    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:

    xk+1 = xk - f(xk)f'(xk)/(f'(xk).f'(xk))
    Mes tutoriels avancés sur la triangulation par filet à surface et sur les octree - N'hésitez pas à consulter les tutoriels et FAQ 2D/3D/jeux.

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo