Pregled postupaka

U ovome radu biti će prikazano kako su uzorci prisutni u izgradnji nekog modernog grada iskorišteni kao pravila algoritama i proceduralnih tehnika koje će pokušati izgraditi računalni model jednog takvog grada. Opisat će se niz tehnika korištenih za modeliranje mnogih aspekata urbanih scena - prometnica, zgrada, kuća, itd.

Svako urbano područje sadrži prometnu infrastrukturu koja prati utjecaje populacije i okoliša [3]. Ako krenemo od ideje da grad raste uzduž i okolo mreže prometnica i ulica koje se protežu nekim terenom, nećemo puno pogriješiti. Oblik mreže prometnica uvijetovat će nekoliko faktora: oblik terena, položaj voda i drugih prirodnih prepreka, gustoća naseljenosti.

Za izradu virtualnog grada potrebno je izraditi prometnu mrežu i generirati veći broj modela građevina. Iz nekoliko slikovnih mapa danih na ulazu u sustav, sustav generira mrežu prometnica i ulica, dijeli zemlju u parcele i kreira prikladnu geometriju za zgrade postavljene na te parcele.

Cijelokupni proces stvaranja virtualnog grada na temelju ulaznih podataka može se prikazati cijevovodom u kojemu je izlaz iz prethodne faze ulaz u slijedeću. Na temelju ulaznih mapa prirodnih prepreka i elevacije terena stvara se tenzorsko polje koje se naknadno može dodatno urediti korisnički zadanim uzorcima. Stvoreno tenzorsko polje ulaz je u fazu generiranja glavne prometne mreže - većih gradskih prometnica. U slijedećog fazi na temelju kreirane glavne prometne mreže obavlja se stvaranje kvartova - zatvorenih područja koje omeđuju prometnice glavne prometne mreže u kombinaciji sa granicama prirodnih prepreka. Unutar pojedinih kvartova identičnim postupkom kojime je stvorena glavna prometna mreža generira se mreža lokalnih kvartovskih ulica. Ponovnim detektiranjem zatvorenih područja, ovaj puta unutar svakog pojedinačnog kvarta, kreiraju se individualni blokovi - najmanje jedinice građevinskog terena omeđene ulicama. Blokovi se u postupku parcelizacije dijele u zasebne građevinske parcele. Lista građevinskih parcela ulaz je u poslijednju fazu - fazu generiranja geometrije, gdje se na svakoj parceli kreira po jedna građevina. Na slici 5 shematski je prikazan cijelokupni proces.

**Slika 5:**Shematski prikaz procesa
$\includegraphics[width=0.7\textwidth]{pipeline.eps}$

Izgradnja tenzorskog polja

Rezultantno tenzorsko polje kreira se na temelju topografskih podataka (granica voda, šuma, parkova, etc.), visinske mape, statističkih podataka (gustoće naseljeništva), te korisnički zadanih ograničenja (poželjnih prometnih uzoraka).

Korisnik kao ulaz u sustav specificira topografske i statističke podatke u obliku 2D mapa. Mape mogu biti ručno nacrtane, proceduralno generirane ili dobivene na temelju stvarnih podataka. Koristeći elemente tenzorskog polja korisnik zadaje položaj i oblik poželjnih prometnih uzoraka. Za svaki ulaz u sustav kreira se tenzorsko polje koje odgovara ulaznim podacima. Rezultantno tenzorsko polje dobije se težinskim sumiranjem svih ulaznih tenzorskih polja.

Slika 9 shematski prikazuje proces generiranja tenzorskog polja na temelju svih ulaznih podataka. Na temelju korisnički zadanih elemenata polja stvara se tenzorsko polje $T_{\sigma}$ , koje zajedno sa tenzorskim poljem stvorenim na temelju mape prirodnih prepreka $T_{\Gamma}$ i tenzorskim poljem mape elevacije terena , tvori rezultantno tenzorsko polje koje navodi proces generacije prometne mreže.

**Slika 9:**Izgradnja tenzorskog polja
$\includegraphics[width=1.0\textwidth]{tensor-field-generation.eps}$

