Geomipmapping part II - usuwanie dziur w w geometrii terenu

Jak poradzić sobie z powstałymi w poprzednim artykule "dziurami geometrii" ?? Cóż sposobów jest kilka ja znam 2, które w mniejszym w lub mniejszym stopniu postaram się przedstawić.

Rozwiązanie za pomocą "Skirt"

Skirt (z ang. spódniczka), służy dodaniu dodatkowej "spódniczki" do każdego z sektorów. Jest to rozwiązanie o tyle dobre, bo nie przy stwarza dużych problemów przy implementacji i w miarę dobrze spełnia swoje zadanie.

Dobra to jak taka spódniczka wygląda ? Na rysunku zaznaczone to jest na czerwono :

źródło : http://regedit.gamedev.pl/Download/Galeria/Rozne%20screeny/Teren/Terrain3.png

Co musimy zrobić by dodać tę dodatkową warstwę sektorów ?

Dla skrajnych wierzchołków sektora (leżących na bokach sektora) można dodać dodatkową warstwę wierzchołków o współrzędnych takich samych jak wierzchołki podstawowe, lecz opuszczone o jakąś konkretną wartość (np o długość boku sektora, chodź w praktyce potrzeba dużo mniejszych wartości).

Gdy dodamy te dodatkowe wierzchołki wystarczy obliczyć jeszcze texCoord' y i odpowiednio połączyć w trójkąty. Tego pomysłu nie mam zaimplementowanego u siebie.

Rozwiązanie za pomocą dodatkowego indeksowania

W tym rozwiązaniu zakłada się, że poziom szczegółowości nie może różnić się więcej niż jeden. Tutaj zamiast jednego zestawu IB tworzy się 16 zestawów index bufferów (tak naprawdę można chyba 8 ale nie będę się zagłębiać dalej). Po co ? Przygotowuje się wszystkie podzbiory krawędzi tak by pasowały do poziomu szczegółowości sąsiada. Lecz by można było zastosować to rozwiązanie musimy lekko zmodyfikować indexowanie trójkątów. Teraz sektor mający wszystkich sąsiadów o takim poziomie szczegółowości będzie wyglądać tak :

(Indeksowanie w kwadracie czerwonym jest identyczne jak było)

Widać jak zmieniło się indeksowanie trójkątów skrajnych (takich, które łączą się z innymi sektorami)

A jak będzie to wyglądać dla sektorów gdzie jakiś sąsiad ma inny poziom szczegółowości ?(pamiętajmy o założeniu, że nie będzie to poziom większy niż jeden). Rysunek poniżej (pokazuje nam sytuację, gdzie każdy sąsiad ma inny poziom szczegółowości) :

Widzimy w tej sytuacji, że indeksowanie tego sektora wpasuje się nam do innego sektora, rozwiązując tym samym nasz problem, mianowicie usunie dziury w geometrii.

Jak to zaimplementować ? Cóż, moja implementacji do najładniejszych nie należy. Nie będę też przedstawiać tu kodu bo aktualny stan silnika będzie można pobrać w linku na samym dole. Chciałbym jedynie tutaj przedstawić zarys mojego rozwiązania. Obliczam sobie krawędź "normalną" tzn taką, która ma sąsiada o tym samym poziomie i krawędź "dodatkową', która ma sąsiada o innym poziomie szczegółowości. Nie muszę obliczać 4 takich krawędzi "normalnych" i "dodatkowych". Wystarczy 2, jedna obliczająca krawędź w poziomie a druga w pionie, a kolejne 2 oblicze z niedużych przekształceń tych 2 obliczonych wcześniej(tak naprawdę wystarczy jedna krawędź, ale wtedy jest więcej kombinowania, jakie wartości dodać, by otrzymać wszystkie cztery wartości). Każda z czterech krawędzie jest tak ponumerowana :

  

Teraz wystarczy przejść przez wszystkie podzbiory krawędzi. Jak efektywnie wygenerować podzbiory ?

Przedstawię pomysł, który pokazał mi  Pan Marcin Andrychowicz na kółku informatycznym : 

for(int i = 0; i < (1 << n) - 1; ++i){

   for(int j = 0; j < n; ++j)

      if(i & j) cout << j << " ";

   cout << j;

}

