遍历KDTree

Question

当我试图渲染一个场景时，我的渲染有一些问题。

这是我的遍历算法：

bool KDTree::traverse(Ray &ray, Node &node, double &tMin, double     &tMax, double &tNear, double &u, double &v, Triangle* &hitObject)
{
if(node.tris.size() == 0) return 0;

bool current = false;
//bool intersected = false;
if(!node.isLeaf)
{
    int axis = node.split_axis;
    double tSplit = (node.split_pos - ray.orig[axis]) / ray.dir[axis];
    Node* nearNode = ray.orig[axis] < node.split_pos ? node.leftNode : node.rightNode;
    Node* farNode = ray.orig[axis] < node.split_pos ? node.rightNode : node.leftNode;

    if (tSplit > tMax)
        return traverse(ray, *nearNode , tMin, tMax, tNear, u, v, hitObject);//case A
    else if (tSplit < tMin)
    {
        if(tSplit>0)
            return traverse(ray, *farNode, tMin, tMax, tNear, u, v, hitObject);//case B
        else if(tSplit<0)
                return traverse(ray, *nearNode, tMin, tMax, tNear, u, v, hitObject);//case C
        else
        {//tSplit==0
            if(ray.dir[axis]<0)
                return traverse(ray, *farNode, tMin, tMax, tNear, u, v, hitObject);//case D
            else
                return traverse(ray, *nearNode, tMin, tMax, tNear, u, v, hitObject);//case E
        }
    }
    else
    {
        if(tSplit>0)
        {//case F
            current = traverse(ray, *nearNode, tMin, tSplit, tNear, u, v, hitObject);
            if (current != false)
                return current;
            else
                return traverse(ray, *farNode, tSplit, tMax, tNear, u, v, hitObject);
        }
        else
        {
            return traverse(ray, *nearNode,tSplit, tMax, tNear, u, v, hitObject);//case G
        }
    }
}
else
{
    tNear = 9999999;

    for(unsigned int i = 0; i < node.tris.size(); ++i)
    {
        double t = 9999999;
        if(node.tris[i]->intersect(ray, t, u, v) && t < tNear)
        {
            hitObject = node.tris[i];
            tNear = t;
        }
    }

    return (hitObject != nullptr);
}   
}

这是我的构建算法：

