Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Fermer une surface triangulée
Bonjour,
Est ce que quelqu'un connait un bon algorithme permettant de fermer une surface triangulée ?
- Fermer les trous
- Éliminer les intersections entre les triangles
- Si la surface est formée d'intersection de 2 ou plusieurs sous-surface, combiner ces sous surface en une seule.
- autres critères de surfaces fermée.
Je cherche un article, un livre ou un code (ou des suggestions d'algorithme... ).
Merci
Juste pour la fermeture des trous, on peut cherche du côté de Mesh Repair/ Mesh Hole filling.
Quelques papiers par exemple (le deuxième est plutôt compliqué quand même) :
- http://www.iis.sinica.edu.tw/~kychen...pdf/eg2005.pdf
- http://www.cs.tau.ac.il/~asharf/shre...onts_final.pdf
Envoyé par Nehmé
Encore une fois, tu ne donnes pas le problème exact...
Si une surface est triangulée, il n'y a ni intersection de triangles , ni trous, et elle est fermée...
Donc, tu n'as pas utilisé une méthode normale de triangulation pour la créer.
Expose donc comment a été obtenue cette surface, de manière précise... Et évite le mot triangulation, qui a une signifcation précise... (voir ci-dessous)
NB : par définition, une méthode de triangulation donne un résultat fermé, sans intersection.
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
Salut!
Tout à fait d'accord avec souviron34. J'ajouterais que, si ton problème se pose, c'est que ta méthode de "triangulation" qui est mauvaise. C'est là que tu dois chercher.
Jean-Marc Blanc
Calcul numérique de processus industriels
Formation, conseil, développement
Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)
Salut,
En faite les maillages que je désire réparer ne sont pas fait par moi. Les données que j'ai provienne de différent logiciels et je n'ai aucun contrôle sur leur création. On m'envoie des données et on me demande de faire des traitements avec, ces données contienent souvent des trous et des intersections de sous surfaces et je désire les réparer pour pouvoir effectuer des traitements dessus avec des logiciels qui nécessitent des surfaces bien fermées. (Par exemple des fois je veux raffiner le maillage existent avec un mailleur comme Tetgen par exemple, mais ce dernier plante si la surface d'entrée n'est pas bien fermée)
on arrive enfin au fond du problème !!!!
Qu'on essaye de te faire cracher depuis le début
récupérer un code de maillage n'est pas très compliqué.
Pourquoi prendre un code avec des contraintes telles que celles-ci ?
A mon avis, le plus simple (et ça solutionnerais aussi ton autre problème), serait de récupérer tous tes points venant des diverses sources, et re-faire un maillage à partir de l'ensemble. Tu serais certain que cela satisfait à toutes les conditions d'un coup, et c'est pas long à coder..
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
Salut,
Qu'on essaye de te faire cracher depuis le début
récupérer un code de maillage n'est pas très compliqué.
Pourquoi prendre un code avec des contraintes telles que celles-ci ?
A mon avis, le plus simple (et ça solutionnerais aussi ton autre problème), serait de récupérer tous tes points venant des diverses sources, et re-faire un maillage à partir de l'ensemble. Tu serais certain que cela satisfait à toutes les conditions d'un coup, et c'est pas long à coder..
D'abord il y a aucun lien entre mon autre problème est celui ci !
deuxièmement tu me proposes de récupérer tous les points sans aucune topologie et de reconstruire mes surfaces avec un maillage ? WOW, à partir d'un ensemble de points, on peut construire plusieurs surfaces différentes si ce n'est pas une infinité !
Le problème que j'ai posé est clair et nette, y a rien de caché dans le trous surviron. si tu veux d'autres informations comme mon poids, ma taille, ou la couleur de mes yeux, laisses moi savoir ca pourra toujours aider à réparer un maillage !
Salut,
C'est justement le problème de ton problème... as tu une référence entre tes éléments et la géométrie sur laquelle ils s'appuient, ou n'as-tu que les éléments?
Si tu es dans le second cas, tu essaies de fermer une surface que tu ne connais pas et avec des trous... on tombe sur ta remarque fort judicieuse...
Le problème est peut-être clair pour toi, mais la manière dont tu le présentes ne l'est pas du tout...
Qu'est-ce que tu appelles un trou? (zone non maillée dans une surface, gap entre des noeuds, ...)
Qu'est-ce que tu appelles le fermer? (mailler le trou, fusionner les noeuds, ...)
Qu'est-ce que ces intersections entre triangles? un bon algo de triangulation ne produit pas ceci... ce sont des triangles d'une même surface, ou des triangles de deux surfaces différentes.
Concernant la combinaison de surfaces, ça serait bien de préciser si tu es en 2D ou en 3D. Parce que la combinaison de surfaces 3D qui s'intersectent, j'ai un peu de mal à voir... en 2D ça passerait mieux (même en 2D "spatiale"), mais là je ne vois plus ce que tu entends par "intersection"...
Pour les critères, je crois que le plus simple est de faire le tour... et de voir si on revient au point de départ. Facile à vérifier si tu as une triangulation... correcte.
Au final, sans plus de précisions de ta part sur ton problème, je rejoins la proposition de souviron34...
Salut,
C'est justement le problème de ton problème... as tu une référence entre tes éléments et la géométrie sur laquelle ils s'appuient, ou n'as-tu que les éléments?
Si tu es dans le second cas, tu essaies de fermer une surface que tu ne connais pas et avec des trous... on tombe sur ta remarque fort judicieuse...
Le problème est peut-être clair pour toi, mais la manière dont tu le présentes ne l'est pas du tout...
Qu'est-ce que tu appelles un trou? (zone non maillée dans une surface, gap entre des noeuds, ...)
Qu'est-ce que tu appelles le fermer? (mailler le trou, fusionner les noeuds, ...)
Qu'est-ce que ces intersections entre triangles? un bon algo de triangulation ne produit pas ceci... ce sont des triangles d'une même surface, ou des triangles de deux surfaces différentes.
Concernant la combinaison de surfaces, ça serait bien de préciser si tu es en 2D ou en 3D. Parce que la combinaison de surfaces 3D qui s'intersectent, j'ai un peu de mal à voir... en 2D ça passerait mieux (même en 2D "spatiale"), mais là je ne vois plus ce que tu entends par "intersection"...
Pour les critères, je crois que le plus simple est de faire le tour... et de voir si on revient au point de départ. Facile à vérifier si tu as une triangulation... correcte.
Au final, sans plus de précisions de ta part sur ton problème, je rejoins la proposition de souviron34...
Salut,
Je suis d'accord avec toi plegat, parce que t'es critique sur la manière que j'ai posé le problème sont plutôt constructive et tes remarque sont bien claires et correctes.
J'ai uniquement les éléments, la géométrie peut être n'importe quoi.C'est justement le problème de ton problème... as tu une référence entre tes éléments et la géométrie sur laquelle ils s'appuient, ou n'as-tu que les éléments?
Les trous dans mon cas sont souvent des triangles manquants. Par exemple, le trou peut être un seul triangle, les noeuds de ce triangle existe, mais ces noeuds ne sont pas reliés topologiquement. Des fois le trous peut être formé de par exemple 5 noeuds, et j'aimerai que ce trous soit fermé en maillant ces 5 noeuds.( c'est une approximation ici, mais acceptable puisque les trous sont souvent très petit par rapport à la surface totale)Qu'est-ce que tu appelles un trou? (zone non maillée dans une surface, gap entre des noeuds, ...)
Qu'est-ce que tu appelles le fermer? (mailler le trou, fusionner les noeuds, ...)
Ce qui arrive ici est que certaine surfaces tracées sur des logiciels de design comme catia ou autocad, semblent fermées à l'oeil du concepteur, mais en réalité il y a certain points que ce concepteur voit confondu malgré qu'il ne le sont pas. Par exemple il veut tracer un cube, il trace les 6 faces, chaque face semble partager 2 sommets avec une autre, mais ce n'est pas vrai, c'est juste que ces 2 sommets sont très proches. une fois le cube construits, ce concepteur peut le mailler dans Catia par exemple sans détecter que la surface n'est pas bien fermée, ceci résultera de trous ou d'intersections de triangles.Qu'est-ce que ces intersections entre triangles? un bon algo de triangulation ne produit pas ceci... ce sont des triangles d'une même surface, ou des triangles de deux surfaces différentes.
Pour les autres cas d'intersections, c'est moins prioritaire et je préfère laisser ca à plus tard.
Merci
Ca ne va pas être simple alors...
Ok... alors il va te falloir faire une recherche de la frontière de ton maillage dans ce cas. Tu parcours toutes les arêtes de tes éléments, et tu conserve celles qui n'apparaissent qu'une seule fois (et qui donc appartiennent à la frontière, car n'ayant pas d'éléments en vis-à-vis). Ensuite, à partir de ces arêtes solitaires, tu crées des listes chainées pour définir les différentes frontières.
Par exemple, si tu récupères les arêtes AB, BC,CD, AD, EF,FG,GH,EH, ça te donne deux frontières ABCD et EFGH.
Une fois les frontières définies, il ne reste plus qu'à trianguler. Attention à repérer la frontière globale auparavant (celle-là elle est déjà triangulée!).
Pour la triangulation, soit tu fais un truc à la sauvage (on crée des triangles en suivant les sommets: ABCD donne ABC, ACD... donne pas forcément de "jolis" triangles), soit tu fais un petit delaunay... ou autre, à ta convenance.
Mais auparavant tu fusionnes les noeuds coïncidents!
Ok, donc ce ne sont pas des trous, ce sont des erreurs d'approximation (ou de tolérance). Là, il va te falloir parcourir toute ta liste de noeuds, et fusionner les noeuds dont la distance est inférieure à une certaine tolérance que tu définis. Pense à modifier les connectivité des triangles en fonction des fusions.
Exemple: tu définis la tolérance à 1E-3, les sommets A et B sont distants de 1E4, donc à fusionner. Tu as deux triangles ACD et BDE. Tu vas fusionner A et B, donc le triangle BDE devient ADE (ou inversement, ACD devient BCD, selon ta préférence).
Là aussi, plusieurs méthodes. Bourrine, tu parcours ton tableau de sommet, et pour chaque sommet tu calcules sa distance par rapport aux noeuds suivants, et tu fusionnes si nécessaire. Ou tu peux utiliser un octree.
Ce n'était pas des intersections là, juste des histoires de connectivité. Rien de grave...
Pense à optimiser tes algorithmes, ça risque d'être couteux en temps de calcul...
Merci plegat pour ton aide !
Mes données sont des surfaces en 3D et non pas des volumes( par exemple pour un cube, j'ai seulement les surfaces frontières qui sont les 6 faces)ttention à repérer la frontière globale auparavant (celle-là elle est déjà triangulée! ).
Dans ce cas je ne devrais pas repérer la frontière globale non ? toutes les arrêtes de ma surface doivent appartenir à 2 triangles. (sur la frontière ou non)
Sauf ceux appartenant au trous !
Tout à fait.
Une fois tes noeuds coïncidents fusionnés, si tu fais ta recherche d'arêtes "solitiaires", tu ne devrais trouver que celles qui délimitent des trous. Mais des vrais trous!
D'accord merci.
Pour le fusionnement des noeuds je le fais toujours avant de traiter mes données. L'entreprise où je travaille utilise un logiciel appelé ParaviewGeo qui est une version modifié de Paraview (adapté pour l'industrie minière) et dans Paraview il existe un filtre appelé "CleanPolyData" que j'utilise pour fusionner mes points selon une tolerance choisie.
Et moi mon premier papier il t'intéresse pas ?
C'est un gros sujet de recherche en géométrie algorithmique 3D quand même ça!
A priori, vu les réponses d'après, tes trous ne sont peut-être pas problématiques.
Un truc simple déjà que tu peux commencer à faire, c'est de fusionner les sommets quand ils sont trop proches, en fonction d'un seuil, mais quand les trous sont trop gros, ça marche plus.
Tiens, d'autres papiers (toute façon, c'est à choisir en fonction du niveau de maths requis, des bibliothèques d'optimisation numériques à disposition, des performances requises et de la difficulté du problème) :
http://www-ljk.imag.fr/Publications/...67/RR-6535.pdf
http://www-graphics.stanford.edu/pap...b-holefill.pdf
-----
Sinon, en recherche 3D, les mots-clés c'est : David Zorin, Hugues Hoppe, Leif Kobbelt, Matthieu Desbrun...
Salut HanLee
Merci pour tes liens ! j'ai sauvgardé les PDF dès que t'as posté les liens. Le truc c'est que j'ai plusieurs projet en même temps et j'essais de partager mon temps. les idées de plegat m'ont aidé a résoudre une bonne partie du problème (surtout son idée sur la liste chainée) mais il reste pas mal de chose non reglé et des cas de trou ou d'intersections pire que ceux que j'ai présenté. mais vue que mon problème n'est pas totalement définie et qu'il y avait du monde qui me criait dessus, J'ai preféré fermer la discussion pour l'instant et tenter de définir mieux mon problème. Les articles que t'as fourni m'aideront beaucoup à définir mieux mon problème et à trouver des solutions.
Merci pour les nouveaux liens !
Personne ne t'a crié dessus !! Si tu es aussi sucspetible que ça, ça ira mal pour toi dans le futur..
Je te demandais juste (et je n'étais pas le seul) de préciser ton problème, car la solution que l'on entrevoyait n'est qu'un "patch" , un "hack", si tu préfères. La vraie solution repose sur une vraie analyse du problème...
Si tu préfères faire un spagetti qui ne résoudra pas tous les cas, bonne chance à toi ..
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
t'inquiètes pas pour moi Surviron, t'as raison qu'il faut que je définisse mieux le problème et t'es pas le seul qui m'a passé cette remarque. Mais si t'as remarqué c'est seulement tes remarques que je n'ai pas aimé parce que souvent ( dans l'autre discussion sa se voit très bien ) tu donnes des remarques et des critiques sans avoir lu la discussion comme il faut, ce qui fait en sorte que tu te retrouve hors sujet. Et toute les réponses que j'ai vu de ta part sont:
- expose mieux ton problème
- oui c'est une bonne solution mais il existe plus simple
- ...
Si t'as pas le temps de trouver une solution plus simple, sa sert a quoi de venir nous dire que tu sais qu'il y a une plus simple ?
Vaut mieux que tu écrives tes réponses dans le but de aider à résoudre le problème et non pas pour signer ta présence.
Désolé pour tous ces attaques, mais il me semble que tu voulais une explication.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager