Wprowadzenie do grafiki komputerowej systemu cząstek pozwoliło na zwiększenie realizmu obiektów, które ze względu na swój trudny do określenia kształt ciężko było przedstawić za pomocą siatki wielokątów. Z wykorzystaniem tej techniki generowanie realistycznych chmur, płomieni, czy też rozmaitych efektów specjalnych (wybuchy, dym, opary cieczy) przestało stwarzać problemy. Metoda ta pozwala również na generowanie roślinności, pęknięć, osadów, ale również może być użyta jako system do generowania ukształtowania terenu.

Autor: Korneliusz Warszawski
Źródło: Software Developer’s Journal 12/2007 (156) http://sdjournal.org

Pierwsze próby odzwierciedlenia terenu mogły odbyć się jedynie z wykorzystaniem mocy obliczeniowej superkomputerów, które były w stanie przetworzyć dużą liczbę wielokątów w rozsądnym czasie. Wraz z rozwojem procesorów, a w szczególności wprowadzeniem do komputerów osobistych dedykowanych układów graficznych, możliwe stało się wyświetlenie przez nie wcześniej wygenerowanego terenu, a realistyczne efekty odwzorowania krajobrazu, przestały być domeną symulatorów wojskowych.

Mapa wysokościowa i siatka wielokątów

Podstawową strukturą danych tworzoną na potrzeby generowanego ukształtowania terenu jest tzw. mapa wysokościowa lub zwana inaczej mapą wysokości. Na podstawie zgromadzonych tu danych tworzy się siatkę wielokątów odwzorowujących dane ukształtowania terenu. Mapa wysokościowa zorganizowana jest w tablicę, której kolejne wiersze i kolumny odpowiadają za „długość” i „szerokość” geograficzną terenu, natomiast wartości w komórkach wyznaczają wysokości w danym punkcie. Zamiast liczbowej tablicy wysokości może być użyta mapa bitowa, sprowadzona do skali szarości, gdzie współrzędne piksela odpowiadają za pozycję danego wierzchołka siatki wielokątów, natomiast odcień określa wartość jego wysokości. Odpowiedni dobór siatki wielokątów ma spory wpływ na jakość generowanego ukształtowania terenu, a jej dokładność maleje wraz ze wzrostem liczby wierzchołków wchodzących w skład podstawowej figury danej siatki. Przykładowo siatka, której podstawą jest kwadrat jest mniej dokładna od siatki stworzonej z trójkątów. Wraz ze wzrostem liczby wielokątów użytych do jej budowy, drastycznie spada wydajność rysowania. Przy optymalizacji odzwierciedlania dużych map wysokościowych korzysta się z techniki, w której zmniejsza się ilości szczegółów siatki wraz ze wzrostem odległości od punktu obserwacji, czyli zamienia się siatkę jednorodną (składającą się z identycznych figur), na siatkę niejednorodną. Przykładowo, można to wykonać poprzez zamianę grupy sąsiednich wierzchołków na pojedynczy element z wysokością określoną jako średnią wysokości całej grupy, bądź stosując takie uśrednianie wyłącznie dla grup elementów sąsiednich o zbliżonej wysokości, pozostawiając wszystkie wierzchołki o znacznie odbiegających wartościach, aby były uwidocznione również na dalekich planach. Dobranie odpowiedniego poziomu szczegółów znacznie poprawi wydajność rysowania siatki, przy jednoczesnej niewielkiej utracie jakości odzwierciedlenia danej mapy wysokości.

Generowanie terenu

W każdym systemie cząsteczkowym niezależnie do jakich celów będzie on użyty, występuje element uwalniający nowo stworzone cząstki, zwany generatorem lub emiterem oraz zbiór cząstek. Po stworzeniu mapy wysokościowej i przygotowaniu odpowiedniej siatki wielokątów można przystąpić do parametryzacji systemu cząsteczkowego, określając atrybut generatora, zasady zachowania cząstek oraz ich kolizji z mapą wysokościową. Określenie odpowiednich wartości parametrów ma największy wpływ na rodzaj generowanego terenu.

Krok 1: Przygotowanie mapy wysokościowej

