Неявное k- d дерево

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

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

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

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

// Assigning attributes to inner nodes of a complete implicit k-d tree

// create an integer help hyperrectangle hyprec (its volume vol(hyprec) is equal the amount of leaves)
int hyprec[2][k] = { { 0, ..., 0 }, { length_1, ..., length_k } };
// allocate once the array of attributes for the entire implicit k-d tree
attr *a = new attr[volume(hyprec) - 1];

attr implicitKdTreeAttributes(int hyprec[2][k], attr *a)
{
  if (vol(hyprec) > 1) // the current node is an inner node
  {
    // evaluate the split plane's orientation o and its position p using the underlying complete split-function
    int o, p;
    completeSplittingFunction(hyprec, &o, &p);
    // evaluate the children's integer hyperrectangles hyprec_l and 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;
    // evaluate the children's memory location a_l and a_r 
    attr* a_l = a + 1;
    attr* a_r = a + vol(hyprec_l);
    // evaluate recursively the children's attributes c_l and c_r 
    attr c_l = implicitKdTreeAttributes(hyprec_l, a_l);
    attr c_r = implicitKdTreeAttributes(hyprec_r, a_r);
    // merge the children's attributes to the current attribute c 
    attr c = merge(c_l, c_r);
    // store the current attribute and return it
    a[0] = c;
    return c;
  }
  // The current node is a leaf node. Return the attribute belonging to the corresponding gridcell
  return attribute(hyprec);
}

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

Приложения

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

Сложность

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

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

См. также

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