Leksykon IT › Programowanie › Möller–Trumbore

Möller–Trumbore

Programowanie Svenska → Zaktualizowano: 2026-10-27

Standardowy test przecięcia promienia z trójkątem, który znajduje punkt trafienia bez liczenia płaszczyzny trójkąta.

Podręcznikowe podejście ma dwa kroki: przecięcie promienia z płaszczyzną trójkąta, a potem sprawdzenie, czy punkt trafienia leży wewnątrz wszystkich trzech krawędzi. Tomas Möller i Ben Trumbore wykazali w 1997 roku, że płaszczyzna jest zbędna. Promień zapisuje się jako początek plus kierunek, trójkąt jako wierzchołek i dwa wektory krawędzi, a powstały układ rozwiązuje się wzorami Cramera — to kilka iloczynów wektorowych i skalarnych. Od razu wychodzą odległość t oraz współrzędne barycentryczne u i v.

Nie trzeba przechowywać danych płaszczyzny dla każdego trójkąta, co miało znaczenie, gdy pamięci brakowało. Dziś algorytm tkwi w niemal każdym programowym ray tracerze, w raycastach względem koliderów siatkowych i w wybieraniu obiektów myszą. Wczesne wyjścia po sprawdzeniu u i v sprawiają, że większość chybień kończy się w połowie obliczeń.

← Wróć do leksykonu