Sprowadza się do wypełnienia całej mapy dowolną wartością (zazwyczaj polega na wyzerowaniu, bądź wypełnieniu losowymi wartościami wszystkich komórek mapy).

Listing 1. Wyznaczenie nowej pozycji cząstki w wirtualnej

przestrzeni

(…reszta implementacji…)

/* Parametry wejściowe bloku

————————-

PartDisp – struktura przechowująca pozycję cząstki

step – współczynnik przesunięcia cząstki

*/

int Xmove = random(1000); // szansa na przemieszczenie w

osi X

int Ymove = random(1000); // szansa na przemieszczenie w

osi Y

int Zmove = random(1000); // szansa na przemieszczenie w

osi Z

// 25% na przesunięcie w osi X w jedną lub drugą stronę,

// 50% na pozostanie w osi X.

if (Xmove > 250)

{

if (Xmove < 500)

{

PartDisp.X += 1 * step;

}

}

else

{

PartDisp.X += -1 * step;

}

// 20% na przesunięcie w osi Y w górę

// 30% na pozostanie w osi Y,

// 50% na przesunięcie w osi Y w dół (cząstka ma największą

szansę ruchu w kierunku mapy)

if (Ymove > 200)

{

if (Ymove < 300)

{

PartDisp.Y += 1 * step;

}

}

else

{

PartDisp.Y += -1 * step;

}

// 25% na przesunięcie w osi Z w jedną lub drugą stronę,

// 50% na pozostanie w osi Z.

if (Zmove > 250)

{

if (Zmove < 500)

{

PartDisp.Z += 1 * step;

}

}

else

{

PartDisp.Z += -1 * step;

}

(…reszta implementacji…)

Krok 2: Ustawienie parametrów generatora

Ustawienie pozycji generatora w wirtualnej przestrzeni. Powinien on być położony w pewnej odległości od siatki wielokątów, aby cząsteczki miały możliwość swobodnego ruchu zanim się z nią zetkną. Ponadto należy określić kształt i rozmiar okna generatora, czyli powierzchni, na jakiej będą generowane nowe cząstki oraz przestrzeń, na której będą się one poruszać.

Krok 3: Ustawienie parametrów cząstek

System cząstek nie kontroluje pojedynczych obiektów, ale określa ogólne zasady zachowania podczas ich cyklu życiowego (czasu pomiędzy stworzeniem przez generator, a zniszczeniem cząstki). Dodatkowymi parametrami cząstek mogą być:

• prędkość opadania – cząstki o większej wartości będą szybciej zbliżać się do siatki wielokątów;
• masa, rozmiar, kształt – parametry, od których zależy, jaki obszar mapy wysokości i w jaki sposób będzie modyfikowany, gdy cząstka opadnie na siatkę wielokątów;
• lepkość, magnetyzm – parametry, od których zależeć może to czy cząstki mogą się łączyć ze sobą podczas lotu w „super-cząstkę” oraz może określać czy cząstka o niskiej wartości tego parametru zsunie się w dół zbocza siatki wielokątów po jej osiągnięciu. Może również określić szansę na rozpad „super-cząstki”, jeśli takowa zostanie już utworzona.

Listing 2. Test na zsunięcie się cząstki na niższy poziom

(…reszta implementacji…)

/* Parametry wejściowe bloku

————————-

x_zero, z_zero – współrzędne zetknięcia

cząstki z mapą wysokościową

viscosity – lepkość cząstki

heightmap – mapa wysokościowa

SIZE – rozmiar mapy wysokościowej

*/

for (int i = x_zero – 1; i <= x_zero + 1; i++)

{

// koniec testu

bool stop = false;

// pominięcie indeksów z poza zakresu

if (i < 0 || i >= SIZE)

{

continue;

}

for (int j = z_zero – 1; j <= z_zero + 1; j++)

{

if (heightmap[i, j] < heightmap[x_zero, z_zero])

{

// pominięcie indeksów z poza zakresu

if (j < 0 || j >= SIZE)

{

continue;

}

// różnica poziomów

float elevation = heightmap[x_zero, z_zero] -

heightmap[i, j];

// sprawdzenie czy się zsunie cząstka

if (random(101) / 100.0f < elevation * viscosity) {

// przypisanie nowych współrzędnych

x_zero = i;

z_zero = j;

// cząstka się zsunęła, więc spełniono warunki

końca testu

stop = true;

break;

}

}

}

if (stop) { break; }

}

