Скрытый k-d дерево - Implicit k-d tree - Wikipedia

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

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

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

Условия "мин Макс k-d дерево "и" неявный k-d tree "иногда путают. Это потому, что первая публикация, использующая термин" неявный k-d дерево " ^[1] действительно использовал явный мин / макс k-d деревья, но называли их "неявными k-d деревья ", чтобы указать, что они могут использоваться для трассировки лучей неявно заданных изоповерхностей. Тем не менее, в этой публикации использовались также тонкие k-d деревья, которые являются подмножеством неявных k-d деревья с ограничением, что они могут быть построены только на целочисленных гипер прямоугольниках со сторонами, равными степени двойки. Скрытый k-d деревья, как здесь определено, были недавно введены с приложениями в компьютерной графике.^[2][3] Как можно присвоить атрибуты неявным k-d узлов дерева, можно ссылаться на неявный k-d дерево, имеющее минимальные / максимальные значения, присвоенные его узлам как «неявное минимальное / максимальное значение. k-d дерево ".

Строительство

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

Расщепляющие функции

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

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

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

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

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

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

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

Присваивание атрибутов неявному k-d узлы дерева

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

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

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

// Назначение атрибутов внутренним узлам полного неявного k-d дерева// создаем целое число help hyper rectangle hyprec (его объем vol (hyprec) равен количеству листьев)int hyprec[2][k] = { { 0, ..., 0 }, { length_1, ..., length_k } };// один раз выделяем массив атрибутов для всего неявного k-d дереваattr *а = новый attr[объем(hyprec) - 1];attr implicitKdTreeAttributes(int hyprec[2][k], attr *а){  если (объем(hyprec) > 1) // текущий узел - это внутренний узел  {    // оцениваем ориентацию плоскости разделения o и ее положение p, используя лежащую в основе полную функцию разделения    int о, п;    completeSplittingFunction(hyprec, &о, &п);    // оцениваем детские целочисленные гипер прямоугольники 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 = а + 1;    attr* a_r = а + объем(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 = слияние(c_l, c_r);    // сохраняем текущий атрибут и возвращаем его    а[0] = c;    возвращаться c;  }  // Текущий узел является листовым. Вернуть атрибут, принадлежащий соответствующей ячейке сетки  возвращаться атрибут(hyprec);}

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

Приложения

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

Сложность

Учитывая неявный k-d дерево, натянутое на k-мерная сетка с п ячейки сетки.

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

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

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

Рекомендации

1. Инго Вальд, Хайко Фридрих, Герд Мармитт, Филипп Слусаллек и Ханс-Петер Зайдель «Ускоренная трассировка лучей изоповерхности с использованием неявных деревьев KD» IEEE-транзакции по визуализации и компьютерной графике (2005)
2. Маттиас Гросс, Карстен Лоевски, Мартин Бертрам и Ханс Хаген «Быстрый неявный k-d Trees: Accelerated Isosurface Ray Tracing and Maximum Intensity Projection for Large Scalar Fields »CGIM07: Proceedings of Computer Graphics and Imaging (2007) 67-74
3. Маттиас Гросс (доктор философии, 2009 г.) К научным приложениям для интерактивного литья лучей
4. Бернард Дювенхаге «Использование неявного минимального / максимального KD-дерева для выполнения эффективных расчетов линии обзора местности» в «Трудах 6-й Международной конференции по компьютерной графике, виртуальной реальности, визуализации и взаимодействию в Африке», 2009.