OpenWalnut  1.2.5
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
WKdTree.cpp
1 //---------------------------------------------------------------------------
2 //
3 // Project: OpenWalnut ( http://www.openwalnut.org )
4 //
5 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
6 // For more information see http://www.openwalnut.org/copying
7 //
8 // This file is part of OpenWalnut.
9 //
10 // OpenWalnut is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU Lesser General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // OpenWalnut is distributed in the hope that it will be useful,
16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU Lesser General Public License for more details.
19 //
20 // You should have received a copy of the GNU Lesser General Public License
21 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
22 //
23 //---------------------------------------------------------------------------
24 
25 #include <algorithm>
26 #include <vector>
27 
28 #include "../common/WAssert.h"
29 #include "../common/WLogger.h"
30 
31 #include "WKdTree.h"
32 
33 WKdTree::WKdTree( int size, float *pointArray ) :
34  m_size( size ), m_pointArray( pointArray )
35 {
36  WAssert( size > 2, "The current kD-tree implementation works only with at least 3 vertices." );
37  m_tree.clear();
38  m_tree.resize( size );
39 
40  wlog::debug( "KdTree" ) << " Start building KdTree";
41 
42  for( int i = 0; i < size; ++i )
43  m_tree[i] = i;
44 
45  int root = ( size - 1 ) / 2;
46  std::nth_element( m_tree.begin(), m_tree.begin() + root, m_tree.end(), lessy( m_pointArray, 0 ) );
47 
48  int rootLeft = ( root - 1 ) / 2;
49  std::nth_element( m_tree.begin(), m_tree.begin() + rootLeft, m_tree.begin() + root - 1, lessy( m_pointArray, 1 ) );
50 
51  int rootRight = ( size + root ) / 2;
52  std::nth_element( m_tree.begin() + root + 1, m_tree.begin() + rootRight, m_tree.end(), lessy( m_pointArray, 1 ) );
53 
54  WKdTreeThread *thread1 = new WKdTreeThread( m_pointArray, &m_tree, 0, rootLeft - 1, 2 );
55  WKdTreeThread *thread2 = new WKdTreeThread( m_pointArray, &m_tree, rootLeft + 1, root - 1, 2 );
56  WKdTreeThread *thread3 = new WKdTreeThread( m_pointArray, &m_tree, root + 1, rootRight - 1, 2 );
57  WKdTreeThread *thread4 = new WKdTreeThread( m_pointArray, &m_tree, rootRight + 1, size - 1, 2 );
58 
59  wlog::debug( "KdTree" ) << "Start threads";
60 
61  thread1->run();
62  thread2->run();
63  thread3->run();
64  thread4->run();
65 
66  wlog::debug( "KdTree" ) << "All threads started";
67 
68  thread1->wait();
69  thread2->wait();
70  thread3->wait();
71  thread4->wait();
72 
73  wlog::debug( "KdTree" ) << "All threads finished";
74 
75  delete thread1;
76  delete thread2;
77  delete thread3;
78  delete thread4;
79 }
80 
82 {
83 }
84 
85 void WKdTree::buildTree( int left, int right, int axis )
86 {
87  if( left >= right )
88  return;
89 
90  int div = ( left + right ) / 2;
91  std::nth_element( m_tree.begin() + left, m_tree.begin() + div, m_tree.begin() + right, lessy( m_pointArray, axis ) );
92 
93  buildTree( left, div - 1, ( axis + 1 ) % 3 );
94  buildTree( div + 1, right, ( axis + 1 ) % 3 );
95 }
96 
97 WKdTreeThread::WKdTreeThread( float* pointArray, std::vector< unsigned int >* tree, int left, int right, int axis ) :
98  WThreadedRunner(), m_tree( tree ), m_pointArray( pointArray ), m_left( left ), m_right( right ), m_axis( axis )
99 {
100 }
101 
103 {
105  wlog::debug( "KdTree" ) << "thread finished";
106 }
107 
108 void WKdTreeThread::buildTree( int left, int right, int axis )
109 {
110  if( left >= right )
111  return;
112 
113  int div = ( left + right ) / 2;
114  std::nth_element( m_tree->begin() + left, m_tree->begin() + div, m_tree->begin() + right, lessy( m_pointArray, axis ) );
115 
116  buildTree( left, div - 1, ( axis + 1 ) % 3 );
117  buildTree( div + 1, right, ( axis + 1 ) % 3 );
118 }