Мин/маx КД стабло
| Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Мин/маx кд-стабло је К-D стабло са две скаларне вредности - минималне и максималне - додељене својим чворовима. Минимум/максимум унутрашњег чвора је једнак минимуму/максимуму своје деце.
Конструкција уреди
Мин/маx кд- стабла се могу конструисати рекурзивно. Почевши од корена чвора, оријентација цепање авиона и положај се процењују. Онда се цепачи авиона код деце и мин/маx вреност рекурзивно процењују. Минимална/максимална вредност текућег чвора је једноставно минимум/максимум од минимума/максимума своје деце.
Особине уреди
Мин/маx кд стабло има осим особина кд стабла, посебну особину, да се сваки унутрашњи чвор који има мин/маx вредност поклапа са мин/маx вредношћу од бар једног детета. Ово омогућава одбацивање складиштења мин/маx вредности код лисних чворова чувајући два бита у унутрашњим чворовима, додељујући мин/маx вредност деци: Сваки унутрашњи чвор мин/маx вредности ће бити познат унапред, где се чворови мин/маx вредности чувају одвојено. Сваки унутрашњи чвор има осим две мин/маx вредности такође два дата бита, дефинишући свако дете чије су мин/маx вредности додељене (0: левом детету, 1: десном детету). Недодељене мин/маx вредности деце су из текућег чвора већ познате мин/маx вредности. Два бита се такође могу чувати у најмање значајним битовима мин/маx вредности, који дакле могу бити апроксимирани фракционишући их доле/горе.
Резултујућа меморија није мања, као што су лисни чворови потпуних бинарних кд-стабала половина од чворова у стаблу.
Апликације уреди
Мин/маx кд-стабла се користе за "метод бацања зрака" изо-површине,Раy Цастинг исосурфаце/МИП (пројекција максималног интензитета). Изо-површина раy цастинг-а заобилази само чворове за које изабрана изо-линија лежи између мин/маx вредности текућег чвора. Чворови који не задовољавају овај услов, не садрже изо-површину са датим изо-линијама и стога се прескачу (прескакање празног простора). За МИП, чворови се не заобилазе ако је њихов максимум мањи од тренутног максималног интензитета дуж зрака. Повољна визуелизација раy цастинг-а омогућава "бацање зрака" (чак и промену изо-површине) за врло велика скаларна поља на интерактивним брзинама смењивања слика на рачунарима. Посебно имплицитна максимална кд-стабла су оптимални избор за визуелизацију скаларних поља дефинисаних на праволинијским мрежама (види[1][2][3]). Слично имплицитно мин/маx кд-стабло се може користити за ефикасну процену попут терена линије вида.[4]
Види још уреди
- К-D стабло
- Имплицитно К-D стабло
Референце уреди
- ^ Маттхиас Гроß, Царстен Лојеwски, Мартин Бертрам анд Ханс Хаген "Фаст Имплицит КД-Треес: Аццелератед Исосурфаце Раy Трацинг анд Маxимум Интенситy Пројецтион фор Ларге Сцалар Фиелдс" ЦГИМ07: Процеедингс оф Цомпутер Грапхицс анд Имагинг (2007) 67-74
- ^ Инго Wалд, Хеико Фриедрицх, Герд Мармитт, Пхилипп Слусаллек анд Ханс-Петер Сеидел "Фастер Исосурфаце Раy Трацинг усинг Имплицит КД-Треес" ИЕЕЕ Трансацтионс он Висуализатион анд Цомпутер Грапхицс (2005)
- ^ Маттхиас Гроß (ПхД, 2009) Тоwардс Сциентифиц Апплицатионс фор Интерацтиве Раy Цастинг
- ^ Бернардт Дувенхаге "Усинг Ан Имплицит Мин/Маx КД-Трее фор Доинг Еффициент Терраин Лине оф Сигхт Цалцулатионс" ин "Процеедингс оф тхе 6тх Интернатионал Цонференце он Цомпутер Грапхицс, Виртуал Реалитy, Висуалисатион анд Интерацтион ин Африца", 2009.