Triangle Triangle Intersection dans l'Espace 3d
Je travaille avec de la 3d la géométrie. J'ai besoin de trouver l'intersection de triangle avec un autre triangle.
Quel algorithme pourrais-je utiliser?
Vous devez vous connecter pour publier un commentaire.
Ce document décrit une mise en œuvre:
http://knight.temple.edu/~lakaemper/cours/cis350_2004/etc/moeller_triangle.pdf
Noter qu'il existe différentes techniques, selon que vous voulez connaître le point/segment où l'intersection est produite, ou tout simplement de dire si une intersection est arrivé. Ce document vous donnera le segment de droite représentant l'intersection.
Beaucoup de gens apparemment compter sur une mise en œuvre (lien vers le code source) de la méthode décrite en 2006 dans le document suivant (lien vers PDF):
Il y a cependant un problème avec ce code (à l'exception de l'adoption d'un vieux style de programmation, l'utilisation non conventionnelle de notations et de perdre le sous-jacent interprétation géométrique): "déterminant chose" ne font pas nécessairement de votre math plus robuste, si c'est fait dans le mauvais sens.
Je suggère d'utiliser Moeller de la méthode (lien vers PDF) ou de prendre un coup d'oeil à Delliver de papier (lien vers PDF), mis en œuvre dans la bibliothèque CGAL (lien, "Triangle_3_Triangle_3_do_intersect.h").
Un exemple: l'intersection de routine de mise en œuvre ci-dessus indique que les triangles (p0,p1,p2) et (q0,q1,q2) défini par les points suivants
sont pas d'intersection. Voici une photo de l'triangles:
Et voici l'extrait de code (ajout de code d'origine):
Une dernière remarque sur le nombre d'opérations arithmétiques: puisque la méthode prend en entrée pré-calculé bord de vecteurs, 12 +/- opérations doivent être ajoutées au Tableau I. du papier.
Dernier mais pas le moins important: veuillez vérifier ce que je suis en train d'écrire sur votre propre et de me donner vos commentaires si vous pensez que j'ai mal compris quelque chose!
Il y a de bonnes papier par Devillers et coll., avec le titre de "plus Rapide Triangle-Triangle Intersection des Tests" -- (oui, fait une recherche google, mais les mots clés de recherche sont importants...)
De toute façon, leur point (par rapport à la Moeller papier dans MichaelM de réponse), c'est que vous devriez vraiment obtenir votre combinatoire de l'information en faisant des déterminants de la sélection de groupes de 4 points (le document décrit comment). Cela évite le calcul des valeurs intermédiaires qui peut être problématique incompatibles, et qui ne sera probablement pas en fait être plus vite...
Vous pouvez consulter ces déterminants de déterminer si le tétraèdre formé par les 4 points est droitier, gaucher, ou dégénérer (c'est à dire, planes). Cette valeur détermine également si l'un des 4 points est d'un côté ou de l'autre du plan formé par les trois autres, et si l' (mise en scène) de la ligne formée par deux des 4 est d'un côté ou de l'autre de la ligne formée par les deux autres.
Pour faire une longue histoire courte, en faisant le déterminant chose qui rend votre math plus robuste, et si vous faites attention, vous pouvez convertir des algorithmes qui ne sont pas d'abord faire le déterminant chose dans ceux qui le font. Ou, vous pouvez simplement lire le journal.