Leszek Godlewski - struktury drzewiaste

Leszek Godlewski · inf. sem. 3, gr. 1 · AiSD1
Struktury drzewiaste
Spis treści
Wstęp....................................................................................................................................................1
Drzewa binarne.....................................................................................................................................1
Trochę historii – BSP (Binary Space Partition) w grach.................................................................1
Binarny podział przestrzeni – jak to działa?....................................................................................2
Budowa drzewa sceny.....................................................................................................................3
Problem wyboru płaszczyzny podziału.......................................................................................5
Rysowanie sceny z użyciem drzewa BSP........................................................................................6
ABT (Adaptive Binary Tree) – BSP dla dynamicznych scen?........................................................7
Różnice wobec drzew BSP.........................................................................................................7
Drzewa czwórkowe..............................................................................................................................8
Renderowanie terenu z użyciem map wysokości............................................................................8
Optymalizacja widocznych łat.........................................................................................................9
Łaty łat, czyli drzewo................................................................................................................10
Dalsze udoskonalenia................................................................................................................10
Podsumowanie....................................................................................................................................11
Bibliografia.........................................................................................................................................12
Wstęp
Drzewa to jedne z najważniejszych struktur danych, jakimi dysponuje informatyka. Za ich
pomocą opisuje się wiele problemów, w których występuje jakaś hierarchia, gdyż w naturalny
sposób ją reprezentują. Ułatwiają kluczową operację, jaką jest przeszukiwanie, przez co stosuje się
je we wszystkich dziedzinach informatyki – bazach danych, grafice komputerowej, przetwarzaniu
tekstów. Jednakże jako programista gier komputerowych – z zamiłowania, a także z zawodu –
opiszę je z właśnie takiego punktu widzenia.
W pierwszej części referatu skupię się na wykorzystaniu drzew binarnych; w drugiej opiszę
pokrótce struktury pokrewne - mianowicie drzewa czwórkowe.
Cały prezentowany kod jest napisany w języku C. Wybierałem angielskie nazwy symboli
w kodzie gdyż uważam, że są bardziej eleganckie. Nie implementowałem funkcji pomocniczych
wykonujących pewne elementarne operacje, gdyż ich treść jest nieistotna z punktu widzenia tematu
referatu.
Tam, gdzie nie jest to uściślone, zakładam przestrzeń trójwymiarową.
Drzewa binarne
Trochę historii – BSP (Binary Space Partition) w grach
Drzewa BSP na dobre zagościły w grach komputerowych od czasu pierwszej gry
1
z trójwymiarową grafiką, która trafiła na szeroki rynek – Wolfensteina 3D (1992), której
technologię stworzył w id Software programista John Carmack, człowiek mający dziś w środowisku
twórców gier status żywej legendy. Abstrahując od bardzo ciekawej metody rasteryzacji grafiki,
która doczekała się własnej nazwy – tzw. 2,5D – jednym z kluczowych elementów silnika gry było
właśnie zastosowanie drzew BSP. Umożliwiły one sensowną organizację przestrzenną obiektów
(oraz geometrii poziomów – ścian, sufitów, podłóg itp.) rozmieszczonych na poziomach gry w taki
sposób, by optymalizować potencjalnie widoczne zbiory powierzchni (ang. PVS – Potentially
Visible Sets) przed skierowaniem sceny do renderowania, czy wykrywanie kolizji. Biorąc pod
uwagę osiągi maszyn z tego okresu (rok 1992 to jeszcze czasy dominacji wczesnych procesorów z
rodziny 80X86, wymagania sprzętowe gry mówią o 80286 i 640 kB pamięci RAM), Carmack miał
niewielkie pole manewru, jeśli chodzi o czas wykonania algorytmu. Na szczęście zastosowanie
drzew BSP rozwiązało ten trudny problem.
Postęp technologiczny spowodował pojawienie się potężniejszego sprzętu, a id Software
wydawało następne gry: Doom (1993), Doom II (1994), Quake (1996), Quake II (1997) itd. Każda
z nich stanowiła kolejną rewolucję technologiczną w dziedzinie gier, ale w sercach ich silników
nadal pozostawały drzewa BSP. Fragmenty kodu dotyczące drzew BSP datowane na rok 1990
można znaleźć w kodzie źródłowym nawet najnowszej z dostępnych na licencji GPL gier
korzystających z technologii id Software, czyli cycki i Wolfenstein: Enemy Territory (2003),
a zapewne i w zupełnie najnowszych produkcjach, których technologie wywodzą się z tych
rozwiązań, czyli serii Call of Duty, w tym wydanych w 2010 r. Modern Warfare 2 oraz Call of
Duty: Black Ops.
BSP oczywiście używano już wcześniej, m. in. w operacjach CSG (Constructive Solid
Geometry) w oprogramowaniu typu CAD, czy wykrywaniu kolizji w robotyce. Użycie
hiperpłaszczyzn do podziału sceny zaproponowano już w 1969 roku (z tym, że płaszczyzny ręcznie
umieszczał w niej projektant); na pełniejsze zdefiniowanie drzewa BSP musiały jednak poczekać do
roku 1980 i publikacji Henry'ego Fuchsa [Fuchs80].
Binarny podział przestrzeni – jak to działa?
Przechodząc do sedna problemu – BSP jest metodą podziału przestrzeni na wypukłe
podzbiory za pomocą hiperpłaszczyzn. Taki podział prowadzi właśnie do struktury drzewa
binarnego, które to drzewo od tej pory będę nazywał drzewem BSP.
Drzewo BSP powstaje przez rekursywny podział przestrzeni na dwie części, aż do spełnienia
pewnego warunku (mogą nim być np. rozmiary przestrzenne węzła czy liczba obiektów świata gry,
które obejmuje; zależy to od pożądanego efektu). Przykładowo, w drzewie używanym w procesie
wykrywania kolizji podziału dokonuje się do momentu, gdy węzeł będący kandydatem na liść
drzewa jest wystarczająco prosty, by sprawdzać go indywidualnie. W renderingu natomiast szuka
się takiego podziału, aby uzyskać liście będące wypukłymi elementami geometrii, dzięki czemu
można z użyciem takiego drzewa łatwo zastosować tzw. algorytm malarza1
.
1 Algorytm malarza – stosowany powszechnie w grafice komputerowej, polega na rysowaniu obiektów w kolejności
od najdalszego do najbliższego. Piksele dalszych obiektów są nadpisywane pikselami obiektów bliższych.
2
Nie da się uniknąć wzrostu ilości ostatecznych obiektów, gdyż każdy element geometrii
przecinający się z dzielącymi przestrzeń płaszczyznami musi także zostać podzielony (lub też
zduplikowany – w takim wypadku każda z kopii trafia do innego węzła). Ze względów
wydajnościowych jest także pożądane, by drzewo było rozsądnie zbalansowane, dlatego też
zaprojektowanie algorytmu generującego poprawnie i efektywnie dobre drzewo BSP jest
najtrudniejszą częścią implementacji (przeszukiwanie go jest już sprawą trywialną).
Ilustracja poniżej pokazuje proces podziału nieregularnego wielokąta w kilka wypukłych
figur, generując jedną kompletną gałąź drzewa BSP.
Z uwagi na to, że użyteczność drzewa BSP zależy od jego jakości, dobry algorytm generujący
jest niezbędny. Większość algorytmów będzie z gatunku z powrotami, testując wiele możliwości dla
każdego podziału, aż do znalezienia akceptowalnego kompromisu, co przekłada się na długi czas
wykonania.
Budowa drzewa sceny
Zaprezentuję teraz przykładowy algorytm generacji drzewa BSP. Pragnę tylko zaznaczyć, że
w rozumieniu tego algorytmu płaszczyznę reprezentujemy jako parę {n ,d } , gdzie n to wektor
normalnej płaszczyzny, a d to jej odległość od środka układu współrzędnych wzdłuż normalnej.
Taki sposób opisu pozwala dzielić przestrzeń na znajdującą się przed (po stronie grotu strzałki
wektora normalnej) i za płaszczyzną.
Zacznę od definicji struktury pojedynczego węzła drzewa:
typedef struct BSPNode_s {
// wskaźniki na węzły leżące przed i za płaszczyzną podziału oraz
// na rodzica
struct BSPNode_s *front, *back, *parent;
// płaszczyzna podziału
Plane plane;
// lista wielokątów sceny tworzących dany węzeł
3
PolygonListNode *polygons;
} BSPNode;
Węzły front i back są także nazywane dziećmi. Strukturę opatrzono odpowiednimi
komentarzami.
Poniżej przedstawiam listing algorytmu generującego drzewo na podstawie listy wielokątów
tworzących scenę:
BSPNode *BuildTree(PolygonListNode *polygons) {
// listy wielokątów, które będą rozdzielane na węzły-dzieci
PolygonListNode *frontList = NULL, *backList = NULL;
// wielokąt wg którego będziemy dzielić przestrzeń
PolygonListNode *splitter = NULL;
// zmienne pomocnicze
PolygonListNode *p;
BSPNode *n;
// jeśli nie ma już wielokątów, węzeł jest niepotrzebny
if (!polygons)
return NULL;
// w przeciwnym razie tworzymy nowy węzeł
n = malloc(sizeof(*n));
memset(n, 0, sizeof(*n));
// wybierz wielokąt, wg którego podzielimy przestrzeń (i usuń go z listy!)
splitter = PickSplitterPolygon(polygons);
// użyj jego płaszczyzny jako płaszczyzny podziału
n->plane = GetPolygonPlane(splitter);
// dodaj wielokąt do listy wielokątów węzła
AddPolygonToList(&n->polygons, splitter);
// iteruj po wszystkich wielokątach w liście
for (p = polygons; p != NULL; p = p->next) {
// czy wielokąt leży przed płaszczyzną podziału?
if (IsPolygonInFrontOfPlane(p, n->plane))
AddPolygonToList(&frontList, p);
// czy zatem leży za nią?
else if (IsPolygonBehindPlane(p, n->plane))
AddPolygonToList(&backList, p);
// w takim razie czy przecina płaszczyznę?
else if (!IsPolygonCoplanarWithPlane(p, n->plane)) {
PolygonListNode *front, *back;
SplitPolygon(p, &front, &back);
AddPolygonToList(&frontList, front);
AddPolygonToList(&backList, back);
// a więc jest koplanarny, dodaj do bieżącego węzła
} else
// mój poduszkowiec jest pełen węgorzy!
AddPolygonToList(&n->polygons, p);
}
4
// rekursywnie buduj dalsze gałęzie
n->front = BuildTree(frontList);
n->back = BuildTree(backList);
return n;
}
W powyższym kodzie chciałbym zwrócić uwagę na jedną rzecz. Mianowicie, generacja
drzewa jako tako niczym się nie wyróżnia w stosunku do dowolnej innej drzewiastej struktury. Nie
widać też na pierwszy rzut oka miejsca, w którym algorytm mógłby robić wcześniej wspomniane
powroty.
Problem wyboru płaszczyzny podziału
Diabeł tkwi w szczegółach, a konkretnie w funkcji PickSplitterPolygon(). To tak naprawdę na
niej spoczywa cała efektywność i wydajność algorytmu – od wyboru wielokąta tworzącego
płaszczyznę podziału zależy jakość (zbalansowanie) rozwiązania, a więc naszego drzewa BSP.
Jednym ze stosowanych podejść jest opisanie kryteriów wyboru kilkoma funkcjami:
• objętość węzłów-dzieci – oba wygenerowane węzły powinny obejmować obszar
o podobnej objętości; ta funkcja faworyzuje płaszczyzny dzielące obecny węzeł na
dwa o równych rozmiarach:
f 1P=∣V 1−V 2∣
• liczba wielokątów – powierzchnie do narysowania powinny być równomiernie
rozmieszczone w drzewie:
f 2P=∣W 1−W 2∣ gdzie W1, W2 to ilości wielokątów w danych węzłach,
• liczba przecinanych wielokątów – ze względu na fakt, że każdy wielokąt
przecinający się z płaszczyzną podziału musi zostać podzielony, staramy się
minimalizować ilość takich podziałów, aby zapobiec niekontrolowanemu zwiększaniu
się złożoności sceny:
f 3P=np gdzie np to liczba przecinających się z płaszczyzną wielokątów.
Nie są to oczywiście wszystkie kryteria, jakie można stosować, a jedynie te najpopularniejsze
i najbardziej oczywiste.
Aby znaleźć najlepszą płaszczyznę podziału, wszystkie powyższe funkcje musimy
zminimalizować. Nie jest to tak proste zadanie, jak może się zdawać, gdyż f2 i f3 są w istocie
dyskretne, co oznacza, że mogą mieć wiele minimów lokalnych w zależności od geometrii sceny,
którą analizujemy. Dodatkowo przypiszemy każdemu z kryteriów pewną wagę, co pozwoli na
większą kontrolę nad całym procesem. W rezultacie otrzymujemy następujące równanie:
f P=w1⋅f 1 Pw2⋅f 2 Pw3⋅f 3P
Którą to funkcję oczywiście powinniśmy minimalizować. Idealne wartości wag
poszczególnych kryteriów zależą od konkretnego zastosowania – przykładowo, jeśli generujemy
drzewo dla scen, które już na wejściu składają się z dużej liczby wielokątów, powinniśmy dużą
5
wagę przypisać funkcji f3 – zapewni nam to minimalną ilość dodatkowych wielokątów
wygenerowanych w wyniku przecięć z naszymi hiperpłaszczyznami.
Rysowanie sceny z użyciem drzewa BSP
Kiedy mamy już wygenerowane drzewo, możemy się zabrać za renderowanie sceny
algorytmem malarza z jego użyciem – czynność, która w porównaniu z tworzeniem drzewa jest
prosta, łatwa i przyjemna:
void Render(Point cameraPosition, BSPNode *n) {
// warunek przerwania rekursji
if (n == NULL)
return;
// kamera jest przed płaszczyzną
if (DistanceFromPlane(cameraPosition, n->plane) > 0) {
// najpierw wyrenderuj gałąź za płaszczyzną
Render(cameraPosition, n->back);
// następnie obecny węzeł
DrawPolygons(n->polygons);
// na koniec gałąź przed płaszczyzną
Render(cameraPosition, n->front);
// kamera jest za płaszczyzną
} else {
// najpierw wyrenderuj gałąź przed płaszczyzną
Render(cameraPosition, n->front);
// następnie obecny węzeł
DrawPolygons(n->polygons);
// na koniec gałąź za płaszczyzną
Render(cameraPosition, n->back);
}
}
Oczywiście aby rozpocząć cały proces, należy wywołać funkcję Render() z korzeniem drzewa
jako argumentem.
Na pierwszy rzut oka kod wygląda nieco bezsensownie – funkcja rekursywnie wywołuje się
w jedną lub w drugą stronę. Wystarczy jednak krótka analiza aby się przekonać, że w ten sposób
wywołania DrawPolygons() będą następować dokładnie w takiej samej kolejności, w jakiej
ułożyłoby je dużo kosztowniejsze obliczeniowo sortowanie według głębokości:
1. jeśli kamera jest przed płaszczyzną (to znaczy, że odleglejsze od niej elementy są za
nią):
1. renderuj gałąź za płaszczyzną,
2. renderuj obecny węzeł,
3. renderuj gałąź przed płaszczyzną,
2. jeśli natomiast kamera jest za płaszczyzną (elementy odleglejsze są przed nią):
1. renderuj gałąź przed płaszczyzną,
6
2. renderuj obecny węzeł,
3. renderuj gałąź za płaszczyzną.
ABT (Adaptive Binary Tree) – BSP dla dynamicznych scen?
Z biegiem czasu drzewa BSP zaczęły odchodzić w zapomnienie. Sprawdzały się świetnie
w optymalizacji wyświetlania i wykrywania kolizji w statycznych scenach z zamkniętymi
przestrzeniami, ale zupełnie nie nadawały się do obsługi coraz większych i coraz bardziej
zmiennych światów, w jakich rozgrywają się gry. Drzewa BSP są nieelastyczne, praktycznie każda
zmiana w geometrii stwarza konieczność wygenerowania go od nowa, na co po prostu brakuje
komputerom mocy obliczeniowej, gdyż trzeba by było robić to w czasie rzeczywistym. Na dodatek
przy scenach z wielkimi, otwartymi przestrzeniami, zbudowanymi z użyciem wielkich ilości
wielokątów i połaci terenu, jakie spotyka się dziś w każdym nowym tytule, drzewa BSP
rozrastałyby się do kolosalnych rozmiarów, a czas ich generacji ciągnąłby się w nieskończoność.
Istnieje wiele alternatywnych sposobów radzenia sobie z tym problemem, ale w tym
podrozdziale opiszę tylko drzewa ABT (ang. Adaptive Binary Tree – dostosowujące się drzewo
binarne), z uwagi na ich bliskie pokrewieństwo z drzewami BSP. Zostały one zaproponowane w
2002 r. przez Yanna Lombarda [Lombard02]. Wspomniana już w ich nazwie zdolność do adaptacji
przejawia się w tym, że:
• węzły drzewa mogą dynamicznie zmieniać swoje rozmiary,
• oraz mogą na siebie nachodzić, w celu redukcji ilości przecięć z płaszczyznami
podziału.
Jak widać, są to dość istotne odstępstwa od idei BSP.
Różnice wobec drzew BSP
Kolejną fundamentalną zmianą w koncepcji jest fakt, że zasadniczą cechą opisującą węzeł nie
jest już jego płaszczyzna podziału, a AABB2
opisane na zawartej w nim geometrii.
Za tym idą zmiany w funkcji wybierającej płaszczyznę podziału – po pierwsze, płaszczyzna
musi być także równoległa do którejś z płaszczyzn wyznaczanych przez dwie z osi układu
współrzędnych. Ten warunek pozwala nam dodać nowe kryterium oceny jakości płaszczyzny
podziału:
f 4P=max sx , sy ,sz gdzie sx, sy, sz to wymiar AABB wzdłuż danej osi.
Funkcję tę dodajemy do wcześniej podanego równania z odpowiednią wagą i również
próbujemy minimalizować. Pragnę zaznaczyć, że jest to prawdopodobnie najważniejsze kryterium
w przypadku ABT.
Zmiana ta powoduje także, że nie możemy już szukać płaszczyzny za pomocą wielokątów
znajdujących się w węźle – z uwagi na warunek równoległości z osiami układu współrzędnych
2 Ang. Axis-Aligned Bounding Box – wyrównany do osi prostopadłościan opisujący, czyli minimalny prostopadłościan
o krawędziach równoległych do osi układu współrzędnych opisany na najbardziej zewnętrznych punktach zbioru.
7
geometria poziomu nie jest już wiarygodnym „dawcą” płaszczyzn. Musimy zatem wyznaczyć ją
inną metodą. Oto niektóre z proponowanych w różnych publikacjach (np. [Campbell03],
[Lombard03], [Teran-Ravniker04]) metod:
• próbkowanie liniowe – podział najdłuższej osi dzielonej przestrzeni na równe odcinki
i ocenianie jakości każdego z podziałów,
• bisekcja – zaczynamy od podziału w połowie, wyznaczamy jego jakość; następnie
każdą z połówek dzielimy jeszcze raz na pół, porównujemy ich jakości podziału
z jakością nadrzędnego i kontynuujemy proces aż do uzyskania zadowalającego
wyniku,
• próbkowanie stochastyczne – wybór losowych płaszczyzn, wyznaczenie ich jakości
i wybór najlepszej,
• próbkowanie niejednorodne – metoda podobna do próbkowania liniowego, w której
krok podziału nie jest stały, lecz taki, by zapewnić gęstsze próbkowanie w środku
przedziału niż na jego krańcach,
• statystycznie ważone próbkowanie wielokrotne – zadziwiająco skuteczna metoda
polegająca na wyznaczeniu mediany i odchylenia standardowego wszystkich
wierzchołków dzielonej przestrzeni, a następnie próbkowanie pewnej ilości
płaszczyzn w obrębie odchylenia standardowego.
Poza tym obsługa ABT jest bardzo podobna do drzew BSP.
Drzewa czwórkowe3
Ten wariant drzewa różni się od drzewa binarnego tym, że każdy węzeł zamiast dwóch ma
cztery węzły-dzieci. Ta cecha sprawia, że struktura ta nadaje się idealnie do podziału powierzchni
płaskich (lub w przybliżeniu płaskich). W grach komputerowych mogą to być np. duże połacie
terenu, i właśnie nad takim zastosowaniem skupię się w tej sekcji.
Renderowanie terenu z użyciem map wysokości
Najpopularniejszą obecnie techniką obsługi (tj. nie tylko renderowania, wykorzystywana jest
ona także w wykrywaniu kolizji) dużych połaci terenu jest użycie tzw. map wysokości. Jest to na
pierwszy rzut oka dwuwymiarowy, najczęściej kwadratowy obrazek, np. taki:
3 Ang. quadtree.
8
W istocie jest to jednak pewna forma reprezentacji płaszczyzny funkcji dwóch zmiennych z =
f(x, y) – każdemu punktowi o współrzędnych (x, y) przypisuje ona wysokość, na jakiej ten punkt
powinien się znaleźć. Taką połać terenu można wyrenderować algorytmem typu brute-force:
int x, y;
for (y = 0; y < height – 1; ++y) {
for (x = 0; x < width – 1; ++x) {
// narysuj prostokąt
DrawQuad(
// wierzchołek (x, y)
heightmap[y * width + x],
// wierzchołek (x + 1, y)
heightmap[y * width + x + 1],
// wierzchołek (x + 1, y + 1)
heightmap[(y + 1) * width + x + 1],
// wierzchołek (x, y + 1)
heightmap[(y + 1) * width + x]
);
}
}
Jak się łatwo domyślić, taki algorytm nie będzie zbyt efektywny dla połaci terenu większych
rozmiarów – jego złożoność rośnie liniowo wraz z polem powierzchni mapy wysokości (lub z
kwadratem jej boku, jeśli jest ona oczywiście kwadratowa).
Optymalizacja widocznych łat
Aby nieco skrócić czas renderowania naszego terenu, całą połać można podzielić na mniejsze
kwadraty, tzw. łaty, o pewnych wymiarach, np. odpowiadających 16x16=256 pikselom mapy
wysokości. Przed wysłaniem zestawu prostokątów do renderowania iterujemy po wszystkich łatach
i sprawdzamy ich zawieranie się w ostrosłupie widoczności4
:
4 Proces znany także jako frustum culling – okr...