Discussion :

[nicolas66]

Bonjour tlm,

Je suis actuellement en train de bosser sur un projet de maillages. Je dois charger différents formats de fichiers (ply, obj, off, etc ...) et je me suis aperçu d'un petit problème. Mon prog se basait uniquement sur des maillages triangulaires. Mais il existe parfois dans des fichiers des quads ou autre.

Je dois donc redécouper chacune de mes faces pour n'avoir que des triangles mais je ne vois pas trop comment faire . Je connais les coordonnées des points. Quelqu'un aurait-il la solution à mon problème ? Merci d'avance en tout cas.


Nico.

[maamar]

quel type de traingulation utilisé vous ?

[nin2]

Salut !

Je suppose que les facettes que tu charges sont planes. Il existe beaucoup d'algoritmes de triangulation de polygones.

S'il s'agit de polygones convexes ou étoilés, il suffit de calculer l'isobarycentre et de relier ensuite chaque couple de sommets du polygone au barycentre pour obtenir des triangles.

Si les polygones que tu charges ne sont pas convexes, alors là, c'est un peu plus compliqué, l'idée générale est de découper tes faces en plusieurs faces convexes et d'appliquer ensuite la méthode précédente.

Voila. Si ce n'est pas très clair, je peux entrer plus dans le détail ...

[nicolas66]

Oui je pense aussi que les facettes à charger sont planes. Dans ce cas-ci, peux-tu m'expliquer un peu plus en détail l'algo à effectuer ? Merci .

[nin2]

Salut !

Si j'ai bien compris, le principal problème est qu'il figure dans ton maillage des polygones autres que des triangles, quads par exemple. L'idée est de découper ces quads en triangles en utilisant une méthode très simple :

1ère étape : calcul de l'isobarycentre du quad (enquelque sorte son "milieu").
Tu disais que tu possédais les coordonnées de tes sommets. L' isobarycentre est en fait la moyenne de tous les points du polygone (ou quad). Le mieux c'est de prendre un exemple simple. Imaginons que tu travaille avec un quad à 4 sommets A, B C et D dont les coordonnées sont (xA,yA,zA), (xB,yB,zB), (xC,yC,zC), (xD,yD,zD). Appelons G l'isobarycentre du quad ABCD. Soit (xG,yG,zG) les coordonnées de G. Les formules mathématiques du calcul de l'isobarycentre donnent :
xG = (xA+xB+xC+xD)/4
yG = (yA+yB+yC+yD)/4
zG = (zA+zB+zC+zD)/4
Tu remarqueras qu'il s'agit tout simplement d'un calcul de moyenne basique.
Si tu as plus de points, c'est le même principe ...

2ème étape : triangulation.
Une fois que tu possède le barycentre G de ton quad, il faut relier chaque couple de sommets (consécutifs) à ton barycentre pour obtenir des triangles. Dans notre exemple, cela revient à créer quatre triangles : ABG, BCG, CDG et DAG.
Ainsi, tu peux transformer tous tes quads en triangles.

3ème étape : Attention !
Cette méthode ne fonctionnera bien que pour trianguler des surfaces convexes, mais normalement, tu ne travailles qu'avec des surfaces convexes puisque tu les récupères dans un maillage.

J'espère que cela te convient. Si des points ne sont pas clairs où s'il te manque des infos pour travailler, n'hésite pas, c'est un domaine que j'aime bien et dans lequel je bosse actuellement.

Bon courage !

[hamster]

est ce qu'il n'est pas plus simple de "couper" le quadrangle en deux triangles ?? C'est plus économique que d'en créer 4 non ?

Je comprends pas pourquoi il ne suffit pas de déterminer la diagonale la plus courte et de s'en servir pour couper le quadrangle en deux triangles...

[nin2]

Re-salut,

