OpenWalnut  1.4.0
WKdTree.h
00001 //---------------------------------------------------------------------------
00002 //
00003 // Project: OpenWalnut ( http://www.openwalnut.org )
00004 //
00005 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
00006 // For more information see http://www.openwalnut.org/copying
00007 //
00008 // This file is part of OpenWalnut.
00009 //
00010 // OpenWalnut is free software: you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as published by
00012 // the Free Software Foundation, either version 3 of the License, or
00013 // (at your option) any later version.
00014 //
00015 // OpenWalnut is distributed in the hope that it will be useful,
00016 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 // GNU Lesser General Public License for more details.
00019 //
00020 // You should have received a copy of the GNU Lesser General Public License
00021 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
00022 //
00023 //---------------------------------------------------------------------------
00024 
00025 #ifndef WKDTREE_H
00026 #define WKDTREE_H
00027 
00028 #include <algorithm>
00029 #include <vector>
00030 
00031 #include "../common/WThreadedRunner.h"
00032 
00033 /**
00034  * implements the compare function for std::nth_element on a point array
00035  */
00036 struct lessy
00037 {
00038     float const * const data; //!< stores the pointer to the data array
00039     const int pos; //!< stores the axis at which the array is sorted
00040 
00041     /**
00042      * constructor
00043      * \param data pointer to the array
00044      * \param pos x,y or z axis
00045      */
00046     lessy( float const * const data, const int pos ) :
00047         data( data ), pos( pos )
00048     {
00049     }
00050 
00051     /**
00052      * comparison operator less
00053      * \param lhs
00054      * \param rhs
00055      * \return is lhs smaller than rhs
00056      */
00057     bool operator()( const unsigned int& lhs, const unsigned int& rhs ) const //NOLINT
00058     {
00059         return data[3 * lhs + pos] < data[3 * rhs + pos];
00060     }
00061 };
00062 
00063 /**
00064  * class to provide threaded computation of parts of the kd tree
00065  */
00066 class WKdTreeThread: public WThreadedRunner
00067 {
00068 public:
00069     /**
00070      * constructor
00071      *
00072      * \param pointArray
00073      * \param tree pointer to the tree
00074      * \param left boundary of the part to compute
00075      * \param right boundary of the part to compute
00076      * \param axis starting axis
00077      */
00078     WKdTreeThread( float* pointArray, std::vector< unsigned int >* tree, int left, int right, int axis );
00079 
00080     /**
00081      *  recursive function to compute a part of the kd tree
00082      *
00083      *  \param left
00084      *  \param right
00085      *  \param axis
00086      */
00087     void buildTree( int left, int right, int axis );
00088 
00089     /**
00090      * entry for the run command
00091      */
00092     virtual void threadMain();
00093 
00094     std::vector< unsigned int >* m_tree; //!< stores a pointer to the tree
00095     float *m_pointArray; //!< stores a pointer to the vertex array
00096 
00097     int m_left; //!< stores left boundary, since the threadMain method has no arguments
00098     int m_right; //!< stores left boundary, since the threadMain method has no arguments
00099     int m_axis; //!< stores axis, since the threadMain method has no arguments
00100 };
00101 
00102 /**
00103  * implements the computation of a kd tree on a point array
00104  */
00105 class WKdTree
00106 {
00107 public:
00108     /**
00109      * constructor
00110      *
00111      * \param size
00112      * \param pointArray
00113      */
00114     WKdTree( int size, float* pointArray );
00115 
00116     /**
00117      * destructor
00118      */
00119     ~WKdTree();
00120 
00121     std::vector< unsigned int > m_tree; //!< stores the tree
00122 
00123 private:
00124     /**
00125      *  recursive function to compute a part of the kd tree
00126      *
00127      *  \param left
00128      *  \param right
00129      *  \param axis
00130      */
00131     void buildTree( int left, int right, int axis );
00132     int m_size; //!< size of the tree
00133     unsigned int m_root; //!< index of the root point
00134     float *m_pointArray; //!< stores a pointer to the vertex array
00135 };
00136 
00137 #endif  // WKDTREE_H