Accueil🇫🇷Chercher

Algorithme d'intersection de Möller–Trumbore

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[1]. Il est utilisé en infographie pour effectuer du lancer de rayons sur un maillage triangulaire[2].

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

Notes et références

(en) Cet article est partiellement ou en totalité issu de la page de Wikipédia en anglais intitulée « Möller–Trumbore intersection algorithm » (voir la liste des auteurs).

  1. Möller et Trumbore, « Fast, Minimum Storage Ray-Triangle Intersection », Journal of Graphics Tools, vol. 2,‎ , p. 21–28 (DOI 10.1080/10867651.1997.10487468)
  2. « Ray-Triangle Intersection », lighthouse3d (consulté le )
  3. Intersection de rayons de surfaces tessellées: quadrangles contre triangles, Schlick C., Subrenat G. Graphics Gems 1993


Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.