Drzewo ósemkowe
(c) Nü, CC-BY-SA-3.0
Po lewej – rekursywny podział sześcianu, po prawej – drzewo ósemkowe odpowiadające podziałom
Drzewo ósemkowe (ang. octree) – stosowana w grafice komputerowej struktura danych będąca drzewem, używana do przestrzennego podziału trójwymiarowej przestrzeni na mniejsze, regularne części.
Konstrukcja drzewa ósemkowego polega na otoczeniu całości sceny trójwymiarowej sześcianem (lub prostopadłościanem), który następnie dzielony jest na osiem mniejszych, a z kolei każdy z nich na osiem kolejnych itd. – proces podziału ma charakter rekurencyjny.
Najczęściej boki sześcianu są równoległe do osi układu współrzędnych, dzięki temu operacje geometryczne znacznie się upraszczają.
Zastosowanie drzew ósemkowych
- Efektywna reprezentacja wokseli – w każdym liściu pełnego drzewa ósemkowego zapisana jest informacja o tym, czy dany sześcian zawiera woksel, czy też nie (jest „pusty”). Wówczas możliwe jest „spakowanie” informacji, gdy bowiem wszystkie osiem dzieci danego węzła są puste (lub wszystkie są zajęte), można je usunąć, zaś do węzła przepisać informację o zajętości.
- Wykrywanie kolizji.
- Kwantyzacja kolorów w obrazach cyfrowych – polega na zmniejszaniu liczby kolorów, przy zachowaniu jak najmniejszych błędów wizualnych.
- W renderingu grafiki 3D, usprawnienie usuwania niewidocznych obiektów, znajdujących się poza bryłą widzenia (ang. view frustum culling) – co umożliwia bardzo szybkie odrzucanie (lub akceptowanie) całych gałęzi drzewa bez zagłębianie się w nie, tj. bez dodatkowych, czasochłonnych testów. Testowanie widoczności ma charakter rekurencyjny i zaczyna się od korzenia drzewa ósemkowego. Sprawdzanie widoczności sześcianu zapisanego w węźle:
- Jeśli jest on niewidoczny, to nie są widoczne także wszystkie obiekty, które się w nim znajdują; podobnie jeśli jest w całości widoczny – widoczne są także wszystkie obiekty w nim zawarte.
- Jeśli natomiast widoczność sześcianu jest częściowa, przechodzi się w głąb drzewa i testuje widoczność jego ośmiorga dzieci – mniejszych sześcianów.
Na zielono zaznaczono sześciany w całości znajdujące się wewnątrz bryły widzenia, na czerwono znajdujące się poza nią, na niebiesko zawarte częściowo w bryle widzenia
Zobacz też
- drzewo czwórkowe – dwuwymiarowy odpowiednik drzew ósemkowych
- drzewo kd
- drzewo BSP
Media użyte na tej stronie
Octree2.png
(c) Nü, CC-BY-SA-3.0
(c) Nü, CC-BY-SA-3.0
- Bildbeschreibung: Schemazeichnung eines de:Octrees, einer Datenstruktur der Informatik.
- Zeichner: Nü
- Datum: 7. April 2006
Quadtree division example.svg
(c) Wojciech mula z polskiej Wikipedii, CC-BY-SA-3.0
Ilustracja do art. Drzewo ósemkowe pokazująca iddę stosowania tych struktur do odrzucania niewidocznych części sceny trójwymiarowej, znajdujących się poza bryłą widzenia.
(c) Wojciech mula z polskiej Wikipedii, CC-BY-SA-3.0
Ilustracja do art. Drzewo ósemkowe pokazująca iddę stosowania tych struktur do odrzucania niewidocznych części sceny trójwymiarowej, znajdujących się poza bryłą widzenia.
Rysunek wykonany w Inkscape.
Na zielono zaznaczono sześciany w całości znajdujące się wewnątrz bryły widzenia, na czerwono znajdujące się poza nią, na niebiesko zawarte częściowo w bryle widzenia.