Rozdział 13 pokazał, jak BVH przycina drzewo trawersowania. Nie pokazał, jak zbudować dobre drzewo w pierwszej kolejności — a od tego zależy, czy przycinanie faktycznie coś da.
TL;DR
Podział po samej liczbie obiektów może dać pudełka, które się mocno nakładają — a nakładające się pudełka rzadko dają się przycinać.
Surface Area Heuristic (SAH) szacuje oczekiwany koszt trawersowania dla każdego kandydata na podział i wybiera najlepszy — poniżej policzony, konkretny przykład z dwoma kandydatami i realnym zwycięzcą.
LBVH (krzywa Mortona) buduje drzewo błyskawicznie na GPU; spatial splits (SBVH) tną same obiekty, gdy grupowanie ich całych nie wystarcza.
Pass: Problem
Dlaczego podział na pół nie wystarcza
Najprostsza strategia — podziel obiekty na dwie równe grupy po liczbie, wzdłuż najdłuższej osi — działa świetnie, gdy obiekty są rozłożone równomiernie. Zawodzi, gdy nie są: gęsty klaster małych obiektów w jednym rogu i jeden odległy, duży obiekt gdzie indziej wciąż podzieli się „po połowie”, produkując dwa ogromne, mocno nakładające się pudełka — a przycinanie z Rozdziału 13 działa tylko wtedy, gdy pudełka faktycznie się rozchodzą w przestrzeni.
Median.vs.spatial.splitoverlap matters
Te same dziewięć obiektów — po lewej podział „po liczbie” psuje wszystko, po prawej podział rozumie przestrzeń.
Pass: SAH
Surface Area Heuristic: licz koszt, nie zgaduj
SAH formalizuje „jak dobry jest ten podział”, szacując oczekiwany koszt trawersowania — prawdopodobieństwo, że promień wejdzie w każde dziecko, przybliżone stosunkiem powierzchni jego pudełka do powierzchni pudełka rodzica:
koszt(podział) = C_trav + (SA_L/SA_parent)·N_L·C_isect + (SA_R/SA_parent)·N_R·C_isectSA — powierzchnia pudełka (surface area); N — liczba obiektów w dziecku; C_trav, C_isect — koszty jednostkowe trawersowania i testu przecięcia
Budowa drzewa próbuje wielu kandydatów na podział (zwykle wzdłuż każdej osi, w kilkunastu pozycjach) i wybiera ten o najniższym koszcie SAH — rekurencyjnie, dla każdego węzła.
SAH.cost.landscapeminimum wins
Dolina kosztu — nie zawsze pośrodku, nie zawsze intuicyjna, ale policzona, nie odgadnięta.
Pełny przykład liczbowy — te same 4 obiekty co w poprzednim diagramie
Kandydat 2 wygrywa (2,565 < 2,913) — mimo że dzieli obiekty bardziej „nierówno” (3 kontra 1, nie 2 kontra 2).
Sprawdzenie sensu: brak podziału (jeden węzeł, testuj wszystkie 4) kosztowałby 4·C_isect=4,0 — oba kandydaci są lepsi niż brak podziału, a Kandydat 2 jest lepszy od Kandydata 1 właśnie dlatego, że odizolowanie odległego obiektu daje dużo mniejsze, szczelniejsze pudełko SA_R=6, nie 30.
Pass: Alternatywy
LBVH i spatial splits
LBVH (Linear BVH) pomija kosztowną, rekurencyjną ocenę SAH: sortuje obiekty według ich pozycji na krzywej Mortona (Z-order — bity x, y, z przeplecione w jedną liczbę) i budowa drzewa staje się prostym sortowaniem, świetnie równoległym na GPU. Jakość drzewa jest nieco niższa niż z SAH, ale budowa jest na tyle szybka, że opłaca się przebudowywać je co klatkę dla animowanej geometrii.
Spatial splits (SBVH) rozwiązują inny problem: gdy jeden obiekt jest bardzo długi (ściana przez całą scenę), żaden podział po liczbie obiektów nie pomoże — ten jeden obiekt i tak trafi do obu dzieci. SBVH pozwala przeciąć pudełko obiektu w przestrzeni, przypisując różne jego fragmenty do różnych dzieci.
LBVH.morton+ spatial split
Z-order odwiedza sąsiadów w przestrzeni po kolei — idealne do sortowania. Po prawej: jeden długi obiekt, przecięty na dwa fragmenty.
Z praktyki
To dlaczego „Build Acceleration Structure” trwa zauważalnie dłużej dla scen z milionami trójkątów w Arnoldzie czy RenderManie — wysokiej jakości SAH build jest kosztowny, ale opłaca się przy renderze trwającym godziny. Sprzętowy RT (RTX) w grach używa szybszych, LBVH-podobnych buildów z refittingiem co klatkę — bo scena i tak zmienia się 60 razy na sekundę, więc idealne drzewo nie ma czasu się przydać.
Słowniczek
Median split
Podział po liczbie obiektów, niezależnie od ich rozmieszczenia w przestrzeni.
Surface Area Heuristic (SAH)
Szacowanie kosztu podziału przez stosunek powierzchni pudełek.
Koszt trawersowania
Oczekiwana liczba operacji potrzebna do przejścia drzewa dla promienia.
LBVH
Szybka budowa BVH przez sortowanie po krzywej Mortona.
Kod Mortona (Z-order)
Przeplot bitów współrzędnych, dający jednowymiarowe uporządkowanie punktów 3D.
Spatial split (SBVH)
Przecinanie pudełka obiektu między dzieci, nie tylko grupowanie całych obiektów.
Co dalej
Dodatek D, ostatni, rozwija Rozdział 19: jak faktycznie liczy się wagi w filtrze denoisera, i czemu agresywny denoising „gubi” futro i ostre kaustyki.