Где мой код обхода дерева kd неверен?

Я оптимизировал мой c ++ raytracer. Я отслеживаю отдельные лучи через kdtrees. До сих пор я использовал рекурсивный алгоритм Хаврана «B», который кажется устаревшим и преувеличенным для ООП. Мой новый код настолько короток, насколько это возможно (и, надеюсь, его легче оптимизировать с помощью компилятора и легче поддерживать):

    struct StackElement{
KDTreeNode<PT>* node;
float tmax;
array<float, 3> origin;
};

//initializing explicit stack
stack<StackElement> mystack;

//initialize local variables
KDTreeNode<PT>* node = tree.root;
array<float, 3> origin {ray.origin[0], ray.origin[1], ray.origin[2]};
const array<float, 3> direction {ray.direction[0], ray.direction[1], ray.direction[2]};
const array<float, 3> invDirection {1.0f / ray.direction[0], 1.0f / ray.direction[1], 1.0f / ray.direction[2]};
float tmax = numeric_limits<float>::max();
float tClosestIntersection = numeric_limits<float>::max();
bool notFullyTraversed = true;

while(notFullyTraversed) {
if (node->isLeaf()) {

//test all primitives inside the leaf
for (auto p : node->primitives()) {
p->intersect(ray, tClosestIntersection, intersection, tmax);
}

//test if leaf + empty stack => return
if (nodeStack.empty()) {
notFullyTraversed = false;
} else {
//pop all stack
origin = mystack.top().origin;
tmax = mystack.top().tmax;
node = mystack.top().node;
mystack.pop();
}
} else {
//get axis of node and its split plane
const int axis = node->axis();
const float plane = node->splitposition();

//test if ray is not parallel to plane
if ((fabs(direction[axis]) > EPSILON)) {
const float t = (plane - origin[axis]) * invDirection[axis];

//case of the ray intersecting the plane, then test both childs
if (0.0f < t && t < tmax) {
//traverse near first, then far. Set tmax = t for near
tmax = t;
//push only far child onto stack
mystack.push({
(origin[axis] > plane )  ? node->leftChild() : node->rightChild() ,
tmax - t,
{origin[0] + direction[0] * t, origin[1] + direction[1] * t, origin[2] + direction[2] * t}
});
}
}
//in every case: traverse near child first
node = (origin[axis] > plane) ? node->rightChild() : node->leftChild();

}
}

return intersection.found;

Это не пересекает дальнего ребенка достаточно часто. Где я могу пропустить связанный случай?

-2

Решение

Одна проблема была маленькой (оригинал, неправильный код):

      //traverse near first, then far. Set tmax = t for near
tmax = t;
//push only far child onto stack
mystack.push({ ... , tmax - t,  ...    });

он всегда помещает 0.0f в стек в качестве расстояния выхода для дальнего узла, что означает, что для пересечений положительный t не принимается.

Перестановка обеих строк решает эту проблему.

Моя трассировка / решения в стеке по-прежнему отличаются (Havran выполняет примерно на 25% больше итераций) с выходным изображением, имеющим 99,5% тех же пикселей. Это проблема округления с плавающей запятой, но она все еще не отвечает на вопрос: какой случай не распознается этой упрощенной реализацией? Или какая операция не является (численно) достаточно стабильной в этой версии?

0

Другие решения


По вопросам рекламы [email protected]