Тест пересечения Ray vs KD-Tree не работает ⇐ C++

[Anonymous]

Краткий контекст
Я пишу базовый трассировщик пути на базе ЦП и в настоящее время пытаюсь реализовать ускоренную структуру данных "KD- Tree", чтобы ускорить пересечение Ray и Object.
Проблема
Пересечение Ray и KD-дерева. тест не работает. Я верю, что конструкция KD-Tree работает, однако я не совсем в этом уверен. Ниже я проведу небольшой тест, который, по-видимому, покажет, что дерево построено правильно.
Что я НЕ ищу
Что я НЕ ищу
Что я НЕ ищу
strong>
Я знаю, что моя текущая реализация KD-Tree не оптимизирована, и это нормально, потому что наивный вариант на данный момент достаточно хорош. Всегда можно провести оптимизацию, предварительно запустив ее.

Часть 1: реализация KD-Tree.
Насколько я понимаю, основная идея построения KD-дерева заключается в следующем.
Отправная точка: Набор треугольников, составляющих сетку, и пустой KdNode.

• Вычислить AABB, содержащий текущий набор треугольников . В самом начале это будет AABB полной сетки.
• Выберите ось разделения. В случае KD-дерева порядок разделения фиксирован. Я выбрал Y -> Z -> X. Кроме того, вычислите среднюю точку этой оси, которая будет использоваться для определения, на какой стороне выбранной оси находится треугольник.
• Разделить текущий набор треугольников на два подмножества, каждое из которых соответствует треугольникам, центр тяжести которых находится на одной стороне выбранной оси разделения.
• Рекурсивное построение дочерние узлы используют два новых подмножества треугольников.

Чтобы избежать построения огромных деревьев, я установил глубину предел для дерева, а также минимальный размер набора треугольников. Если мы зашли слишком глубоко в дерево, остановите рекурсию и создайте лист из оставшихся треугольников. Та же ситуация возникает, когда текущий набор треугольников слишком мал, поскольку в этот момент мы мало что получаем, например. разбиение 8 треугольников на два подмножества. Вероятно, нам лучше просто перебирать оставшиеся несколько треугольников, выполняя тесты пересечения Луча и треугольника для каждого из них.
Кроме того, обратите внимание, что я работа ТОЛЬКО с статическими сценами. Дерево KD создается до запуска трассировщика пути.
Класс KdNode

Код: Выделить всё

// KdNode.h
class KdNode {
public:
KdNode() = default;
~KdNode();

// Recursive build-function
KdNode* Build(std::vector& triangles, const int& depth);
bool IntersectsRay(const Ray& ray, HitPayload& hp) const;

bool IsLeaf{ false };

KdNode* left{ nullptr };
KdNode* right{ nullptr };

std::vector tris{};
AABB bbox{};
};

Построение дерева

Код: Выделить всё

// KdNode.cpp
KdNode* KdNode::Build(std::vector& triangles, const int& depth)
{
KdNode * const parent = new KdNode(); // TODO: Use smart pointers.

if (triangles.size() == 0)
return parent; // 

Подробнее здесь: [url]https://stackoverflow.com/questions/78343398/ray-vs-kd-tree-intersection-test-is-not-working[/url]