KONSTRUKTIVNA GEOMETRIJA
SA SLOBODNO OBLIKOVANIM OBJEKTIMA

Ako su elementi površine dovoljno blizu jedan drugoga, tako da su njihovi mali radijusi dostatni da postoji presjek dva diska, klasificiramo takve elemente površine kao presjecajuće.Postupak ponovnog uzorkovanja obavlja se za svaki element površine s klasificiran kao presjecajući. Tijekom testiranja elementa površine s (inside-outside test) na pripadnost tijelu, osim odluke o samoj pripadnosti unutra-vani računa se i najbliži susjed, element površine t. Presjek elementa površine s i površine drugog tijela aproksimira se presjekom elementa s i ravnine kojoj pripada element t (najbliži susjed). Taj presjek je tetiva kružnice sa centrom u x_s i radijusa r_s  (kružnice kojom je predstavljen element površine s). Ravnina kroz element površine t razdvaja tom tetivom element površine s u dva dijela. Zavisno od operacije koja se obavlja na tijelima potrebno je zadržati unutarnji ili vanjski dio. Pošto novi element površine nije pravilnog oblika tj. nije istog oblika kakvog su svi ostali elementi površine, pristupa se aproksimaciji nove površine sa jednim ili više novih elemenata površine. 

 Da bi pokrili površinu starog elementa površine sve do presjeka s tijelom, konstruira se malo manji element površine s'. Taj element površine treba biti toliko velik da mu kružnica na suprotnoj strani od presjeka dira kružnicu starog elementa površine, a s druge strane da prelazi ravninu presjeka za neki mali iznos (može ga odrediti korisnik). Taj iznos naziva se overshoot error i potrebno ga je imati kako bi novokonstruirani krug pokrio što veći dio tetive koja označava presjek. Ako je h udaljenost centra elementa površine x_s do tetive presjeka, onda novi radijus r_s' treba biti (r_s + h + e) / 2. Kako bi se u potpunosti pokrila tetiva presjeka, dodaju se još sa svake strane po dva manja elementa površine radijusa r_s / 3.

Modificirana metoda

Pri aproksimaciji elemenata površine trokutnom mrežom, odstupanja idelanog oblika elementa površine (oblik kruga) od onog dobivenog uzorkovanjem trokuta i prikazom trokutima mogu biti znatna. Zbog toga je potrebno modificirati predstavljenu metodu ponovnog uzorkovanja elemenata površine te je prilagoditi prikazu trokutnom mrežom.

 Obrada elementa površine predstavljenog trokutom počinje kada se ustanovi da mu je najbliži susjed, pomoću kojeg ga se klasificira, dovoljno blizu da bi mogao postojati presjek. Sljedeći korak je pojedinačna provjera položaja za svaki od tri vrha trokuta elementa površine s u odnosu na ravninu u kojoj leži element površine t. Provjera se obavlja uvrštavanjem koordinata vrha kojeg provjeravamo u jednadžbu ravnine elementa površine t.

Mogući su sljedeći položaji vrhova u odnosu na ravninu:

• svi vrhovi su s pozitivne strane ravnine P ili na samoj ravnini,

• svi vrhovi su s negativne strane ravnine P ili na samoj ravnini,

• jedan od vrhova je s pozitivne strane ravnine, a drugi od vrhova su s negativne strane ravnine,

• dva vrha su s pozitivne strane ravnine, a jedan od vrhova je s negativne strane ravnine,

• jedan od vrhova leži u ravnini, a druga dva su svaki s jedne strane ravnine

