Wstęp

Artykuł opowiada o atlasach tekstur. Na początku przedstawimy wszystko w sposób bardzo
ogólny, a później zagłębimy się w zagadnienie bardziej szczegółowo. Całość kończy
implementacja dynamicznego atlasu tekstur i użycie go do wyświetlania grafiki
dwuwymiarowej.

Z przedstawionym materiałem powinien poradzić sobie każdy średniozaawansowany
programista. Załączony kod jest napisany w języku C++ z użyciem biblioteki Direct3D. Mam
nadzieję, że każdy znajdzie tu dla siebie małe co nieco.

Wprowadzenie do tematu

Na początku wypadałoby powiedzieć czym właściwie są atlasy tekstur. Weźmy kilka tekstur,
złóżmy je w jedną większą i... mamy atlas. Tak, pod tym tajemniczym pojęciem nie kryje się
nic więcej niż łączenie tekstur.

Rys 1. Przykładowy atlas tekstur w grze casual

Powiesz pewnie, że to oczywiste, możliwe, że nawet stosujesz już podobne rozwiązania. W
przypadku teksturowania modeli używa się przecież często jednej tekstury dla całego modelu.
Właściwie dlaczego? Przecież łatwiej by było teksturować każdą część osobno i nie
przejmować się odpowiednim ułożeniem wszystkiego na teksturze. Odpowiedź jest prosta:
wydajność.

O wydajności słów kilka

Im mniejsza będzie ilość odwołań do karty graficznej, tym większa będzie wydajność
renderowania. To właśnie dlatego modele grupuje się (ang. batching) po materiałach,
teksturach, stanach renderingu itp. Jeżeli będziemy rysowali po kolei dwa modele z taką samą
nałożoną teksturą, to nie będziemy musieli jej zmieniać, a zatem odpada część komunikacji z
kartą graficzną.

Komunikacja z kartą graficzną jest kosztowna - pamiętajmy, że po drodze są dwie dodatkowe
warstwy: API graficzne i sterownik. Jak możemy przeczytać w "Accurately Profiling
Direct3D API Calls" [1], operacja zmiany tekstury może zająć 2500-3100 cykli procesora.
Gdybyśmy chcieli poświęcić cały czas procesora taktowanego 2 GHz to moglibyśmy

wykonać ~800 000 takich w ciągu sekundy, czyli około 13 000 zmian na klatkę przy 60 FPS.
A co z innymi ustawieniami renderingu? Bardzo łatwo sprawić, że gra będzie ograniczona
przez procesor główny, a nie przez kartę graficzną.

Często tekstury są tym elementem, który ogranicza możliwości grupowania. Dzięki użyciu
atlasów możemy to zmienić - ponieważ nie będziemy musieli zmieniać tekstur aż tak często
jak wcześniej, powinno udać się przyspieszyć rendering.

Zaczynamy zabawę

Atlasy tekstur można podzielić na dwa rodzaje: statyczne i dynamiczne. Pierwsze tworzone są
w zewnętrznych aplikacjach i już gotowe trafiają do użytku w grze. Drugie są tworzone na
bieżąco podczas wczytywania i zwalniania zasobów. Na razie zajmiemy się tymi pierwszymi,
na drugie przyjdzie czas w dalszej części artykułu.

Użycie statycznych atlasów jest proste i może się okazać, że nawet nie musisz nic zmieniać w
swoim kodzie:

1. Wybierz tekstury, które chcesz pogrupować.
2. Stwórz z nich atlas (lub atlasy) za pomocą odpowiedniego programu.
3. Zmień odwołania do tekstur i koordynaty w swoich modelach, aby wskazywały na

odpowiednie części atlasu.

Realizacja tego jest prosta, a przyrost wydajności powinien być widoczny od razu.
Przykładowo, można w atlasie umieścić tekstury wszystkich jednostek w grze rts, tekstury
wszystkich pocisków w grze FPS, wszystkie tekstury cząsteczek, itp. Punkt drugi można
zrealizować np. za pomocą "Atlas Creation Tool" [2] od firmy nVidia. Do programu
dołączona jest dokumentacja, która opisuje sposób użycia. Oprócz tekstury zawierającej dane
atlasu otrzymujemy plik z informacją o położeniu poszczególnych tekstur.

