Implicitno k-d stablo

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.

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 stablo 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 grafici. 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[2][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[1][i] - hyprec[0][i]))}

Položaj p ravni podele:

p = roundDown((hyprec[0][o] + hyprec[1][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[2][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[2][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[2][k], hyprec_r[2][k];
   hyprec_l       = hyprec;
   hyprec_l[1][o] = p;
   hyprec_r       = hyprec;
   hyprec_r[0][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[0] = 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.

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$\mathrm {O} (kn)$ vremena.
• Skladištenje atributa u čvorove oduzima $\mathrm {O} (n)$ memorije
• "Bacanje zraka" izo-površina/MIP skalarnog polja koje je ispod koristeći odgovarajuće implicitno max k-d stablo oduzima, grubo procenjeno, $\mathrm {O} (\log(n))$vremena.

Vidi još

• K-D stablo
• Min/max KD stablo