La méthode que je t'ai proposé fonctionne avec des polygones qui peuvent avoir plus de quatres sommets. La méthode que tu propose fonctionne uniquement avec des quadrilatères.
Par contre si tu travaille uniquement avec des quads, tu peux decouper en deux selon une diagonale. C'est clair que c'est moins couteux !!! Dans ce cas, pour trouver la meilleure diagonale, l'dée c'est de tester avec les deux et de garder celles qui découpe en deux triangles qui ont les angles les plus grands possibles (cela évite d'avoir des triangles plats, ce qui est mieux à la visualisation).
Si tu récupères d'autres figures depuis tes fihiers (du style pentagones, hexagones ...), alors la méthode du barycentre est celle la mieux adaptée (celle qui va créer les meilleurs triangles).

Si tu veux, j'ai des cours plus poussés (avec des schémas) sur le problème de la triangulation. N'hésite pas !

A+

[hamster]

Dans ce cas, pour trouver la meilleure diagonale, l'dée c'est de tester avec les deux et de garder celles qui découpe en deux triangles qui ont les angles les plus grands possibles (cela évite d'avoir des triangles plats, ce qui est mieux à la visualisation).

Y'a pas un rapport avec Voronoï et Delaunay ?

[nin2]

L'idée de chercher les angles maximum dans les triangles est le principe fondammental de l'algorithme de triangulation de Delaunay. Cependant, cet algo permet la triangulation d'un nuage de point et ne me semble pas adapté à ton problème. Je pense qu'il fonctionnerait, mais il me semble que ce serait mettre en place une usine à gaz pour pas grand chose. Maintenant si ca te tente de l'implémenter ou si tu en a vraiment l'utilité, cela peut etre très intéresant, à mon avis.

[hamster]

ben à la base c'est pas mon problème, c'est pluôt celui de nicolas66.

mais je posais cette question par simple curiosité.
en tout cas merci pour la réponse

[nin2]

Oups, je suis désolé, je n'avais pas vu que je changeais d'interlocuteur
En tout cas, si tu as d'autres questions, n'hésite pas !
@+

[nicolas66]

Bon j'ai implémenté ca hier et ca marche nikel.

Ca me semble quand même bizarre qu'il n'existe pas une méthode plus poussée pour découper n'importe quel polygone en un minimum de triangles. Comme le signale hamster, rien qu'avec un quad, on en créé 2 fois plus. Je signale au passage que les mesh que je charge sont énormes (yen a même qu'on ne peut pas charger en une fois ..).

Ah oui j'allais oublier : merci qd même pour m'avoir aider là-dessus, j'avais pas d'idée du tout

[Kangourou]

salut,

si, ca existe lees algos pour decouper un polygone en triangles, mais si c'est pas convexe c'est pas facile.

Cela dit, si on est avec un polgone convexe, il y a une methode plus simple (ert moins gourmande) qu'en utilisant le centre de gravite :
- On choisit un sommet
- on cree un triangle avec ce sommet, son voisin, et le voisin suivant,
- on continue tant quon ne revient pas au sommet de depart.

Dans le cas d'un quadrialtere, ca revient a faire 2 triangles
pour des polygones avec N cotes, ca fait N-2 triangles.

A+

[sovitec]

si, ca existe lees algos pour decouper un polygone en triangles, mais si c'est pas convexe c'est pas facile.

Cela dit, si on est avec un polgone convexe, il y a une methode plus simple (ert moins gourmande) qu'en utilisant le centre de gravite :
- On choisit un sommet
- on cree un triangle avec ce sommet, son voisin, et le voisin suivant,
- on continue tant quon ne revient pas au sommet de depart.

Dans le cas d'un quadrialtere, ca revient a faire 2 triangles
pour des polygones avec N cotes, ca fait N-2 triangles.

Je n'ai jamais entendu parler de maillage par des polygones non convexes. De toutes façon la méthode de nin2 ne marcherait dans ce cas (le barycentre ne se trouve pas forcément à l'intérieur du polygone).

Sinon, comme le suggère hamster, on peut toujours utiliser la triangulation de Delaunay, car la méthode que tu décris à un gros inconvénient : elle produits des triangles très plats, ce qui pose beaucoup de problèmes pour un maillage (artéfacts visuels, ...).

[mtopoloff]

Tiens j'ai entendu que les mesh ne peuvent pas etre chargé en une seule fois ???? Combien de polygones font-ils ? Quelle machine utilises tu ?

Je dis ca parceque ca me semble bizarre....

[nicolas66]

oula c'est des mesh énormes j'ai plus les chiffres en tête, jte dirai ça à l'occaz ...

[Akta3d]

Salut, moi je vais avoir le meme genre de probleme dans les prochaines semaines. Donc je cherche déjà une piste.

Je cherche a mailler un contour pas forcement convexe. Et ce contour est deja subdiviser par des points. Chaque ligne du contour ne possede pas forcement le meme nombre de points.

J'ai regardé la methode de Delauney, c'est pas mal comme technique, mais ne correspond pour des cas non convexe.

On a parler un peu plus haut d'une méthode pour redoucoupé le contour en 2 ou plusieurs coutours convexes. Quelqu'un aurait t-il d'autres informations sur la méthode a employé

Ou peut etre une autre méthode que Delauney.

Merci pour vos reponses

[Kangourou]

salut,

Akta, pour decouper un polygone non convexe en plusieurs polygones convexes, tu peux essayer de diviser en plusieurs triangles.

- prendre un point qui fait un angle <180 avec ses voisins
- creer un triangle avec ce point et ses 2 voisins
- supprimer les 2 aretes du polygone initial, et les remplacer par l'arete joignant les 2 voisins.
En iterant jusqu'a ce que le polygone n'ait plus que 3 points, on obtient finalement une liste de facettes triangulaires.

je crois qu'il est possible d'optimiser en commencant par les points qui forment les angles les plus petits, afin d'eviter les grands triangles tres plats.

A+

[Akta3d]

Merci pour cette réponse,

pour mon probleme je n'ai pas besoin de découper toutes ma surface en triangle, j'ai juste besoin de n'avoir plus que des contours convexe pour appliqué une méthode de Delauney.

La maille obtenue est destiné à faire du calcul numérique et ta méthode me donnerait un maillage pas vraiment régulier. En tout cas merci pour ta réponse ca va déjà bien m'aider.

Merci et A++