Тест пересечения с kd-деревом

Question

Мое текущее понимание kd-дерева:что на каждом узле мы разделяем наши точки на две одинаково большие группы для одной оси.

Мы выполняем итерацию по отдельной оси, пока дерево не будет насыщено.

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

---

У меня есть вопрос о том, как это сделать.

Как мы справляемся со странными треугольниками, в которых мы не можем легко разделить (треугольники, пересекающие другие треугольники или треугольники, которые охватывают все?

Делаем ли мы даже треугольники или вершины?

Как именно мы проверяем пересечение луча, который мы посылаемс камеры?

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

Answer 1

Краткий ответ: все зависит от вашего приложения.Существует несколько вариаций kd-деревьев.

Как мы справляемся со странными треугольниками, в которых мы не можем сделать простые разбиения?

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

Если вы обнаружите, что ваша плоскость расщепления проходит через примитив, у вас есть два варианта.Либо разделите примитив, либо добавьте его в оба поддерева.Что вы должны сделать, зависит от вашего приложения.

Разбиваем ли мы даже треугольники или разбиваемые по вершинам?

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

Как именно мы проверяем пересечение луча, который мы посылаем из камеры?

Это делается путем обхода дерева.Итак, вы начинаете с корневого узла и проверяете, пересекается ли луч с соответствующим ограничивающим прямоугольником (который является всем пространством).Затем вы проверяете, какое из двух поддеревьев сначала пересекается лучом, и переходите к этому.И затем вы повторяете: вы проверяете на пересечение с AABB узла (который вы строите постепенно из плоскостей расщепления).Если луч не пересекает AABB, то немедленно вернитесь обратно к родительскому узлу.Если это так, переходите к первому ребенку.Когда вы вернетесь к первому дочернему элементу, перейдите ко второму дочернему элементу (если только вы не нашли пересечение).

Для получения более подробной информации я бы посоветовал взглянуть на специфичные для приложения экземпляры kd-деревьев..