Неявное k -d дерево
Неявное , k -d дерево — это k -d дерево определенное неявно над прямолинейной сеткой . его плоскостей Положения и ориентации расщепления задаются не явно, а неявно некоторой рекурсивной функцией расщепления, определенной на гиперпрямоугольниках дерева , принадлежащих узлам . Плоскость разделения каждого внутреннего узла располагается на плоскости сетки базовой сетки, разделяя сетку узла на две подсетки.
Номенклатура и ссылки [ править ]
Термины « min/max k -d дерево » и «неявное k -d дерево» иногда путают. Это связано с тем, что первая публикация, использующая термин «неявное k -d дерево», [1] на самом деле использовал явные деревья min/max k -d, но называл их «неявными деревьями k -d», чтобы указать, что они могут использоваться для трассировки лучей неявно заданных изо-поверхностей. Тем не менее, в этой публикации также использовались тонкие k -d-деревья, которые являются подмножеством неявных k -d-деревьев с тем ограничением, что их можно строить только на целочисленных гиперпрямоугольниках с длинами сторон, равными степеням двойки. Неявные k -d-деревья, определенные здесь, были недавно введены и нашли применение в компьютерной графике. [2] [3] Поскольку можно назначать атрибуты неявным узлам дерева k -d, можно называть неявное дерево k -d, узлам которого присвоены минимальные/максимальные значения, как «неявное дерево min/max k -d».
Строительство [ править ]
Неявные k -d-деревья обычно не строятся явно. При доступе к узлу его ориентация и положение в плоскости разделения оцениваются с использованием специальной функции разделения, определяющей дерево. Различные функции расщепления могут привести к созданию разных деревьев для одной и той же базовой сетки.
Функции расщепления [ править ]
Функции расщепления могут быть адаптированы для специальных целей. Ниже две спецификации специальных классов функций расщепления.
- Невырожденные функции расщепления не позволяют создавать вырожденные узлы (узлы, объем соответствующего целочисленного гиперпрямоугольника которых равен нулю). Соответствующие им неявные k -d-деревья являются полными двоичными деревьями , которые имеют для n листовых узлов n-1 внутренних узлов. Соответствующие им неявные k -d деревья являются невырожденными неявными k -d деревьями .
- Полные функции расщепления - это невырожденные функции расщепления, соответствующие им неявные листовые узлы k -d дерева представляют собой отдельные ячейки сетки, так что они имеют на один внутренний узел меньше, чем количество ячеек сетки, заданное в сетке. Соответствующие неявные 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)
Присвоение атрибутов неявным k узлам дерева -d [ править ]
Преимущество неявных k -d-деревьев состоит в том, что ориентацию и положение их разделенной плоскости не нужно сохранять явно.
Но в некоторых приложениях помимо ориентации и положения разделенной плоскости требуются дополнительные атрибуты во внутренних узлах дерева. Эти атрибуты могут быть, например, отдельными битами или одиночными скалярными значениями, определяющими, представляют ли интерес подсетки, принадлежащие узлам, или нет. Для полных неявных k -d деревьев можно заранее выделить массив атрибутов правильного размера и присвоить каждому внутреннему узлу дерева уникальный элемент в этом выделенном массиве.
Количество ячеек сетки равно объему целочисленного гиперпрямоугольника, принадлежащего сетке. Поскольку полное неявное k -d-дерево имеет на один внутренний узел меньше, чем ячейки сетки, заранее известно, сколько атрибутов необходимо сохранить. Отношение « Объем целочисленного гиперпрямоугольника к внутренним узлам » вместе с полной функцией разделения определяет рекурсивную формулу, присваивающую каждой плоскости разделения уникальный элемент в выделенном массиве. Соответствующий алгоритм приведен ниже в C-псевдокоде.
// Присвоение атрибутов внутренним узлам полного неявного дерева kd
// создаем целочисленную справку гиперпрямоугольник hyprec (его объем vol(hyprec) равен количеству листьев)
int hyprec [ 2 ][ k ] = { { 0 , .. ., 0 }, { length_1 , ..., length_k } };
// выделяем один раз массив атрибутов для всего неявного дерева kd
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 ][ о ] знак равно п ;
hyprec_r = hyprec ;
hyprec_r [ 0 ][ о ] знак равно п ;
// оцениваем расположение дочерней памяти 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 , а_р );
// объединяем дочерние атрибуты с текущим атрибутом c
attr c = merge ( c_l , c_r );
// сохраняем текущий атрибут и возвращаем его
a [ 0 ] = c ;
вернуть с ;
}
// Текущий узел является листовым узлом. Возвращает атрибут, принадлежащий соответствующему
возвращаемому атрибуту ячейки сетки ( hyprec );
}
Стоит отметить, что этот алгоритм работает для всех прямолинейных сеток. Соответствующий целочисленный гиперпрямоугольник не обязательно должен иметь длину сторон, равную степени двойки.
Приложения [ править ]
Неявные max- k деревья -d используются для распределения лучей изоповерхностей /MIP ( проекция максимальной интенсивности ). Атрибут, назначенный каждому внутреннему узлу, представляет собой максимальное скалярное значение, заданное в подсетке, принадлежащей этому узлу. Узлы не пересекаются, если их скалярные значения меньше искомого изо-значения/текущей максимальной интенсивности вдоль луча. Низкие требования к объему памяти для неявного max k d-дерева и благоприятная сложность визуализации приведения лучей позволяют выполнять преобразование лучей (и даже менять изоповерхность) очень больших скалярных полей с интерактивной частотой кадров на обычных ПК. Аналогично, неявное минимальное/максимальное kd-дерево может использоваться для эффективной оценки таких запросов, как линия обзора местности . [4]
Сложность [ править ]
Дано неявное k -d дерево, охватывающее k -мерную сетку с n ячейками сетки.
- Присвоение атрибутов узлам дерева занимает время.
- Сохранение атрибутов узлов занимает Память.
- Приведение лучей изо-поверхностей/MIP к базовому скалярному полю с использованием соответствующего неявного дерева max k -d занимает примерно время.
См. также [ править ]
Ссылки [ править ]
- ^ Инго Вальд, Хайко Фридрих, Герд Мармитт, Филипп Слусаллек и Ханс-Петер Зайдель «Быстрая трассировка лучей изоповерхности с использованием неявных KD-деревьев» Транзакции IEEE по визуализации и компьютерной графике (2005)
- ^ Маттиас Гросс, Карстен Лоевски, Мартин Бертрам и Ханс Хаген «Быстрые неявные деревья k -d: ускоренная трассировка лучей изоповерхности и проекция максимальной интенсивности для больших скалярных полей» CGIM07: Труды компьютерной графики и визуализации (2007) 67-74
- ^ Маттиас Гросс (доктор философии, 2009 г.) К научным применениям интерактивного лучевого литья
- ^ Бернард Дювенхаге «Использование неявного минимального / максимального KD-дерева для эффективных расчетов прямой видимости на местности» в «Материалах 6-й Международной конференции по компьютерной графике, виртуальной реальности, визуализации и взаимодействию в Африке», 2009.