Drzewo OCT


Drzewo czwórkowe (ang. Quad tree). Podobnie jak drzewo BSP 2D służy do podziału powierzchni płaszczyzny. Powierzchnia płaszczyzny jest dzielona dwoma prostopadłymi płaszczyznami na cztery równe części, z których każda może być dzielona dalej tworząc kolejne gałęzie drzewa czwórkowego. W najprostszym przypadku jest to płaska mapa składająca się z komórek o zadanych jednakowych wymiarach. Do lokalizacji komórki obserwatora bierzemy np. składowe x i z pozycji obserwatora pomijając składową y. Następnie renderujemy zawarte w komórce obserwatora wielokąty terenu oraz wielokąty zawarte we wszystkich innych komórkach, których odległości są mniejsze od zadanej i znajdują się przed obserwatorem. Wielokąty terenu są budowane z tzw. mapy wysokości (ang. Highmap), która została losowo wygenerowana dla każdej komórki. Proces budowy wielokątów z mapy wysokości może być wykonany wcześniej i do silnika wczytywany jest już gotowy teren. Możemy wykorzystać mgłę lub rozjaśnić składowe koloru krajobrazu dla wielokątów znajdujących się dalej od obserwatora. Często wielokąty terenu znajdujące się powyżej lub poniżej pewnego poziomu mają zmodyfikowane składowe koloru, co daje złudzenie ośnieżenia wierzchołków gór lub zmiany barwy dna morskiego.

Drzewo ósemkowe (ang. OCT tree). Podobnie jak drzewo BSP 3D służy do podziału przestrzeni sceny. Zapis sceny do drzewa OCT polega na wpisaniu wielokątów sceny w strukturę komórek zgrupowanych po osiem. Komórki z grupy są dzielone trzema prostopadłymi płaszczyznami na osiem równych części, z których każda może być dzielona dalej tworząc kolejne gałęzie drzewa OCT. Dzielimy tylko te komórki, które zawierają wielokąty sceny. Proces podziału kończymy gdy komórki są puste lub zawierają ustaloną ilość wielokątów. Najprostsze wykorzystanie drzewa OCT polega na lokalizacji komórki, w której znajduje się obserwator i renderowaniu grafiki zawartej w tej komórce oraz komórkach widzianych przez obserwatora, które jednak nie przekraczają pewnej zadanej odległości. Drzewa OCT mogą być wykorzystywane do zapisu i przetwarzania terenu.

Autor: Mirosław Kozioł, Komires Sp. z o.o.

Numer artykułu: 20
Wysłany: Sun, Feb 14, 2010 2:22 PM
Ostatnio zmieniony: Sun, Feb 14, 2010 3:47 PM

Adres URL: https://www.komires.net/article.php?id=20