bvh.h

/*
    This file is part of Nori, a simple educational ray tracer
 
    Copyright (c) 2015 by Wenzel Jakob, Romain Prévost
 
    Nori is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License Version 3
    as published by the Free Software Foundation.
 
    Nori is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
    along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
 
#if !defined(__NORI_BVH_H)
#define __NORI_BVH_H
 
#include <nori/shape.h>
 
NORI_NAMESPACE_BEGIN
 
class BVH {
    friend class BVHBuildTask;
public:
    BVH() { m_shapeOffset.push_back(0u); }
 
    virtual ~BVH() { clear(); };
 
    void clear();
 
    void addShape(Shape *shape);
 
    void build();
 
    bool rayIntersect(const Ray3f &ray, Intersection &its, 
        bool shadowRay = false) const;
 
    uint32_t getShapeCount() const { return (uint32_t) m_shapes.size(); }
 
    uint32_t getPrimitiveCount() const { return m_shapeOffset.back(); }
 
    Shape *getShape(uint32_t idx) { return m_shapes[idx]; }
    
    const Shape *getShape(uint32_t idx) const { return m_shapes[idx]; }
 
    const BoundingBox3f &getBoundingBox() const {
        return m_bbox;
    }
 
protected:
    uint32_t findShape(uint32_t &idx) const {
        auto it = std::lower_bound(m_shapeOffset.begin(), m_shapeOffset.end(), idx+1) - 1;
        idx -= *it;
        return (uint32_t) (it - m_shapeOffset.begin());
    }
 
    BoundingBox3f getBoundingBox(uint32_t index) const {
        uint32_t shapeIdx = findShape(index);
        return m_shapes[shapeIdx]->getBoundingBox(index);
    }
    
    Point3f getCentroid(uint32_t index) const {
        uint32_t shapeIdx = findShape(index);
        return m_shapes[shapeIdx]->getCentroid(index);
    }
 
    std::pair<float, uint32_t> statistics(uint32_t index = 0) const;
 
    /* BVH node in 32 bytes */
    struct BVHNode {
        union {
            struct {
                unsigned flag : 1;
                uint32_t size : 31;
                uint32_t start;
            } leaf;
 
            struct {
                unsigned flag : 1;
                uint32_t axis : 31;
                uint32_t rightChild;
            } inner;
 
            uint64_t data;
        };
        BoundingBox3f bbox;
 
        bool isLeaf() const {
            return leaf.flag == 1;
        }
 
        bool isInner() const {
            return leaf.flag == 0;
        }
 
        bool isUnused() const {
            return data == 0;
        }
 
        uint32_t start() const {
            return leaf.start;
        }
 
        uint32_t end() const {
            return leaf.start + leaf.size;
        }
    };
private:
    std::vector<Shape *> m_shapes;       
    std::vector<uint32_t> m_shapeOffset; 
    std::vector<BVHNode> m_nodes;       
    std::vector<uint32_t> m_indices;    
    BoundingBox3f m_bbox;               
};
 
NORI_NAMESPACE_END
 
#endif /* __NORI_BVH_H */