Min/max KD stablo

Из Википедије, слободне енциклопедије
Jump to navigation Jump to search
Trodimenzionalno K-D 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[уреди]

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[уреди]

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[уреди]

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š[уреди]

Reference[уреди]

  1. ^ 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
  2. ^ 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)
  3. ^ Matthias Groß (PhD, 2009) Towards Scientific Applications for Interactive Ray Casting
  4. ^ 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.