Triangle Triangle Intersection dans 3d-Space

Question

Je travaille avec une géométrie 3D. J'ai besoin de trouver l'intersection du triangle avec un autre triangle.

Quel algorithme pourrais-je utiliser?

Answer 1

Googling revelead this. Je pense que cela explique cela en détail!

Answer 2

Ce document décrit une implémentation:

http://knight.temple.edu/~lakaemper/courses/cis350_2004/etc/moeller_triangle.pdf

Notez qu'il existe différentes techniques selon que vous voulez connaître le point/segment où l'intersection a eu lieu, ou tout simplement dire si un Intersection est arrivé. Ce papier vous donnera le segment de droite représentant l'intersection.

Answer 3

Il y a une bonne paper par Devillers et al avec le titre "Tests Triangle-Triangle intersection plus rapide" - (oui, a fait une recherche google, mais les mots-clés de recherche sont importants ...)

Quoi qu'il en soit, leur point (par rapport à l'article de Moeller dans la réponse de MichaelM) est que vous devriez vraiment obtenir vos informations combinatoires en faisant des déterminants de groupes sélectionnés de 4 points (l'article décrit comment). Cela évite de calculer des valeurs intermédiaires qui peuvent être problématiques et qui ne seront probablement pas plus rapides ...

Vous pouvez considérer ces déterminants comme déterminant si le tétraèdre formé par les 4 points est droitier, gaucher, ou dégénéré (c'est-à-dire, planaire). Cette valeur détermine également si l'un des quatre points est d'un côté ou de l'autre du plan formé par les trois autres, et si la ligne (dirigée) formée par deux des quatre est d'un côté ou de l'autre du ligne formée par les deux autres. Pour faire une histoire courte, faire la chose déterminante rend vos maths plus robustes, et si vous faites attention, vous pouvez habituellement convertir des algorithmes qui n'ont pas initialement fait la chose déterminante en ceux qui le font. Ou, vous pourriez juste lire le journal.

Answer 4

Beaucoup de gens comptent apparemment sur une mise en œuvre (link to source code) de la méthode décrite en 2006 dans le document suivant (link to PDF):

Tropp, Oren, Ayellet Tal et Ilan Shimshoni. "Un triangle rapide à test d'intersection de triangle pour la détection de collision." Ordinateur Animation et mondes virtuels 17,5 (2006): 527-535.

Il y a cependant un problème avec ce code (sauf pour l'adoption d'un style ancien de programmation, en utilisant les notations non conventionnelles et de délier l'interprétation géométrique sous-jacente): « chose déterminante » ne font pas nécessairement vos calculs plus robuste, se fait la mauvaise direction.

Je suggère d'utiliser soit la méthode de Moeller (link to PDF) ou jeter un oeil à papier de Delliver (link to PDF), mis en œuvre dans la bibliothèque CGAL (link, "Triangle_3_Triangle_3_do_intersect.h").

Un exemple: la routine d'intersection mis en oeuvre ci-dessus indique que les triangles (p0, p1, p2) et (q0, q1, q2) défini par les points suivants

p0 = (-21, -72, 63) 
p1 = (-78, 99, 40) 
p2 = (-19, -78, -83) 
q0 = (96, 77, -51) 
q1 = (-95, -1, -16) 
q2 = (9, 5, -21) 

sont pas intersectant . Voici une image des triangles:

Et voici l'extrait de code (ajouter au code d'origine):

#include <iostream> 

inline void setPoint(double p[3], const double x, const double y, const double z) 
{ 
    p[0] = x; p[1] = y; p[2] = z; 
} 

inline void computeEdges(double v0[3], double v1[3], const double p0[3], const double p1[3], const double p2[3]) 
{ 
    v0[0] = p1[0]-p0[0]; 
    v0[1] = p1[1]-p0[1]; 
    v0[2] = p1[2]-p0[2]; 
    v1[0] = p2[0]-p0[0]; 
    v1[1] = p2[1]-p0[1]; 
    v1[2] = p2[2]-p0[2]; 
} 

void main() 
{ 
    unsigned int numErrors(0), count(0); 
    double p0[3], p1[3], p2[3], q0[3], q1[3], q2[3]; 
    double v0[3], v1[3], w0[3], w1[3]; 
    bool res, answer; 
    int ret; 

    std::cout << "Testing the correctness of tr_tri_intersect3D" << std::endl; 

    { 
     // Non excluding triangles in generic positions, big determinants, intersecting 
     ++count; 
     setPoint(p0, -21, -72, 63); 
     setPoint(p1, -78, 99, 40); 
     setPoint(p2, -19, -78, -83); 
     setPoint(q0, 96, 77, -51); 
     setPoint(q1, -95, -1, -16); 
     setPoint(q2, 9, 5, -21); 
     answer = true; 

     computeEdges(v0, v1, p0, p1, p2); 
     computeEdges(w0, w1, q0, q1, q2); 
     int ret = tr_tri_intersect3D(p0, v0, v1, q0, w0, w1); 
     bool res = (ret != 0); 

     if(res != answer) 
     { 
      std::cout << "# wrong answer on test " << count << "!\n"; 
      ++numErrors; 
     } 
    } 

} 

Une note finale sur le nombre d'opérations arithmétiques: puisque la méthode prend en entrée les vecteurs de bord pré-calculé, 12 +/- opérations doivent être ajoutées au tableau I. du papier.

Last but not least: s'il vous plaît vérifier ce que je suis en train d'écrire sur votre propre et me donner des commentaires si vous pensez que j'ai mal compris quelque chose!