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"