Drzewo ósemkowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Po lewej - rekursywny podział sześcianu, po prawej - drzewo ósemkowe odpowiadające podziałom

Drzewo ósemkowe (ang. octree) to 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 następnie 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:

  1. 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.
  2. W renderingu grafice 3D usprawniają odrzucanie niewidocznych obiektów, znajdujących się poza bryłą widzenia (view frustum culling) - można bardzo szybko odrzucać (lub akceptować) całe gałęzie 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. Sprawdzana jest widoczność sześcianu zapisanego w węźle:
    • Jeśli jest on niewidoczny, wiadome jest, że 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śmiu 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.
  3. Wykrywanie kolizji
  4. Kwantyzacja kolorów w obrazach cyfrowych - polega na zmniejszaniu liczby kolorów, przy zachowaniu jak najmniejszych błędów.

Zobacz też[edytuj | edytuj kod]