Testowanie promienia przeciw każdemu trójkątowi ze sceny liczącej miliony trójkątów byłoby katastrofalnie wolne. BVH sprawia, że sprawdzasz dziesiątki, nie miliony — bez zmiany ani jednego wzoru z Rozdziału 4.
Każdy promień pierwotny (Rozdział 3), cienia (Rozdział 6), odbity i załamany (Rozdział 7) potrzebuje testu przecięcia ze sceną (Rozdział 4). Naiwne podejście: sprawdź promień przeciw każdemu trójkątowi po kolei. Dla siatki z milionami trójkątów, przy wielu promieniach na piksel (Rozdział 8) i głębokości rekurencji z Rozdziału 7 — liczba testów eksploduje, mimo że promień naprawdę trafia w jeden, może dwa trójkąty.
Prosty test ray-AABB (axis-aligned bounding box — pudełko o ścianach równoległych do osi) jest dużo tańszy niż test ray-trójkąt. Kluczowa obserwacja: jeśli promień mija pudełko, gwarantowane jest, że mija wszystko wewnątrz niego — możesz odrzucić całą grupę za darmo, bez sprawdzania ani jednego trójkąta w środku.
BVH (Bounding Volume Hierarchy) zagnieżdża takie pudełka w drzewo: korzeń obejmuje całą scenę, każdy poziom dzieli się na mniejsze pudełka, aż liście zawierają już tylko kilka trójkątów. Trawersowanie: testuj pudełko; jeśli trafione, zejdź do dzieci; jeśli nie — od razu odetnij całe poddrzewo.
Pudełko to przecięcie trzech „plasterków” (slabs) — po jednym na każdą oś. Dla każdej osi liczysz t, przy którym promień wchodzi i wychodzi z plasterka, tym samym wzorem promienia P(t)=O+tD z Rozdziału 2. Promień trafia w pudełko, jeśli przedziały t z wszystkich osi się przecinają:
Budowa dobrego BVH — gdzie dzielić każdy węzeł — to osobne zagadnienie. Produkcyjne renderery używają SAH (Surface Area Heuristic): szacują koszt trawersowania dla różnych podziałów i wybierają ten, który minimalizuje oczekiwaną liczbę testów, zamiast dzielić po prostu na pół.
↓ Dodatek C — jak dokładnie działa SAHTo dlatego animowana, deformująca się geometria (postacie ze szkieletem, symulacje tkaniny) jest droższa w ray tracingu niż statyczna: BVH trzeba przebudować albo dopasować (refit) co klatkę. Sprzętowy ray tracing (RTX, wspomniany w Rozdziale 1) to w dużej mierze dedykowany układ do właśnie tego trawersowania.
BVH zmniejsza liczbę testów na promień. W następnym rozdziale zajmiemy się tym, jak policzyć miliony niezależnych promieni na raz — wielowątkowość na CPU i rozbieżność (divergence) na GPU.