Min /max k d-дерево — это k -d дерево с двумя скалярными значениями — минимумом и максимумом — назначенными его узлам. Минимум/максимум внутреннего узла равен минимуму/максимуму его дочерних минимумов/максимумов.
Min/max k d-деревья могут быть построены рекурсивно. Начиная с корневого узла, оценивается ориентация и положение плоскости разделения. Затем рекурсивно оцениваются плоскости разделения и значения min/max дочерних узлов. Значение min/max текущего узла — это просто минимум/максимум из его минимумов/максимумов дочерних узлов.
Min/max k dtree имеет - помимо свойств k d-дерева - особое свойство, что min/max значения внутреннего узла совпадают с min/max значением любого из дочерних узлов. Это позволяет отказаться от хранения min/max значений в листовых узлах, сохраняя два бита во внутренних узлах, назначая min/max значения дочерним узлам: min/max значения каждого внутреннего узла будут известны заранее, тогда как min/max значения корневого узла хранятся отдельно. Каждый внутренний узел имеет помимо двух min/max значений также два бита, определяющих, какому дочернему узлу назначаются эти min/max значения (0: левому дочернему узлу, 1: правому дочернему узлу). Неназначенные min/max значения дочерних узлов являются уже известными min/max значениями текущего узла. Два бита также могут быть сохранены в младших битах min/max значений, которые, следовательно, должны быть аппроксимированы путем дробления их вниз/вверх.
Полученное сокращение памяти не является незначительным, поскольку конечные узлы полных двоичных k d-деревьев составляют половину узлов дерева.
Min/max k d-деревья используются для лучевых кастингов изоповерхностей /MIP ( проекция максимальной интенсивности ). Лучевой кастинг изоповерхности пересекает только узлы, для которых выбранное изозначение лежит между минимальным/максимальным значениями текущего узла. Узлы, которые не удовлетворяют этому требованию, не содержат изоповерхности для заданного изозначения и поэтому пропускаются (пропуск пустого пространства). Для MIP узлы не пересекаются, если их максимум меньше текущей максимальной интенсивности вдоль луча. Благоприятная сложность визуализации лучевого кастинга позволяет лучевой кастинг (и даже изменять изоповерхность для) очень больших скалярных полей при интерактивной частоте кадров на обычных ПК. Особенно неявные макс k d-деревья являются оптимальным выбором для визуализации скалярных полей, определенных на прямолинейных сетках (см. [1] [2] [3] ). Аналогично неявное min/max kd-дерево может использоваться для эффективной оценки запросов, таких как линия видимости местности . [4]