next up previous contents
Next: 4.5 Povzetek Up: 4 Sledenje zarku Previous: 4.3.3 Pregled ostalih povrsin Vsebina: contents

4.4 Izboljsave osnovnega algoritma

Osnovni algoritem metode sledenja zarku je mogoce izboljsati na razlicne nacine, ki pa so odvisne od tega, kaj zelimo doseci. Zaradi casovne zahtevnosti metode sta ocitna dva izkljucujoca trenda: povecanje hitrosti obstojecih algoritmov ali zamenjava z boljsimi ter nasprotne teznje k cim bolj realisticnim prikazom. Vprasanja, ki si jih normalno postavimo pri ocenjevanju potreb v upodabljanju so:

Oceno stopnje zahtevnosti trenutnih algoritmov v upodabljanju in druga vprasanja glede kompleksnosti in subjektivne ocene realisticnih slik najdemo v [CS94]. Mozne so tudi izboljsave v pogledu casovne optimizacije posameznih algoritmov.

Ena osnovnih izboljsav, ki se lahko enostavno aplicirajo v obstojece algoritme s predpisano maksimalno globino rekurzije, temelji na dejstvu, da se pri veckratnem odbijanju zarka, manjsa tudi pomembnost zadnjih zarkov. Prispevki k osvetlitvi zaporedno generiranih zarkov se na koncu rekurzije mnozijo med seboj. Tudi pri visoko odbojnih scenah se kaj hitro zgodi, da ze po nekaj odbojih zadnji zarek ne vpliva bistveno na osvetlitev prvega presecisca. Zaradi tega je mozno vpeljati adaptivno kontrolo pomembnosti sukcesivnih sekundarnih zarkov, ki lahko prekine rekurzivno generiranje zarkov se predno doseze maksimalno predpisano globino. Tako se v rutino Trace() na strani gif normalno uvede dodatna utezna spremenljivka weight, ki se kumulativno racuna (mnozi) z lokalnim koeficientom za zrcalni odboj ali zrcalni prehod. Predpisani minimalni prispevek normalno velja globalno za celotno sceno.

 

 

Slika 4.7: Presek dveh omejitvenih prostorov

Drugi pomemben pristop k povecanju hitrosti racunanja presekov je uporaba omejitvenih volumnov (bounding volume) za objekte pri katerih je racunanje presekov zelo zahtevno. Osnovna ideja je v tem, da za kompleksne objekte poiscemo enostavnejse objekte, ki v celoti vsebujejo kompleksni objekt (povrsino). Ko iscemo presek zarka z vsemi moznimi objekti se za komplekne objekte raje uporabi presecni test omejitvenega volumna, ki ga veliko hitreje izracunamo. Sele ce obstaja presek med zarkom in omejitvenim volumnom, se pristopi k izracunavanju preseka med kompleksnim objektom in zarkom. Najenostavnejsi omejitveni volumen je seveda krogla, ki pa nima lastnosti tesnega prileganja in je lahko zaradi tega neucinkovita.

Kot omejitveni volumni so mozni tudi razlicni kvadri poljubno orientirani v prostoru. Kot omejitveni volmuen se lahko uporabi tudi presek dveh ali vec poljubnih omejitvenih prostorov. Pri taki omejitvi se pri testiranju moznosti obstoja preseka kompleksnega objekta in zarka, testira presek z vsemi volumni, ki kompleksni objekt omejujejo. Primer takega objekta je prikazan na sliki 4.7. Presek s kompleksnim objektom je smiselno izracunati le ce obstaja presek z vsemi omejitvenimi prostori kompleksnega objekta. Koliko omejitvenih volumnov se se splaca postaviti okoli enega samega objekta, je predvsem odvisno od razmerja zahtevnosti izracuna preseka osnovnega objekta in omejitvenega prostora. Ker se presek zarka obicajno izracunava za vse objekte v sceni, se lahko zgodi, da obstaja vec presekov kompleksih objektov z enim samim zarkom. Ce se preseki omejitvenih prostorov med seboj ne stikajo, lahko enostavno opustimo tocno racunanje presekov tistih kompleksih objektov, ki so za prvim objektom.

Podobno strategijo lahko uvedemo tudi pri mesanih okoljih, kjer imamo enostavne objekte brez omejitvenih prostorov in kompleksne objekte z omejitvenimi prostori. Pri dolocanju preseka se lahko zgodi, da obstaja najblizji presek za enostavni objekt, nato pa mu sledi presek z omejitvenim prostorom. V takih primerih prav tako ni potrebno tocneje dolociti preseka za kompleksni objekt.

Sheme z omejitvenimi prostori sicer nekako linearizirajo potreben racunski cas, tudi ce imamo v sceni vecje stevilo zahtevnih objektov. Problem se pojavi z vecanjem stevila osnovnih primitivov. Tako naletimo na problem kompleksnih scen, kjer stevilo objektov bistveno vpliva na racunski cas, saj je se vedno potrebno za vsak zarek izracunati (testirati) presek z vsemi objekti v sceni. Ce uporabimo nekoliko spremenjen pristop pri gradnji seznama objektov, pri katerem bi se ze vnaprej vedelo ali sploh obstaja moznost preseka zarka in objekta, bi bil cas neodvisen od stevila objektov. Eden od enostavnejsih prijemov je ta, da naredimo prostorski seznam, ki razdeli upodabljani prostor na enako velike kocke (voxle). Vsaki kocki pripisemo seznam objektov, ki jih kocka vsaj deloma vsebuje. Pri iskanju presekov zarka s se neznanimi objekti, najprej poiscemo preseke zarka s kockami. Ko dobimo presecne kocke, lahko iz seznamov, ki pripadajo kockam enostavno dobimo seznam moznih objektov, ki jih je potrebno testirati na presek. Uniformna delitev prostora pa najveckrat ni primerna zaradi spominske zahtevnosti, kot tudi algoritmicne pocasnosti.

Boljse sheme, kot sta oktalno drevo (octree) in binarna razdelitev prostora (Binary Space Partitioning), racionalneje razdelijo prostor. Omenjeni shemi imata strogo urejeno drevo z moznostjo adaptivne delitve prostora na mestih z vecjo gostoto objektov. Dolocanje polozaja tocke v drevesu je dokaj hitro tudi pri podrobnejsih delitva prostora. Iskanje polozaja tocke se pricne pri korenu drevesa in konca na koncnem listu v katerem je zapisan objekt, ki vsebuje testirano kocko v prostoru. V scenah z neenakomerno porazdelitvijo se lahko zgodi, da drevo pretirano raste v nekaterih smereh, zato je potrebno uporabiti modificirane sheme, ki uravnotezijo drevo tako, da je dostopni cas do vsakega lista enak.

V metodo sledenja zarku lahko enostavno vpeljemo tudi konstruktivno geometrijo trdnih teles (Constructive Solid Geometry). Z uvedbo CSG pa je potrebno adaptirati vecino algoritmov: od osnovnih za iskanje najblizjega presecisca pa do algoritmov za apriori delitve prostora.

Poleg omenjenih algoritmov s katerimi je mozno pospesiti osnovno metodo sledenja zarku, obstajajo tudi nekateri drugi, z manjsim prispevkom k hitrosti [AK91]. Paralelizacija vseh algoritmov je ena od metod, ki bistveno pripomore k zmanjsanju casa potrebnega za upodabljanje in bo podrobneje predstavljena na konkretnem primeru v poglavju 7.



Copyright © 1995 Leon Kos, Univerza v Ljubljani