Implicitno k-d stablo

Имплицитно к-д стабло је к-д стабло дефинисано имплицитно над униформном (праволинијском) мрежом. Позиције и оријентације његових равни поделе нису дате експлицитно већ имплицитно неком рекурзивном сплиттинг-функцијом дефинисане на хиперправоугаоницима који припадају чворовима стабла. Сваки унутрашњи чвор равни поделе је постављен на мрежну раван равни која лежи испод, делећи мрежу чвора у две подмреже.

Грађење и складиштење 2д имплицитног маx к-д стабла коришћењем сплитинг-функције медијана мреже. Свака ћелија мреже има додељену једну скаларну вредност од ниске (јарко плава) до високе (јарко црвена). Меморијски отисак мреже је приказан у доњој линији. Предефинисаном меморијском отиску имплицитног маx к-д стабла је потребна једна скаларна вредност мање од тога. Складиштење максималних вредности чвора је приказано у горњој линији.

Номенклатура и референце

Изрази "мин/маx к-д стабло" и "имплицитно к-д стабло" се некад помешају. Ово је зато што је прва публикација која је искористила израз мин/маx к-д стабло^[1] у ствари користила експлицитна к-д стабла а наводила их као имплицитна да назначи да могу бити коришћена за раy трацинг имплицитно датих изо-површи. Ипак, ова публикација је такође користила слим к-д стабла која су подскуп имплицитних к-д стабала са ограничењем да могу бити саграђени само преко целобројног хиперправоугаоника са дужинама страница које су степен броја 2. Имплицитна к-д стабла дефинисана на овај начин су недавно представљена, са применама у компјутерској графици^[2]^[3]. Пошто је могуће доделити атрибуте чворовима имплицитног к-д стабла, за имплицитна к-д стабла која имају мин/маx вредности додељене својим чворовима можемо рећи да су "имплицитна мин/маx к-д стабла".

Грађење

Имплицитна к-д стабла у општем случају нису конструисана експлицитно. Када приступамо чвору, оријентација и положај његове равни поделе се израчунавају специфичном сплиттинг-функцијом која дефинише стабло. Различите сплиттинг-функције могу дати различита стабла за исту мрежу која лежи испод.

Сплиттинг-функције

Сплиттинг-функције се могу прилагодити посебним сврхама. Ово су две спецификације посебних класа сплиттинг-функција:

Не-дегенерисана сплиттинг-функција не дозвољава стварање дегенерисаних чворова (чворова којима је запремина одговарајућег целобројног хиперправоугаоника једнака нули). Њихова одговарајућа имплицитна к-д стабла су бинарна стабла, која за н листова имају н - 1 унутрашњих чворова. Њихова одговарајућа к-д стабла су не-дегенерисана имплицитна к-д стабла.
потпуне сплиттинг-функције су не-дегенерисане сплиттинг-функције такве да њихова одговарајућа к-д стабла имају листове који су појединачне ћелије мреже такве да имају један унутрашњи чвор мање од броја ћелија датих у мрежи. Њихова одговарајућа имплицитна к-д стабла су потпуна имплицитна к-д стабла.

Пример потпуне сплиттинг-функције је медијана мреже. Она ствара прилично балансирано имплицитно к-д стабло користећи целобројне хиперправоугаонике хyпрец[2][к] са к димензија за сваки чвор имплицитног к-д стабла. Хиперправоугаоници дефинишу које ћелије униформне мреже припадају њиховом одговарајућем чвору. Ако је запремина овог хиперправоугаоника једнака један, одговарајући чвор је једна ћелија мреже и зато се не дели даље и обележава се као лист. У супротном, најдужа страна хиперправоугаоника се бира као оријентација о. Одговарајућа раван поделе п је постављена на мрежну раван која је најближа медијани мреже хиперправоугаоника у тој оријентацији.

Оријентација о равни поделе:

o = min{argmax(i = 1 ... k: (hyprec[1][i] - hyprec[0][i]))}

Положај п равни поделе:

p = roundDown((hyprec[0][o] + hyprec[1][o]) / 2)

Додељивање атрибута чворовима имплицитног к-д стабла

Очигледна предност имплицитних к-д стабала је то што оријентација и положај њихових равни поделе не мора бити сачувана експлицитно. Неке апликације поред оријентације и положаја равни поделе захтевају и атрибуте унутрашњих чворова. Ови атрибути могу на пример бити појединачни битови или појединачне скаларне вредности, дефинишући да ли су подмреже које припадају чворовима предмет интересовања или не. За потпуна имплицитна к-д стабла могуће је пре-алоцирати низ атрибута тачне величине и доделити сваком унутрашњем чвору јединствен елемент у том алоцираном низу.

