HIT GEO Sergej Čapelnik IS NJE ETRIJS H PODAT Območna geodetska uprava Slovenj Gradec, Slovenj Gradec dr. Borut Žalik Fakulteta za elektrotehniko, računalništvo in informatiko, Maribor Prispelo za objavo: 1998-08-12 Pripravljeno za objavo: 1998-10-12 Izvleček V članku predstavljamo tehniko enakomerne delitve prostora ter prednosti, ki jih prinaša. Prostor delimo na več manjših enako velikih delov, ki jim pravimo celice. V 3D- prostoru imajo te celice obliko kocke, v 2D-prostoru pa obliko kvadrata. Namen delitve prostora je lokalizirati operacije nad geometrijskimi elementi, jih tako pospešiti ter vpeljati med geometrijske elemente neko strukturo. V postopku delitve prostora se vsi geometrijski elementi v tem prostoru porazdelijo po posameznih celicah. Ta porazdelitev poteka v dveh korakih. V prvem koraku se poiščejo Bresenhamove celice, v naslednjem koraku pa še manjkajoče Nebresenhamove celice. Algoritem deluje v aritmetiki s plavajočo vejico, kljub temu pa je zelo učinkovit. Predstavili smo tudi izboljšano metodo enakomerne delitve prostora, in sicer enakomerno adaptivno delitev prostora, ki temelji na celicah z različno velikostjo in odpravlja problem prenatrpanosti posameznih celic z geometrijskimi elementi. Ključne besede: celica, enakomerna adaptivna delitev prostora, enakomerna delitev prostora, rasterizacijski algoritmi Abstract This paper presents an efficient approach to, and the advantages oj; traversing a uniformly subdivided space pierced by a line segment. A voxel, as the basic constituent element of a uniformly subdivided space, is restricted to the form of a cube. The algorithm works in two steps. In the first step, the so-called Bresenham voxels are identified and, by comparing their position codes, their type of connectivity is determined. To achieve the required connectivity between neighbouring voxels, the second step of the algorithm is applied to find the missing voxels. In this way, the algorithm efficiently switches between face-, edge- and vertex-connectivity. Although the algorithm works with floating-point precision, in computational terms, it is extremely efficient. Keywords: ray tracing, uniform space subdivision, voxel, voxel traversing Geodetski vestnik 42 (1998) 3 ov UVOD Delitev prostora je rnetoda, ki močno zmanjša potreben procesorski čas pri različnih problemih računalniške geometrije in računalniške grafike. V grobem ločimo enakomerno in adaptivno delitev prostora. Že samo ime tehnike pove, da je treba obravnavani prostor razdeliti na več manjših, enako velikih delov. Tehniko delitve prostora lahko uporabimo nad 3D in tudi nad 2D-prostorom (ravnino). V obeh primerih prostor/ravnino delimo v enako velike dele, ki so razporejeni v mrežno strukturo s stranicami, vzporednimi koordinatnim osem. V 3D so te celice običajno kocke (pravimo jim ·voksli), v 2D pa kvadrati. V nadaljevanju bomo te elementarne dele imenovali celice. Tehnika delitve prostora je dolgo veljala za neuporabno, predvsem zaradi velikih pomnilniških zahtev. Zamislimo si delitev prostora z mrežo, ki prostor razdeli na 1024 delov po vsaki osL S tem smo dobili 1024 x 1024 x 1024 celic Če bi bila vsaka celica predstavljena le z enim bitom, bi nas to stalo 1 Gb prostora. V preteklosti so bile predlagane posebne strojne rešitve, ki bi premostile ta problem. Problemi, ki izvirajo iz računalniške geometrije (geometrijska iskanja, računalniška grafika, sledenje žarku), ne zahtevajo tako goste delitve. Za optimalno delovanje zadošča že nekaj sto celic. Takšno število celic pa lahko shranimo in obdelujemo že na običajnih osebnih računalnikih. Pri uporabi tehnike delitve prostora pridemo do rešitve problema v dveh korakih. Prvi korak je korak inicializacije. V tem koraku prostor razdelimo na potrebno število manjših delov celic. Vsaki celici je pripet seznam geometrijskih elementov (točke, črte, krivulje, mnogokotniki, ploskve, telesa), ki so prisotni v njej. Če se kakšen geometrijski element pojavi v več celicah, preide na seznam v vseh celicah. Celice so med seboj urejene glede na koordinatno izhodišče. Korak inicializacije mora biti končan hitro ter realiziran tako, da povečanje števila celic ne povzroči hudega povečanja potrebnega procesorskega časa. Po koncu inicializacijskega koraka se zavržejo vse prazne celice. Algoritem se osredotoči le•na tiste celice, ki nosijo neko informacijo. Dejanski problem je rešen v drugem koraku. Zaradi delitve prostora lahko to naredimo povsem lokalno (znotraj ene celice ali s pomočjo nekaj sosednjih celic), kar se kaže v bistvenem zmanjšanju potrebnega procesorskega časa. Podatki v geodeziji (še posebej v katastru) so sestavljeni iz točk, črt, mnogokotnikov ter črk. Algoritmi, ki v koraku inicializacije te geometrijske elemente prepoznavajo in razvrščajo po celicah, so sorazmerno preprosti. Nekoliko več težav je pri krivuljah in ploskvah svobodnih oblik (npr. B-zlepki, ki pa jih v klasičnih aplikacijah v geodeziji redko srečamo). Prav tako imamo pri geodeziji pogosto opravka le z dvema dimenzijama, kar algoritme še dodatno poenostavi. Slika 1 prikazuje daljico in nekaj mnogokotnikov. Zaniffm nas, ali daljica seka katerega od njih. Najbolj preprost in naiven način iskanja presečišč bi bil tak, kjer bi iskali presečišča daljice z vsakim_ robom vsakega mnogokotnika. Pri teh nekaj mnogokotnikih bi to še šlo, v primeru veliko večjega števila le-teh pa je treba problem rešiti lokalno. Poiskati je treba celice, v katerih so tako daljica kot mnogokotniki oziroma njihovi robovi. Takšne celice so v zgornjem primeru tri (Slika 1 ). V pn;i celici bi iskali le presečišča temnega trikotnika z daljico, v drugi celici so kandidati za presek vsi temni mnogokotniki, v zadnji celici pa bi iskali preseke daljice s temnim šestkotnikorn in kvadratom. Kako gosta naj bo mreža celic Geodetski vestnik 42 (1998) 3 oziroma kako velike naj bodo celice, da bodo algoritmi enakomerne delitve prostora optimalno delovali nad danimi podatki, je zelo težko vprašanje. Da lahko vsaj približno odgovorimo na to vprašanje, potrebujemo predvsem nekaj izkušenj. V literaturi smo zasledili formulo, ki pravi: velikost celice 4 (x,mu - Xmio)* (ym,, -y m,.,) * 3 n kjer so: = maksimalna vrednost okna po X osi = minimalna vrednost okna po X osi = maksimalna vrednost okna po Y osi = minimalna vrednost okna po Y osi Xmax Xmin Ymax Ymin n = število geometrijskih elementov, ki jih obdelujemo. o qo Slika 1: Prikaz prednosti delitve prostora Da bi omogočili hiter dostop do podatkov, jih moramo primerno predstaviti v pomnilniku računalnika. Osredotočiti se moramo na ozek del zanimivih podatkov in izvajati operacije le na njih. Tako je lahko odziv dobrega sistema zelo hiter kljub ogromnim količinam podatkov. V ozadju takšnih sistemov se skrivajo različne hierarhične podatkovne strukture. Podatki, shranjeni v eni od takšnih hierarhičnih struktur, omogočajo dajanje hitrih odgovorov na geometrijska vprašanja, kot so: katera točka je najbližja točki p, katera mnogokotnika delita podan rob, katere parcele so sosednje podani parceli ipd. prejšnji številki Geodetskega vestnika smo že predstavili eno od takšnih hierarhičnih podatkovnih struktur, ki je zelo popularna. To so štiriška drevesa. Štiriška in osmiška drevesa kot podatkovni strukturi za hierarhično delitev prostora Geodetski vestnik 42 (1998) 3 sta v literaturi dobro opisani, prav tako je dobro opisana enakomerna delitev prostora. Praktično ničesar pa nismo našli o adaptivni/prilagoditveni enakomerni delitvi prostora, ki jo trenutno razvijamo. Prav ta delitev prostora naj bi bila po naših pričakovanjih najprimernejša za geodetske aplikacije. Pri razvoju enakomerne adaptivne metode se nismo odločili za uporabo štiriških oziroma osmiških dreves. Razvili smo podatkovno relacijsko bazo, primerno za naš problem. Algoritmi, ki dostopajo do podatkov v naši bazi, so zaradi tega preprostejši in predvsem hitrejši. ALGORITMI ZA PREPOZNAVANJE (RASTERIZACIJO) GEOMETRIJSKIH ELEMENTOV '\ T grobem ločimo : V o algoritme, ki pri svojem delu uporabljajo celoštevilsko aritmetiko~ Začetna in končna točka vsake daljice je predstavljena s celoštevilskimi koordinatami. • Algoritme, ki pri svojem delu uporabljajo števila s plavajočo vejico. Za predstavitev začetne in končne točke vsake daljice so uporabljena števila z decimalno vejico (realna števila). Celoštevilski algoritmi so seveda hitrejši in niso podvrženi napakam zaokroževanja. Kljub temu se algoritmom s plavajočo vejico v določenih primerih ni možno izogniti (npr. če je celica velika eno enoto). Pri našem delu uporabljamo algoritem s plavajočo vejico. Koordinate začetnih in končnih točk daljic ter velikost celic so podane z realnimi števili. Kljub temu algoritem dosega željeno hitrost. Celice so razporejene v mrežo, vzporedno koordinatnim osem. // / / / / / / / / / / / / / / / / / / / / / / / f /////////////V b ////////////// /////////////V/ ////////////···--.;; 1/ v/ v v " Vl/1/VV / V 1/ 1/ v v / 1/ V /v v VIV V / / / VIV V / / / /VV V v / / / / / v v v / v / v v / / v v,, / v / v / / v / / v / / f/} / / p C ··-• v -------------···------------------ y~ vel'lkost celice ylks s ( X lks' Y11,s , 2 1k.l z 11,s z a) b) Slika 2: a) Organizacija celic v 3D-koordinatnem prostoru b) Lokalni koordinatni sistem celice Geodetski vestnik 42 (1998) 3 ot je razvidno iz slike 2a, sta položaj mreže in njena velikost opredeljena s točko o in tremi realnimi števili ( a, b, c ), ki določajo njeno dolžino, višino in globino. Gostota mreže določa velikost posamezne celice. Položaj celice v mreži podajajo tri števila, vsako za svojo koordinato. Celica, ki je spredaj, na dnu in skrajno levo je izhodišče referenčnega sistema. Tudi vsaka celica ima svoj lokalni koordinatni sistem, ki je enako usmerjen kot koordinatni sistem mreže (Slika 2b ). Koordinate znotraj posamezne celice se preprosto izračunajo s pomočjo izhodiščne točke po , položaja celice v mreži in lokalnih koordinat celice. • Bresenhamove celice Nebresenhamove celice Slika 3: Primer rasterizacije daljice v 2D-prostoru Osnovno idejo algoritma za prepoznavanje (rasterizacijo) podajamo v dveh korakih: o s pomočjo Bresenhamovega algoritma poiščemo tako imenovane Bresenhamove celice (temno obarvane celice na sliki 3). V ta namen najprej poiščemo tisto os premice, v kateri je naklon najmanjši. Z drugimi besedami, poiščemo os, v kateri je razdalja med začetno in končno točko daljice največja. Zahtevano je, da so ko1:2rdinate začetne točke daljice manjše od koordinat končne točke daljice. Ce niso, jih zamenjamo. o Poiščemo še Nebresenhamove celice (sivkasto obarvane na sliki 3). S tem je problem lokaliziran. V praksi je naš algoritem realiziran tako, da se iskanje Bresenhamovih in Nebresenhamovih celic prepleta, oboje pa se izračuna v enem samem koraku. Psevdokoda našega algoritma: vnos daljice (začetne in končne točke) z inicializacijo : o če daljica ni v celoti znotraj mreže celic, izračunaj presečiščne točke daljice z lupino mreže o poišči začetno in končno celico, ki jih prebada naša daljica o določi razvijalno os ( os z najmanjšim naklonom) o opravi določene globalne izračune. Predelani Bresenhamov algoritem začne z iskanjem zasedenih celic pri začetni točki daljice in ga nadaljuje v razvijalni osi, dolder ne doseže končne točke daljice. To Geodetski vestnik 42 (1998) 3 naredi na naslednji način: a) if najdena zadnja Bresenhamova celica, then končaj, else nadaljuj s korakom b b) izračunaj naslednjo Bresenhamovo celico c) ugotovi tip povezanosti zadnjih dveh izračunanih celic d) if obe celici nimata skupnega roba, then poišči še Nebresenhamovo celico e) vmisevkoraka). Da bi čimbolj skrajšali čas procesiranja algoritma, je treba odpraviti vsa nepotrebna preverjanja, tip povezanosti (skupen rob ali skupno oglišče, skupno lice) pa mora biti določen zelo hitro. Operacije, ki se najpogosteje pojavljajo znotraj algoritma, morajo biti seveda najhitrejše. Da smo pri našem algoritmu upoštevali opisane zahteve, kaže dejstvo, da se faza inicializacije nad 10 000 geometrijskimi elementi opravi v pičli sekundi. V 3D-prostoru ima ~saka celica 26 možnih sosedov. S pomočjo razvijalne osi zmanjšamo število potencialnih Bresenhamovih celic s 26 na 9. Ko ugotovimo naslednjo Bresenhamovo celico, še vedno obstaja možnost, da smo izpustili kakšno celico, ki je ne bi smeli zanemariti. To so Nebresenhamove celice. Iskanje teh celic je najbolj zahtevno opravilo znotraj algoritma. Če želimo poiskati te celice, moramo poznati tip povezanosti zadnjih dveh najdenih Bresenhamovih celic. Da ugotovimo tip povezanosti, je treba poznati naslova zadnjih dveh najdenih Bresenhamovih celic v mreži celic (naslov celice pove npr.: ta celica je tretja od koordinatnega izhodišča po X osi, sedma po Y osi in peta po Z osi). S primerjavo naslovov celic ugotovimo tip povezanosti celic. Če se naslova v 3D prostoru razlikujeta v vseh treh koordinatah, gre za povezanost le v eni točki. Pri takšni povezanosti je tudi najtežje odkriti Nebresenhamove celice. Če pa se sosednji celici razlikujeta le v eni koordinati (razvijalni osi), potem iskanje Nebresenhamovih celic ni potrebno. Hitrost našega algoritma je možno še izboljšati, predvsem z opravo zahteve, da naj ima začetna točka daljice v smeri razvijalne osi manjše koordinate kot končna točka daljice. V določenih primerih bi bilo priporočljivo spremeniti obliko celice iz kocke v kvader. Nekateri avtorji gredo pri spreminjanju oblike celice tako daleč, da kvadrat v 2D zamenjajo s pravilnim šestkotnikom ali s poljubnimi različno velikimi trikotniki. ENAKOMERNA ADAPTIVNA METODA DELITVE PROSTORA Trenutno znotraj Centra za geometrijsko modeliranje v okviru magistrske naloge razvijamo metodo, ki temelji na enakomerni adaptivni metodi delitve prostora. Skupaj z novimi algoritmi za označevanje celic in iskanja sosednosti razmišljamo tudi o drugačni relacijski bazi, kot smo jo uporabljali doslej. Enakomerna adaptivna· delitev je zelo podobna zgoraj opisani. Bistvena razlika je v delitvi prostora oziroma ravnine. Ta delitev se opravi na dveh ravneh. Uporabimo osnovno delitev (kot pri prej opisani metodi) ter podrobnejšo delitev tam, kjer je to potrebno (na mestih, kjer je gostota geometrijskih elementov bistveno večja od povprečja). Slika 4 prikazuje organizacijo relacijske podatkovne baze pri enakomerni adaptivni metodi deljenja 2D-prostora. Zgoraj levo opazimo mrežo celic, ki delijo prostor. Določen odstotek celic ne vsebuje nobenega geometrijskega elementa, zato lahko te celice po koraku inicializacije takoj zavržemo. Celicam, ki vsebujejo geometrijske elemente, pridružimo seznam teh elementov. Dejansko je to seznam kazalcev, ki Geodetski vestnik 42 (1998) 3 kažejo na iste geometrijske elemente v podatkovnem skladišču. Vsakemu geometrijskemu elementu določi mesto v podatkovnem skladišču sekljalna funkcija. Celice, ki so po prvem koraku inicializacije zelo natrpane z geometrijskimi elementi, nadalje delimo. Geometrijske elemente teh celic izbrišemo iz pod3.tkovnega skladišča. Izbrišemo tudi sezname kazalcev na te geon.aetrijske elemente. Ustvarimo nov kazalec, ki kaže podatkovno strukturo mreže celic, dobljene z deiit;1ijo ene celice. Ta sekundarna mreža s svojimi manjšimi celicami seveda nima svojega podatkovnega skladišča, temveč uporablja skupno podatkovno skladišče. Ob spremembi organizacije relacijske baze podatkov se nekoliko spremenijo tudi aigoritmi enakomerne adaptivne delitve prostora. Slabost navadne enakomerne delitve prostora je neenakomerna zasedenost celic. Metoda bi gotovo delovala najbolje v primeru, ko bi bilo število geometrijskih elementov v vseh zasedenih celicah približno enako. podatkovno skladišče 11 3 4 5 CJ l~~~ c O o o c"J ••••• •' [L'[i.1rl-, ~I __ L.J N L~ LJ o /' ;, ✓/ [~ .. Slika 4: Organizacija podatkov znotraj relacijske baze podatkov Primer: na karto ene katastrske občine položimo mrežo enako velikih kvadratov (recimo 4 cm x 4 cm). Določen kvadrat (celica) bo vseboval kup parcelnih črt oziroma poligonov. To bo v primeru, ko bo celica pokrivala strnjeno naselje. Celice zunaj strnjenih naselij pa bodo skoraj prazne. Tudi drugačna oblika celic ne bi bistveno pripomogla k odpravi tega problema. Rešitev je očitno v različni velikosti celic. Izboljšan algoritem enakomerne adaptivne delitve prostora se bo od prej opisanega algoritma bistveno razlikoval v koraku inicializacije. To je korak, kjer vse Geodetski vestnik 42 (1998) 3 geometrijske elemente razporedimo v mrežo celic, kar je tudi samoumevno, saj je sedaj mreža precej drugačna. Pričakujemo, da si bo korak inicializacije pri metodi enakomerne adaptivne delitve prostora odrezal večji kos procesorskega časa, kot je bil to primer v prejšnji metodi, vendar hkrati pričakujemo precej hitrejše odzive nadaljnjih operacij nad geometrijskimi elementi, ki sledijo koraku inicializacije. Ker se inicializacija za določeno risbo naredi le enkrat, ostalih operacij pa je običajno precej, pričakujemo, da se bo poseg v algoritem izkazal kot upravičen, in bo izpolnil naša pričakovanja. ZAKLJUČEK V članku smo predstavili enakomerno in enakomerno adaptivno delitev prostora. O enakomerni delitvi prostora in podatkovnih strukturah, ki jih pri svojem delu uporablja, je bilo v tuji strokovni literaturi napisanega že precej, o enakomerni adaptivni metodi pa nis)llo zasledili praktično ničesar. Razvoj metode s pripadajočimi podatkovnimi strukturami in algoritmi zato predstavlja poseben izziv. Prav enakomerna adaptivna delitev prostora naj bi bila po naših pričakovanjih najprimernejša za geodetske aplikacije. Litem tura: Cleary, ]. G., Wyvill, G., Analysis of an algorithm far fast ray tracing using uniform space subdivision. The Visual Computer, Springer-Verlag, 1988, št. 4, str. 65-83 Laurini, R., Milleret-Raffort, F., Topological reorganization of inconsistent geographical databases: A step towards their ce11ification. Computer & Graphics, 1994, zv. 18, št. 6, str. 803-813 Mortenson, M. E., Geometric Modeling. John Wiley & Sons, New York, 1985 Samet, H., The Design andAnalysis of Spatial Data Structures. Addison-Wesley, 1989 Tsung-Pao F., Piegl, L.A., Delaunay Triangulation Using a Uniform G1id. IEEE Computer Graphics &Applications, zv. 13, št. 3, 1993, str. 36-47 tx9912 Liu, Y.K., The Generation of Straight Lines on Hexagonal Grids. Computer Graphics Forum, 1993, zv. 12, št. 1, str. 27 -31 Recenzija: Uroš Mladenovič doc.dr. Radoš Šumrada Geodetski vestnik 42 (1998) 3