|
U mladoj računalnoj znanosti i njenoj grani, računalnoj
grafici, te srodnim područjima već godinama se koristi konstruktivna
geometrija čvrstih tijela (engl. Constructive Solid Geometry
– CSG) kao vrlo korisna alatka. U računalom potpomognutom dizajnu (CAD)
se konstruktivna geometrija primjenjuje na osnovne oblike tj. primitive
kao što su kugle, cilindri i kocke da bi se od njih spajanjem, presjecima
i oduzimanjem (Booleovim operacijama) izgradili kompleksniji geometrijski
oblici. Pokazalo se da je konstruktivna geometrija korisna i kad se žele
upotrijebiti kompleksniji objekti proizvoljne - slobodne forme (engl.
free-form solids). Nezamislivo je da bilo koji programski alat namijenjen
modeliranju trodimenzionalnih objekata ne podržava mogućnosti obavljanja
ovakvih Booleovih operacija na tijelima, pa se kao primjeri poznatiji
širem krugu korisnika mogu nabrojiti 3DStudioMAX, Catia ili
Maya, kao primjeri najpoznatijih profesionalnih alata sa
implementiranim moćnim algoritmima i širokim spektrom mogućnosti
manipulacije objekata.
Međutim postoji problem s objektima konstruktivne
geometrije što nije trivijalno predstaviti prostor koji ti objekti
zauzimaju, niti njihovu površinu koja je u pravilu vrlo nepravilna i
složena, a samim time niti izračunati rezultate Booleovih operacija između
takvih objekata. Konstruktivna geometrija često pri iscrtavanju koristi
blagodati posebnog grafičkog sklopovlja da bi se postigao dovoljno veliki
broj slika (okvira) u sekundi (engl. Frame Per Second
– FPS) [AD04], ali postoje i drugi pristupi prikazu tijela
koji pribjegavaju pretvorbi CSG struktura u površine zadane mrežom
poligona koju može prikazati svaki današnji grafički sklop. Uobičajeni
postupci prikaza tijela su prikazi mrežom poligona, parametarskim plohama,
brišućim plohama, volumnim reprezentacijama (engl. voxel), a s porastom
snage širokodostupnih grafičkih procesora i općenito grafičkog sklopovlja
došlo je u zadnje vrijeme do jakog razvoja nekih alternativnih pristupa,
kao što je prikaz tijela sufrelima.
Riječ surfel je engleski pojam koji označava
elementarni dio površine, a nastao je kao spoj riječi surface što
znači površina i riječi element, te ga dostojno možemo zamijeniti, u
hrvatskim prijevodu, pojmom element površine. Surfeli su dijelovi
površine tijela čiji prikaz je zamišljen kao točka u trodimenzionalnom
prostoru koja aproksimira dio površine i njenu orijentaciju u prostoru.
Pošto se tijelo ne predstavlja nekim načinom koji bi dao informaciju o
njegovom volumenu (kao npr. volumnim elementima), potrebno je, s obzirom
na elemente površine i njihovu orijentaciju, razlikovati unutarnji i
vanjski dio tijela. Kada postoji klasifikacija na unutrašnje i vanjsko za
neka dva objekta moguće je na njih primijeniti Booleove operatore (unija,
presjek, razlika). Lako je zaključiti da se veliki dijelovi površine dvaju
tijela ne sijeku već postoji relativno mali broj presjecajućih elemenata
površine na onim mjestima gdje jedno tijelo prodire u drugo. Ova činjenica
se koristi da bi se efikasno klasificirali elementi površine svakog tijela
i to u tri skupine: vanjski, unutarnji i presjecajući s obzirom na drugo
tijelo.
Još prije ne tako puno godina nije bilo neobično da se
modeliranje 3D scena obavlja bez vizualnog sučelja u nekom tekstualnom
modu, ali velik razvoj računalne industrije učinio je standardom da
moderna računalna aplikacija ima vizualno sučelje blisko korisniku (engl.
user friendly) i ne samo to već da pruža mogućnost interaktivnog rada.
Kada se govori o interaktivnosti postoje razna mišljenja o graničnom broju
iscrtanih okvira u sekundi koji je potreban da bi se nešto smatralo
interaktivnim. U posljednje vrijeme vrijednost koja se nekako najčešće
spominje je minimalno nekih 10-tak FPS-a.
Pri prikazu tijela elementima površine postoje dva
problema u pokušaju da se postigne interaktivnost. Prvi je kako što brže
odrediti za neki element površine prvog tijela leži li unutar ili izvan
drugog tijela, a drugi je kako u kratkom vremenu obraditi bridove
novonastalog tijela tako da budu pravilni i oštri. Ove probleme riješili
su Bart Adams i Philip Dutre s Katholike Universiteit Leuven
osmislivši algoritam brzog sortiranja potpomognut oktalnim stablima (engl.
Octree) za grupiranje veće količine srodnih elemenata površine (kad se
kaže srodnih misli se na one koji po svojim karakteristikama imaju slične
vrijednosti tj. zadovoljavaju neki zadani kriterij – najčešće položaj ili
orijentacija) i operacijom preračunavanja starih elemenata površine na
granicama presjeka tijela u nove elemente površine koji bolje opisuju
novonastalu površinu odnosno njen rub.
Ovaj rad je nadahnut radom
Adamsa i Dutrea, te će dati pregled korištenih algoritama i postupaka u
njihovom radu i usporediti ih sa drugim srodnim postupcima koji se koriste
u sadašnjoj računalnoj grafici.
|