Izgradnja prometne mreže

Prometna mreža generira se na temelju prethodno izgrađenog tenzorskog polja. Postupak izgradnje prometne mreže bazira se na praćenju glavnih i sporednih hiperlinija toka.

Važan aspekt svih uzoraka prometnih mreža je postojanje dva dominantna smjera koja proizlaze iz potrebe za što boljim iskorištenjem prostora. Iz tenzorskog polja proizlaze dva seta linija toka - jedan prati polje glavnog svojstvenog vektora dok drugi prati polje sporednog svojstvenog vektora [2].

Praćenje linija toka

Praćenje određene hiperlinije toka svodi se na integriranje vektorskog polja glavnog ili sporednog svojstvenog vektora tenzora , počevši od točke :

$\displaystyle p = p(l), \quad l \epsilon [0, +\infty \rangle$

$\displaystyle p(0) = p_0 = \left[\begin{array}{c} x_0 \\ y_0 \end{array}\right]$

$\displaystyle E_v(p) = \frac{\partial p}{\partial l}$

$\displaystyle p(l_k + \Delta l) = p(l_k) + \int_{l=l_k}^{l=l_k + \Delta l} E\Big( p(l) \Big) dl$

Za ravnomjerno polaganje mreže linija toka koristi se adaptacija algoritma za praćenje linija opisan u radu Jobarda i Lefera [13]. Za numeričku integraciju koristi se Runge-Kutta postupak:

$\displaystyle p_{k+1} = p_k + h \frac{m_1 + 2m_2 + 2m_3 + m4}{6}$

$\displaystyle m_1 = E(p_k)$

$\displaystyle m_2 = E(p_k + h \frac{m_1}{2})$

$\displaystyle m_3 = E(p_k + h \frac{m_2}{2})$

$\displaystyle m_4 = E(p_k + h m_3)$

Postupak praćenja hiperlinije se zaustavlja ukoliko se zadovolji jedan od uvijeta:

granica domene polja je dosegnuta,
dosegnuta je degenerirana točka,
praćena hiperlinija sječe postojeću hiperliniju,
dosegnuta je maksimalna specificirana duljina hiperlinije.

Ispraćena hiperlinija toka koja zadovoljava uvijet minimalne dužine postaje kandidat za novu prometnicu prometne mreže. U kontekstu izgradnje prometne mreže jedna prometnica naziva se brid, zbog uske povezanosti postupka izgradnje prometne mreže sa izgradnjom grafa povezanosti. Također zbog istog razloga mijesto gdje se sijeku prometnice - križanja, čvorišta - nazivaju se vrhovi.

Izgradnja bridova

Na temelju ispraćene hiperlinije toka stvaraju se bridovi prometne mreže. Jedan brid u prometnoj mreži definiraju slijedeći podaci:

početna točka $V_{begin}$ - točka u kojoj brid zapičinje,
krajnja točka $V_{end}$ - točka u kojoj brid završava,
trag (engl. trace) - poredani niz točaka koje se nalaze na pripadajućoj hiperliniji te su međusobno udaljene najviše $d_{sample}$ .

**Slika 14:** Shematski prikaz brida prometne mreže
$\includegraphics{edge.eps}$

Da li će nova linija postati brid i u kakvom obliku ovisi o izgledu do tada izgrađene prometne mreže, tj. o položaju postojećih bridova.

Ukoliko je krajnja točka novog brida udaljena $d_{connect}$ od točke traga postojećeg brida , te ako novi brid sa postojećim zatvara kut ne manji od $45^{\circ}$ , tada se spojna točka bridova pretvara u novi vrh , postojeći brid se sječe na dva dijela, a novi vrh postaje zavšna točka novog brida (slika 15a).
Ukoliko je krajnja točka novog brida udaljena $d_{connect}$ od postojećeg vrha , tada postojeći vrh postaje krajnja točka novog brida, te tako novi brid završava u postojećem prometnom čvorištu (slika 15b).
Ukoliko novi brid ne sječe postojeći niti se spaja u postojeće čvorište tada se na poziciji završne točke $V_{end}$ novog brida stvara novi vrh prometne mreže , pod uvijetom da $d_{sep}$ oko novog vrha nema postojećih vrhova (slika 15c).

**Slika 15:**Stvaranje novog brida
$\includegraphics{edge-new-1.eps}$ (a) Novi brid sječe postojeći brid $\includegraphics{edge-new-2.eps}$ (b) Novi brid spaja se u postojećem vrhu $\includegraphics{edge-new-3.eps}$ (c) Novi brid stvara novi vrh

Rasadne točke

Praćenje hiperlinije toka uvijek započinje u tzv. rasadnoj točki (engl. seed point). Početni skup rasadnih točkaka u tenzorskom polju može biti zadan od strane korisnika ili može biti proceduralno generiran.

Sve aktualne rasadne točke drže se u prioritetnoj listi. Prioritet svake točke može ovisiti o raznim parametrima, a kao najvažniji navode se [2]:

udaljenost do najbliže prirodne prepreke ,
udaljenost do najbliže degenerirane točke tenzorskog polja ,
udaljenost do najbližeg centra populacije .

Wonka et al. u [2] predlažu slijedeći izraz za računanje prioriteta:

$\displaystyle \omega_{p_s} = e^{-d_b} + e^{-d_s} + e^{-d_p}$

Postupak izgradnje prometne mreže u svakoj iteraciji iz prioritetne liste uzima točku najvišeg prioriteta. Praćenjem hiperlinije toka iz te točke potencionalno se stvara novi brid. U slučaju da je novi brid uspješno stvoren, na lokaciji krajnje točke novog brida $V_{end}$ stvara se nova rasadna točka koja se dodaje u prioritetnu listu.

Graf povezanosti

Usporedno sa postupkom stvaranja prometne mreže obavlja se postupak izgradnje grafa povezanosti prometne mreže , gdje je skup vrhova grafa - točaka gdje se pojedine prometnice spajaju, a je skup bridova - cestovnih segmenata koji se protežu između dva spojišta.

Prije početka procesa izgradnje prometne mreže graf sadrži vrhove u točkama koje odgovaraju pozicijama inicijalnih rasadnih točaka. Svakom iteracijom postupka izgradnje u graf se dodaju vrhovi koji odgovaraju krajnjim točkama novo-stvorenih bridova $V_{end}$ , te se u graf dodaje veza izmežu vrhova koji su u toj iteraciji postali spojeni prometnicom.

Tako izgraženi graf koristi se u slijedećoj fazi postupka za pronalaženje kvartova i urbanih blokov unutar prometne mreže. Taj postupak obavlja se traženjem poligona u izvedenom grafu.

Formiranje urbanih područja

Izlaz iz faze generiranja prometne mreže (bilo glavne ili sporedne) u suštini je samo skup linija (bridova) međusobno spojenih u spojnim točkama (vrhovima). Takvu prometnu mrežu može se izravno reprezentirati planarnim grafom , gdje točke u kojima se linije spajaju tvore skup vrhova grafa $\mathcal{V}(G) = V$ , a linije koje se protežu između spojnih točaka tvore skup bridova grafa $\mathcal{E}(G) = E$ . Takav graf stvoren na temelju generirane prometne mreže nazivati ćemo izvedeni graf.

Izvedenim grafom koristiti ćemo se za pronalazak zatvorenih područja domene koja su sa svih strana omeđena prometnicama prometne mreže u kombinaciji sa granicama prirodnih prepreka. Područja omeđena prometnicama glavne prometne mreže nazivati ćemo kvartovi (engl. districts), a područja omeđena lokalnim kvartovskim ulicama nazivati ćemo blokovi (engl. blocks).

**Slika:** Detekcija poligona iz prometne mreže
$\includegraphics[width=0.45\textwidth]{polygons-1.eps}$ (a) Ulazna prometna mreža	$\includegraphics[width=0.45\textwidth]{polygons-2.eps}$ (b) Izvedeni graf
$\includegraphics[width=0.45\textwidth]{polygons-3.eps}$ (c) Izolirani individualni poligoni