thumb|Građenje i skladištenje 2d implicitnog max k-d stabla korišćenjem spliting-funkcije medijana mreže. Svaka ćelija mreže ima dodeljenu jednu skalarnu vrednost od niske (jarko plava) do visoke (jarko crvena). Memorijski otisak mreže je prikazan u donjoj liniji. Predefinisanom memorijskom otisku implicitnog max k-d stabla je potrebna jedna skalarna vrednost manje od toga. Skladištenje maksimalnih vrednosti čvora je prikazano u gornjoj liniji.|400px|right Implicitno k-d stablo je k-d stablo definisano implicitno nad uniformnom (pravolinijskom) mrežom. Pozicije i orijentacije njegovih ravni podele nisu date eksplicitno već implicitno nekom rekurzivnom splitting-funkcijom definisane na hiperpravougaonicima koji pripadaju čvorovima stabla. Svaki unutrašnji čvor ravni podele je postavljen na mrežnu ravan ravni koja leži ispod, deleći mrežu čvora u dve podmreže.

Nomenklatura i reference

Izrazi "min/max k-d stablo" i "implicitno k-d stablo" se nekad pomešaju. Ovo je zato što je prva publikacija koja je iskoristila izraz min/max k-d stabloIngo 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) u stvari koristila eksplicitna k-d stabla a navodila ih kao implicitna da naznači da mogu biti korišćena za ray tracing implicitno datih izo-površi. Ipak, ova publikacija je takođe koristila slim k-d stabla koja su podskup implicitnih k-d stabala sa ograničenjem da mogu biti sagrađeni samo preko celobrojnog hiperpravougaonika sa dužinama stranica koje su stepen broja 2. Implicitna k-d stabla definisana na ovaj način su nedavno predstavljena, sa primenama u kompjuterskoj graficiMatthias Groß, Carsten Lojewski, Martin Bertram and Hans Hagen "Fast Implicit k-d Trees: Accelerated Isosurface Ray Tracing and Maximum Intensity Projection for Large Scalar Fields" CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74Matthias Groß (PhD, 2009) Towards Scientific Applications for Interactive Ray Casting. Pošto je moguće dodeliti atribute čvorovima implicitnog k-d stabla, za implicitna k-d stabla koja imaju min/max vrednosti dodeljene svojim čvorovima možemo reći da su "implicitna min/max k-d stabla".

Građenje

Implicitna k-d stabla u opštem slučaju nisu konstruisana eksplicitno. Kada pristupamo čvoru, orijentacija i položaj njegove ravni podele se izračunavaju specifičnom splitting-funkcijom koja definiše stablo. Različite splitting-funkcije mogu dati različita stabla za istu mrežu koja leži ispod.

Splitting-funkcije

Splitting-funkcije se mogu prilagoditi posebnim svrhama. Ovo su dve specifikacije posebnih klasa splitting-funkcija: Ne-degenerisana splitting-funkcija ne dozvoljava stvaranje degenerisanih čvorova (čvorova kojima je zapremina odgovarajućeg celobrojnog hiperpravougaonika jednaka nuli). Njihova odgovarajuća implicitna k-d stabla su binarna stabla, koja za n listova imaju n - 1 unutrašnjih čvorova. Njihova odgovarajuća k-d stabla su ne-degenerisana implicitna k-d stabla. potpune splitting-funkcije su ne-degenerisane splitting-funkcije takve da njihova odgovarajuća k-d stabla imaju listove koji su pojedinačne ćelije mreže takve da imaju jedan unutrašnji čvor manje od broja ćelija datih u mreži. Njihova odgovarajuća implicitna k-d stabla su potpuna implicitna k-d stabla.

Primer potpune splitting-funkcije je medijana mreže. Ona stvara prilično balansirano implicitno k-d stablo koristeći celobrojne hiperpravougaonike hyprec[k] sa k dimenzija za svaki čvor implicitnog k-d stabla. Hiperpravougaonici definišu koje ćelije uniformne mreže pripadaju njihovom odgovarajućem čvoru. Ako je zapremina ovog hiperpravougaonika jednaka jedan, odgovarajući čvor je jedna ćelija mreže i zato se ne deli dalje i obeležava se kao list. U suprotnom, najduža strana hiperpravougaonika se bira kao orijentacija o. Odgovarajuća ravan podele p je postavljena na mrežnu ravan koja je najbliža medijani mreže hiperpravougaonika u toj orijentaciji.

Orijentacija o ravni podele: o = min{argmax(i = 1 ... k: (hyprec[i] - hyprec[i]))} Položaj p ravni podele: p = roundDown((hyprec[o] + hyprec[o]) / 2)

