Алгоритм Моллера — Трумбора

Алгоритм Моллера — Трумбора — алгоритм для определения пересечения прямой (луча) и треугольника в трёхмерном пространстве, для работы которого не требуется предварительное вычисление уравнения плоскости, содержащей треугольник. Данный алгоритм также может быть использован в компьютерной графике для реализации трассировки лучей с использованием полигональных сеток, состоящих из треугольников.

Назван по имени авторов — Томаса Моллера (Tomas Möller) и Бена Трумбора (Ben Trumbore).

Реализация на языке C++

Ниже представлена реализация алгоритма на языке C++ с использованием библиотеки GLM:

#include <glm/glm.hpp>
using namespace::glm;

// orig и dir задают начало и направление луча. v0, v1, v2 - вершины треугольника.
// Функция возвращает расстояние от начала луча до точки пересечения или 0.
float
triangle_intersection(const vec3& orig,
                      const vec3& dir,
                      const vec3& v0,
                      const vec3& v1,
                      const vec3& v2) {
    vec3 e1 = v1 - v0;
    vec3 e2 = v2 - v0;
    // Вычисление вектора нормали к плоскости
    vec3 pvec = cross(dir, e2);
    float det = dot(e1, pvec);

    // Луч параллелен плоскости
    if (det < 1e-8 && det > -1e-8) {
        return 0;
    }

    float inv_det = 1 / det;
    vec3 tvec = orig - v0;
    float u = dot(tvec, pvec) * inv_det;
    if (u < 0 || u > 1) {
        return 0;
    }

    vec3 qvec = cross(tvec, e1);
    float v = dot(dir, qvec) * inv_det;
    if (v < 0 || u + v > 1) {
        return 0;
    }
    return dot(e2, qvec) * inv_det;
}