KDTree 3D by splitting using mid point : Bounding Box Intersection gives me artifacts

Question

Hi am writing my Ray Tracing code. I am mostly done with my experiments and now trying to optimize it for best speed. So am implementing KDTree and splitting the triangles using mid point. Without KDTree my result was fine, but with KDtree am getting some artifacts in the output. I am not getting any clue on where am going wrong.

Before KDTree

After KDTree

My KDTree code is here:

#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

Finally found the issue in my code.

1) Longest Axis based splitting contributed to the slow traversing. The KDTree construction actually did not happen efficiently or did not happen at all for some situations.

2) The Bounding Box calculation gave me the artifacts. After trying out many different code from papers and books, found the Most efficient and best Ray-boundingbox intersection test algorithm.