Неявное дерево kd

редактировать

Построение и сохранение неявного 2D-дерева max kd с использованием медианного разделения сетки -функция. Каждой ячейке прямолинейной сетки присвоено одно скалярное значение от низкого (ярко-синий) до высокого (ярко-красный). Объем памяти сетки указан в нижней строке. Для предопределенного объема памяти неявного max kd-tree требуется на одно скалярное значение меньше этого. Сохранение максимальных значений узла указано в верхней строке.

неявное k-d дерево - это k-d дерево, неявно определенное над прямолинейной сеткой. Позиции его разделенных плоскостей 'и ориентации задаются не явно, а неявно некоторой рекурсивной функцией разделения, определенной на гипер прямоугольниках, принадлежащих дерево узлов. Плоскость разделения каждого внутреннего узла расположена на плоскости сетки базовой сетки, разделяя сетку узла на две подсетки.

Содержание

1 Номенклатура и ссылки
2 Конструкция
- 2.1 Функции разделения
- 2.2 Назначение атрибутов неявным узлам дерева kd
3 Приложения
4 Сложность
5 См. Также
6 Ссылки

Номенклатура и ссылки

Термины «минимальное / максимальное дерево kd » и «неявное дерево kd» иногда путают. Это связано с тем, что первая публикация, использующая термин «неявное k-d дерево», действительно использовала явные min / max k-d деревья, но называла их «неявными k-d деревьями», чтобы указать, что они могут использоваться для трассировки лучей неявно заданных iso-поверхностей. Тем не менее, в этой публикации использовались также тонкие k-d-деревья, которые являются подмножеством неявных k-d-деревьев с ограничением, что они могут быть построены только на целочисленных гипер прямоугольниках со сторонами, равными степеням двойки. Неявные k-d деревья, как здесь определено, были недавно введены с приложениями в компьютерной графике. Поскольку возможно назначать атрибуты неявным узлам k-d дерева, можно ссылаться на неявное k-d дерево, которое имеет минимальные / максимальные значения, присвоенные его узлам, как «неявное минимальное / максимальное k-d дерево».

Построение

Неявные k-d деревья обычно не строятся явно. При доступе к узлу его ориентация и положение плоскости разделения оцениваются с помощью специальной функции разделения, определяющей дерево. Различные функции разделения могут привести к получению разных деревьев для одной и той же базовой сетки.

Функции разделения

Функции разделения могут быть адаптированы для специальных целей. Под двумя спецификациями специальных классов функций расщепления.

Невырожденные функции-расщепления не позволяют создавать вырожденные узлы (узлы, у которых соответствующий целочисленный объем гипер прямоугольника равен нулю). Соответствующие им неявные k-d деревья являются полными двоичными деревьями, которые имеют для n листовых узлов n - 1 внутренних узлов. Соответствующие им неявные деревья kd являются невырожденными неявными деревьями kd .
полными функциями расщепления являются невырожденными функциями расщепления, чьи соответствующие неявные листовые узлы дерева kd являются отдельными ячейками сетки, так что они имеют один внутренний узел меньше, чем количество ячеек, указанное в сетке. Соответствующие неявные k-d деревья являются полными неявными k-d деревьями .

Полная функция разделения - это, например, медианная функция разделения сетки . Он создает довольно сбалансированные неявные k-d деревья, используя k-мерные целочисленные гипер прямоугольники hyprec [2] [k], принадлежащие каждому узлу неявного k-d дерева. Гиперпрямоугольники определяют, какие ячейки прямолинейной сетки принадлежат их соответствующему узлу. Если объем этого гипер прямоугольника равен единице, соответствующий узел является единственной ячейкой сетки и, следовательно, не подлежит дальнейшему разделению и не помечается как листовой узел. В противном случае в качестве ориентации o выбирается самая длинная протяженность гиперугольника. Соответствующая плоскость разделения p размещается на плоскости сетки, которая является ближайшей к медиане сетки гипер прямоугольника вдоль этой ориентации.

Ориентация разделенной плоскости o:

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

Положение разделенной плоскости p:

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

Назначение атрибутов неявные узлы kd-дерева

Очевидным преимуществом неявных kd-деревьев является то, что ориентации и положения их плоскости разделения не нужно сохранять явно.

Но некоторые приложения требуют помимо ориентации плоскости разделения и позиционирования дополнительных атрибутов во внутренних узлах дерева. Эти атрибуты могут быть, например, одиночными битами или одиночными скалярными значениями, определяющими, представляют ли подсетки, принадлежащие узлам, интерес или нет. Для полных неявных k-d деревьев можно предварительно выделить массив атрибутов правильного размера и назначить каждый внутренний узел дерева уникальному элементу в этом выделенном массиве.

