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

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

Назван по имени авторов — Томаса Моллера (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; }