Количина ћелија у мрежи је једнака запремини целобројног хиперправоугаоника који припада мрежи. Како потпуно имплицитно к-д стабло има за један мање унутрашњих чворова него ћелија мреже, унапред се зна колико атрибута треба да се сачува. Релација "Запремина целобројног хиперправоугаоника у односу на унутрашње чворове" дефинише са потпуном сплиттинг-функцијом рекурзивну формулу додељујући свакој равни поделе јединствен елемент у алоцираном низу. Одговарајућ алгоритам је дат у C-псеудо коду испод.

// 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);
}

Вреди додати да овај алгоритам ради за све униформне (праволинијске) мреже. Одговарајући целобројни хиперправоугаоник не мора обавезно имати дужине страница које су степен броја два.

Примена

Имплицитна маx-к-д стабла се користе за "метод бацања зрака" изо-површина/МИП (пројекција максималног интензитета). Атрибут додељен сваком унутрашњем чвору је максимална скаларна вредност дата у подмрежи која припада чвору. Кроз чворове се не путује ако је њихова скаларна вредност мања од тражене исо-вредности/тренутног максималног интензитета дуж зрака. Складиштење код имплицитног маx к-д стабла није захтевно и повољна сложеност визуализација код "бацања зрака" дозвољавају да се "бацање зрака" користи за веома велика скаларна поља при интерактивној брзини смењивања слика на рачунарима. Слично, имплицитно мин/маx к-д стабло може да се користи да се ефикасно оцене упити као што је теренска линија погледа.^[4]

Сложеност

За дато имплицитно к-д стабло разапето преко мреже са к димензија и н ћелија мреже.

Додела атрибута чворовима стабла одузима $\mathrm {O} (kn)$ времена.
Складиштење атрибута у чворове одузима $\mathrm {O} (n)$ меморије
"Бацање зрака" изо-површина/МИП скаларног поља које је испод користећи одговарајуће имплицитно маx к-д стабло одузима, грубо процењено, $\mathrm {O} (\log(n))$ времена.

Види још

Референце

^ Инго Wалд, Хеико Фриедрицх, Герд Мармитт, Пхилипп Слусаллек анд Ханс-Петер Сеидел "Фастер Исосурфаце Раy Трацинг усинг Имплицит КД-Треес" ИЕЕЕ Трансацтионс он Висуализатион анд Цомпутер Грапхицс (2005)
^ Маттхиас Гроß, Царстен Лојеwски, Мартин Бертрам анд Ханс Хаген "Фаст Имплицит к-д Треес: Аццелератед Исосурфаце Раy Трацинг анд Маxимум Интенситy Пројецтион фор Ларге Сцалар Фиелдс" ЦГИМ07: Процеедингс оф Цомпутер Грапхицс анд Имагинг (2007) 67-74
^ Маттхиас Гроß (ПхД, 2009) Тоwардс Сциентифиц Апплицатионс фор Интерацтиве Раy Цастинг
^ Бернардт Дувенхаге "Усинг Ан Имплицит Мин/Маx КД-Трее фор Доинг Еффициент Терраин Лине оф Сигхт Цалцулатионс" ин "Процеедингс оф тхе 6тх Интернатионал Цонференце он Цомпутер Грапхицс, Виртуал Реалитy, Висуалисатион анд Интерацтион ин Африца", 2009.

[1] Инго Wалд, Хеико Фриедрицх, Герд Мармитт, Пхилипп Слусаллек анд Ханс-Петер Сеидел "Фастер Исосурфаце Раy Трацинг усинг Имплицит КД-Треес" ИЕЕЕ Трансацтионс он Висуализатион анд Цомпутер Грапхицс (2005)

[2] Маттхиас Гроß, Царстен Лојеwски, Мартин Бертрам анд Ханс Хаген "Фаст Имплицит к-д Треес: Аццелератед Исосурфаце Раy Трацинг анд Маxимум Интенситy Пројецтион фор Ларге Сцалар Фиелдс" ЦГИМ07: Процеедингс оф Цомпутер Грапхицс анд Имагинг (2007) 67-74

[3] Маттхиас Гроß (ПхД, 2009) Тоwардс Сциентифиц Апплицатионс фор Интерацтиве Раy Цастинг

[4] Бернардт Дувенхаге "Усинг Ан Имплицит Мин/Маx КД-Трее фор Доинг Еффициент Терраин Лине оф Сигхт Цалцулатионс" ин "Процеедингс оф тхе 6тх Интернатионал Цонференце он Цомпутер Грапхицс, Виртуал Реалитy, Висуалисатион анд Интерацтион ин Африца", 2009.

[1]

[2]

[3]

[4]