Войти
A min / max kd-tree - это kd tree с двумя скалярными значениями - минимальным и максимальным - присвоенными его узлам. Минимум / максимум внутреннего узла равен минимуму / максимуму его дочерних минимумов / максимумов.
Мин / макс kd-деревья могут быть построены рекурсивно. Начиная с корневого узла, оценивается ориентация и положение плоскости разделения. Затем плоскости разделения детей и минимальные / максимальные значения вычисляются рекурсивно. Минимальное / максимальное значение текущего узла - это просто минимум / максимум его дочерних минимумов / максимумов.
min / max kdtree имеет - помимо свойств kd-дерева - специальное свойство, согласно которому минимальные / максимальные значения внутреннего узла совпадают, каждое с минимальным / максимальным значением либо один ребенок. Это позволяет отказаться от хранения минимальных / максимальных значений в конечных узлах, сохраняя два бита на внутренних узлах, присваивая минимальные / максимальные значения дочерним элементам: минимальные / максимальные значения каждого внутреннего узла будут известны заранее, где минимальные значения корневого узла / max значения хранятся отдельно. Каждый внутренний узел имеет помимо двух значений min / max также два заданных бита, определяющих, какому дочернему элементу назначены эти минимальные / максимальные значения (0: левому дочернему элементу 1: правому дочернему элементу). Неназначенные минимальные / максимальные значения дочерних элементов - это уже известные минимальные / максимальные значения текущего узла. Эти два бита также могут быть сохранены в младших разрядах минимального / максимального значений, которые, следовательно, должны быть аппроксимированы путем их дробления вниз / вверх.
Результирующее сокращение памяти немалое, поскольку конечные узлы полных двоичных kd-деревьев составляют половину узлов дерева.
Мин / макс kd-деревья используются для литья лучей изоповерхностей / MIP (проекция максимальной интенсивности ). При моделировании лучей изоповерхности проходят только узлы, для которых выбранное значение находится между минимальным / максимальным значениями текущего узла. Узлы, которые не удовлетворяют этому требованию, не содержат изоповерхность для данного изозначения и поэтому пропускаются (пропуск пустого пространства). Для MIP узлы не пересекаются, если их максимум меньше текущей максимальной интенсивности вдоль луча. Благоприятная сложность визуализации при наложении лучей позволяет отображать лучи (и даже изменять изоповерхность для) очень больших скалярных полей с интерактивной частотой кадров на обычных ПК. В частности, неявные max kd-деревья являются оптимальным выбором для визуализации скалярных полей, определенных на прямолинейных сетках (см.). Аналогичным образом неявное kd-дерево min / max может использоваться для эффективной оценки таких запросов, как Terrain Прямая видимость.