Количество ячеек сетки в сетке равно объему целочисленного гипер прямоугольника, принадлежащего сетке. Поскольку полное неявное k-d дерево имеет на один внутренний узел меньше, чем ячеек сетки, заранее известно, сколько атрибутов необходимо сохранить. Отношение «Объем целочисленного гипер прямоугольника к внутренним узлам» вместе с полной функцией разделения определяет рекурсивную формулу, присваивающую каждой плоскости разделения уникальный элемент в выделенном массиве. Соответствующий алгоритм представлен ниже в C-псевдокоде.

// Присвоение атрибутов внутренним узлам полного неявного kd-дерева // создание целого числа help hyper rectangle hyprec (его объем vol (hyprec) равен количеству листьев) int hyprec [2] [k] = {{0,..., 0}, {длина_1,..., длина_k}}; // однократно выделяем массив атрибутов для всего неявного k-d дерева attr * a = new attr [volume (hyprec) - 1]; attr implicitKdTreeAttributes (int hyprec [2] [k], attr * a) {if (vol (hyprec)>1) // текущий узел является внутренним узлом {// оценивает ориентацию плоскости разделения o и ее положение p с помощью лежащая в основе полная функция разделения int o, p; completeSplittingFunction (hyprec, o, p); // вычисляем детские целочисленные гипер прямоугольники hyprec_l и 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; // оцениваем расположение детской памяти a_l и a_r attr * a_l = a + 1; attr * a_r = a + vol (hyprec_l); // рекурсивно оцениваем дочерние атрибуты c_l и c_r attr c_l = implicitKdTreeAttributes (hyprec_l, a_l); attr c_r = implicitKdTreeAttributes (hyprec_r, a_r); // объединить дочерние атрибуты с текущим атрибутом c attr c = merge (c_l, c_r); // сохраняем текущий атрибут и возвращаем его a [0] = c; return c; } // Текущий узел является листовым узлом. Вернуть атрибут, принадлежащий соответствующему атрибуту возврата gridcell (hyprec); }

Стоит отметить, что этот алгоритм работает для всех прямолинейных сеток. Соответствующий целочисленный гипер прямоугольник не обязательно должен иметь длину стороны, равную степени двойки.

Приложения

Неявные деревья max-kd используются для литья лучей изоповерхностей / MIP (максимальная интенсивность проекция ). Атрибут, присвоенный каждому внутреннему узлу, - это максимальное скалярное значение, указанное в подсетке, принадлежащей узлу. Узлы не пересекаются, если их скалярные значения меньше искомого изо-значения / максимальной интенсивности тока вдоль луча. Низкие требования к хранилищу неявного max kd-дерева и благоприятная сложность визуализации для преобразования лучей позволяют преобразовывать лучи (и даже изменять изоповерхность для) очень больших скалярных полей с интерактивной частотой кадров на обычных ПК. Точно так же неявное min / max kd-tree может использоваться для эффективной оценки таких запросов, как terrain линия обзора.

Сложность

Учитывая неявное kd-дерево, охватываемое k -мерная сетка с n ячейками.

Для присвоения атрибутов узлам дерева требуется $O (kn) {\ displaystyle \ mathrm {O} (kn)}$ ${\ mathrm {O}} (kn)$ time.
Сохранение атрибутов для узлов принимает $O (n) {\ displaystyle \ mathrm {O} (n)}$ $\ mathrm {O} (n)$ memory.
Изоповерхности моделирования лучей / MIP базового скалярного поля с использованием соответствующего неявного max Дерево kd занимает примерно $O (log ⁡ (n)) {\ displaystyle \ mathrm {O} (\ log (n))}$ ${\ mathrm {O}} (\ log (n))$ времени.

См. также

Ссылки

^Инго Вальд, Хайко Фридрих, Герд Мармитт, Филипп Слусаллек и Ханс-Петер Зайдель «Более быстрая трассировка лучей изоповерхности с использованием неявных деревьев KD» IEEE-транзакции по визуализации и компьютерной графике (2005 г.)
^Маттиас Гросс, Карстен Лоевски, Мартин Бертрам и Ханс Хаген «Быстрые неявные деревья kd: ускоренная изоповерхностная трассировка лучей и проекция максимальной интенсивности для больших скалярных полей» CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74
^Маттиас Гросс (доктор философии, 2009 г.) К научному применению ications for Interactive Ray Casting
^Бернард Дювенхейдж "Использование неявного KD-дерева мин / макс для выполнения эффективных расчетов прямой видимости местности" в "Трудах 6-й Международной конференции по компьютерной графике, виртуальной реальности, визуализации и взаимодействию в Африке", 2009.