Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

Atlasy tekstur jako prosty sposób przyspieszania renderingu

Tekst został importowany z Warsztatowych artykułów. Jego oryginalnym autorem jest Rafał Kozik. Jeżeli został importowany poprawnie, usuń ten szablon!

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.

atlas_1.jpg
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.

mip-map.png
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.

mip-map2.png
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 2n będziemy wstawiać na pozycjach będących wielokrotnością 2n. Dlaczego? £atwo zauważyć, że pozycja podczas generowania kolejnego poziomu mip-mapy zmieni się na 2n-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 2n i generować tylko n mip-map.
  2. Jeżeli 2n 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.

cb.jpg
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.

coords_move.png
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ę.
lena.jpg
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.

atlas_2.jpg
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:

ddx_ddy.png
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:

wrap_error.jpg
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:
    • Ustaw teksturę.
    • Ustaw transformację.
    • 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:
    • Jeżeli zmieniasz ustawienie renderingu (tekstura, blending, itp.) lub bufor rysowania jest pełny to narysuj jego zawartość.
    • 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.

qt.png
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 2n będziemy nazywać węzłem rozmiaru n. Tworząc atlas o boku 2n, 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:

qt2.png
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 2n 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 2n, 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:

order.png
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:

def_a.jpg
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ą:

def_b.jpg
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:

def_c.jpg
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.

speed.jpg
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.

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

Tekst dodał:
revo
10.11.2008 23:19

Ostatnia edycja:
revo
10.11.2008 23:19

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#1 edytuj 10.11.2008 23:19 revo 31.52 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • Syriusz (@Syriusz) 11 listopada 2008 19:28
    Super! Właśnie tego potrzebowałem w tej chwili ;). Następnym razem daj też .pdf...
  • ~xXx 12 listopada 2008 11:52
    Bardzo dobry art
  • ~cmons 12 listopada 2008 15:49
    No artykuł bardzo dobry :) choć myślałem, że dowiem się trochę przydatnych dla mnie nowinek, bo to już wszystko ( pod 2D ) zrobiłem w swoim silniku, ale dzięki tobie mogę trwać w upewnieniu, że mam "dobrze" ;) wielki PLUS :)
  • Tomasz Dąbrowski (@Dab) 13 listopada 2008 18:27
    Jeżeli chodzi o mipmapy to można jeszcze pomyśleć o PS z czymś w rodzaju tex2Dlod (samplowanie konkretnej mipmapy tekstury).
  • ~cmons 14 listopada 2008 20:59
    Mam małe pytanie. Z treści artykułu wynika, że jeśli przesune koordynatory o pół teksela do środka (0.5f) to wtedy zawsze będzie brał udział w renderowaniu cały teksel plus fakt, że nigdy nie będzie próbkować pikseli sąsiednich. A tak nie jest, przynajmniej w OpenGL, renderuje mi pół teksela na brzegach...
  • ~cmons 14 listopada 2008 21:04
    Oczywiście, po zeskalowaniu dopiero to widać, a normalnie to zaokrągla do 1 teksela i odejmuje wtedy po jednym tekselu na obramowaniu.
  • ~cmons 14 listopada 2008 21:06
    Dodam jeszcze, że chodzi mi o renderowanie w dwóch wymiarach.
  • Tomasz Dąbrowski (@Dab) 26 grudnia 2008 17:43
    Nie 0.5f, tylko 1.0f/Xf, gdzie X = szerokość tekstury w pikselach.
  • revo (@revo) 29 grudnia 2008 11:20
    Dab, 0.5f/Xf ;)
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)