2007.12_Cząsteczkowe generowanie ukształtowania terenu_[Programowanie Grafiki].pdf

Grafika

komputerowa

ukształtowania terenu

W prowadzenie do grafiki komputerowej sys-

Korneliusz Warszawski

temu 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 przed-

stawić za pomocą siatki wielokątów. Z wykorzysta-

niem 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 generowa-

nie roślinności, pęknięć, osadów, ale również może

być użyta jako system do generowania ukształtowa-

nia terenu.

Pierwsze próby odzwierciedlenia terenu mogły

odbyć się jedynie z wykorzystaniem mocy oblicze-

niowej superkomputerów, które były w stanie prze-

tworzyć dużą liczbę wielokątów w rozsądnym cza-

sie. Wraz z rozwojem procesorów, a w szczegól-

ności wprowadzeniem do komputerów osobistych

dedykowanych układów graficznych, możliwe sta-

ło się wyświetlenie przez nie wcześniej wygenero-

wanego terenu, a realistyczne efekty odwzorowa-

nia krajobrazu, przestały być domeną symulatorów

wojskowych.

1 1

1 1 1

1 1

2 2

0 0 0 0

Rysunek 1. Mapa wysokościowa i stworzona na jej

podstawie siatka z trójkątów równoramiennych

terenu, a jej dokładność maleje wraz ze wzrostem

liczby wierzchołków wchodzących w skład podsta-

wowej 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, drastycz-

nie spada wydajność rysowania. Przy optymalizacji

odzwierciedlania dużych map wysokościowych ko-

rzysta 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ę jedno-

rodną (składającą się z identycznych figur), na siat-

kę niejednorodną.

Przykładowo, można to wykonać poprzez za-

mianę grupy sąsiednich wierzchołków na pojedyn-

czy element z wysokością określoną jako śred-

nią wysokości całej grupy, bądź stosując takie

uśrednianie wyłącznie dla grup elementów sąsied-

nich o zbliżonej wysokości, pozostawiając wszyst-

kie wierzchołki o znacznie odbiegających warto-

ściach, aby były uwidocznione również na dalekich

planach. Dobranie odpowiedniego poziomu szcze-

gółów znacznie poprawi wydajność rysowania siat-

ki, przy jednoczesnej niewielkiej utracie jakości od-

zwierciedlenia danej mapy wysokości.

Mapa wysokościowa

i siatka wielokątów

Podstawową strukturą danych tworzoną na potrze-

by generowanego ukształtowania terenu jest tzw.

mapa wysokościowa lub zwana inaczej mapą wy-

sokości. Na podstawie zgromadzonych tu danych

tworzy się siatkę wielokątów odwzorowujących da-

ne ukształtowania terenu.

Mapa wysokościowa zorganizowana jest w tabli-

cę, której kolejne wiersze i kolumny odpowiadają za

„długość” i „szerokość” geograficzną terenu, nato-

miast wartości w komórkach wyznaczają wysoko-

ści w danym punkcie. Zamiast liczbowej tablicy wy-

sokości może być użyta mapa bitowa, sprowadzona

do skali szarości, gdzie współrzędne piksela odpo-

wiadają za pozycję danego wierzchołka siatki wie-

lokątów, natomiast odcień określa wartość jego wy-

sokości.

Odpowiedni dobór siatki wielokątów ma spo-

ry wpływ na jakość generowanego ukształtowania

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 gene-

ratorem lub emiterem oraz zbiór cząstek. Po stwo-

rzeniu mapy wysokościowej i przygotowaniu odpo-

wiedniej siatki wielokątów można przystąpić do pa-

rametryzacji 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.

Autor jest studentem studiów doktoranckich na Wydzia-

le Elektrotechniki, Informatyki i Telekomunikacji na Uni-

wersytecie Zielonogórskim. Obecnie pracuje jako Ad-

ministrator Systemów Informatycznych Sądu Rejonowe-

go w Nowej Soli.

Kontakt z autorem: k.warszawski@weit.uz.zgora.pl

www.sdjournal.org

Software Developer’s Journal 12/2007

Cząsteczkowe generowanie

Cząsteczkowe generowanie ukształtowania terenu

Listing 1. Wyznaczenie nowej pozycji cząstki w wirtualnej

przestrzeni

Rysunek 2. Przykłady siatek wielokątów

( ... 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

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).

Krok 2: Ustawienie parametrów generatora

Ustawienie pozycji generatora w wirtualnej przestrzeni. Po-

winien on być położony w pewnej odległości od siatki wielo-

kątów, aby cząsteczki miały możliwość swobodnego ruchu

zanim się z nią zetkną. Ponadto należy określić kształt i roz-

miar okna generatora, czyli powierzchni, na jakiej będą ge-

nerowane nowe cząstki oraz przestrzeń, na której będą się

one poruszać.

// 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)

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 życio-

