L'algorithme d'intersection "rayon-triangle" de Möller-Trumbore, nommé après de ses inventeurs Tomas Möller et Ben Trumbore, est une méthode de calcul rapide de l'intersection d'un rayon et d'un triangle en trois dimensions, sans nécessiter le pré-calcul de l'équation du plan contenant le triangle. Il est utilisé en infographie pour effectuer du lancer de rayons sur un maillage triangulaire.
Implémentation C++ Voici une implémentation de l'algorithme en C++ : bool RayIntersectsTriangle(Vector3D rayOrigin, Vector3D rayVector, Triangle* inTriangle, Vector3D& outIntersectionPoint) { const float EPSILON = 0.0000001; Vector3D vertex0 = inTriangle->vertex0; Vector3D vertex1 = inTriangle->vertex1; Vector3D vertex2 = inTriangle->vertex2; Vector3D edge1, edge2, h, s, q; float a,f,u,v; edge1 = vertex1 - vertex0; edge2 = vertex2 - vertex0; h = rayVector.crossProduct(edge2); a = edge1.dotProduct(h); if (a > -EPSILON && a < EPSILON) return false; // Le rayon est parallèle au triangle.
f = 1.0/a; s = rayOrigin - vertex0; u = f * (s.dotProduct(h)); if (u < 0.0 || u > 1.0) return false; q = s.crossProduct(edge1); v = f * rayVector.dotProduct(q); if (v < 0.0 || u + v > 1.0) return false;
// On calcule t pour savoir ou le point d'intersection se situe sur la ligne. float t = f * edge2.dotProduct(q); if (t > EPSILON) // Intersection avec le rayon
outIntersectionPoint = rayOrigin + rayVector * t; return true;
else // On a bien une intersection de droite, mais pas de rayon. return false;
Implémentation Java Ce qui suit est une implémentation de l'algorithme en Java, utilisant javax.vecmath (API Java 3D): public class MollerTrumbore {
private static double EPSILON = 0.0000001;
public static boolean rayIntersectsTriangle(Point3d rayOrigin, Vector3d rayVector, Triangle inTriangle, Point3d outIntersectionPoint) { Point3d vertex0 = inTriangle.getVertex0(); Point3d vertex1 = inTriangle.getVertex1(); Point3d vertex2 = inTriangle.getVertex2(); Vector3d edge1 = new Vector3d(); Vector3d edge2 = new Vector3d(); Vector3d h = new Vector3d(); Vector3d s = new Vector3d(); Vector3d q = new Vector3d(); double a, f, u, v; edge1.sub(vertex1, vertex0); edge2.sub(vertex2, vertex0); h.cross(rayVector, edge2); a = edge1.dot(h); if (a > -EPSILON && a < EPSILON) { return false; // Le rayon est parallèle au triangle.
f = 1.0 / a; s.sub(rayOrigin, vertex0); u = f * (s.dot(h)); if (u < 0.0 || u > 1.0) { return false;
q.cross(s, edge1); v = f * rayVector.dot(q); if (v < 0.0 || u + v > 1.0) { return false;
// On calcule t pour savoir ou le point d'intersection se situe sur la ligne. double t = f * edge2.dot(q); if (t > EPSILON) // // Intersection avec le rayon
outIntersectionPoint.set(0.0, 0.0, 0.0); outIntersectionPoint.scaleAdd(t, rayVector, rayOrigin); return true; } else // On a bien une intersection de droite, mais pas de rayon.
return false;
Voir aussi Articles connexes Ray tracing Algorithme d'intersection de Badouel Algorithme de Schlick–SubrenatIntersection de rayons de surfaces tessellées: quadrangles contre triangles, Schlick C., Subrenat G. Graphics Gems 1993 pour l'intersection rayon-quadrilatère
Liens externes Version MATLAB de cet algorithme (hautement vectorisé) Algorithme d'intersection rayon-triangle de Baldwin-Weber
Notes et références
Catégorie:Pages avec des traductions non relues Catégorie:3D Catégorie:Algorithme d'infographie