src/rcrt/BIHNode.hpp

Go to the documentation of this file.

#ifndef BIHNODE_HPP_
#define BIHNODE_HPP_

#include <iostream>
#include <limits>
#include <algorithm>
#include <stdexcept>
#include <vector>
#include "Traceable.h"
#include "primitives/AABB.h"
#include "loaders/conversion.hpp"

namespace rcrt
{

class BIHSplit
{
public:
        float split;
        Axis axis;
        
        BIHSplit(float s, Axis ax) : split(s), axis(ax)
        {}
};


template<class T>
class BIHNode
{
private:
        BIHNode<T>* children[2];
        
        std::vector<T*>* traceables;
        
        int leftIndex;
        
        int rightIndex;
        
        float clip[2];
        
        Axis splitAxis;
        
        
        Intersection leafIntersect(Ray& r, const float& tMin, const float& tMax) const
        {
                Intersection hit;
                if(leftIndex > rightIndex)//sanity check for an empty/invalid node
                        return hit;
                for(int i = leftIndex; i < rightIndex+1; i++){
                        float rmin = r.minDist();
                        float rmax = r.maxDist();
                        r.setMinDist(std::max(tMin,rmin));
                        r.setMaxDist(std::min(tMax,rmax));//set values for intersecting
                        Intersection curr = traceables->at(i)->intersect(r);
                        r.setMaxDist(rmax);//reset values for next intersection
                        r.setMinDist(rmin); 
                        if(curr.isValid()){
                                if(curr.getDistance() < hit.getDistance()){
                                        hit = curr;//current is nearer
                                }
                                if(curr.getDistance() < r.maxDist())
                                        r.setMaxDist(curr.getDistance());//a valid intersection limits the ray
                        }
                                        
                }
                return hit;
                
        }
        
        void initNodeAsLeaf(std::vector<T*>* trList, int left, int right)
        {
                children[0] = children[1] = 0;
                clip[0] = clip[1] = 0;
                traceables = trList;
                leftIndex = left;
                rightIndex = right;
                splitAxis = X_AXIS;
        }
        
        void initNode(const AABB& bbox, std::vector<T*>* trList, int left, int right, int depth, int singleDepth = 0)
        {
                int n = right-left+1;
                int MAXDEPTH = 100;//TODO make MAXDEPTH a parameter on construction
                int MAXSINGLED = 12;//TODO make MAXSINGLED a parameter on construction
                if(n <= 0){//this would be an error in the code, cannot occur currently :)
                        throw std::runtime_error("[BIH-Build] - error: indices overlap: left=" + toString(left) + " right=" + toString(right));
                }
                else if(n == 1 || depth > MAXDEPTH || singleDepth > MAXSINGLED){
                        //we'll create a leaf
                        initNodeAsLeaf(trList,left,right);
                        return;
                }
                else {
                        //get the split plane = middle of major axis of the bbox
                        BIHSplit sp = getSplitPlane(bbox);
                        
                        //partition trList[left...right] based on the BIHSplit
                        int i = left;
                        int j = right;
                        
                        //keep track of minimum and maximum of left and right elements
                        float minL = std::numeric_limits<float>::infinity();
                        float minR = std::numeric_limits<float>::infinity();
                        float maxL = -std::numeric_limits<float>::infinity();
                        float maxR = -std::numeric_limits<float>::infinity();
                        
                        while(i <= j){
                                const AABB& box = trList->at(i)->getBoundingBox();
                                
                                //get the centroid of the current element
                                float pos = trList->at(i)->getCentroid()[sp.axis];
                                float minB = box.getMin(sp.axis);
                                float maxB = box.getMax(sp.axis);
                                if(pos <= sp.split){//element is left
                                        //update minimum and maximum
                                        minL = std::min(minB, minL);
                                        maxL = std::max(maxB, maxL);
                                        i++;
                                } else {//element must be swapped to right
                                        minR = std::min(minB, minR);//update
                                        maxR = std::max(maxB, maxR);
                                        if(i != j){
                                                T* currL = trList->at(i);
                                                (*trList)[i] = trList->at(j);
                                                (*trList)[j] = currL;
                                        }
                                        j--;
                                }
                        }
                        // here i = j+1 and i is the leftmost element of the right interval                     
                        
                        
                        //create bounding boxes for the child nodes
                        //this implements the global heuristic as described
                        //in the BIH paper because we always split along 
                        //the middle of the largest axis of the bbox
                        //and do not modify our boxes in any other way
                        //shrinking the boxes to the contained objects
                        //did not provide better performance, leads to
                        //an inefficient clipping of empty space
                        Point3D minRP = bbox.getMinP();
                        minRP[sp.axis] = sp.split;
                        Point3D maxRP = bbox.getMaxP();
                        
                        Point3D minLP = bbox.getMinP();
                        Point3D maxLP = bbox.getMaxP();
                        maxLP[sp.axis] = sp.split;
                        
                        AABB leftB(minLP,maxLP);
                        AABB rightB(minRP,maxRP);
                        
                        //initialize values of this node
                        splitAxis = sp.axis;
                        leftIndex = left;
                        rightIndex = right;
                
                        if(i > right){//no right child
                                //create a "single" node with different clipping 
                                clip[0] = minL;
                                clip[1] = maxL;                         
                                children[0] = new BIHNode(leftB,trList,left,right,depth+1, singleDepth + 1);
                                children[1] = 0;
                        }
                        else if(i <= left){//no left child
                                //create a "single" node with different clipping
                                clip[0] = minR;
                                clip[1] = maxR;
                                children[0] = new BIHNode(rightB,trList,left,right,depth+1, singleDepth +1);
                                children[1] = 0;

                        } else {//generate standard node and recurse
                                clip[0] = maxL;
                                clip[1] = minR;                         
                                children[0] = new BIHNode(leftB,trList,left,i-1,depth+1);
                                children[1] = new BIHNode(rightB,trList,i,right,depth+1);
                        }
                }
        }
        
public:
        BIHNode<T>()//empty node
        {
                children[0] = children[1] = 0;
                splitAxis = X_AXIS;
                clip[0] = clip[1] = 0;
                leftIndex = -1; rightIndex = -2;
        }
        