Jeżeli chcemy trochę więcej elastyczności, to punkt trzeci możemy wykonać już podczas
wczytania modeli. Może się okazać, że używanie takich atlasów jest kłopotliwe podczas
testowania - podmiana tekstury w zasobach gry wymaga przebudowania całego atlasu. Na
potrzeby testowania możemy zmienić sposób ładowania tekstur - najpierw sprawdzamy czy
istnieje tekstura o wskazanej nazwie na dysku (i używamy niezmienionych koordynatów), a
dopiero później sprawdzamy czy jest załadowana do któregoś z atlasów (i odpowiednio
zmieniamy koordynaty). Takie rozwiązanie uprości testowanie, a na koniec wystarczy
przebudować atlas i skasować niepotrzebne pliki.

Wady

Gdyby rozwiązanie to było idealne, mógłbym w tym momencie skończyć pisać. Niestety nie
jest tak kolorowo, atlasy poprawiają możliwości grupowania, ale mają kilka wad:



problem z mip-mappingiem;



color bleeding i filtrowanie;



koordynaty tekstur spoza zakresu [0,1].

Na szczęście można je zminimalizować i do tego będziemy właśnie dążyli. W dokumencie
"Improve Batching Using Texture Atlases" [3] pokazano jak sobie z tym radzić, jednak nie
wszystkie zaprezentowane tam techniki działają idealnie - przyjrzymy się im dokładnie i w
razie potrzeby zaprezentuję alternatywne rozwiązania.

Mip-mapping

Mip-mapping jest kluczowy ze względu na wydajność i jakość generowanego obrazu.
Technika ta polega na tym, że tworzymy zmniejszone wersje tekstur (najczęściej uśredniając
teksele) i to ich używamy podczas teksturowania.

Rys 2. Tekstura i jej mip-mapy

To, która mip-mapa zostanie użyta, zależy od tego jak bardzo zmieniają się koordynaty
tekstury wielokąta w stosunku do współrzędnych ekranu. Dzięki temu obszary dalsze i mniej
widoczne (gdzie taka zmiana koordynatów jest większa) używają mniejszych mip-map.
Technika ta jest realizowana sprzętowo i decyzja o tym, która mip-mapa ma zostać użyta, jest
dokonywana dla każdego piksela. Jeżeli nie będziemy używać mip-map, zauważymy
widoczny aliasing tekstury.

Rys 3. Przykład użycia mip-map: po lewej bez, po prawej z włączonym mip-mappingiem.
Obraz pochodzi z [4]

Od razu widać jaki będzie problem z użyciem mip-map w połączeniu z atlasem - podczas
generowania mip-map. Na pewnym poziomie, różne tekstury atlasu zostaną złączone podczas
uśredniania tekseli. Problem ten rozwiążemy dość prosto:

1. Będziemy używać tylko kwadratowych tekstur, których boki są potęgą 2.
2. Będziemy układać je w atlasie w taki sposób, żeby tworzenie mip-mapy nie

powodowało zakłóceń.

Punkt pierwszy i tak jest zwykle spełniony, a w razie potrzeby możemy uzupełnić teksturę do
odpowiednich rozmiarów. Z drugim punktem też nie ma większych problemów - wystarczy,
że teksturę rozmiaru 2

n

będziemy wstawiać na pozycjach będących wielokrotnością 2

n

.

Dlaczego? £atwo zauważyć, że pozycja podczas generowania kolejnego poziomu mip-mapy
zmieni się na 2

n-1

, tak samo jak rozmiar tekstury w mip-mapie. Tak więc dane tekstury nie

powinny zostać zakłócone podczas generowania kolejnego poziomu mip-mapy. Postępując w
ten sposób możemy też wygenerować pozostałe poziomy mip-mapy.

Problem pojawia się gdy tekstura w mip-mapie ma już rozmiar 1 piksela, a będziemy
generować kolejną mip-mapę - zostaną wtedy uśrednione teksele z kilku tekstur. Z tym
możemy sobie poradzić na kilka sposobów:

1. Ograniczyć się do trzymania w atlasie tylko tekstur rozmiaru 2

n

i generować tylko n

mip-map.

2. Jeżeli 2

n

jest rozmiarem najmniejszej tekstury w atlasie, to generować tylko n mip-

map;

3. Zignorować problem - przecież go tam wcale nie ma.

Rozwiązania z dwóch pierwszych punktów znacznie ograniczają funkcjonalność. Okazuje się,
że problem możemy zignorować z bardzo prostego powodu - jeżeli mielibyśmy użyć takich
zniekształconych danych mip-mapy, to trójkąt który chcielibyśmy narysować byłby mniejszy

niż pół piksela. Taki trójkąt nie powinien wygenerować żadnych pikseli na ekranie, a zatem
zniekształcone dane nie zostaną użyte.

Oczywiście takie zniekształcone teksele w mip-mapach są niepotrzebne. Dlatego możemy ich
po prostu nie inicjalizować. Tak robi właśnie "Atlas Creation Tool". Przy okazji ogranicza
ilość mip-map do takiej, która jest naprawdę potrzebna - jeżeli chcielibyśmy wygenerować
wszystkie poziomy mip-map dla tekstury atlasu, to ostatnie z nich będą zawierały tylko
niezainicjalizowane, zbędne dane.

Color bleeding i filtrowanie

Co się stanie, jeżeli będziemy próbkować teksturę z atlasu przy jej krawędziach? Jeżeli
będziemy mieli włączone filtrowanie, to dostaniemy zniekształcony kolor przez teksel z
sąsiedniej tekstury w atlasie. Niestety jest to poważny problem i jego rozwiązanie nie jest aż
tak trywialne jak w przypadku mip-map.

Rys 4. Color bleeding na obrazie po prawej. Wygenerowano za pomocą "Atlas Comparison
Viewer" [2]

Gdybyśmy nie używali mip-map, można by było przesunąć koordynaty tekstury o pół teksela
'do środka'. Próbkowanie teksela w jego środku sprawia, że nawet przy włączonym
filtrowaniu tylko on będzie brał udział w obliczeniach.

Rys 5. Zmiana koordynatów

Niestety na kolejnym poziomie mip-mapy to pół teksela to będzie już ćwierć teksela, więc
problem się powtórzy. Takie rozwiązanie jest jednak wystarczające w przypadku gier 2D, o
czym zostanie jeszcze wspomniane później.

Problem możemy częściowo rozwiązać dodając obramowanie do tekstury, powielając jej
krawędzie (lub wstawiając piksele przezroczyste, w zależności od przeznaczenia tekstury) i
zmniejszyć obszar próbkowania tylko do obszaru bez dodanych krawędzi - dzięki temu
podczas próbkowania powinny być pobierane prawidłowe dane. Aby zachować własność, że
tekstura ma boki będące potęgą 2, musimy ją przeskalować w dół przed dodaniem krawędzi i
dopiero zmodyfikowaną teksturę umieścimy w atlasie. Może to niestety pogorszyć jakość, a
na dalszych poziomach mip-map problem wciąż będzie występował.

Jak to zwykle bywa, możemy próbować rozwiązywać ten problem na kilka sposobów:

1. Wyłączyć filtrowanie - jeżeli tekstura ma wystarczająco dużą rozdzielczość, to efekt i

tak powinien być dobry, a mip-mapy zagwarantują dobrą jakość pomniejszonych
tekstur.

2. Nie używać mip-map - to upraszcza trochę sprawę. Dobre rozwiązanie do gier 2D, w

których mip-mapy przeważnie nie są potrzebne.

3. Powiększyć teksturę w specjalny sposób.

Rozwiązań 1 i 2 nie trzeba tłumaczyć. Rozwiązanie 3 to moja propozycja, która może
rozwiązać część problemów z atlasami tekstur kosztem pamięci.

Color bleeding powstaje dlatego, że próbkujemy nie tę teksturę, którą byśmy chcieli. Dlatego
stworzymy nową, większą teksturę w taki sposób:

1. tworzymy nową teksturę o dwukrotnie większej długości boków;
2. wstawiamy teksturę na sam środek;
3. resztę uzupełniamy powielając teksturę.

Rys 6. "Powiększenie" tekstury

Rozwiązanie to używa niestety aż czterokrotnie więcej pamięci, ale ma wiele zalet. Jedną z
nich jest to, że podczas próbkowania będziemy pobierali dane tylko z właściwego obrazu,
jeżeli podamy koordynaty obrazu ze środka tekstury. Ostatnią mip-mapą jaka powinna zostać
wtedy użyta jest 2x2 piksele, a taki wybór koordynatów sprawi, że będziemy próbkować tylko
obszar pomiędzy środkami tekseli, dzięki czemu unikniemy color bleedingu.

Koordynaty tekstur spoza zakresu [0,1]

Graficy są przyzwyczajeni do tego, że mogą używać koordyntów tekstur spoza zakresu [0,1],
dzięki czemu mogą powielać teksturę. Jak można się łatwo domyślić, użycie tego w
połączeniu z atlasem nie jest prostą sprawą. Użycie koordynatów tekstury spoza obszaru w
którym umieszczona jest tekstura w atlasie sprawi, że wyświetlimy inną teksturę, zamiast
powielić tę, którą chcieliśmy.

Rys 7. Miejsce [1.5, 0.5] dla zaznaczonej tekstury

Możemy to rozwiązać w taki sposób:



powielić teksturę kilkukrotnie, żeby graficy dysponowali większym zakresem;



emulować to zachowanie w PS.

Rozwiązanie pierwsze może wymagać bardzo dużej ilości pamięci, a dodatkowo użycie
prostokątnych tekstur znacznie skomplikowałoby algorytm pakowania tekstur do atlasu.
Rozwiązanie z PS wydaje się ciekawsze - możemy przekształcić koordynaty do zakresu [0,1],
a następnie przetransformować do odpowiedniego miejsca w atlasie (1).

Okazuje się, że i tym razem nie obejdzie się bez problemów - jak już wspomniałem przy
okazji mip-map, to, która mip-mapa zostanie użyta, zależy od tego jak bardzo zmieniają się
koordynaty tekstury wielokąta względem współrzędnych ekranu. Jeżeli nastąpi gwałtowna
zmiana koordynatów tekstury, to zostanie użyta dużo mniejsza mip-mapa i powstaną
artefakty. Przy adresowaniu wrap, taki problem będzie występował w miejscach, gdzie łączą
się powielane fragmenty tekstury. Na szczęście (od PS 2.0a) możemy użyć instrukcji ddx i
ddy, dzięki którym ręcznie obliczymy zmianę koordynatów tekstury względem
współrzędnych ekranowych i przekażemy ją do samplera, aby wymusić odpowiednią mip-
mapę.

Koordynaty, które chcemy przekazać do ddx i ddy to koordynaty z oryginalnej tekstury
przetransformowane do przestrzeni atlasu (2). Dzięki temu dostaniemy dostęp do
odpowiednich mip-map. Poniżej znajduje się zrzut ekranu z programu Render Monkey, który
ilustruje problem. Pokazuje zmiany wyliczone przez ddx i ddy dla (1) i (2) (powiększona
suma wartości absolutnych ich wyników). Na każdą ścianę sześcianu nakładana miała być
czterokrotnie powtórzona tekstura:

Rys 8. Wizualizacja ddx i ddy dla (1) (po lewej) i (2) (po prawej). Czym jaśniej tym mniejsza
mip-mapa zostałaby użyta.

Jak widać w (1), na łączeniach tekstur zostałyby użyte nieodpowiednie mip-mapy, gdybyśmy
nie użyli (lub użyli źle) ddx i ddy. Okazuje się jednak, że to nie jest jeszcze koniec naszych
problemów. Trzeba się zastanowić w jaki sposób rozwiążemy problem próbkowania tekstur
na krawędziach obszaru w atlasie. Jeszcze raz musimy przyjrzeć się problemowi, który już
przed chwilą rozpatrywaliśmy dla mip-map. Okazuje się, że przesuwanie koordynatów tekstur
w tym wypadku nie sprawdzi się dobrze, nawet jeżeli wcześniej mogło okazać się
wystarczające. Nie dość, że tekstury mogą przestać do siebie idealnie pasować, to w
miejscach łączenia pojawi się widoczny aliasing:

Rys 9. Błędy przy łączeniu tekstur. Wygenerowano za pomocą "Atlas Comparison Viewer"
[2]

Jak się okazuje, użycie powiększonej tekstury, jaką zaproponowałem dla mip-map,
rozwiązuje ten problem - zawsze powinniśmy próbkować z dobrego obszaru i otrzymać dobry
wynik. Prawie zawsze. Istnieje kilka możliwości w jaki sposób zachowują się koordynaty
spoza zakresu [0,1] - musimy emulować to za pomocą PS, a dodatkowo musimy pamiętać o
uzupełnieniu tekstury podczas powiększania zgodnie z tym sposobem. Jest to jakieś
ograniczenie, ale znacznie mniejsze niż w innych rozwiązaniach. Nie tracimy przy tym na
jakości generowanego obrazu.

Atlasy w grach 2D

Uźycie atlasów w grach 2D jest szczególnie atrakcyjne. Wiele elementów występujących w
grze możemy zapakować do jednego atlasu, a następnie używać ich do rysowania.
Ograniczenie się do dwóch wymiarów oznacza też często, że mip-mapy nie będą nam
potrzebne. Dodatkowo, dużo łatwiej obejść się bez koordynatów tekstur spoza zakresu [0,1].
Uprości nam to trochę atlas.

Często stosowane podejście do rysowania grafiki 2D na GPU wygląda tak:



Ustaw rzutowanie ortogonalne.



Dla każdego sprajta:

o

Ustaw teksturę.

o

Ustaw transformację.

o

Narysuj sprajta.

Rozwiązanie to nie jest jednak efektywne i przy kilku tysiącach sprajtów wydajność
renderingu może spaść na tyle, że renderowany obraz nie będzie już płynny. Najciekawsze
jest to, że doświadczymy tego nawet na komputerach z wielordzeniowymi procesorami i
potężnymi kartami graficznymi.

Oczywiste jest, że wypadałoby jakoś pogrupować rendering, ale użycie samego atlasu może
okazać się niewystarczające. Pójdziemy jeszcze o krok dalej - przerzucimy całą transformację

na CPU, a do karty będziemy przesyłać już przetransformowane wierzchołki. Teraz będziemy
chcieli, żeby rendering wyglądał tak:



Ustaw rzutowanie ortogonalne.



Dla każdego sprajta:

o

Jeżeli zmieniasz ustawienie renderingu (tekstura, blending, itp.) lub bufor
rysowania jest pełny to narysuj jego zawartość.

o

Utwórz przetransformowane wierzchołki czworokąta z odpowiednimi
koordynatami tekstury i dodaj je do bufora.



Narysuj zawartość bufora.

Oczywiście, jeżeli bufor jest pusty, to nic nie rysujemy. Takie rozwiązanie pozwala na
zwiększenie ilości rysowanych sprajtów do kilkudziesięciu tysięcy. Jak łatwo zauważyć, w
ten schemat wpasowuje się też użycie tekstur, które nie są zapakowane do atlasu - wtedy przy
każdej zmianie tekstury bufor będzie opróżniany.

Zabieramy się za implementację

Teraz zajmiemy się implementacją prostego atlasu i użyciem go do wyświetlania grafiki 2D.
Atlas będzie skonstruowany tak, aby łatwo można go było użyć we własnym projekcie, a w
przyszłości rozbudowywać. Nie będziemy zajmować się użyciem shaderów. Osoby
zainteresowane będą mogły dodać to we własnym zakresie - będzie to dobra wprawka dla
czytelnika do rozbudowania załączonego kodu.

Atlas podobny do tego, który tu zaprezentuję, użyłem w swoim poprzednim projekcie i na
pewno będę używał w kolejnych. Korzyści są widoczne gołym okiem, a użycie bardzo proste.
Część rzeczy na pewno da się zrobić inaczej/lepiej, ale mam nadzieje, że i tak będzie się
można z tego przykładu czegoś nauczyć.