void KDTree::buildkdtree(Node &node)
{
std::cout << "stò inizializzando il nodo di profondità: " << node.depth << std::endl;
if(node.tris.size() <= 30 || node.depth >= 15)
{
    std::cout << "ho creato una foglia di livello: " << node.depth << " , con " << node.tris.size() << " triangoli" << std::endl;
    node.isLeaf = true;
    return;
}

int axis = (node.depth % 3);
std::vector<Vec3d> midPoints;
for(unsigned int i = 0; i < node.tris.size(); ++i)
{
    midPoints.push_back(node.tris[i]->getMidPoint());
}
std::vector<double> mid;
node.split_axis = axis;
node.rightNode = new struct Node;
node.leftNode = new struct Node;
double max, min, med;
switch(node.split_axis)
{
    case(0):
        std::cout << "splitto su x" << std::endl;
        for(unsigned int i = 0; i < midPoints.size(); ++i)
        {
            mid.push_back(midPoints[i].x);
        }

        std::sort(mid.begin(), mid.end());

        if(mid.size() % 2 == 0)
            med = (mid[mid.size()/2 - 1] + mid[mid.size()/2]) / 2;
        else
            med = mid[mid.size()/2];

        node.split_pos = med;

        std::cout << "l'intervallo e': (" << node.bbox->xMin << " ," << node.bbox->xMax << ")\n";
        std::cout << "split_pos = " << node.split_pos << std::endl;

        node.rightNode->bbox = new Bbox(node.bbox->xMax, node.split_pos, node.bbox->yMax, node.bbox->yMin, node.bbox->zMax, node.bbox->zMin);
        node.leftNode->bbox = new Bbox(node.split_pos, node.bbox->xMin, node.bbox->yMax, node.bbox->yMin, node.bbox->zMax, node.bbox->zMin);

        for(unsigned int i = 0; i < node.tris.size(); ++i)
        {
            node.tris[i]->getExtreme(max, min, axis);
            if(min <= node.split_pos)
                node.leftNode->tris.push_back(node.tris[i]);
            if(max >= node.split_pos)
                node.rightNode->tris.push_back(node.tris[i]);
        }
    break;

    case(1):
        std::cout << "splitto su y" << std::endl;
        for(unsigned int i = 0; i < midPoints.size(); ++i)
        {
            mid.push_back(midPoints[i].y);
        }

        std::sort(mid.begin(), mid.end());

        if(mid.size() % 2 == 0)
            med = (mid[mid.size()/2 - 1] + mid[mid.size()/2]) / 2;
        else
            med  = mid[mid.size()/2];

        node.split_pos = med;

        std::cout << "l'intervallo e': (" << node.bbox->yMin << " ," << node.bbox->yMax << ")\n";
        std::cout << "split_pos = " << node.split_pos << std::endl;

        node.rightNode->bbox = new Bbox(node.bbox->xMax, node.bbox->xMin, node.split_pos, node.bbox->yMin, node.bbox->zMax, node.bbox->zMin);
        node.leftNode->bbox = new Bbox(node.bbox->xMax, node.bbox->xMin, node.bbox->yMax, node.split_pos, node.bbox->zMax, node.bbox->zMin);

        for(unsigned int i = 0; i < node.tris.size(); ++i)
        {
            node.tris[i]->getExtreme(max, min, axis);
            if(min <= node.split_pos)
                node.leftNode->tris.push_back(node.tris[i]);
            if(max >= node.split_pos)
                node.rightNode->tris.push_back(node.tris[i]);
        }
    break;

    case(2):
        std::cout << "splitto su z" << std::endl;
        for(unsigned int i = 0; i < midPoints.size(); ++i)
        {
            mid.push_back(midPoints[i].z);
        }

        std::sort(mid.begin(), mid.end());

        if(mid.size() % 2 == 0)
            med = (mid[mid.size()/2 - 1] + mid[mid.size()/2]) / 2;
        else
            med  = mid[mid.size()/2];

        node.split_pos = med;

        std::cout << "l'intervallo e': (" << node.bbox->zMin << " ," << node.bbox->zMax << ")\n";
        std::cout << "split_pos = " << node.split_pos << std::endl;

        node.rightNode->bbox = new Bbox(node.bbox->xMax, node.bbox->xMin, node.bbox->yMax, node.bbox->yMin, node.split_pos, node.bbox->zMin);
        node.leftNode->bbox = new Bbox(node.bbox->xMax, node.bbox->xMin, node.bbox->yMax, node.bbox->yMin, node.bbox->zMax, node.split_pos);

        for(unsigned int i = 0; i < node.tris.size(); ++i)
        {
            node.tris[i]->getExtreme(max, min, axis);
            if(min <= node.split_pos)
                node.leftNode->tris.push_back(node.tris[i]);
            if(max >= node.split_pos)
                node.rightNode->tris.push_back(node.tris[i]);
        }
    break;

    default:
        std::cout << "Errore, non ho uno dei tre assi" << std::endl;
    break;
}

std::cout << "i " << node.tris.size() << " triangoli del padre sono stati divisi così\n";
std::cout << node.rightNode->tris.size() << " nel nodo di destra\n";
std::cout << node.leftNode->tris.size() << " nel nodo di sinistra\n" << std::endl;

node.rightNode->depth = node.depth + 1;
node.leftNode->depth = node.depth + 1;

std::cout << "sto processando figlio di destra del nodo di profondità: " << node.depth << std::endl;
buildkdtree(*(node.rightNode));
std::cout << "sto processando figlio di sinistra del nodo di profondità: " << node.depth << std::endl;
buildkdtree(*(node.leftNode));}

有人能帮我吗？

PS:这是我得到的图像：

​

​

Answer 1

我写射线追踪器的时候也有同样的问题。实际上，问题可能在构建代码中，或者在遍历代码中。考虑一下，如果您构建了一个糟糕的树，一个“正确”的遍历也会导致工件。

我在射线追踪器的基础上构建了一个简单的OpenGL渲染器，从而发现了这个问题。这涉及以下方面：

1. 创建一个OpenGL呈现实例，并将其提供给您的场景和摄像机信息。看起来你只有三角形和一两个光，所以这应该很容易。OpenGL为我们的目的提供了一个很好的近似。
2. 使用GLUT创建一个输出窗口，并在一个连续的呈现循环中显示OpenGL输出。修改输出窗口，使其接受用户输入(键盘、鼠标等)，以移动相机的位置和方向。
3. 修改OpenGL呈现器，以绘制所有KDNode边框。使包围盒半透明。
4. 创建第二个包含树控件的窗口。将KDTree绑定到树控件，以便KDTree中的每个元素都对应于树控件中的一个节点。您现在应该能够直观地检查您的KDTree了。
5. 修改树窗口，以便接受用户输入以选择、展开和折叠节点。
6. 修改您的OpenGL渲染器，使当前选定的treenode( KDNode )边界框和分配给该KDNode的三角形以特殊颜色绘制。

现在，通过在树窗口中选择一个节点，您可以看到相关的KDNode的边界框，以及分配给KDNode的三角形，并且您可以移动摄像机来验证您认为分配给KDNode的三角形实际上是分配给节点的。

当我第一次这么做的时候，我惊讶地发现，我对这棵树的心智模型与我的算法所创造的是多么的不同。使用此工具，您应该能够验证您的构建代码正在执行您认为它正在做的事情。您还可以使用它对构建代码的参数进行微调，以获得更有效的树。

您的输出窗口应该如下所示(米歇尔·博西提供)：

​

​

编辑：另一个例子由李一宁提供

编辑:阿波罗·埃利斯提供的第三个例子