Triangle Triangle Intersection dans l'espace 3D

Ce document décrit une implémentation:

http://knight.temple.edu/~lakaempper/ Cours / CIS350_2004 / etc / Moeller_triangle.pdf

Notez qu'il existe différentes techniques, selon que vous souhaitiez connaître le point / segment où l'intersection s'est produite ou indiquez simplement si un intersect est arrivé. Ce document vous donnera le segment de ligne représentant l'intersection.

Il y a un bon papier Par Devillers et al avec le titre "Tests d'intersection Triangle-Triangle plus rapide" - (Oui, a fait une recherche Google, mais les mots-clés de recherche sont importants ...)

Quoi qu'il en soit, leur point (comparé au papier Moeller dans la réponse de Michaelm) est que vous devriez vraiment obtenir vos informations combinatoires en faisant des déterminants de certains groupes de 4 points (le document décrit comment). Cela évite de calculer les valeurs intermédiaires qui peuvent être problématiquement incohérentes et qui ne seront probablement pas réellement plus rapides ...

Vous pouvez examiner ces déterminants comme déterminants si le tétraèdre formé par les 4 points est droitier, gaucher ou dégénéré (c'est-à-dire planar). 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 que la ligne (dirigée) 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, faire la chose déterminante rend votre calcul plus robuste, et si vous faites attention, vous pouvez généralement convertir des algorithmes qui n'ont pas initialement fait la chose déterminante dans ceux qui font. Ou, vous pouvez simplement lire le papier.

Beaucoup de gens s'appuient apparemment sur une implémentation ( Lien vers le code source ) de la méthode décrite en 2006 dans le document suivant ( Lien vers 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 existe cependant un problème avec ce code (à l'exception de l'adoption d'un ancien style de programmation, en utilisant des notations non conventionnelles et de perdre l'interprétation géométrique sous-jacente): "chose déterminante" ne rend pas nécessairement plus robuste, si fait de la mauvaise voie.

Je suggère d'utiliser la méthode de Moeller ( Lien vers pdf ) ou jeter un oeil au papier de Delliver ( Lien vers pdf) , implémenté dans la bibliothèque CGAL ( lien , "trianggle_3_triangle_3_do_intersect.h"). < / p>

un exemple : la routine d'intersection implémentée ci-dessus indique que les triangles (P0, P1, P2) et (q0, q1, q2) définis par les points suivants < Pré> xxx

est pas intersection. Voici une image des triangles:

Et voici le code de code (ajouter au code d'origine): xxx

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

dernier mais non le moindre: veuillez vérifier ce que j'écris à vous-même et donnez-moi des commentaires si vous pensez que j'ai mal compris quelque chose! < / p>