W kodzie używam prawie wszędzie shared_ptr (i weak_ptr do pary) z biblioteki boost, żeby
nie martwić się zwalnianiem pamięci. Kod był pisany w Visual C++ 2005 EE z użyciem
DirectX 9.0c SDK (November 2007).

Drzewo czwórkowe

Drzewo czwórkowe to drzewo, w którym każdy węzeł wewnętrzny ma maksymalnie do 4
synów. Drzewo to jest często stosowane do różnych podziałów przestrzeni dwuwymiarowej.
Każdemu węzłowi odpowiada pewien kawałek przestrzeni (korzeń obejmuje całą przestrzeń),
a synowie powstają poprzez podział rodzica na 4 równe części. Jest to analogiczna struktura
dwuwymiarowa do drzew ósemkowych w 3D.

Rys 10. Przykład drzewa czwórkowego

Dlaczego właśnie drzewo czwórkowe? Po pierwsze, jest to dość prosta konstrukcja. Po
drugie, przy użyciu takiego drzewa naturalne jest wstawianie tekstur w liściach drzewa.
Konstrukcja drzewa zapewnia też, że tekstury będą umieszczone w taki sposób, że podczas
generowania mip-map nie zostaną złączone żadne dwie tekstury w atlasie (poza
najmniejszymi, nieistotnymi, poziomami mip-map).

Wstawianie do atlasu

Dla uproszczenia węzeł rozmiaru 2

n

będziemy nazywać węzłem rozmiaru n. Tworząc atlas o

boku 2

n

, mamy na początku jeden węzeł rozmiaru n. Będziemy zmieniać podział tego drzewa

podczas dodawania/usuwania węzłów.

Po wstawieniu tekstury do atlasu chcemy otrzymać coś takiego:

Rys 11. Struktura atlasu po wstawieniu pierwszej tekstury

Jak widać, powstała duża ilość pustych węzłów. Zapamiętamy je na liście wolnych węzłów
rozmiaru n (dla każdego rozmiaru osobna lista). Przyjrzyjmy się teraz algorytmowi
wstawiania. Wstawiając teksturę o bokach 2

n

prosimy drzewo o udostępnienie węzła rozmiaru

n. Jeżeli na liście wolnych węzłów tego rozmiaru jest jakiś węzeł to go wybieramy. W
przeciwnym przypadku musimy podzielić większe węzły drzewa tak, aby otrzymać węzeł o
odpowiednim rozmiarze. Funkcja pobierania węzła mogłaby wyglądać mniej więcej tak:

QTNodeRef QTTree::GetNode(int k)
{

// próbujemy pobrać węzeł większy niż rozmiar atlasu, znaczy to, że

// nie ma już odpowiedniej ilości miejsca w atlasie

if (k > Size()) return QTNodeRef();

// nie ma odpowiedniego węzła na liście wolnych węzłów, dzielimy

if (freeList[k].length() == 0)

{

QTNodeRef n = GetNode(k+1);

if (n)

{

// dzielimy węzeł na 4 i dodajemy synów do listy

wolnych węzłów

SplitNode(n);

}

else return QTNodeRef();

}

// wyciągamy węzeł z listy wolnych węzłów

QTNodeRef node = freeNodesList[k].back();

freeNodesList[k].pop_back();

return node;

}

Usuwanie z atlasu

Usuwanie tekstur z atlasu jest dość proste. Musimy tylko dla każdego węzła zliczać ile jego
dzieci jest w użyciu i jeżeli żaden (czyli 0 na 4) nie jest zajęty to powinniśmy je usunąć.
Dzięki temu po usunięciu wszystkich tekstur z atlasu znów dostaniemy jeden duży węzeł.

Podczas usuwania tekstury z atlasu będziemy też czyścić przestrzeń, którą zajmowała w
atlasie. Pozwoli nam to na oglądanie aktualnego stanu atlasu, a w przypadku wstawienia
tekstur, których wymiar nie będzie wynosił dokładnie 2

