Rozdział 4 dał Ci gotowy przepis: edge1, edge2, h, det, s, q, t, u, v — i działało. Ten dodatek pokazuje, że nic z tego nie jest magią ani szczęśliwym zgadywaniem — to wzór Cramera na banalny układ trzech równań, tylko zapisany przez iloczyny wektorowe, żeby uniknąć jawnego liczenia wyznaczników 3×3.
TL;DR
„Promień trafia w trójkąt” to układ 3 równań liniowych z 3 niewiadomymi: t, u, v.
Rozwiązanie przez wzór Cramera wymaga jednej sztuczki: iloczynu potrójnego trzech wektorów i jego cyklicznej symetrii, a·(b×c) = b·(c×a) = c·(a×b).
h, det, s, q z Rozdziału 4 to dosłownie cztery konkretne wyznaczniki tego układu — ten dodatek pokazuje, który jest który.
Pass: Warunek
Punkt wspólny: promień = punkt na trójkącie
Promień z Rozdziału 2 to P(t) = O + t·D. Punkt na trójkącie z Rozdziału 4, zapisany przez wierzchołek A i wektory krawędzi, to P = A + u·edge1 + v·edge2 (to dosłownie te same u, v co wagi barycentryczne — tylko wyrażone przez edge’e, nie przez A, B, C wprost). Trafienie to sytuacja, w której obie strony opisują ten sam punkt:
O + t·D = A + u·edge1 + v·edge2
Przegrupuj tak, żeby wszystkie niewiadome (t, u, v) były po jednej stronie, a znane wektory po drugiej. Oznacz s = O − A:
−t·D + u·edge1 + v·edge2 = s
Vector.setup3 unknowns hidden in plain sight
Trzy znane wektory (s, edge1, edge2) i jeden nieznany kierunek D — t, u, v mówią, jak je poskładać, żeby się zgodziły.
Pass: Układ
Układ trzech równań, trzech niewiadomych
Powyższe równanie wektorowe to w rzeczywistości trzy zwykłe równania skalarne — jedno na współrzędną x, jedno na y, jedno na z. Zapisane jako macierz razy wektor niewiadomych:
[ −D | edge1 | edge2 ] · [t, u, v]ᵗ = smacierz 3×3, której kolumnami są wektory −D, edge1, edge2; standardowy układ liniowy, żadnej specjalnej struktury geometrycznej
To jest dokładnie taki układ, jaki rozwiązywałeś na studiach metodą eliminacji Gaussa albo wzorem Cramera. Möller i Trumbore po prostu zauważyli, że dla układów 3×3 wzór Cramera można zapisać wyłącznie przez iloczyny wektorowe i skalarne — bez jawnego wypisywania wyznacznika 3×3 ze wzoru rozwinięcia Laplace’a.
Pass: Cramer
Wzór Cramera i iloczyn potrójny
Dla układu M·x = s, gdzie M ma kolumny (c₁, c₂, c₃), wzór Cramera mówi: każda niewiadoma xᵢ to wyznacznik macierzy M z i-tą kolumną zastąpioną przez s, podzielony przez wyznacznik M:
xᵢ = det(Mᵢ) / det(M)
Kluczowa sztuczka: wyznacznik macierzy 3×3 zbudowanej z trzech wektorów jako kolumn to iloczyn potrójny (triple product) tych wektorów — a iloczyn potrójny ma cykliczną symetrię, którą można przestawiać bez zmiany wartości:
det([a|b|c]) = a·(b×c) = b·(c×a) = c·(a×b)te trzy wyrażenia są sobie równe — możesz wybrać tę wersję, która wygodniej się liczy
Cyclic.triple.producta·(b×c)=b·(c×a)=c·(a×b)
Ta sama wartość, trzy sposoby zapisu — przesuwasz „kropkę” cyklicznie po trzech wektorach.
Pass: Podstawienie
Skąd się biorą h, det, s, q
Zastosuj wzór Cramera do naszego układu, kolumna po kolumnie, i za każdym razem użyj cyklicznej symetrii, żeby zapisać wynik przez to, co już masz policzone:
det(M) = det([−D | edge1 | edge2]) = −D·(edge1×edge2) = edge1·(D×edge2) = edge1·hgdzie h = D×edge2 — to dosłownie krok 2 z diagramu pipeline’u w Rozdziale 4
det(Mᵤ) = det([−D | s | edge2]) = −D·(s×edge2) = s·(D×edge2) = s·h → u = (s·h) / det
det(Mᵥ) = det([−D | edge1 | s]) = −D·(edge1×s) = D·(s×edge1) = D·q → v = (D·q) / det, gdzie q = s×edge1
det(M_t) = det([s | edge1 | edge2]) = s·(edge1×edge2) = edge2·(s×edge1) = edge2·q → t = (edge2·q) / det
To wszystko. Każda linia algorytmu z Rozdziału 4 — h, det, s, q, u, v, t — to jeden konkretny wyznacznik z Cramera, przepisany przez cykliczną symetrię triple product tak, żeby dało się go policzyć dwoma iloczynami wektorowymi i kilkoma iloczynami skalarnymi, bez rozpisywania macierzy 3×3 wprost.
Pass: Weryfikacja
Ten sam przykład, dwiema metodami
Weź trójkąt i promień z Rozdziału 4: A=(0,0,0), B=(4,0,0), C=(0,3,0), O=(1,1,5), D=(0,0,−1). Policz t, u, v obiema metodami i porównaj.
Identyczne wyniki: t=5,0, u=0,25, v=0,333 — dwiema, na pierwszy rzut oka różnymi, drogami.
To nie przypadek — to ta sama cykliczna symetria triple product, użyta w każdej linii wyżej.
Z praktyki
Ta sama technika — zapisz „czy promień trafia w kształt X” jako układ liniowy, rozwiąż Cramerem, uprość przez cykliczną symetrię triple product — działa dla każdego prymitywu opisanego liniowo: czworokątów (quads), dysków, nawet niektórych powierzchni parametrycznych. Jeśli kiedykolwiek będziesz pisać własny test przecięcia dla nietypowego kształtu, to jest dokładnie ta metoda, od której warto zacząć.
Słowniczek
Wzór Cramera
xᵢ = det(Mᵢ)/det(M) — rozwiązanie układu liniowego przez wyznaczniki.
Iloczyn potrójny (triple product)
a·(b×c) — skalar równy wyznacznikowi macierzy z kolumnami a, b, c.
Trzy równania skalarne (x,y,z) z trzema niewiadomymi (t,u,v).
Co dalej
Ta sama technika (Cramer + triple product) wraca, gdy w Rozdziale 13/Dodatku C liczysz przecięcia ray-AABB metodą slab test — tam też rozwiązujesz układ liniowy, tylko rozdzielony na trzy niezależne osie zamiast jednego układu 3×3.