KONSTRUKTIVNA GEOMETRIJA
SA SLOBODNO OBLIKOVANIM OBJEKTIMA

Oktalna stabla koja su konstruirana za svako tijelo iskoristit će se za brzi algoritam testiranja položaja elemenata površine tijela A u odnosu na tijelo B jer je potrebno odrediti koji dio površine prvog tijela je unutar (ili izvan) drugog tijela i obratno. Testiranje oktalnih stabala se vrši hijerarhijski. Prvo se provjerava preklapa li se testirana ćelija s korijenom drugog stabla.Provjera presjeka dvije kocke (dvije ćelije oktalnog stabla) se obično vrši po teoremu razdvajajuće osi.Gledajući preklapanje obujmice ćelije s oktalnim stablom drugog tijela moguće je razlikovati četiri slučaja:

• obujmica se ne preklapa s oktalnim stablom drugog tijela,

• obujmica se preklapa samo s vanjskim ćelijama oktalnog stabla drugog tijela,

• obujmica se preklapa samo s unutarnjim ćelijama oktalnog stabla drugog tijela,

• obujmica se preklapa sa najmanje jednom graničnom ćelijom oktalnog stabla drugog tijela.

U prvom slučaju, nema uopće preklapanja gledanog prostora s drugim tijelom pa se svi elementi površine u dotičnoj ćeliji mogu klasificirati kao vanjski. U drugom slučaju se elementi površine, također, klasificiraju kao vanjski jer se ćelija preklapa samo s vanjskim ćelijama oktalnog stabla te su svi elementi površine testirane ćelije izvan tijela koje se promatra. U trećem slučaju isto nema presjeka s površinom drugog tijela, ali su sad svi elementi površine smješteni u unutarnje ćelije drugog stabla pa ih se klasificira kao unutrašnje. I konačno, četvrti slučaj, koji je najkompliciraniji jer postoji mogućnost presjeka tijela A i tijela B. Zbog takve mogućnosti elementi površine se ne mogu odmah klasificirati. Potrebno je rekurzivno testirati svaki neprazni čvor-dijete počevši od korijena pa sve do listova stabla.

Za svaki čvor-dijete ponavlja se testiranje od korijena drugog tijela sve dok obujmica testirane ćelije siječe barem jednu od graničnih ćelija drugog tijela. Kada se ovim postupkom dođe do lista stabla pristupa se testiranju svakog elementa površine pojedinačno u odnosu na drugo tijelo. Jasno je da će se element površine klasificirati kao vanjski (unutarnji) ako upadne u vanjsku (unutarnju) ćeliju, međutim ako upadne u graničnu ćeliju potrebno ga je testirati s obzirom na njemu najbliži element površine.

 Klasifikacija elementa površine S u graničnoj ćeliji pomoću njemu najbližeg susjeda T i njegove normale n_t.

Provjerom predznaka sklarnog umnoška normale najbližeg susjeda t i vektora spojnice elementa površine s i t dolazi se do informacije o smještaju elementa površine s u odnosu na drugo tijelo: ako je n_t ∙ (x_t – x_s) > 0,  s se klasificira kao unutarnji element površine, a inače kao vanjski.

Pošto elementi površine nisu samo točke postoji mogućnost da se oni i sijeku. U tom slučaju trebalo bi im smanjiti radijuse da rubovi novonastalog tijela ne bi imali probode.