Drzewo BVH

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Drzewo brył ograniczających (ang. bound volume hierarchy, BVH) – struktura danych do przechowywania i szybkiego wykonywania zapytań na temat obiektów w przestrzeni trójwymiarowej. Najczęściej stosowana w grafice komputerowej do akceleracji algorytmu śledzenie promieni (ray tracing) oraz w symulacjach fizyki ciał do akceleracji detekcji kolizji (np. w grach komputerowych).

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

Drzewo BVH ma najczęściej postać przestrzennie zrównoważonego drzewa binarnego (chociaż stosuje się też drzewa o rozwidleniu 4, 8 czy 16). Obiekty są ograniczone poprzez prostsze bryły (najczęściej pudełka – prostopadłościany ze ścianami równoległymi do osi układu współrzędnych lub kulami), 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 na dół (poprzez podział większych brył na mniejsze), jak i z dołu na górę (poprzez łączenie brył mniejszych w większe).

W porównaniu do drzew kd (również stosowanych w śledzeniu promieni i symulacjach) w przypadku scen dynamicznych (w których obiekty się poruszają 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 drzewa kd są szybsze, 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ż[edytuj | edytuj kod]