n

, nie powstaną błędy.

Określenie porządku na węzłach

Jeżeli węzły na listach wolnych węzłów będziemy przechowywali w dowolnej kolejności, to
prędzej czy później nastąpi duża fragmentacja atlasu. Nie chcemy do tego dopuścić i
chcielibyśmy, aby ilość utworzonych węzłów w drzewie była jak najmniejsza.

Będziemy numerować węzły w drzewie, w taki sposób, żeby wszystkie węzły rozmiaru n
miały inne numery. Dodatkowo węzły położone wyżej będą miały numery mniejsze od
położonych niżej.

Zdefiniujemy nasze numerowanie rekurencyjnie:



Korzeń ma numer 0



Jeżeli węzeł ma numer n, to jego dzieci mają kolejno numery 4*n, 4*n+1, 4*n+2,
4*n+3

Dzięki użyciu takiego numerowania, zawsze podczas wstawiania będą wybierane najmniejsze
węzły, w sensie tego porządku.

Jeżeli podzielimy nasze drzewo na 16 węzłów, to mają takie numerowanie:

Rys 12. Porządek na węzłach drzewa

Defragmentacja atlasu

Wspomniałem już wcześniej o problemie fragmentacji atlasu. Teraz czas przyjrzeć mu się
dokładniej, na przykładzie. Mamy 6 tekstur - 4 rozmiaru 32x32px, 1 rozmiaru 16x16px i 1
rozmiaru 64x64px. Wstawiamy do atlasu 64 tekstury, za każdym razem wybierając losową z
nich. Dostaniemy coś takiego:

Rys 13a. Atlas po wstawieniu tekstur

Jak widać wszystko ułożyło się całkiem ładnie i nie ma zbędnych wolnych przestrzeni. Teraz
okazuje się, że część tekstur już nie jest nam potrzebna i zostawimy tylko co czwartą:

Rys 13b. Atlas po usunięciu części tekstur

Teraz chcielibyśmy wstawić teksturę rozmiaru 256x256px i okazuje się, że nie możemy tego
zrobić - nie ma w atlasie wystarczająco dużo przestrzeni (tzn. jest, ale nie w jednym
kawałku). Niestety musimy przeorganizować atlas tak, żeby pozbyć się wolnych miejsc
("nieciągłości").

Pomysł jest bardzo prosty oprócz list wolnych węzłów zapamiętajmy listy węzłów z
teksturami, ale w ich przypadku powinniśmy użyć odwrotnego porządku. Teraz wystarczy
nam prosta reguła - jeżeli na liście wolnych węzłów rozmiaru n i liście oteksturowanych
węzłów tego samego rozmiaru są jakieś węzły, to bierzemy pierwsze z nich. Jeżeli mają
różnych rodziców i wolny węzeł jest mniejszy (w sensie naszego porządku) od węzła
zajętego, to podmieniamy ich zawartość. Jeżeli rodzice węzłów są tacy sami, to niewiele się
zmienia, dlatego nie będziemy ich ruszać.

W załączonej implementacji można podać ile kroków defragmentacji należy wykonać - dzięki
temu nie trzeba robić wszystkiego na raz i można rozłożyć na wiele klatek.

Dla powyższej sytuacji, pełna defragmentacja zajęła 0.15 ms na komputerze z procesorem
Core 2 Duo 1.8 GHz i kartą GeForce 8600 GTS. Efekt defragmentacji jest taki:

Rys 13c. Atlas po defragmentacji

Jak widać, zastosowanie takiego porządku sprawiło, że część węzłów pozostała niezmieniona.
Pozbyliśmy się też fragmentacji, o co nam chodziło.

O wydajności znów trochę

Przydałoby się teraz spojrzeć na wydajność i sprawdzić jak to wszystko działa w praktyce.

Rys 14. Porównanie wydajności, fragmenty okien

