Triangulation de facettes planes
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 ...
:)
Triangulation : explications ...
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 !
:D
Couper en deux ou en quatre ...
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+
Re: Couper en deux ou en quatre ...
Citation:
Envoyé par nin2
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 ?
A propos de Voronoi et Delaunay
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.