Discussion :

[lybhur]

Bonjour,

Tout d'abord, j'ai déjà posé cette question sur le forum Matlab mais apparemment, mon problème relève plus des mathématiques (domaine dans lequel je suis loin d'être un crack !!...). Je reformule donc mon problème ici :

J'ai un fichier de données constituant un nuage de points. Il s'agit du maillage à base de triangles d'une pièce quelconque et je dispose donc des coordonnées du sommet de chaque triangle X, Y, Z, ainsi que les composantes de la normale à chaque triangle nx, ny, nz.

A partir du barycentre de chacun de ces triangles, je fais partir une ligne de courant (cf. plan.jpg) et mon problème est le suivant : je cherche à savoir si les lignes de courant recoupe ma pièce de départ.

Une méthode brutale consiste à tester chaque point constituant mes différentes lignes de courant sur chaque triangle composant ma géométrie (10 000 points par lignes de courant pour 4200 triangles = plus de 3h de calcul et la première ligne de courant toujours pas terminée d'analyser...)

Pour simplifier, et grâce à votre forum, je retrouve l'équation du plan constitué par tous mes points et mes intersections sont définies en moins d'une minute !! Merci à vous !

Mais, la vraie vie est malheureusement plus compliquée : voici la véritable pièce sur laquelle je cherche à faire la même chose (cf. pièce2.jpg).

J'ai donc besoin de trouver l'équation de la surface qui "fit" au mieux mon nuage de points (1ère question). A partir de cette équation, comment je fais pour définir que 2 points consécutifs sur une ligne de courant sont de part et d'autre ou du même côté de cette surface (2de question).

[vincent69]

Il faut utiliser des méthodes de recouvrement par sphère ou par OBB (Oriented Bounding Box - Boite englobante orientée) et construire un arbre.
Recherche un peu sur le net, il y a des publi sur le sujet et ça marche très bien.
Le principe de base est le suivant : tu mets tous tes triangles dans une grande boite. Puis tu coupes la boite en deux et tu sépares donc tes triangles en deux en fonction de la boite à la quelle ils appartiennent et tu recoupes tes boites jusqu'a qu'il n'y ait qu'1 triangle par boite.
Tu obtiens donc un arbre de boite avec en général un niveau faible de niveaux...
Ensuite pour tester une intersection, ben tu testes avec la plus grande boite. Si ça coupe tu descends sinon tu laisses tomber, et ainsi de suite jusqu'au niveau le plus bas ou tu testes l'intersection de ta droite avec le triangle.

Ce genre de technique est utilisé, entre autre, dans les jeux pour détecter les collisions...


Si on me pousse vraiment je pourrais faire un article là-dessus...