Drzewo BVH

Drzewo brył ograniczających (ang. Bound Volume Hierarchy, BVH) – struktura danych do przechowywania i szybkiego wykonywania zapytań dotyczących obiektów w przestrzeni trójwymiarowej. Najczęściej stosowana jest w grafice komputerowej do akceleracji algorytmu śledzenia promieni (ang. ray tracing) oraz w symulacjach fizyki ciał do akceleracji detekcji kolizji (np. w grach komputerowych). Drzewo BVH ma najczęściej postać przestrzennie zrównoważonego drzewa binarnego (chociaż stosuje się też drzewa o rozwidleniu 4, 8 czy 16).

Przykładowe drzewo BVH obiektów dwuwymiarowych, w którym używane są prostokąty otaczające AABB

Obiekty znajdujące się w przestrzeni trójwymiarowej ograniczone są poprzez prostsze bryły – najczęściej prostopadłościany ze ścianami równoległymi do osi układu współrzędnych (ang. box, pudełko) lub kule – a ograniczenie drzewa łatwo wyznaczyć poprzez ograniczenie dwóch poddrzew.

Drzewa BVH mają różną konstrukcję w zależności od zastosowań. Można je budować zarówno z góry w dół (poprzez podział większych brył na mniejsze), jak i z dołu w górę (poprzez łączenie brył mniejszych w większe).

W przeciwieństwie do drzewa kd (również stosowanych w metodach śledzenia promieni i symulacjach), w przypadku scen dynamicznych, (w których obiekty poruszają się lub pojawiają i znikają) drzewo BVH łatwo uaktualnić poprzez utrzymanie struktury i zmianę rozmiarów pudełek, tak aby było nadal prawidłowe i bliskie optymalności – która i tak zwykle jest oparta na heurystykach. W przypadku drzew kd jest to niemożliwe. W praktyce korzystanie z nich jest bardziej wydajne, jednak z uwagi na koszt tworzenia jakichkolwiek drzew w przypadku scen dynamicznych używa się drzew BVH, ponieważ można je zbudować raz i wykorzystać w wielu następnych klatkach sceny – podobieństwo sceny w czasie powoduje, że drzewo BVH jest wystarczająco dobre.

Zobacz też

• bryła brzegowa
• drzewo BSP
• drzewo kd
• R-drzewo
• drzewo ósemkowe