Bounding volume

Bryła brzegowa otaczająca model głowy

Bounding volume (bryła brzegowa, objetość ograniczająca) to w komputerowej grafice 3D bryła w uproszczony sposób przedstawiająca jak najmniejszą przestrzeń, w której całkowicie mieszczą się dane obiekty. Używa się ich, np. aby uprościć wykrywanie kolizji oraz sprawdzanie widoczności na ekranie zawartych w nich obiektów, dlatego że na uproszczonych bryłach można dużo szybciej i prościej wykonać testy kolizji.

Obiekty w grafice 3D złożone są z pojedynczych polygonów. Sprawdzenie kolizji każdego z tysięcy polygonów z pierwszego obiektu z polygonami z drugiego obiektu trwa długo, dlatego przy sprawdzaniu kolizji dwóch obiektów najpierw sprawdza się czy ich bounding volume mają kolizję, a jeżeli nie mają można od razu powiedzieć, że zawarte w nich obiekty też nie mają kolizji.

[edytuj] Najczęstsze typy bounding volume

• Bounding sphere (ang. sphere - kula) to jak najmniejsza kula kompletnie otaczająca obiekt. Można bardzo szybko sprawdzić kolizję jednej kuli z drugą: dwie kule nie pokrywają się, gdy odległość między ich środkami jest większa od sumy ich promieni.

• Bounding box (ang. box - pudełko) to jak najmniejszy prostopadłościan kompletnie otaczający dany obiekt.
  Bounding box może być ułożony:
  • w dowolnej pozycji, wtedy jest to oriented bounding box (OBB)
  • równo z osiami układu współrzędnych - axis-aligned bounding box (AABB)

Łatwiej jest sprawdzić kolizję AABB, ale OBB dużo dokładniej opisuje kształt obiektu.

Często najpierw sprawdza się kolizje bounding sphere, później kolizję bounding box, a na końcu kolizję samych obiektów.

[edytuj] Hierarchie brył brzegowych

Dodatkowo bryły brzegowe grupuje się w kolejne bryły brzegowe, a powtarzając procedurę, tworzy w ten sposób hierarchie (o strukturze drzewa, z jedną bryłą brzegową obejmującą całą scenę). Hierarchie te (BVH, Bounding Volume Hierarchies) używa sie powszechnie przy wykrywaniu kolizji oraz renderowaniu scen dynamicznych (obliczenie samego BVH jest kosztowne, ale jego zgrubna aktualizacja po zmianie pozycji obiektów jest prosta) techniką śledzenia promieni.

Obliczanie optymalnego BVH dla danego zastosowania jest zadaniem trudnym (ilość możliwych podziałów obiektów w binarnym BVH z AABB jest rzędu 2ⁿ). Korzysta się albo z pomocy programu do modelowania, w którym taka hierarchia jest już zawarta w obiektach, albo używa algorytmów przybliżonych (używając prostych AABB, rozpatrując jedynie kilka możliwości, oraz stosują inne heurezy).