Jak to działa ? najpierw idzie pętla przez wszystkie podzbiory (lekkie przypomnienie z prawdopodobieństwa jak to policzyć). Ilość podzbiorów równa się 2 ^ n - 1. Potem idziemy przez wszystkie elementy, by sprawdzić, jakie elementy należą do aktualnie liczonego podzbioru. Warunek if(i & j) sprawdza czy element j należy do podzbioru i. Ale dlaczego to działa ? Operator & to zwykłe mnożenie bitowe. W naszym przykładzie warunek jest prawdziwy jeżeli i - ty bit jest równy jeden. Jeżeli nie bardzo rozumiesz rozpisz na kartce to powinieneś zrozumieć o co chodzi. Teraz wiedząc już jak wygenerować podzbiory przechodzimy do obliczania wszystkich IB.

Jak pokazałem wyżej puszczamy pętle przez wszystkie podzbiory (trzeba tylko delikatnie pozmieniać wartości w pętli bo trzeba zauważyć, że może występować taki index buffer, który nie będzie miał żadnej krawędzi "dodatkowej", dzieje się to przy sąsiadach o takim samym poziomie szczegółowości, a podzbiór nie może być przecież zerowy). U nas moc podzbioru oczywiście wynosi 4 bo mamy 4 krawędzie, numerowane :0, 1, 2, 3 jak pokazałem wyżej na rysunku. Wystarczy teraz dla i - tego podzbioru sprawdzić, które krawędzie w sobie zawiera, właśnie ten warunek to robi if(i & j) i dodać odpowiednie index' y i na koniec wygenerować wszystkie IB. No i na koniec renderując dany sektor musimy obliczyć, który zestaw index buffera wybrać. Robię to tak :

    int EvoHeightMap::GetGeoDetail(int i, int j){
        int result = 0;
        if(i > 0 && geoMap[i][j] < geoMap[i - 1][j]) result |= 4;
        if(j > 0 && geoMap[i][j] < geoMap[i][j - 1]) result |= 2;
        if(i < (numOfSectors - 1) && geoMap[i][j] < geoMap[i + 1][j]) result |= 1;
        if(j < (numOfSectors - 1) && geoMap[i][j] < geoMap[i][j + 1]) result |= 8;
        return result;
    }

geoMap - to tablica 2 - wymiarowa zawierająca jaki jest poziom geomipmappingu dla sektora [i][j].

Teraz nie ma już żadnych dziur :

Aktualny kod silnika do pobrania TUTAJ.

Pozdrawiam Norbert G.

Geomipmapping przy terenie

Dziś chciałbym przedstawić na czym polega metoda geomimappingu i jak ją zastosować do naszego terenu.

Podział terenu na sektory

Pierwszą rzecz jaką chciałbym przedstawić w tym artykule to podział całej naszej heightmpay na sektory. Z założenia teren jest kwadratem o boku będącą wielokrotnością 2. Drugim założeniem silnika jest to, że liczba sektorów również musi być wielokrotnością 2. Spójrzmy na poniższy rysunek, który wszystko to przedstawia :

Kwadratowa heightmapa o boku 256 została podzielona na na 16 sektorów, który każdy będzie mieć wymiary 64 x 64.... no właśnie nie dokońca. Tak naprawdę musimy dodać 1 wiersz i jedną kolumnę bo inaczej renderując sektory uzyskamy dziru pomiędzy sektorami, których chcemy uniknąć (rysunek poniżej) :

 Na powyższym rysunku widać pęknięcia terenu. Rozwiązanie jest takie, że wymiary sektora powinny być
mieć wymiary 2 ^ n + 1(czyli tak naprawdę i heightmapa powinna mieć wymiary 2^n + 1 ale przyjąłem, że będzie to 2^n a jeden dodatkowy wiersz i kolumnę dodaję ręcznie i ustawiam ich wierzchołki na ostatnią kolumnę/wiersz). Czyli sektory powinny wyglądać mniej więcej tak(czerwona linia to nasze sektory) :

w funkcji void EvoHeightMap::Load(EvoTexture* heightMap, int amountOfSectors, float xzScale = 1.0f, float yScale = 1.0f);

amountOfSectors to właśnie ilość sektorów na jeden bok. Na powyższym rysunku dalibyśmy tam wartość 2.

Geomipmapping w teorii

