OpenWalnut
1.4.0
|
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