        BIHNode<T>(const AABB& bbox, std::vector<T*>* trList, int left, int right, int depth = 0, int singleD = 0)
        {
                initNode(bbox, trList, left, right, depth, singleD);
        }
        
        virtual ~BIHNode()
        {
                if(children[0] != 0) delete children[0];
                if(children[1] != 0) delete children[1];
        }
        
        
        virtual Intersection intersect(Ray& r, const float& tMin, const float& tMax) const
        {
#if 0
                r.bihnodes++;//enable this for the BIHTracer, only for debugging purposes
#endif
                
                if(isLeaf()){
                        return leafIntersect(r, tMin, tMax);
                }
                //we intersect the ray against both splitting planes in this node
                float dir = r.dir()[splitAxis];
                float org = r.org()[splitAxis];
                float t[2];
                float invdir = r.invDir()[splitAxis];//use precalculated values
                int near = r.dirSign()[splitAxis];//can encode which node is
                int far = 1 - near;//near with the sign of the direction along the axis
                t[0] = (clip[0]-org)*invdir;//calculated the distances
                t[1] = (clip[1]-org)*invdir;
                
                
                if(dir != 0) {//if the direction is 0 invDir will be NaN, just intersect with both in that case
                        if(isSingle()){//special single node intersection
                                if(t[near] > tMax || t[far] < tMin)
                                        return Intersection();
                                else {//has only one child
                                        return children[0]->intersect(
                                                        r, std::max(t[near], tMin), std::min(t[far], tMax));
                                }
                        }
                        if(t[near] < tMin && t[far] > tMax){
                                //ray segment between clip zones
                                return Intersection();
                        }
                        if(t[near] < tMin){
                                //ray segment only through far node
                                if(t[far] > tMin){//adapt current ray segment
                                        Intersection is(children[far]->intersect(r, t[far], tMax));
                                        if(is.isValid() && is.getDistance() < r.maxDist())
                                                r.setMaxDist(is.getDistance());//update r.maxDist for valid intersections
                                        return is;
                                } else {
                                        return children[far]->intersect(r, tMin, tMax);
                                }
                        }
                        if(t[far] > tMax){
                                //ray segment only through near node
                                if(t[near] < tMax){//adapt current ray segment
                                        Intersection is(children[near]->intersect(r, tMin, t[near]));
                                        if(is.isValid() && is.getDistance() < r.maxDist())
                                                r.setMaxDist(is.getDistance());
                                        return is;
                                } else {
                                        return children[near]->intersect(r, tMin, tMax);
                                }
                        }
                }
                // ray segment through both nodes       

                if(isSingle()){//special single case
                        return children[0]->intersect(
                                        r, std::max(t[near], tMin), std::min(t[far], tMax));
                }
                
                Intersection isN, isF;
                //go through near node
                isN = children[near]->intersect(r, tMin, tMax);

                if(isN.isValid() && isN.getDistance() < r.maxDist())
                        r.setMaxDist(isN.getDistance());
        
                // go through far node  
                isF = children[far]->intersect(r, tMin, tMax);
                
                const bool valN = isN.isValid();
                const bool valF = isF.isValid();
                
                //check for the intersection that is the nearest and valid
                if(valN && valF){
                        if(isN.getDistance() < isF.getDistance()){
                                return isN;
                        }
                        return isF;
                }
                if(!(valN || valF)){
                        return Intersection();
                }
                if(!valN)
                        return isF;
                else
                        return isN;
        }
        
        bool isLeaf() const
        {
                return children[0] == 0 && children[1] == 0;
        }
        
        bool isSingle() const
        {
                return children[0] != 0 && children[1] == 0;
        }
        
        bool isEmpty() const
        {
                return traceables == 0 || traceables.empty();
        }
        
        std::vector<T*>* getTraceables()
        {
                return traceables;
        }
        
        static BIHSplit getSplitPlane(const AABB& box)
        {
                Axis a = box.getMainAxis();
                return BIHSplit(box.getCentroid()[a], a);
        }
        
};

}

#endif /*BIHNODE_HPP_*/

---