wego (czasu pomiędzy stworzeniem przez generator, a znisz-

czeniem 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, ja-

ki obszar mapy wysokości i w jaki sposób będzie mody-

fikowany, 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ół zbo-

cza 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.

if ( Ymove > 200 )

{

if ( Ymove < 300 )

{

PartDisp . Y += 1 * step ;

}

else

{

PartDisp . Y += - 1 * step ;

}

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 mo-

// 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 ... )

poziom 0 poziom 1

poziom 2

Rysunek 3. Zmiana poziomu szczegółów siatki wielokątów

Software Developer’s Journal 12/2007

www.sdjournal.org

Grafika

komputerowa

przed

0,75

0,5

przed

0,25

Rysunek 4. Normalizacja

Rysunek 5. Wygładzanie

gą być generowane pojedynczo lub w grupach, co korzyst-

niej wpływa na wydajność pracy algorytmu.

ła się do mapy wysokościowej, w przeciwnym wypadku algo-

rytm może nigdy nie zakończyć swojej pracy.

Krok 5: Przemieszczenie cząstek

Cząstki przemieszczają się w wirtualnej przestrzeni swobod-

nie, a ich ruch w całości lub tylko częściowo bazuje na praw-

dopodobieństwie (uwzględniając dodatkowe parametry).

Ruch cząstki powinien być tak określony, aby cząstka zbliża-

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ń poru-

szania się.

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

( ... reszta implementacji ... )

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

{

continue ;

}

/* 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

// różnica poziomów

loat elevation = heightmap [ x_zero , z_zero ] -

heightmap [ i , j ];

// sprawdzenie czy się zsunie cząstka

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

{

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

// koniec testu

// przypisanie nowych współrzędnych

bool stop = false ;

x_zero = i ;

z_zero = j ;

// pominięcie indeksów z poza zakresu

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

{

continue ;

}

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

końca testu

stop = true ;

break ;

}

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

{

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

{

if ( stop ) { break ; }

}

( ... reszta implementacji ... )

// pominięcie indeksów z poza zakresu

www.sdjournal.org

Software Developer’s Journal 12/2007

Cząsteczkowe generowanie ukształtowania terenu

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 );

Rysunek 6. Wynik wygładzania

}

( ... reszta implementacji ... )

A więc czy jej pozycja nie przekroczyła minimalnej i maksy-

malnej wartości współrzędnych w każdej z osi.

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 ma-

py nie są mniejsze i ewentualnie wykonać zmianę współrzęd-

nych cząstki na niższy poziom. Po wykonaniu przemieszczenia

można ponownie wykonać ten krok dla nowej pozycji cząstki.

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.

Krok 9: Zmodyfikuj mapę wysokościową

W momencie, w którym następuje zetknięcie cząstki z siat-

ką 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

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ąst-

kę powierzchni mapy wysokościowej nie zsunie się ona na

Listing 3. Modyfikacja mapy wysokościowej

( ... reszta implementacji ... )

// pominięcie indeksów z poza zakresu

/* 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

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

{

continue ;

}

// wyliczenie modyikatora wysokości dla danego punktu

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

{

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

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

- z_zero , 2 )));

// pominięcie indeksów z poza zakresu

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

wysokości

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

{

continue ;

}

if ( height > 0 )

{

heightmap [ i , j ] += height ;

}

( ... reszta implementacji ... )

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

{

Software Developer’s Journal 12/2007

www.sdjournal.org

Grafika

komputerowa

Normalizacja

Po wygenerowaniu wartości na mapie wysokościowej, ich

zakres może być bardzo szeroki, przez co wizualizacja tere-

nu może nie wyglądać przejrzyście. Aby poprawić tę niedo-

godność można zastosować normalizację na zakres [ 0, 1 ]

wg prostej zależności:

y n = (y - min) / (max - min)

gdzie:

• y n – 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 odznacza-

ją się od reszty terenu to stosując tę metodę można je uwy-

puklić.

Metoda polega na wykonaniu operacji potęgowania dla

każdej wartości mapy wysokościowej. W zależności od wiel-

kości wykładnika potęgi wysokości pośrednie będą się odpo-

wiednio zmniejszały, a najwyższe wzniesienia stawały się smu-

klejsze i przez to będą bardziej wyróżniać się na tle reszty te-

renu.

rozmiar), wylicza się wartość, o jaką będzie zmodyfikowana

wysokość w danym punkcie węzłowym mapy wg zależności:

y i,j = r 2 - ((x i - x 0 ) 2 + (z j - z 0 ) 2 )

Podsumowanie

Zastosowań generowania terenu w dzisiejszym życiu jest

bardzo wiele, począwszy od szkoleń w symulatorach woj-

skowych oraz cywilnych, poprzez kinematografię i przemysł

rozrywki elektronicznej, a skończywszy na elementach co-

raz śmielej wkraczającej w codzienne życie człowieka, rze-

czywistości wirtualnej.

Pomimo, iż system cząsteczkowy nie był stworzony na

potrzeby generowania ukształtowania terenu to całkiem do-

brze nadaje się do tego celu. Dzięki dużej podatności na

parametryzację, za pomocą tej metody można osiągnąć bar-

dzo szerokie spektrum generowanych powierzchni, a dzię-

ki temu stworzyć prawie dowolne ukształtowanie krajobrazu,

zarówno poprzez kształtowanie całej powierzchni mapy wy-

sokoś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 ge-

nerowania ukształtowania terenu, a dzięki temu, iż nie wy-

stępują tutaj skomplikowane obliczenia matematyczne pręd-

kość jej nie maleje wraz z wykonywaniem kolejnych kroków,

z czym mamy do czynienia przy stosowaniu metod opar-

tych na algorytmach fraktalnych. Dzięki temu swobodnie

można ją zaimplementować nawet na średniej klasy kom-

puterze domowym, a oczekiwanie na wygenerowanie du-

żej powierzchni krajobrazu nie będzie trwać dłużej niż kil-

ka minut. n

gdzie:

• y i,j – wyliczona wartość;

• r – rozmiar danej cząstki;

• (x o , z o ) – współrzędne zetknięcia cząstki z mapą wyso-

kościową;

• (x i , z j ) – współrzędne danego punktu, dla którego wy-

konuje 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

www.sdjournal.org

Software Developer’s Journal 12/2007

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: