54
ALGORITEM ZA PRETVORBO TELESA	INFORMATICA 2/91
PREDSTAVLJENEGA Z OVOJNICO V PREDSTAVITEV Z OSMIŠKIM DREVESOM
Keywords: geometric modeling, boundary	Natalija Trstenjak,
representation, octree representation, computer	Borut Žalik, Nikola Guid
graphics	Tehniška fakulteta Maribor
Smetanova 17, 62000 Maribor Slovenija, Jugoslavija
Predstavitev teles z ovojnico Je Široko uporabljena v računalniški grafiki in predstavlja tudi primarno predstavitev v Eksperimentalnem modellrnlku teles, ki smo ga razvili. Vendar pa Je Izvajanje Boolovlh operatorjev, ki so standardno orodje vsakega modellrnlka, zelo težavno nad telesi predstavljenimi z ovojnico. Zato smo kot sekundarno predstavitev v modellrnlku uvedli predstavitev z osmiškimi drevesi, ki Je za Izvajanje Boolovlh operatorjev prav idealna. V tem članku obravnavamo pretvorbo predstavitve z ovojnico poljubnega telesa v predstavitev z osmiškim drevesom. Podrobno smo predstavili iskanje sečlšč med oktantom/ ln poljubnim telesom, ki Je najbolj kritičen del pretvorbe.
An Algorithm for Boundary to Octree Conversion
The boundary representation Is uidely used in computer graphics and it represents a primary representation in our Experimental geometric modeler. An implementation of the regularized Boolean operators which are the standard tools In the solid modelers is very complicated ln the case of boundary representation. For this reason the octree representation Is Included as a secundary representation and II Is almost ideal for the implementation of Boolean operators. In this paper, we consider the problem of converting the boundary representation of a polyhedron to its octree representation. The critical work in the subdlvison process is to determine how an octant Intersects the polyhedron and this problem is described ln details.
1 Uvod
Osnovni problem geometrijskega modeliranja je v opisovanju tridimenzionalnega zveznega telesa v digitalnem računalniku tako, da je predstavitev nedvoumna [HII.L821. Znanih Je več nedvoumnih predstavitev, najpogostejše pa so predstavitev z ovojnico ("boundary representation", B-rep), predstavitev s temeljiml gradniki ("constructive solid
geometry", CSG) in z osmiškimi drevesi ("octree representation") ([REQU821, [REQU83], [MORT85]). Vsaka Izmed predstavitev ima svoje slabosti ln prednosti. Zato večina komercialnih modellrnikov temelji na takolmenovanl hibridni predstavitvi, ki Jo dobimo s kombinacijo vsaj dveh različnih predstavitev, Idealno arhitekturo bi tvorile vse tri prej omenjene predstavitve [MILL89). Za hibridno predstavitev so Izjemno pomembni učinkoviti pretvorbeni algoritmi iz
55
one predstavitve v drugo. V prispevku bomo podali pretvorbenl algoritem iz predstavitve z ovojnico v predstavitev z osmišklm drevesom.
Predstavitev z ovojnico hrani podatke o površju telesa in je sestavljeno lz oglišč, robov ln ploskev. Podatkovna struktura mora hraniti tako sosednostne relacije kot geometrijske podatke, kar zahteva pazljivo načrtovanje podatkovne strukture. Ker Je vsaka ploskev predstavljena eksplicitno, omogoča dodajanje specifičnih informacij vsaki ploskvi telesa (npr. barva, kvaliteta materiala), prav tako pa v principu ni težav pri vgradnji poljubno oblikovanih ploskev ICHIY87]. Pri vlzuallzacijl predstavljenega telesa večjih težav ni, saj lahko žični model prikažemo zelo hitro, mnogo klasičnih algoritmov računalniške grafike za odstranjevanje zakritih robov, senčenje ln uporabljanje pa temelji na tej predstavitvi [PRAT831. Telesa lahko modeliramo z nizko - nlvojskimi operatorji, npr. Eulerjevlmi operatorji, z uporabo višje - nlvojsklh lokalnih operatorjev ln z Boolovlmi operatorji ([MANT82], [WILS851, ICHIY85], (MANT881). Prav implementacija Boolovlh operatorjev, ki so standardno orodje vsakega geometrijskega modelirnika, pa Je v predstavitvi z ovojnico zelo težavno [MANT83J.
Predstavitev z osmišklm drevesom temelji na principu rekurzlvne delitve prostora. Rezultat rekurzlvnega delitvenega procesa je predstavljen z drevesom osme stopnje, katerega vozlišča so ali listi ali sinovi. Korensko vozlišče v Izhodnem drevesu predstavja vhodni prostor. Končna vozllšča-llstl predstavljajo oktante, ki vsebujejo enotske kocke iste barve ln so označena s črna ali bela, odvisno od tega ali se nahajajo znotraj ali zunaj telesa. Vmesna vozlišča Imenujemo notranja vozlišča ln so označena s siva. Ta predstavljajo oktante v prostoru osmiškega drevesa, ki ležijo delno znotraj delno zunaj telesa in jih v rekurzlvnem postopku delimo na podoktante. Vsak oktant ima predpisano osmiško kodo, ki določa njegov položaj glede na oktanta očeta. Osmlške kode oktantov so prikazane na sliki la, primer telesa in njegove predstavitve pa kažeta sliki lb in lc.
Predstavitev z osmiškiml drevesi je prav idealna za Izvajanje Boolovlh operacij. Vsa izračunavanja pri Boolovih operacijah temeljijo na celoštevilski aritmetiki (vse potrebne zaokrožitve smo namreč odpravili že v fazi tvorbe osmiškega drevesa), zato so algoritmi izredno robustni. Glavna slabost Je v tem, ker meja telesa ni eksplicitno znana, zato ni možno hitro prikazati npr. žičnega modela objekta; direktno jih lahko vlzualiziramo samo s tehnikami sledenja žarku ("ray tracing"). Prav tako predstavitev zahteva mnogo pomnilnika, s tem pa je omejena tudi resolucija objekta ICLIF87). Za predstavitev z osmiškiml drevesi razvijajo zaradi njenih dobrih lastnosti tudi specialno namensko aparaturno opremo [KAUF88].
a) Osmiške kode oktantov (oktant 4 je skrit)

h---;
b) Primer telesa
c) Njegova predstavitev z osmišklm drevesom
Slika 1 Osmlške kode oktantov ter predstavitev telesa z osmišklm drevesom
Naš Eksperimentalni geometrijski modellrnik (EGM) Ima primarno predstavitev z ovojnico, sekundarno pa z osmiškiml drevesi. Predstavitev z ovojnico podpira 14 vgrajenih Eulerjevlh operatorjev, domena teles pa vključuje telesa z ravnimi ploskvami [ŽALI89a]. Višje nivojskl operatorji omogočajo tvorbo teles s translaciJskim pomikanjem ln z operatorji, ki upoštevajo značilnosti teles (ŽALI90] . Vgrajeni so tudi Boolovi operatorji, ki pa so uspešni le nad konveksni telesi z lici, ki ne vsebujejo prstanov lŽALI89b). Zaradi tega smo se odločili, da bomo izdelali algoritem za pretvorbo predstavitve z ovojnico v predstavitev z osmiškiml drevesi.
2 Tehnike za tvorbo osmiškega drevesa iz predstavitve z ovojnico
Poznamo različne tehnike za tvorbo osmiškega drevesa, ki se razlikujejo med seboj po obliki vhodnih podatkov. Vhodni podatki so različne predstavitve 3D teles, kot so na primer 3D polja, zaporedne sekcije, slike obrisa objekta, globinske slike in modeli objektov. Med modele objektov spada tudi predstavitev z
56
ovojnico. Poznamo dve tehniki za tvorbo osmiškega drevesa telesa, predstavljenega z ovojnico: tehnika označevanja komponent ln tehnika deli-ln-vladaj.
Tehnika označevanja komponent temelji na principu polnjenja notranjosti zaprte meje, zato ne potrebuje testiranja presečišč. Algoritem Je sestavljen lz dveh delov. V prvem delu pretvorimo mejo objekta v delno 3D binarno drevo. Črni listi drevesa predstavljajo celice, ki sekajo mejo objekta. V drugem delu delno binarno drevo prečno obiščemo ln tiste nedoločene bele liste, ki odgovarjajo notranjosti ali zunanjosti telesa, klasificiramo v črna ali bela vozlišča, skladno s tehniko označevanja. Algoritem generlra binarno verzijo osmiškega drevesa, ki jo lahko enostavno pretvorimo v osmiško drevo.
Druga tehnika za pretvorbo poljubnega telesa, predstavljenega z ovojnico v predstavitev z osmlšklm drevesom, je tehnika deli_in_vladaj, ki Jo bomo v tem članku podrobno predstavili. Ta tehnika velja za grob pristop ln pričenja z enojnim črnim vozliščem - korenom drevesa kot začetno aprokslmaclJo poljubnega telesa in nato nadaljuje z rekurzlvno delitvijo prostora osmiškega drevesa. Algoritem Je predstavljen na sliki 2.
Deli_in_vladaJ ( vozlišče ) (* M : meja - obris telesa •)
Begin
Čase PRESEČIŠČE ( vozllšče.M ) of BELA : opusti vozlišče ln vkorenlnjeno
poddrevo ČRNA : vozlišče.barva = ČRNA SIVA : begin
vozlišče.barva = SIVA for 1 = 0 to 7 Dell_in_vladaJ ( vozi Išče.sini i 1 ) end
end End
Slika 2 Algoritem tehnike deli-ln-vladaj
Kritičen del v procesu delitve Je določiti, kako oktant seka poljubno telo. To lahko opravimo v dveh korakih: v prvem koraku pregledamo ali oktant seka katero koli ploskev poljubnega telesa. Če seka, potem je oktant delno zunaj, delno znotraj telesa, pripadajoče vozlišče v osmlškem drevesu označimo s siva ln oktant delimo na podoktante. Drugače Je oktant ali zunaj ali znotraj telesa. V drugem koraku, katerega bistvo Je vsebnostnl test. določimo, katera od trditev Je pravilna. Če za katero koli ogllšče oktanta ugotovimo, da Je obdano s površino poljubnega telesa, se oktant nahaja znotraj telesa, vozlišče osmiškega drevesa označimo s črna, drugače pa se nahaja zunaj telesa ln vozlišče osmiškega drevesa označimo z bela [H0ME88].
Ugotavljanje presečišča med oktantom ln poljubnim telesom
Testiranje presečišča med oktantom ln poljubnim telesom je v splošnem počasen proces. Da bi povečali hitrost testiranja presečišč, uvedemo lzločevalnl postopek, ki sestoji iz petih korakov oziroma testov:
-	testa mlnlmax,
-	testiranja ravnin ploskev telesa,
-	testiranja ogllšč ploskev telesa,
-	testiranja presečnega mnogokotnlka,
-	testiranja lukenj ploskve telesa.
Namen tega postopka Je v prvih dveh korakih zmanjšati število ploskev telesa, ki bodo prišle v naslednji korak. Izločamo ploskve, ki zagotovo ležijo zunaj oktanta in ga zato ne morejo sekati. Če Je število vseh izločenih ploskev enako številu vseh ploskev telesa, v naslednji korak ne vstopimo, saj lahko v takem primeru določimo barvo vozlišča oziroma presečišča z vsebnostnlm testom. V tretjem koraku želimo ugotoviti, ali oktant seka katero od ploskev telesa, ki Jih nismo izločili ln s tem določiti barvo vozlišča. Vsak nadaljni korak obravnava presečišče bolj podrobno in v zadnjem, petem koraku, barvo vozlišča osmiškega drevesa, ki predstavlja pripadajoč oktant v prostoru osmiškega drevesa, zagotovo določimo.
V podpoglavjih, ki sledijo, Je podrobno obdelan vsak korak in zaključki, ki sledijo iz rezultatov testiranja v omenjenem koraku.
3.1 Test mlnlmax
S testom mlnlmax Izločimo tiste ploskve telesa, ki zagotovo ne sekajo oktanta. Test Je razširjen na 3D prostor, z nJim pa ugotavljamo prekrivanje omejitvenih škatel ("bounding box") ploskev telesa in oktanta (omejitvena škatla ploskve je pravokotna škatla, katere robovi so vzporedni z osmi prostora osmiškega drevesa ln omejuje ploskev). To Je prva groba selekcija ploskev, ki ne sekajo oktanta, saj zaradi narave testa mlnlmax ne moremo trditi, da smo izločili vse takšne ploskve lz nadaljnega postopka [GUID881. Kljub temu pa s tem testom Izločimo veliko število ploskev, še posebej pri večji globini osmiškega drevesa, ko Je lahko oktant napram telesu zelo majhen.
Če s testom mlnlmax Izločimo vse ploskve telesa, kar pomeni, da vse ploskve ležijo zunaj oktanta, se lahko oktant nahaja strogo znotraj telesa ali strogo zunaj telesa. Primer Je podan na sliki 3, kjer Je oktant narisan z močnejšo ln telo s tanjšo črto. Da bi določili, katera od trditev Je pravilna, uporabimo vsebnostnl test ogllšč oktanta v telesu.
57
r.......... • '


a) Oktant strogo znotraj b) Oktant strogo zunaj
telesa
telesa
Slika 3 S testom minimax smo izločili vse ploskve telesa
a) Oktant zunaj telesa b) Oktant znotraj telesa
Slika 5 Ploskve telesa 2, 3, 5 smo Izločili s testom mlnimax,ravnine ploskev 1, 4, 6 sovpadajo z ravninami oktanta
Če s testom minlmax nismo izločili vseh ploskev telesa, oziroma ne moremo trditi, da ležijo vse zunaj oktanta, ne moremo določiti barve vozlišča osmiškega drevesa. Ploskve, ki Jih nismo izločili, testiramo v drugem koraku, ki vključuje test ravnin ploskev.
Če vsota do sedaj izločenih ploskev ni enaka Številu vseh ploskev telesa. Je barva presečišča odvisna od lege ploskev, ki jih še nismo Izločili. Te ploskve testiramo v naslednjem koraku, ki vključuje test ogllšč ploskev.
3.2 Test ravnin ploskev telesa
3.3 Test oglišč ploskev telesa
S tem testom izločimo ploskve telesa, ki se oktanta dotikajo. Za vsako ploskev telesa izračunamo enačbo ravnine, v kateri leži, ln Jo primerjamo z enačbami ravnin, v katerih ležijo ploskve oktanta. Če ravnina ploskve telesa sovpada s katero od ravnin ploskev oktanta, leži ploskev telesa na eni od ploskev oktanta ali pa se oktanta dotika v enem od njegovih robov. Primer je podan na sliki 4, kjer so ploskve telesa označene s vodoravno šrafuro. V tem primeru se ploskev ln oktant zagotovo ne sekata ln ploskev Izločimo Iz nadaljnega postopka.
V tem koraku ne Izločamo ploskev, ampak želimo ugotoviti, ali katera od ploskev zagotovo seka oktant. Ploskve telesa, ki Jih testiramo v tem koraku, lahko:
-	ležijo znotraj oktanta,
-	sekajo oktant,
-	ležijo zunaj oktanta.
J	/
--Ln A	
	
	ffluy
/	/
OP=NP ; MP=0,ZP=0	
b) OP=MP ; NP-0,ZP=0
Slika 4 Ploskve telesa, katerih ravnine sovpadajo z ravninami ploskev oktanta
Če Je vsota ploskev, ki smo Jih Izločili v prvem koraku, ln ploskev, katere smo izločili v drugem koraku, enaka številu vseh ploskev telesa, se lahko oktant nahaja le zunaj ali znotraj telesa (slika 5). Uporabimo vsebnostnl test, da ugotovimo, katera od navedenih trditev je pravilna ln lahko skladno s tehniko označevanja določimo barvo vozlišča osmiškega drevesa.
c) OP=MP+NP ; MP*0, NP*0. ZP=0 Slika 6 Ploskev leži znotraj oktanta
58
Ploskev zagotovo seka oktant, če leži v celoti znotraj oktanta, ali pa seka oktant, ne glede na to ali Je konveksna ali konkavna ln ali ima luknje ali ne. Ta dva položaja ploskve lahko enostavno določimo na podlagi lege njenih oglišč.
Naj Je OP število vseh oglišč ploskve telesa. Število oglišč ploskve zunaj oktanta označimo z ZP, Število ogllSč znotraj oktanta z NP ln število oglišč ploskve na meji oktanta z HP.
Ce se vsa ogllšča ploskve telesa nahajajo znotraj ali na meji oktanta, oziroma če velja
3.4 Test presečnega mnogokotnlka
Za ploskve telesa, ki Jih testiramo v tem koraku velja, da Imajo vsaj eno ogllšče zunaj oktanta ln nobenega ogliSta znotraj oktanta oziroma velja
OP = MP + ZP ; NP = 0, ZP * 0	(3)
Ploskve telesa lahko ležijo zunaj oktanta ali sekajo oktant (slika 8), na rezultat testa pa lahko vpliva tudi konkavnost ploskve.
OP = NP + MP ; ZP = 0	(1)
lahko sklepamo, da se ploskev telesa nahaja, znotraj oktanta (slika 6). Ploskev ne more ležati na eni Izmed ploskev oktanta, kljub temu, da lahko vsa ogllšča ploskve telesa ležijo na meji oktanta, saj bi ploskev Izločili že v drugem koraku, s testom ravnin ploskev telesa (slika 4).
Če se vsaj eno ogllšče ploskve telesa nahaja zunaj oktanta ln vsaj eno ogllSče znotraj oktanta, oziroma če velja
OP = NP + MP + ZP ; ZP * 0 , NP * 0	(2)
ploskev telesa seka oktant, ne glede na to ali je konveksna ali konkavna ln ali ima luknje ali ne (slika 7).
a) 0P=NP+ZP	b) 0P=NP+MP+ZP
MP=0,NP*0,ZP*0	NP*0,MP*0,ZP*0
Slika 7 Ploskev seka oktant
Ko ugotovimo, da se vsaj ena od ploskev telesa nahaja znotraj oktanta ali seka oktant, Je barva vozlišča osmlškega drevesa siva ne glede na položaj ostalih ploskev telesa glede na oktant.
Če za nobeno od ploskev telesa, ki smo Jih testirali v tem koraku ne velja enačba 1 ali enačba 2, ne moremo trditi, da katera od ploskev seka oktant, ali da so vse ploskve zunaj oktanta, zato nadaljujemo s četrtim korakom, ki vključuje test presečnega mnogokotnlka.
a) 0P=ZP;MP=0,NP=0	b) 0P=MP+ZP
NP=0,ZP*0,MP*0
Slika 8 Ploskve telesa ležijo zunaj oktanta ali sekajo oktant
Cilj tega testa je Isti kot v tretjem koraku, le da Je postopek ugotavljanja presečišč bolj natančen, saj moramo upoštevati, da ima ploskev lahko luknje in ni nujno konveksna. Ta test sestoji iz štirih korakov -testov, ki se nanašajo na posamezno ploskev.
Da bi ugotovili položaj ploskve telesa, si pomagamo s presečnim ranogokotnikon, ki ga določajo točke, v katerih ravnina ploskve telesa seka oktant. Ravnina ploskve telesa seka ravnine šestih ploskev oktanta v šestih premicah. Točke, v katerih se teh šest premic seka, določajo ogllšča presečnega mnogokotnlka, ki leži v ravnini ploskve telesa. Ploskev telesa seka oktant le takrat, ko seka presečni mnogokotnlk.
V prvem koraku testiramo število oglišč presečnega mnogokotnlka, ki Je odvisno od položaja ravnine ploskve telesa glede na oktant. Na podlagi rezultatov tega testa, Izločimo ploskve, ki ležijo zunaj oktanta.
Naj Je OPM število vseh oglišč presečnega mnokotnlka. Ko je število oglišč presečnega mnogokotnlka manjše ali enako dva, oziroma če velja
OPM a 2 ; OPM * 0	(4)
se ravnina ploskve telesa dotika oktanta. Ko je število oglišč presečnega mnogokotnlka enako nič, oziroma če velja
59
OPM = O
(5)
leži ravnina ploskve telesa zunaj oktanta. Na podlagi tega sklepamo, da ploskev ne seka oktanta, temveč zagotovo leži zunaj oktanta (slika 9).
a) OPM
b) OPM
c) OPM = 0
Slika 9 Ploskev telesa leži zunaj oktanta
Ko Je število oglišč presečnega mnogokotnlka večje od dva, oziroma velja.
OPM > 2
(6)
ravnina ploskve seka oktant in preidemo na drugi korak (slika 10).
/¡J	
— / /	7
a) OPM = 4
b) OPM = 3
Slika 10 Ploskev telesa seka oktant
V drugem koraku moramo določiti položaj presečnega mnogokotnlka glede na ploskev telesa. Da bi poenostavili vsebnostni test, s katerim določamo položaj oglišč presečnega mnogokotnlka, zavrtimo ravnino, v kateri ležita ploskev In presečni mnogokotnik tako, da je vzporedna s koordinatno ravnino XY. To opravimo tako, da zavrtimo normalni vektor ploskve telesa v koordinatno os Z (slika 11).