(…reszta implementacji…)

Krok 4: Wygenerowanie nowej cząstki

Każda cząstka może być generowana wyłącznie w obszarze określonym przez rozmiar okna generatora. Cząsteczki mogą być generowane pojedynczo lub w grupach, co korzystniej wpływa na wydajność pracy algorytmu.

Krok 5: Przemieszczenie cząstek

Cząstki przemieszczają się w wirtualnej przestrzeni swobodnie, a ich ruch w całości lub tylko częściowo bazuje na prawdopodobieństwie (uwzględniając dodatkowe parametry). Ruch cząstki powinien być tak określony, aby cząstka zbliżała się do mapy wysokościowej, w przeciwnym wypadku algorytm może nigdy nie zakończyć swojej pracy.

Krok 6: Jeśli cząstka wyszła poza obszar to przejdź do kroku 10

Po wykonaniu przemieszczenia cząstki należy sprawdzić czy nie wyszła poza określoną w kroku 2 przestrzeń poruszania się. A więc czy jej pozycja nie przekroczyła minimalnej i maksymalnej wartości współrzędnych w każdej z osi.

Listing 3. Modyfikacja mapy wysokościowej

(…reszta implementacji…)

/* Parametry wejściowe bloku

————————-

SIZE – rozmiar mapy wysokościowej

x_zero, z_zero – współrzędne zetknięcia

cząstki z mapą wysokościową

radius – rozmiar cząstki

*/

for (int i = x_zero – radius; i <= x_zero + radius; i++)

{

// pominięcie indeksów z poza zakresu

if (i < 0 || i >= SIZE)

{

continue;

}

for (int j = z_zero – radius; j <= z_zero + radius; j++)

{

// pominięcie indeksów z poza zakresu

if (j < 0 || j >= SIZE)

{

continue;

}

// wyliczenie modyfikatora wysokości dla danego punktu

float height = (float) (Math.Pow(radius, 2) -

(Math.Pow(i – x_zero, 2) + Math.Pow(j

- z_zero, 2)));

// pominięcie węzłów z ujemną wartością modyfikatora

wysokości

if (height > 0)

{

heightmap[i, j] += height;

}

}

}

(…reszta implementacji…)

Krok 7: Jeśli cząstka nie osiągnęła siatki wielokątów to przejdź do kroku 5

Po wykonaniu przemieszczenia cząstki należy również sprawdzić czy nie osiągnęła ona mapy wysokościowej.

Listing 4. Normalizacja

(…reszta implementacji…)

/* Parametry wejściowe bloku

————————-

min – minimalna wartość na mapie wysokościowej

max – maksymalna wartość na mapie wysokościowej

heightmap – mapa wysokościowa

SIZE – rozmiar mapy wysokościowej

*/

for (int i = 0; i < SIZE; i++)

{

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

{

heightmap[i, j] = (heightmap[i, j] – min) / (max

– min);

}

}

(…reszta implementacji…)

Krok 8: Jeśli cząstka pozostanie w danym punkcie mapy to przejdź do kroku 9

W tym kroku można rozważyć czy po osiągnięciu przez cząstkę powierzchni mapy wysokościowej nie zsunie się ona na niższą elewację. W tym celu należy sprawdzić czy sąsiednie wysokości punktu, w którym nastąpiło zetknięcie cząstki i mapy nie są mniejsze i ewentualnie wykonać zmianę współrzędnych cząstki na niższy poziom. Po wykonaniu przemieszczenia można ponownie wykonać ten krok dla nowej pozycji cząstki.

Krok 9: Zmodyfikuj mapę wysokościową

W momencie, w którym następuje zetknięcie cząstki z siatką wielokątów należy zmodyfikować odpowiedni obszar mapy wysokościowej. Dla każdej komórki mapy wysokościowej, będącej w obszarze modyfikacji cząstki (określonym przez jej rozmiar), wylicza się wartość, o jaką będzie zmodyfikowana wysokość w danym punkcie węzłowym mapy wg zależności: yi,j = r2 – ((xi – x0)2 + (zj – z0)2) gdzie:

• yi,j – wyliczona wartość;

• r – rozmiar danej cząstki;

• (xo, zo ) – współrzędne zetknięcia cząstki z mapą wysokościową;

• (xi, zj) – współrzędne danego punktu, dla którego wykonuje się obliczenie;

• i, j – indeksy współrzędnych.

Krok 10: Zniszcz cząstkę

Zniszczenie cząstki może nastąpić w momencie opadnięcia na siatkę wielokątów oraz w momencie opuszczenia przez nią dozwolonej przestrzeni poruszania się.

Krok 11: Jeśli nie wygenerowano wszystkich cząstek to przejdź do kroku 4

Sprawdzenie czy system jeszcze może wygenerować nowe cząstki.

Krok 12: Jeśli nie zniszczono wszystkich cząstek to przejdź do kroku 5

Sprawdzenie warunku stopu algorytmu. Działa on dopóki wszystkie cząstki nie osiągną siatki wielokątów lub nie opuszczą dozwolonej przestrzeni poruszania się.

Krok 13: Zakończ algorytm Normalizacja

Po wygenerowaniu wartości na mapie wysokościowej, ich zakres może być bardzo szeroki, przez co wizualizacja terenu może nie wyglądać przejrzyście. Aby poprawić tę niedogodność można zastosować normalizację na zakres [0, 1] wg prostej zależności: yn = (y – min) / (max – min) gdzie:

• yn – wyliczona nowa wartość wysokości;
• y – aktualna wartość wysokości;
• min – najmniejsza znaleziona wartość na mapie wysokościowej;
• max – największa znaleziona wartość na mapie wysokościowej.

Rysunek 7. Przykłady wygenerowanego ukształtowania terenu

Wygładzanie

Opcjonalną metodą modyfikacji mapy wysokościowej jest wygładzanie. Jeśli po znormalizowaniu wygenerowanego ukształtowania terenu, szczyty niedostatecznie odznaczają się od reszty terenu to stosując tę metodę można je uwypuklić. Metoda polega na wykonaniu operacji potęgowania dla każdej wartości mapy wysokościowej. W zależności od wielkości wykładnika potęgi wysokości pośrednie będą się odpowiednio zmniejszały, a najwyższe wzniesienia stawały się smuklejsze i przez to będą bardziej wyróżniać się na tle reszty terenu.

Podsumowanie

Zastosowań generowania terenu w dzisiejszym życiu jest bardzo wiele, począwszy od szkoleń w symulatorach wojskowych oraz cywilnych, poprzez kinematografię i przemysł rozrywki elektronicznej, a skończywszy na elementach coraz śmielej wkraczającej w codzienne życie człowieka, rzeczywistości wirtualnej. Pomimo, iż system cząsteczkowy nie był stworzony na potrzeby generowania ukształtowania terenu to całkiem dobrze nadaje się do tego celu. Dzięki dużej podatności na parametryzację, za pomocą tej metody można osiągnąć bardzo szerokie spektrum generowanych powierzchni, a dzięki temu stworzyć prawie dowolne ukształtowanie krajobrazu, zarówno poprzez kształtowanie całej powierzchni mapy wysokościowej, jak i jej ograniczonego wycinka tworząc wyspy oraz archipelagi. Najważniejszą zaletą tej metody jest jej szybkość działania, która zależy głównie od ilości cząstek użytych do generowania ukształtowania terenu, a dzięki temu, iż nie występują tutaj skomplikowane obliczenia matematyczne prędkość jej nie maleje wraz z wykonywaniem kolejnych kroków, z czym mamy do czynienia przy stosowaniu metod opartych na algorytmach fraktalnych. Dzięki temu swobodnie można ją zaimplementować nawet na średniej klasy komputerze domowym, a oczekiwanie na wygenerowanie dużej powierzchni krajobrazu nie będzie trwać dłużej niż kilka minut.

O autorze

Autor jest studentem studiów doktoranckich na Wydziale Elektrotechniki, Informatyki i Telekomunikacji na Uniwersytecie Zielonogórskim. Obecnie pracuje jako Administrator Systemów Informatycznych Sądu Rejonowego w Nowej Soli.
Kontakt z autorem: k.warszawski@weit.uz.zgora.pl