c++ - KDTree 3D 通过使用中点 : Bounding Box Intersection gives me artifacts split

Question

大家好，我正在编写我的光线追踪代码。我基本上完成了我的实验，现在正在尝试优化它以获得最佳速度。因此，我正在实现 KDTree 并使用中点拆分三角形。没有 KDTree，我的结果很好，但是有了 KDtree，我在输出中得到了一些伪像。我不知道哪里出了问题。

在 KDTree 之前

KDTree之后

我的 KDTree 代码在这里:

#include "sgrender.h"

#ifndef KDNODE_H_
#define KDNODE_H_

using namespace std;

struct KDNode {
    BoundingBox bbox;
    KDNode* left;
    KDNode* right;
    vector<Shape*> objects;

    KDNode() {
        bbox = BoundingBox();
    }

    void addObject(Shape*& obj) {
        objects.push_back(obj);
        bbox.expand(obj->bbox);
    }

    void build() {
        printf("Building\n");
        if(objects.size() <= 1)
            return;

        left = new KDNode();
        right = new KDNode();

        Vec midpt = Vec(0, 0, 0);
        for(int i = 0; i < objects.size(); i++)
            midpt = midpt + objects[i]->midpt;

        midpt = midpt * (1.0/ objects.size());

        int axis = bbox.longestAxis();

        for(int i = 0; i < objects.size(); i++) {
            switch(axis) {
                case 0:
                    if(midpt.x > objects[i]->midpt.x)
                        right->addObject(objects[i]);
                    else
                        left->addObject(objects[i]);
                    break;
                case 1:
                    if(midpt.y > objects[i]->midpt.y)
                        right->addObject(objects[i]);
                    else
                        left->addObject(objects[i]);
                    break;
                case 2:
                    if(midpt.z > objects[i]->midpt.z)
                        right->addObject(objects[i]);
                    else
                        left->addObject(objects[i]);
                    break;
            }
        }

        if(left->objects.size() && right->objects.size()) {
            left->build();
            right->build();
        }
    }

    Shape* intersect(Ray r, double &depth) {
        Shape *shape = NULL;

        if(DISABLE_KDTREE) {
            for(int i = 0; i < objects.size(); i++) {
                double d = objects[i]->intersect(r);
                if(d > 0 && d < depth) {
                    depth = d;
                    shape = objects[i];
                }
            }
        } else if(bbox.intersect(r)) {
            if((left && left->objects.size() > 0) || (right && right->objects.size() > 0)) {
                double d = depth;
                if(right && right->objects.size() > 0) {
                    Shape *rshape = right->intersect(r, d);
                    if(rshape && d > 0 && d < depth) {
                        shape = rshape;
                        depth = d;
                    }
                }
                if(left && left->objects.size() > 0) {
                    Shape *lshape = left->intersect(r, d);
                    if(lshape && d > 0 && d < depth) {
                        shape = lshape;
                        depth = d;
                    }
                }
            } else {
                for(int i = 0; i < objects.size(); i++) {
                    double d = objects[i]->intersect(r);
                    if(d > 0 && d < depth) {
                        depth = d;
                        shape = objects[i];
                    }
                }
            }
        }
        return shape;
    }
};

#endif

Answer 1

终于在我的代码中找到了问题。

1) 基于最长轴的拆分导致了缓慢的遍历。在某些情况下，KDTree 构造实际上并没有有效地发生或根本没有发生。

2) 边界框计算给了我伪影。在从论文和书籍中尝试了许多不同的代码后，找到了 Most efficient and best Ray-boundingbox intersection测试算法。