Алгоритм Моллера — Трумбора — алгоритм для определения пересечения прямой (луча) и треугольника в трёхмерном пространстве, для работы которого не требуется предварительное вычисление уравнения плоскости, содержащей треугольникFast, Minimum Storage Ray/Triangle Intersection , Möller & Trumbore. Journal of Graphics Tools, 1997.. Данный алгоритм также может быть использован в компьютерной графике для реализации трассировки лучей с использованием полигональных сеток, состоящих из треугольников.
Назван по имени авторов — Томаса Моллера (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; }
Примечания
Категория:Геометрические алгоритмы