Po lewej stronie bez atlasu, a po prawej z włączonym atlasem tekstur. Wszystkie sprajty mają
losową pozycję, skalę, kolor, przezroczystość, kąt i teksturę. Aby poprawnie wykonać
pomiary, dane te zostały policzone tuż po uruchomieniu aplikacji i sprawdzana jest wydajność
samego rysowania. FPS w lewym górnym rogu, wyświetlany przez FRAPS-a. Na górnych
obrazkach jest 1000 sprajtów, a na dolnych 32000. Okna miały rozdzielczość 800x600 i
zostały trochę przeskalowane.

Jak widać działa to całkiem dobrze i nie widać większych różnic w generowanym obrazie.

Problemy z załączoną implementacją

Załączona implementacja nie jest idealna - pokazuje jednak potencjał tej techniki. Wiele
rzeczy można by było zrobić lepiej. Mój kod może stanowić podstawę do rozbudowy lub
nawet zbudowania wydajnego frameworka 2D. Braki i wady o których warto wiedzieć:



Wszystkie tekstury są w D3DPOOL_MANAGED, szybciej powinno działać w
przypadku tekstur dynamicznych (ale dzięki temu nie trzeba martwić się utratą
urządzenia).



Wszystkie tekstury są w jednym formacie i nie można go podać podczas tworzenia
atlasu.



Brak obsługi mip-map.



Brak zapętlania koordynatów.



Każdy węzeł z teksturą pamięta referencję na teksturę, której zawartość pamięta (a
przez to ciągle jest w pamięci).

Możliwe modyfikacje



Można rozbudować TextureAtlasPart tak, żeby udostępniała koordynaty z
TextureAtlasFrame.



Kolejka tekstur do załadowania, ładowanie ich w osobnym wątku i wstawianie gdy
będzie taka możliwość.





Poprawienie wad (o ile stanowią problem) wymienionych wcześniej ;)



Kod źródłowy

Kod źródłowy i programy przykładowe można pobrać

tutaj

.

Inne rozwiązania

Oczywiście podane podejście nie jest jedynym możliwym. Do przechowywania atlasu można
użyć też tekstur 3D, ale to rozwiązanie ma dwie zasadnicze wady: łaczenie warstw podczas
mip-mappingu i ograniczenie się do jednego rozmiaru tekstur (można też w każdej warstwie
przechowywać taki atlas jak zaproponowałem).

Nowszy sprzęt wspiera jeszcze jedno rozwiązanie, które może okazać się ciekawe - tablice
tekstur. Jest to coś podobnego do tekstur 3D, z tą różnicą, że każda warstwa ma osobne mip
mapy - jeżeli ograniczenie się do tekstur tego samego rozmiaru nie stanowi dla nas problemu,
to znika problem z mip-mapami i koordynatami spoza zakresu [0,1].

Inne zastosowania

Innym typowym zastosowaniem zbierania wielu tekstur w jedną większą całość jest
pakowanie lightmap. Niestety wtedy ograniczenie się do tekstur o rozmiarach będących
potęgami 2 może się okazać zbyt duże. Stosuje się wtedy inne, heurystyczne algorytmy - sam
problem jest NP-trudny (2D bin packing problem).

Warto też wspomnieć o D3DXUVAtlasCreate, D3DXUVAtlasPack i
D3DXUVAtlasPartition. Są to funkcje z D3DX, dzięki którym możemy wygenerować i
używać atlasów dla siatek. Więcej informacji na ten temat można znaleźć w MSDN [5] i
dokumentacji dołączonej do DirectX SDK.

Rys 15. Zastosowanie UVAtlas z DirectX SDK. Obraz pochodzi z [5]

Odniesienia



[1] "Accurately Profiling Direct3D API Calls" -

http://msdn.microsoft.com/en-

us/library/bb172234(VS.85).aspx



[2] "Texture Atlas Tools" -

http://developer.nvidia.com/object/texture_atlas_tools.html



[3] "Improve Batching Using Texture Atlases" -

http://download.nvidia.com/developer/NVTextureSuite/Atlas_Tools/Texture_Atlas_W
hitepaper.pdf



[4] "Mipmapping" -

http://pl.wikipedia.org/wiki/Mipmapping



[5] "UVAtlas" -

http://msdn.microsoft.com/en-us/library/bb206321.aspx