BVH.hpp

Go to the documentation of this file.

 
/*
 * BVH.hpp
 *
 *  @date 21.01.2018
 *  @author Johan M. von Behren <johan@vonbehren.eu>
 */
 
#pragma once
 
#include <vector>
#include <memory>
 
#include "lvr2/geometry/BoundingBox.hpp"
#include "lvr2/geometry/Normal.hpp"
 
using std::unique_ptr;
using std::vector;
using std::pair;
 
namespace lvr2
{
 
template<typename BaseVecT>
class BVHTree
{
public:
 
    BVHTree(const vector<float>& vertices, const vector<uint32_t>& faces);
 
    BVHTree(
        const floatArr vertices, size_t n_vertices,
        const indexArray faces, size_t n_faces
    );
 
    BVHTree(const MeshBufferPtr mesh);
 
    const vector<uint32_t>& getTriIndexList() const;
 
    const vector<float>& getLimits() const;
 
    const vector<uint32_t>& getIndexesOrTrilists() const;
 
    const vector<float>& getTrianglesIntersectionData() const;
 
private:
 
    // Internal triangle representation
    struct Triangle {
 
        Triangle();
 
        // indices in vertex array
        // todo: not used?
        uint32_t idx1;
        uint32_t idx2;
        uint32_t idx3;
 
        BaseVecT center;
        Normal<float> normal;
 
        // intersection pre-computed cache
        float d, d1, d2, d3;
        Normal<float> e1, e2, e3;
 
        // todo: not used?
        BoundingBox<BaseVecT> bb;
    };
 
    // Internal AABB representation
    struct AABB {
        BoundingBox<BaseVecT> bb;
 
        // Triangles corresponding to this AABB
        vector<size_t> triangles;
    };
 
    // Abstract tree node
    struct BVHNode {
        BoundingBox<BaseVecT> bb;
        virtual bool isLeaf() = 0;
    };
    using BVHNodePtr = unique_ptr<BVHNode>;
 
    // Inner tree node
    struct BVHInner: BVHNode {
 
        // Left sub tree
        BVHNodePtr left;
 
        // Right sub tree
        BVHNodePtr right;
        virtual bool isLeaf() { return false; }
    };
    using BVHInnerPtr = unique_ptr<BVHInner>;
 
    // Leaf tree node
    struct BVHLeaf: BVHNode {
 
        // Triangles corresponding to this leaf node
        vector<size_t> triangles;
        virtual bool isLeaf() { return true; }
    };
    using BVHLeafPtr = unique_ptr<BVHLeaf>;
 
    // working variables for tree construction
    BVHNodePtr m_root;
    vector<Triangle> m_triangles;
 
    // cache friendly data for the SIMD device
    vector<uint32_t> m_triIndexList;
    vector<float> m_limits;
    vector<uint32_t> m_indexesOrTrilists;
    vector<float> m_trianglesIntersectionData;
 
    BVHNodePtr buildTree(const vector<float>& vertices, const vector<uint32_t>& faces);
 
    BVHNodePtr buildTree(
        const floatArr vertices, size_t n_vertices,
        const indexArray faces, size_t n_faces
    );
 
    BVHNodePtr buildTreeRecursive(vector<AABB>& work, uint32_t depth = 0);
 
    void createCFTree();
 
    void createCFTreeRecursive(BVHNodePtr currentNode, uint32_t& idxBoxes);
 
    void convertTrianglesIntersectionData();
};
 
} /* namespace lvr2 */
 
#include "lvr2/geometry/BVH.tcc"