Min/max KD stablo
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Min/max kd-stablo je K-D stablo sa dve skalarne vrednosti - minimalne i maksimalne - dodeljene svojim čvorovima. Minimum/maksimum unutrašnjeg čvora je jednak minimumu/maksimumu svoje dece.
Konstrukcija[uredi | uredi izvor]
Min/max kd- stabla se mogu konstruisati rekurzivno. Počevši od korena čvora, orijentacija cepanje aviona i položaj se procenjuju. Onda se cepači aviona kod dece i min/max vrenost rekurzivno procenjuju. Minimalna/maksimalna vrednost tekućeg čvora je jednostavno minimum/maksimum od minimuma/maksimuma svoje dece.
Osobine[uredi | uredi izvor]
Min/max kd stablo ima osim osobina kd stabla, posebnu osobinu, da se svaki unutrašnji čvor koji ima min/max vrednost poklapa sa min/max vrednošću od bar jednog deteta. Ovo omogućava odbacivanje skladištenja min/max vrednosti kod lisnih čvorova čuvajući dva bita u unutrašnjim čvorovima, dodeljujući min/max vrednost deci: Svaki unutrašnji čvor min/max vrednosti će biti poznat unapred, gde se čvorovi min/max vrednosti čuvaju odvojeno. Svaki unutrašnji čvor ima osim dve min/max vrednosti takođe dva data bita, definišući svako dete čije su min/max vrednosti dodeljene (0: levom detetu, 1: desnom detetu). Nedodeljene min/max vrednosti dece su iz tekućeg čvora već poznate min/max vrednosti. Dva bita se takođe mogu čuvati u najmanje značajnim bitovima min/max vrednosti, koji dakle mogu biti aproksimirani frakcionišući ih dole/gore.
Rezultujuća memorija nije manja, kao što su lisni čvorovi potpunih binarnih kd-stabala polovina od čvorova u stablu.
Aplikacije[uredi | uredi izvor]
Min/max kd-stabla se koriste za "metod bacanja zraka" izo-površine,Ray Casting isosurface/MIP (projekcija maksimalnog intenziteta). Izo-površina ray casting-a zaobilazi samo čvorove za koje izabrana izo-linija leži između min/max vrednosti tekućeg čvora. Čvorovi koji ne zadovoljavaju ovaj uslov, ne sadrže izo-površinu sa datim izo-linijama i stoga se preskaču (preskakanje praznog prostora). Za MIP, čvorovi se ne zaobilaze ako je njihov maksimum manji od trenutnog maksimalnog intenziteta duž zraka. Povoljna vizuelizacija ray casting-a omogućava "bacanje zraka" (čak i promenu izo-površine) za vrlo velika skalarna polja na interaktivnim brzinama smenjivanja slika na računarima. Posebno implicitna maksimalna kd-stabla su optimalni izbor za vizuelizaciju skalarnih polja definisanih na pravolinijskim mrežama (vidi [1][2][3]). Slično implicitno min/max kd-stablo se može koristiti za efikasnu procenu poput terena linije vida.[4]
Vidi još[uredi | uredi izvor]
- K-D stablo
- Implicitno K-D stablo
Reference[uredi | uredi izvor]
- ^ Matthias Groß, Carsten Lojewski, Martin Bertram and Hans Hagen "Fast Implicit KD-Trees: Accelerated Isosurface Ray Tracing and Maximum Intensity Projection for Large Scalar Fields" CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74
- ^ Ingo Wald, Heiko Friedrich, Gerd Marmitt, Philipp Slusallek and Hans-Peter Seidel "Faster Isosurface Ray Tracing using Implicit KD-Trees" IEEE Transactions on Visualization and Computer Graphics (2005)
- ^ Matthias Groß (PhD, 2009) Towards Scientific Applications for Interactive Ray Casting
- ^ Bernardt Duvenhage "Using An Implicit Min/Max KD-Tree for Doing Efficient Terrain Line of Sight Calculations" in "Proceedings of the 6th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa", 2009.