Slika 11 Rotacija normale ploskve telesa v koordinatno os Z
Sedaj opravimo vsebnostni test, da ugotovimo položaj presečnega mnogokotnlka glede na ploskev telesa. Presečni mnogokotnik je na vseh nadaljnih slikah označen z navpično Šrafuro, ploskev telesa pa z vodoravno šrafuro.
Naj bo ZPH število oglišč presečnega mnogokotnlka zunaj ploskve, MPM naj bo število oglišč na meji ploskve ln NPM število oglišč znotraj ploskve telesa. Presečni mnogokotnik lahko leži:
-	strogo znotraj ploskve telesa,
-	seka ploskev telesa,
-	znotraj ploskve telesa,
-	zunaj ploskve telesa.
Če so vsa ogllšča presečnega mnogokotnlka znotraj ploskve, oziroma če velja
OPM = NPM ; MPM = 0, ZPM
(7)
potem Je presečni mnogokotnik strogo znotraj ploskve telesa (slika 12), vendar barve vozlišča ne moremo določiti, saj je ta odvisna od medsebojne lege presečnega mnogokotnlka ln lukenj v ploskvi.
Če ploskev nima lukenj, potem ploskev seka oktant (slika I2a) in Je barva vozlišča osmlškega drevesa siva. V primeru, ko Ima ploskev luknje (slika 12b), uporabimo test lukenj ploskve telesa in določimo položaj ploskve glede na oktant.
V primeru, ko enačba 7 nI Izpolnjena, preidemo na tretji korak. V tem koraku želimo ugotoviti, ali presečni mnogokotnik seka ploskev telesa.
a) Ploskev nima luknje
b) Ploskev z luknjo
Slika 12 Presečni mnogokotnik strogo znotraj ploskve telesa
Ce vsaj en rob presečnega mnogokotnlka seka kateri koli rob ploskve telesa, presečni mnogokotnik seka ploskev (slika 13), ne glede na to ali Je ploskev konkavna ali konveksna ln ali Ima luknje ali ne.
60
a) OPM = ZPM
b) OPM = ZPM + NPM
c) OPM = ZPM + NPM + MPM
d) OPM = ZPM + MPM
Slika 13 Presečni mnogokotnlk seka ploskav telesa
Ploskev telesa seka oktant, barva vozlišča osmiškega drevesa Je siva ln prekinemo s testiranjem presečišč.
Ce noben rob presečnega mnogokotnlka ne seka katerega koli roba ploskve telesa, preidemo na četrti korak.
V četrtem koraku ugotavljamo položaj presečnega mnogokotnlka glede na ploskev telesa na osnovi lege njegovih ogllšč.
Če so vsa ogllšča presečnega mnogokotnlka na meji ploskve telesa, oziroma če velja
a) OPM = MPM
b) OPM = ZPM ♦ MPM
c) OPM = ZPM
Slika 15 Presečni mnogokotnlk zunaj ploskve telesa
Ce Je vsaj eno ogllšče presečnega mnogokotnlka znotraj ploskve, oziroma če velja
OPM = NPM + MPM ; ZPM = 0, NPM * 0
(9)
leži presečni mnogokotnlk znotraj ploskve ln ploskev seka oktant (slika 14b,c). Barva presečišča, oziroma vozlišča osmiškega drevesa je siva in prekinemo s testLranJem presečišč.
Če Je vsaj eno oglišče presečnega mnogokotnlka zunaj ploskve telesa,■ozlroma če velja
OPM » MPM ! NPM = 0, ZPM » 0
(8)
OPM = ZPM + MPM ; ZPM * 0, NPM = O
(10)
Je rezultat testa odvisen od lege središčne točke presečnega mnogokotnlka (slika 14a, 15a).
i __ i".
a) OPM = MPM
b) OPM = MPM + NPM
c) OPM = MPM + NPM
Slika 14 Presečni mnogokotnlk znotraj ploskve telesa
Če središčna točka presečnega mnogokotnlka leži znotraj ploskve telesa, leži tudi presečni mnogokotnlk znotraj ploskve ln ploskev seka oktant (slika 14a). Barva presečišča Je siva ln prekinemo s testiranjem presečišč. Če leži središčna točka presečnega mnogokotnlka zunaj ploskve, leži tudi presečni mnogokotnlk zunaj ploskve telesa ln ploskev ne seka oktanta (slika 15a).
leži presečni mnogokotnlk zunaj ploskve (slika 15b,c) ln ploskev ne seka oktanta.
Rezultat testa presečnega mnogokotnlka nam vrne barvo presečišča oziroma vozlišča osmiškega drevesa, če vsaj ena ploskev telesa seka oktant. V primeru, ko nismo dobili barve presečišča, so vse ploskve, ki smo Jih testirali v tem koraku, zunaj oktanta (slika 16) ln oktant lahko leži znotraj telesa, ali zunaj telesa.
a) Oktant Je zunaj telesa
b) Oktant je znotraj telesa
Slika 16 Medsebojna lega telesa ln oktanta
Uporabimo vsebnostnl test ogllšč oktanta v telesu, da bi ugotovili, katera od trditev Je pravilna. Nato skladno s tehniko označevanja predpišemo vozlišču osmiškega drevesa črno ali belo barvo.
61
3.5 Test lukenj ploskve telesa
Presečni mnogokotnlk je strogo znotraj ploskve, ko velja enačba 7. Samo v tem primeru lahko luknja ploskve prekriva presečni mnogokotnlk (slika 12b) ln ploskev ne seka oktanta. Luknja v ploskvi se ne more dotikati roba ploskve niti sekati ploskve, zato v primerih, ko enačba 7 ne velja, presečni mnogokotnlk ne more biti v celoti prekrit z luknjo (slike 13, 14, 15). Ploskev ima lahko več lukenj (slika 17), zato test ponavljamo za vsako luknjo v ploskvi, dokler ne določimo barve presečišča.
Slika 17 Ploskev telesa z luknjami ln lega presečnega mnogokotnika
Ugotoviti moramo aH luknja v celoti prekriva presečni mnogokotnlk, saj v vseh ostalih primerih ploskev vsaj delno prekriva presečni mnogokotnlk, kar pomeni, da ploskev seka oktant.
Presečni mnogokotnlk lahko:
-	seka luknjo,
-	leži znotraj luknje,
-	prekriva luknjo,
-	leži strogo zunaj luknje.
Določanje medsebojne lege luknje ploskve ln presečnega mnogokotnika poteka v treh korakih.
V	prvem koraku uporabimo test mlnimax, s katerim določimo prekrivanje omejitvenih pravokotnikov presečnega mnogokotnika in luknje ploskve. Če se omejitvena pravokotnlka ne prekrivata, nadaljujemo z naslednjo luknjo ploskve. Ce za vse luknje ploskve velja, da se njihovi omejitveni pravokotnlki ne prekrivajo z omejitvenim pravokotnlkom presečnega mnogokotnika, potem presečni mnogokotnlk seka, oziroma leži na ploskvi telesa ln ta seka oktant. Če se omejitvena pravokotnlka luknje ploskve ln presečnega mnogokotnika prekrivata, preidemo na naslednji korak.
V	drugem koraku preverjamo, ali kateri od robov presečnega mnogokotnika seka kateri koli rob luknje ploskve. Ce Je test pritrdilen, leži presečni mnogokotnlk delno na ploskvi telesa in ploskev seka oktant ne glede na to, ali ima ploskev Se kakšno luknjo in kje na ploskvi se ta luknja nahaja (slika 18). Zato lahko v tem primeru zaključimo s testom lukenj ploskve.
Če je test sekanja robov negativen, nadaljujemo s tretjim korakom.
V	tretjem koraku želimo ugotoviti, ali luknja ploskve popolnoma prekriva presečni mnogokotnlk
Slika 18 Presečni mnogokotnlk seka luknjo ploskve
oziroma, ali leži presečni mnogokotnlk v celoti znotraj luknje ploskve. V tem primeru ploskev ne seka oktanta, ne glede na ostale luknje ploskve ln lahko zaključimo s testiranjem. Ce omejitveni pravokotnlk presečnega mnogokotnika omejuje omejitveni pravokotnlk luknje ploskve, ugotavljamo vsebnost luknje ploskve v presečnem mnogokotnlku, drugače pa ugotavljamo vsebnost presečnega mnogokotnika znotraj luknje ploskve. Ta vsebnostni test Je enak v obeh primerih, zato ga lahko posplošimo na ugotavljanje vsebnosti mnogokotnika Ml v mnogokotnlku M2.
Naj bo 0H1 število ogllšč mnogokotnika Ml ln 0M2 Število ogllšč mnogokotnika M2. Število ogllšč mnogokotnika Ml zunaj mnogokotnika M2 označimo z ZM1, število ogllšč Ml znotraj M2 označimo z NM1, število ogllšč, ki ležijo v ogliščih M2 označimo z VM1 in število ogllšč, ki ležijo na robovih M2 označimo z RH1. Če vsa oglišča Ml ležijo v ogliščih M2, oziroma če velja
0M1 = VM1 ; RM1 = 0, ZM1 = 0, NM1 = 0	(11)
ln
0M1 = 0M2	(12)
sta mnogokotnika enaka in se popolnoma prekrivata. V tem primeru leži presečni mnogokotnlk v celoti znotraj luknje ploskve, ne glede na to kateri mnogokotnlk označuje presečni mnogokotnlk ln kateri luknjo ploskve (slika 19). Ploskev telesa ne seka oktanta ln prekinemo s testiranjem.
Slika 19 Mnogokotnika se popolnoma prekrivata
Ce vsa oglišča mnogokotnika Ml ležijo v ogliščih M2 in na robovih M2, oziroma če velja
0M1 = VM1 + RM1 ; ZM1 = 0, NM1 =0	(13)
je mnogokotnlk Ml lahko zunaj ali znotraj mnogokotnika M2. Uporabimo vsebnostni test središčne točke mnogokotnika Ml v mnogokotnlku M2, da ugotovimo, katera trditev je pravilna.
62
i) Presečni mnogokotnik znotraj luknje
b) Presečni mnogokotnik zunaj luknje
Slika 20 Ml presečni mnogokotnik, M2 luknja ploskve
V primeru, ko Ml označuje presečni mnogokotnik ln M2 luknjo ploskve (slika 20), Imamo naslednjo reSltev: Ce presečni mnogokotnik leži znotraj luknje (slika 20a), ploskev ne seka oktanta. Če leži presečni mnogokotnik zunaj luknje ploskve, ploskev seka oktant (slika 20b).
Slika 21 Ml luknja ploskve, M2 presečni mnogokotnik
V primeru, ko Ml označuje luknjo ploskve ln M2 presečni mnogokotnik, Je reSltev naslednja: luknja ploskve lahko leži le znotraj presečnega mnogokotnlka, ker Je oblika presečnega mnogbkotnlka omejena. Zato presečni mnogokotnik leži delno na ploskvi telesa in ta seka oktant (slika 21).
Če vsaj eno ogliSče mnogokotnlka Ml leži znotraj mnogokotnlka M2, oziroma če velja
0M1 = NM1 ♦ RM1 + VM1 ; NM1 * 0, ZM1 = 0
(14)
leži mnogokotnik Ml znotraj mnogokotnlka M2.
Če leži presečni mnogokotnik (Ml) znotraj luknje ploskve (M2), luknja ploskve prekriva presečni mnogokotnik in ploskev ne seka oktanta (slika 22).
Če leži luknja ploskve (Ml) znotraj presečnega mnogokotnlka (M2), leži presečni mnogokotnik delno na ploskvi telesa in ploskev seka oktant (slika 23).
a) RM1 * 0, VM1 * 0
b) RM1 = 0. VM1 = 0
Slika 22 Presečni mnogokotnik (Ml) znotraj luknje ploskve (M2)
Če vsaj eno ogliSče mnogokotnlka Ml leži zunaj mnogokotnlka M2, oziroma če velja
a) RM1 * 0, VM1 * 0
b) RM1 = 0, VM1 = 0
Slika 23 Luknja ploskve (Ml) znotraj presečnega mnogokotnlka (M2)
ln
RM1 * 0 ali VM1 * 0
(16)
leži mnogokotnik Ml zunaj mnogokotnlka M2 ln mnogokotnlka se dotikata. V tem primeru, ne glede na to, kateri mnogokotnik določa luknjo ploskve ln kateri presečni mnogokotnik, ugotovimo, da presečni mnogokotnik leži zunaj luknje ploskve, vendar ga nobena druga luknja ploskve ne more popolnoma prekrivati. Ploskev seka oktant ln prekinemo s testiranjem lukenj (slika 24).
IV w -			
g	■fpj 1		
	fig		
