мин/макс дерево kd
Минимальное /максное k d-дерево — это k -d дерево с двумя скалярными значениями — минимальным и максимальным — присвоенными его узлам. Минимум/максимум внутреннего узла равен минимуму/максимуму его дочерних минимумов/максимумов.
Строительство
[ редактировать ]Min/max k d-деревьев можно строить рекурсивно. Начиная с корневого узла, оценивается ориентация и положение плоскости разделения. Затем рекурсивно оцениваются дочерние плоскости разделения и значения min/max. Минимальное/максимальное значение текущего узла — это просто минимум/максимум его дочерних минимумов/максимумов.
Характеристики
[ редактировать ]Минимальное/максное k dдерево обладает, помимо свойств k d-дерева, особым свойством, заключающимся в том, что мин/макс значения внутреннего узла совпадают со значениями мин/макс любого из дочерних узлов. Это позволяет отказаться от хранения минимальных/максимальных значений на листовых узлах, сохраняя два бита во внутренних узлах, назначая минимальные/максимальные значения дочерним узлам: минимальные/максимальные значения каждого внутреннего узла будут известны заранее, где минимальное значение корневого узла Значения /max хранятся отдельно. Каждому внутреннему узлу, помимо двух минимальных/максимальных значений, также присвоены два бита, определяющие, какому дочернему элементу присвоены эти минимальные/максимальные значения (0: левому дочернему элементу 1: правому дочернему элементу). Неназначенные мин/макс значения дочерних элементов – это уже известные мин/макс значения текущего узла. Эти два бита также могут храниться в младших битах минимальных/максимальных значений, которые, следовательно, должны быть аппроксимированы путем дробления их вниз/вверх.
Результирующее сокращение памяти немаловажно, поскольку конечные узлы полных двоичных k d-деревьев составляют половину узлов дерева.
Приложения
[ редактировать ]Min/max k d-деревья используются для лучевого моделирования изоповерхностей /MIP ( проекция максимальной интенсивности ). Приведение лучей изоповерхности пересекает только те узлы, для которых выбранное изозначение находится между минимальными/максимальными значениями текущего узла. Узлы, которые не удовлетворяют этому требованию, не содержат изоповерхности для данного изозначения и поэтому пропускаются (пропуск пустого пространства). Для MIP узлы не пересекаются, если их максимум меньше текущей максимальной интенсивности вдоль луча. Выгодная сложность визуализации при распределении лучей позволяет выполнять преобразование лучей (и даже изменять изоповерхность) для очень больших скалярных полей с интерактивной частотой кадров на обычных ПК. Особенно неявные max k d-деревья являются оптимальным выбором для визуализации скалярных полей, определенных на прямолинейных сетках (см. [1] [2] [3] ). Аналогичным образом, неявное минимальное/максимальное kd-дерево может использоваться для эффективной оценки таких запросов, как линия обзора местности . [4]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Маттиас Гросс, Карстен Лоевски, Мартин Бертрам и Ханс Хаген «Быстрые неявные KD-деревья: ускоренная трассировка изоповерхностных лучей и проекция максимальной интенсивности для больших скалярных полей» CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74
- ^ Инго Вальд, Хайко Фридрих, Герд Мармитт, Филипп Слусаллек и Ханс-Петер Зайдель «Быстрая трассировка лучей изоповерхности с использованием неявных KD-деревьев» Транзакции IEEE по визуализации и компьютерной графике (2005)
- ^ Маттиас Гросс (доктор философии, 2009 г.) К научным применениям интерактивного лучевого литья
- ^ Бернард Дювенхаге «Использование неявного минимального / максимального KD-дерева для эффективных расчетов прямой видимости на местности» в «Материалах 6-й Международной конференции по компьютерной графике, виртуальной реальности, визуализации и взаимодействию в Африке», 2009.