Ako su svi vrhovi s pozitivne strane ravnine P ili na samoj ravnini znači da nema presjeka elemenata površine, te se element površine klasificira kao vanjski i ne obavlja se ponovno uzorkovanje. Isto vrijedi i za slučaj kada su svi vrhovi s negativne strane ravnine, osim što se sada element površine s klasificira kao unutrašnji. Za slučaj kada imamo jedan vrh sa pozitivne strane ravnine, a dva sa negative strane dolazi do potrebe za lomljenjem elementa površine i stvaranjem tri nova. Na slici se vidi postupak tvorbe novih elemenata površine: pronalaze se sjecišta bridova koji spajaju vrh s jedne strane ravnine sa preostala dva vrha i dobivaju dvije nove točke D i E. Tvori se novi element površine kojeg predstavlja trokut ADE, sa središtem u točci y₁ i normalom istom kao i u početnom trokutu, te se klasificira kao vanjski. Osim ovog trokuta, tvore se još dva trokuta BED i BCE, sa središtima u y₂ i y₃, ali se oni klasificiraju kao unutarnji.

Analogan postupak je u slučaju da su dva vrha s pozitivne strane, a jedan s negativne osim što se sada prvi trokut klasificira kao unutarnji, a preostala dva kao vanjski.  Kada jedan od vrhova pada u ravninu P, tvore se samo dva trokuta jer samo jedan brid siječe ravninu P. Na tom sjecištu formira se nova točka D, te dva trokuta: vanjski – ADB i unutarnji – CBD.

 Pronalaženje presjeka ravnine i brida obavlja se pomoću parametarske jednadžbe brida. Naime, brid se parametarski prikaže kao x =V₁ + t (V₂-V₁), gdje su V₁ i V₂ vektori početne i krajnje točke brida, a t parametar s vrijednošću između 0 i 1. Pošto točka koja je sjecište pravca i ravnine zadovoljava obje jednadžbe (jednadžba ravnine je n_s [x – x_s]=0 ), može se uvrstiti prva jednadžba u drugu, te se iz toga sada može izraziti parametar t brida kao t = n_s (x_s − V₁) / n_s (V₂ − V₁), te dobiti točku presjeka.

 Pri tvorbi novih trokuta potrebno je obratiti pažnju da se održi smjer redoslijeda vrhova onakvim kakav je bio u prvotnom trokutu ( u smjeru kazaljke na satu ili suprotno) kako ne bi stvorili objekt s različito orijentiranim elementima površine. Takav objekt se ne bi pravilno iscrtavao, a pri njegovoj ponovnoj upotrebi bi, u većini slučajeva, došlo do problema s klasifikacijom ćelija oktalnog stabla kao i problema pri unutra-vani testiranju. Jedan od načina kako da se provjeri poredak vrhova, u ovom slučaju, je da se izračuna normala novog trokuta vektorskim produktom dva njegova brida (V₁V₂ x V₁V₃) te se dobiveni vektor usporedi po smjeru sa vektorom normale polaznog trokuta (usporedba po smjeru se vrši sklarnim produktom ova dva vektora). Ukoliko su vektori istog predznaka (smjera) jasno je da je sačuvan poredak vrhova, te nije potrebno ništa mijenjati, ali ako su vektori suprotno orijentirani potrebno je zamijeniti dva vrha trokuta čime se ispravlja njihov poredak.

Modificirana metoda, dakle, omogućava znatno poboljšanje kvalitete izlaznog objekta u području novonastalih rubova (na mjestu presjeka površina polaznih tijela), kao što se može vidjeti na slici,  eliminiranjem nazubljenih ili dvostrukih rubova koji nastaju kada se ne pazi na presjeke pojedinih elemenata površine. Osim vizualnog poboljšanja, ponovnim uzorkovanjem popravlja se strukturni integritet novog objekta jer nazubljeni rubovi pogoduju krivoj klasifikaciji pri ponovnoj upotrebi objekta za daljnje operacije. Nedostatak ponovnog uzorkovanja rubova je potrošnja određenog vremena, te zbog toga treba koristiti što je moguće jednostavnije i brže postupke. Ovaj nedostatak ipak nije previše izražen jer je broj elemenata površine koji se presjecaju relativno malen u odnosu na ukupan broj elemenata površine.  

 Razlika kocke i kugle srednje rezolucije prikazana sa ponovnim uzorkovanjem rubova (lijevo) i bez ponovnog uzorkovanja (desno).