LBKdTree.hpp

Go to the documentation of this file.

#ifndef __LBKDTREE_HPP
#define __LBKDTREE_HPP


#include "lvr2/geometry/LBPointArray.hpp"

#include <ctpl.h>

#include <stdlib.h>
#include <math.h>
#include <list>
#include <unordered_set>

#include <boost/shared_ptr.hpp>

namespace lvr2
{

class LBKdTree {
public:

    LBKdTree( LBPointArray<float>& vertices , int num_threads=8);

    ~LBKdTree();

    void generateKdTree( LBPointArray<float>& vertices );

    boost::shared_ptr<LBPointArray<float> > getKdTreeValues();

    boost::shared_ptr<LBPointArray<unsigned char> > getKdTreeSplits();

private:

    void generateKdTreeArray(LBPointArray<float>& V,
            LBPointArray<unsigned int>* sorted_indices,
            int max_dim);

    boost::shared_ptr<LBPointArray<float> > m_values;

    // split dim 4 dims per split_dim
    boost::shared_ptr<LBPointArray<unsigned char> > m_splits;

    // Static member

    static int st_num_threads;
    static int st_depth_threads;

    static ctpl::thread_pool *pool;

    static void fillCriticalIndices(const LBPointArray<float>& V,
            LBPointArray<unsigned int>& sorted_indices,
            unsigned int current_dim,
            float split_value, unsigned int split_index,
            std::list<unsigned int>& critical_indices_left,
            std::list<unsigned int>& critical_indices_right);

    static void fillCriticalIndicesSet(const LBPointArray<float>& V,
            LBPointArray<unsigned int>& sorted_indices,
            unsigned int current_dim,
            float split_value, unsigned int split_index,
            std::unordered_set<unsigned int>& critical_indices_left,
            std::unordered_set<unsigned int>& critical_indices_right);


    static void generateKdTreeRecursive(int id, LBPointArray<float>& V,
            LBPointArray<unsigned int>* sorted_indices, int current_dim, int max_dim,
            LBPointArray<float> *values, LBPointArray<unsigned char> *splits,
            int size, int max_tree_depth, int position, int current_depth);

    static void test(int id, LBPointArray<float>* sorted_indices);


};

}  /* namespace lvr2 */

#endif // !__LBKDTREE_HPP