Na czym polega geomipmapping ? Jest to jeden z algorytmów LOD (Level of Detail), który ma za zadanie uprościć geometrię odległą od kamery w celu znacznego przyspieszenia renderingu. Jest to coś w rodzaju mipmappingu tylko, że dla geometrii. Założenie jest takie by teren był jakoś podzielony, za pomocą np. drzewa czwórkowego, lecz u siebie implementuję sektory jako tablica dwuwymiarowa po prostu (opisałem to w poprzednim akapicie). Każdy następny level geomipmapping' u zawiera 2 razy mniej wierzchołków (wszystkie wierzchołki brane są co drugi). Poniższy rysunek powinien wszystko wytłumaczyć.

Dany sektor będzie miał log_2(n - 1) + 1 leveli geomipmappingu, gdzie log_2 to logarytm o podstawie 2,
n - ilość wierzchołków w boku sektora i dodajemy 1 bo mamy jeszcze poziom zerowy.

Geomipmapping w praktyce

No dobra ale jak to naprawdę wygląda w praktyce ?? W praktyce jest tak że przygotowujemy po prostu odpowiednie zestawy index bufferów, zawierające odpowiednie wierzchołki. Tak naprawdę będzie nam potrzebny tylko jeden zestaw dla 1 poziomu geomipmappingu, i będziemy po prostu odpowiednio się przesuwać od którego wierzchołka mamy rysować w VBO (ale o tym zachwilkę).

Jak wyznaczyć te zestawy IB dla każdego levelu geomipmappingu....ano już o tym praktycznie pisałem w artykule "Terrain Rendering part I". Wystarczy lekko zmodyfikować ten kod opierając się o ostatni rysunek i tylko trzeba uwzględnić, że każdy następy level będzie tworzył dwa razy większe kwadraty (wzdłuż i wszerz) niż poprzedni poziom.

kod przedstawia się mniej więcej tak :

REP(k, geoLevel){
    int power = 1 << k;
    vector face;
    REP(i, (sectorSize - 1) / power){
            REP(j, (sectorSize - 1) / power){
                //Pierwszy trójkąt
                face.PB(j * power + sectorSize * i);
                face.PB(j * power + sectorSize * i + power);
                face.PB(j * power + sectorSize * i + sectorSize * power);
                //Drugi trójkąt
                face.PB(j * power + sectorSize * i + sectorSize * power);
                face.PB(j * power + sectorSize * i + power);
                face.PB(j * power + sectorSize * i + sectorSize * power + power);
         }
    }

    //Tutaj musimy wygenerować VBO dla kazdego levelu geoMipMapping'u
}

gdzie power -  to 2 ^ k, geoLevel - to ilość poziomów geoMipMappingu, sectorSize - to ilość wierzchołków boku w jednym sektorze.

Wiem, że kod wygląda trochę zagmatwanie ale, trzeba wziąć kartkę do ręki i spróbować zrozumieć to (chodź wszystko zostało wytłumaczone wcześniej, więc myślę, że bez problemu zrobisz własną wersją towrzenia IB).

Teraz tylko wystarczy dla każdego środkowego weirzchołka sektora w zależność od odległości od kamery wybrać odpowiedni poziom. Jak to zrobisz to już twoja sprawa, ja narazei nie mam żadnej dobrej aproksymacji wybierania levelu. Pewnie uzależnię odpowiedni poziom za pomocą funkcji liniowej.

Teraz znając level danego sektora wystarczy tylko to wyrenderować.

glDrawElements(GL_TRIANGLES, countElement, GL_UNSIGNED_INT, (int*)offset);

countElement to liczba elementów danego geoMipMappingu (musimy sobie gdzieś to pozapamiętywać w jakiejś tablicy dla każdego levelu), a offset to przesunięcie od, którego wierzchołka mamy renderować. Dla wierzchołka w wierszu 'i' i kolumnie 'j', offset będzei wynosił 

countElement * (i * numOfSectors + j) * sizeof(unsigned int)

numOfSectors to ilość sektorów na jeden bok dla całej heightmapy. To już wszystko poniżej screen przykładowy.

Widzimy jednak przeszkadzające cięcia w geometrii. Niestety jest to efekt nieunikniony gdy 2 sąsiadujące ze sobą sektory będą posiadać inny poziom geomipmappingu. Są na to sposoby by tego uniknąć lecz to już temat na całkiem nowy artykuł...