Dodeljivanje atributa čvorovima implicitnog k-d stabla

Očigledna prednost implicitnih k-d stabala je to što orijentacija i položaj njihovih ravni podele ne mora biti sačuvana eksplicitno. Neke aplikacije pored orijentacije i položaja ravni podele zahtevaju i atribute unutrašnjih čvorova. Ovi atributi mogu na primer biti pojedinačni bitovi ili pojedinačne skalarne vrednosti, definišući da li su podmreže koje pripadaju čvorovima predmet interesovanja ili ne. Za potpuna implicitna k-d stabla moguće je pre-alocirati niz atributa tačne veličine i dodeliti svakom unutrašnjem čvoru jedinstven element u tom alociranom nizu.

Količina ćelija u mreži je jednaka zapremini celobrojnog hiperpravougaonika koji pripada mreži. Kako potpuno implicitno k-d stablo ima za jedan manje unutrašnjih čvorova nego ćelija mreže, unapred se zna koliko atributa treba da se sačuva. Relacija "Zapremina celobrojnog hiperpravougaonika u odnosu na unutrašnje čvorove" definiše sa potpunom splitting-funkcijom rekurzivnu formulu dodeljujući svakoj ravni podele jedinstven element u alociranom nizu. Odgovarajuć algoritam je dat u C-pseudo kodu ispod.

// Dodela atributa unutrašnjim čvorovima potpunog implicitnog k-d stabla

// napravi celobrojni hiperpravougaonik hyprec // (njegova zapremina vol(hyprec) je jednaka broju listova int hyprec[k] = { { 0, ..., 0 }, { length_1, ..., length_k } }; // alociraj niz atributa za celo implicitno k-d stablo attr *a = new attr[volume(hyprec) - 1];

attr implicitKdTreeAttributes(int hyprec[k], attr *a) { if(vol(hyprec) > 1) // trenutni čvor je unutrašnji čvor { // proceni orijentaciju o i poziciju p ravni podele koristeći potpunu splitting-funkciju int o, p; completeSplittingFunction(hyprec, &o, &p); // proceni celobrojne hiperpravougaonike dece hyprec_l i hyprec_r int hyprec_l[k], hyprec_r[k]; hyprec_l = hyprec; hyprec_l[o] = p; hyprec_r = hyprec; hyprec_r[o] = p; // proceni memorijsku lokaciju dece a_l i a_r attr* a_l = a + 1; attr* a_r = a + vol(hyprec_l); // odredi rekurzivno atribute dece c_l i c_r attr c_l = implicitKdTreeAttributes(hyprec_l, a_l); attr c_r = implicitKdTreeAttributes(hyprec_r, a_r); // spoj atribute dece u trenutni atribut c attr c = merge(c_l, c_r); // sačuvaj trenutni atribut i vrati ga a = c; return c; } // Trenutni čvor je list. Vrati atribut koji pripada odgovarajućoj ćeliji mreže return attribute(hyprec); }

Vredi dodati da ovaj algoritam radi za sve uniformne (pravolinijske) mreže. Odgovarajući celobrojni hiperpravougaonik ne mora obavezno imati dužine stranica koje su stepen broja dva.

Primena

Implicitna max-k-d stabla se koriste za "metod bacanja zraka" izo-površina/MIP (projekcija maksimalnog intenziteta). Atribut dodeljen svakom unutrašnjem čvoru je maksimalna skalarna vrednost data u podmreži koja pripada čvoru. Kroz čvorove se ne putuje ako je njihova skalarna vrednost manja od tražene iso-vrednosti/trenutnog maksimalnog intenziteta duž zraka. Skladištenje kod implicitnog max k-d stabla nije zahtevno i povoljna složenost vizualizacija kod "bacanja zraka" dozvoljavaju da se "bacanje zraka" koristi za veoma velika skalarna polja pri interaktivnoj brzini smenjivanja slika na računarima. Slično, implicitno min/max k-d stablo može da se koristi da se efikasno ocene upiti kao što je terenska linija pogleda.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.

Složenost

Za dato implicitno k-d stablo razapeto preko mreže sa k dimenzija i n ćelija mreže. Dodela atributa čvorovima stabla oduzima vremena. Skladištenje atributa u čvorove oduzima memorije "Bacanje zraka" izo-površina/MIP skalarnog polja koje je ispod koristeći odgovarajuće implicitno max k''-d stablo oduzima, grubo procenjeno, vremena.

Vidi još K-D stablo Min/max KD stablo

Reference

Категорија:Стабла (структуре података)