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

Построение и хранение двумерного неявного max k d-дерева с использованием функции расщепления медианы сетки. Каждой ячейке прямолинейной сетки назначено одно скалярное значение от низкого (ярко-синего) до высокого (ярко-красного). Объем памяти сетки указан в нижней строке. Предопределенный объем памяти неявного max k d-дерева требует на одно скалярное значение меньше этого. Хранение максимальных значений узла указано в верхней строке.

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

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

Термины « min/max k -d tree » и «implicit k -d tree» иногда путают. Это связано с тем, что первая публикация, использующая термин «implicit k -d tree» ^[1], на самом деле использовала явные min/max k -d деревья, но называла их «implicit k -d trees», чтобы указать, что они могут использоваться для трассировки лучей неявно заданных изоповерхностей. Тем не менее, в этой публикации также использовались тонкие k -d деревья, которые являются подмножеством неявных k -d деревьев с ограничением, что они могут быть построены только над целочисленными гиперпрямоугольниками со сторонами, являющимися степенями двойки. Неявные k -d деревья, как определено здесь, были недавно введены с приложениями в компьютерной графике. ^{[2] [3]} Поскольку можно назначать атрибуты узлам неявного k -d дерева, можно ссылаться на неявное k -d дерево, у которого есть значения min/max, назначенные его узлам, как на «implicit 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)

Присвоение атрибутов неявнымк-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 ][ 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 ; } // Текущий узел является листовым узлом. Возвращаем атрибут, принадлежащий соответствующей ячейке сетки return attribute ( hyprec ); }                                                                         

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

Приложения

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

Сложность

Дано неявное k -мерное дерево, охватывающее k -мерную сетку с n ячейками.

• Назначение атрибутов узлам дерева требует времени. ${\displaystyle \mathrm {O} (kn)}$
• Хранение атрибутов узлов требует памяти. ${\displaystyle \mathrm {O} (n)}$
• Наложение лучей на изоповерхности/MIP базового скалярного поля с использованием соответствующего неявного дерева max k -d занимает примерно время. ${\displaystyle \mathrm {O} (\log(n))}$

Смотрите также

• к -д дерево
• мин/макс k -d дерево

Ссылки

1. Инго Вальд, Хайко Фридрих, Герд Мармитт, Филипп Слусаллек и Ханс-Петер Зайдель «Быстрая трассировка лучей изоповерхностей с использованием неявных деревьев KD» Труды IEEE по визуализации и компьютерной графике (2005)
2. Маттиас Гросс, Карстен Лоевски, Мартин Бертрам и Ханс Хаген «Быстрые неявные деревья k -d: ускоренная трассировка лучей изоповерхности и проекция максимальной интенсивности для больших скалярных полей» CGIM07: Труды компьютерной графики и обработки изображений (2007) 67-74
3. Маттиас Гросс (доктор философии, 2009) На пути к научным приложениям для интерактивного анализа лучей
4. Бернардт Дювенхаге «Использование неявного минимального/максимального KD-дерева для эффективных расчетов линии прямой видимости местности» в «Трудах 6-й Международной конференции по компьютерной графике, виртуальной реальности, визуализации и взаимодействию в Африке», 2009.