:|U2H		j	Ei
a) Presečni mnogokotnik (Ml) b) Luknja ploskve (Ml) luknja ploskve (M2)	presečni mnogokotnik (M2)
Slika 24 Mnogokotnik Ml zunaj mnogokotnlka M2
Če vsa ogliSča mnogokotnlka Ml ležijo zunaj mnogokotnlka M2 oziroma, če velja
0M1 = 2M1 ; VM1 = 0, RM1 = 0, NM1 = 0
(17)
leži mnogokotnik Ml strogo zunaj mnogokotnlka M2 (slika 25).
Ne glede na to, kateri mnogokotnik označuje presečni mnogokotnik ln kateri luknjo ploskve, leži presečni mnogokotnik strogo zunaj luknje ploskve, kar pomeni, da lahko ostale luknje ploskve vplivajo na rešitev. Če ploskev nima več lukenj oziroma, če smo obdelali vse luknje ploskve, ploskev seka oktant, drugače pa ponovimo test lukenj za naslednjo luknjo ploskve.
a) Presečni mnogokotnik Ml luknja ploskve M2
b) Luknja ploskve Ml presečni mnogokotnik M2
0M1 = ZM1 + RM1 + VM1 ; ZM1 * 0, NM1 = 0
(15)
Slika 25 Mnogokotnik Ml strogo zunaj mnogokotnlka M2
63
4 Zaključek
5 Literatura
Testiranje presečišč med elementi telesa ln osmiškega drevesa je časovno ln prostorsko zelo zahtevno. Ta zahtevnost Je odvisna predvsem od oblike telesa oziroma od števila vozlišč v osmlškem drevesu in od morebitne konkavnosti in luknjavostl telesa. Naše nadaljnje raziskovalno delo bo temeljilo na Izboljšanju, oziroma optimiranju algoritma, kot tudi na realizaciji algoritma za pretvorbo iz predstavitve z osmišklm drevesom v predstavitev z ovojnico.
Program Je napisan v pascalu in vključen v Eksperimentalni geometrijski modellrnik teles (EGM) [ŽALI89bl. Razvili smo ga na računalniku VAX-8800, za vizualizacljo pa smo uporabili grafični terminal TEK 4207. Rezultati programa so predstavljeni na slikah 26 in 27, kjer smo telesa prikazali z žičnim modelom. Za prikaz telesa ln osmiškega drevesa z odstranjenimi zakritimi robovi smo uporabili razširjen Robertsov algoritem za odstranjevanje zakritih robov ln ploskev ((Š0B088), [Š0B089)).
[CHIY85] Chlyokura, H., F. Klmura, "A Method of Representing the Solid Design Process", IEEE CG&A, Vol. 5. No. 4, 1985, pp. 32 - 41.
ICHIY87] Chlyokura, H. , "An Extended Rounding Operation for Modeling Solids with Free-Form Surfaces", IEEE CG&A, Vol. 7, No. 12, 1987, pp. 27 - 36.
[CLIF87] Clifford, A. S. and H. Samet, "Optimal Quadtree Construction Algorithms", Computer Vision, Graphics, and Image Processing, Vol. 37, No. 3, March 1987, pp. 402 - 419.
[GUID88] Guld, N., ."Računalniška grafika" Tehniška fakulteta Maribor, Maribor 1988.
[HILL82] Hillyard, R., "The Build Group of Solid Modelers", IEEE CG&A, Vol. 2. No. 2, 1982, pp. 43 - 52.
[H0ME88] Homer, H. C. and T. S. Huang, "A Survey of Construction and Manipulation of Octree", Computer Vision, Graphics, and Image Processing, Vol.43, No.3, September 1988, pp. 409 - 431.
Sllka 27 Primer konkavnega telesa
[KAUF88] Kaufman, A. and R. Bakalash, "Memory and Processing Architecture for 3D Voxel - Based Imagery", IEEE CG&A, Vol. 8. No. 6. 1988, pp. 10 - 23.
1MANT82] MantylS, M. and R. Sulonen, "GUB: A Solid Modeler with Euler Operators". IEEE CG&A Vol. 2. No. 7, 1982, pp. 17 - 31.
f^l
[MANT83] Mantyla, M. , "SET operations	of GWB",
Graphics Forum, No. 2-3, 1983,	pp. 122 -134.
(MANT88) Mantyl8, M. , "An Introduction	to Solid
Modeling", Computer Science Press,	Rockvllle, MD (1988).
Slika 26 Primer telesa z luknjo
IMILL89] Miller, R. J.. "Architectural Issues ln Solid Modelers". IEEE CG&A, Vol. 9, No. 5, 1989, pp. 72 - 87.
[M0RT85] Mortenson, M. E. , "Geometric Modeling", John Wiley & Sons, New York, 1985.
64
(PRAT83)
IREQU82]
[REQU83]
(S0B088)
[S0B089]
Pratt. M. J.. "Interactive geometric modelling for CAD/CAM", Eurographics '83 Tuturlals, Zagreb, 1983.
Requlcha, A. A. C., "Solid Modeling: A Historical Summary and Contemporary Assessment", IEEE CG&A, Vol. 2, No. 2, 1982, pp. 9 - 24.
Requlcha, A. A. G, and H. B. VSlcker, "Solid Modeling: Current Status and Research Directions", IEEE CG&A, Vol. 3, No. 5, 1983, pp. 25 - 37.
Sobot, P.. B. Žallk. N. Guld, "Extended Robert's hidden line / hidden surface algorithm for computer graphics", X. International Symposium Computer at the University, Cavtat 1988, pp. 7.5/1-4.
Sobot. P., B. Žallk, N. Guld, "Analiza In uporaba razširjenega Robertsovega algoritma, ki rešuje problem zakritih robov pri mnogokotnlšklh pravilnih telesih", XIII. Slmpozljum o lnformaclonlm tehnologijama, Sarajevo 1989, pp. 227/1-10.
(WEIL85] Weller, K., "Edge-Based Data Structures for Solid Modeling in Curved-Surface Envlronmenst", IEEE CG&A, Vol. 5, No. 1, 1985, pp. 21 - 40.
[UIL.S85] Wilson, P. R., "Euler Formulas and Geometric . Modeling". IEEE CG&A, Vol. 5, No. 8, August 1985, pp. 24 - 36.
[ŽALI89a) Žallk, B., N. Guld, and P. Sobot, "Experimental geometric modeler based on boundary representation", XI. International Symposium Computer at the University, Cavtat 1989, pp. 7.6/1-6.
IŽALI89.bl Žallk, B., "Geometrijski modellrnlk z Eulerjevlml operatorji", Magistrsko delo. Tehniška fakulteta, VTO ERI, Maribor, 1990.
IŽAL1901 Žallk, B.,	N. Guld. "Vgradnja EulerJevlh
operatorjev	in njihova uporaba pri tvorbi teles s translaclJsklra pomikanjem",
Informática,	LJubljana, Vol. 14, No. 2, 1990, pp. 32 - 38.
**********************
Knjiga Antona P. Železnikarja
On the Way to Information
(Na poti k informaciji)
(recenziji na strani 79 in 80) odpira izvirne poglede in možnosti razvoja •
teorije informacije, umetne inteligence in nove poglede na področje informacije.
Profesor Branko Souček
in
doc. dr. ValterMotaln
podajata svoja stališča in ocene o knigi.
Knjigo lahko naročite pri Slovenskem društvu Informatika,
po telefonu (061) 214 455ali na naslov Tržaška c. 2, Ljubljana,
s plačilom din 270. **********************