OpenWalnut
1.3.1
Main Page
Related Pages
Modules
Namespaces
Classes
Files
File List
src
core
kernel
WKdTree.h
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
#ifndef WKDTREE_H
26
#define WKDTREE_H
27
28
#include <algorithm>
29
#include <vector>
30
31
#include "../common/WThreadedRunner.h"
32
33
/**
34
* implements the compare function for std::nth_element on a point array
35
*/
36
struct
lessy
37
{
38
float
const
*
const
data
;
//!< stores the pointer to the data array
39
const
int
pos
;
//!< stores the axis at which the array is sorted
40
41
/**
42
* constructor
43
* \param data pointer to the array
44
* \param pos x,y or z axis
45
*/
46
lessy
(
float
const
*
const
data
,
const
int
pos
) :
47
data( data ), pos( pos )
48
{
49
}
50
51
/**
52
* comparison operator less
53
* \param lhs
54
* \param rhs
55
* \return is lhs smaller than rhs
56
*/
57
bool
operator()
(
const
unsigned
int
& lhs,
const
unsigned
int
& rhs )
const
//NOLINT
58
{
59
return
data
[3 * lhs +
pos
] <
data
[3 * rhs +
pos
];
60
}
61
};
62
63
/**
64
* class to provide threaded computation of parts of the kd tree
65
*/
66
class
WKdTreeThread
:
public
WThreadedRunner
67
{
68
public
:
69
/**
70
* constructor
71
*
72
* \param pointArray
73
* \param tree pointer to the tree
74
* \param left boundary of the part to compute
75
* \param right boundary of the part to compute
76
* \param axis starting axis
77
*/
78
WKdTreeThread
(
float
* pointArray, std::vector< unsigned int >* tree,
int
left,
int
right,
int
axis );
79
80
/**
81
* recursive function to compute a part of the kd tree
82
*
83
* \param left
84
* \param right
85
* \param axis
86
*/
87
void
buildTree
(
int
left,
int
right,
int
axis );
88
89
/**
90
* entry for the run command
91
*/
92
virtual
void
threadMain
();
93
94
std::vector< unsigned int >*
m_tree
;
//!< stores a pointer to the tree
95
float
*
m_pointArray
;
//!< stores a pointer to the vertex array
96
97
int
m_left
;
//!< stores left boundary, since the threadMain method has no arguments
98
int
m_right
;
//!< stores left boundary, since the threadMain method has no arguments
99
int
m_axis
;
//!< stores axis, since the threadMain method has no arguments
100
};
101
102
/**
103
* implements the computation of a kd tree on a point array
104
*/
105
class
WKdTree
106
{
107
public
:
108
/**
109
* constructor
110
*
111
* \param size
112
* \param pointArray
113
*/
114
WKdTree
(
int
size,
float
* pointArray );
115
116
/**
117
* destructor
118
*/
119
~WKdTree
();
120
121
std::vector< unsigned int >
m_tree
;
//!< stores the tree
122
123
private
:
124
/**
125
* recursive function to compute a part of the kd tree
126
*
127
* \param left
128
* \param right
129
* \param axis
130
*/
131
void
buildTree
(
int
left,
int
right,
int
axis );
132
int
m_size
;
//!< size of the tree
133
unsigned
int
m_root
;
//!< index of the root point
134
float
*
m_pointArray
;
//!< stores a pointer to the vertex array
135
};
136
137
#endif // WKDTREE_H
Generated by
1.8.1.2