1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
|
// Included by octree.h
/**\var template<typename T_, int d_=3, class A_> typedef octree<T_,d_,A_>* octree_node<T_,d_,A_>::octree_pointer
*\brief Shorthand for a pointer to an octree.
*/
/**\var template<typename T_, int d_=3, class A_> typedef octree_node<T_,d_,A_>* octree_node<T_,d_,A_>::octree_node_pointer
*\brief Shorthand for a pointer to an octree node (this class).
*/
/**\var template<typename T_, int d_=3, class A_> typedef const octree_node<T_,d_,A_>* octree_node<T_,d_,A_>::const_octree_node_pointer
*\brief Shorthand for a pointer to an immutable octree node (this class).
*/
/**\var template<typename T_, int d_=3, class A_> typedef octree_node<T_,d_,A_>& octree_node<T_,d_,A_>::octree_node_reference
*\brief Shorthand for a reference to an octree node (this class).
*/
/**\var template<typename T_, int d_=3, class A_> typedef const octree_node<T_,d_,A_>& octree_node<T_,d_,A_>::const_octree_node_reference
*\brief Shorthand for a reference to an immutable octree node (this class).
*/
/**\var template<typename T_, int d_=3, class A_> typedef T_ octree_node<T_,d_,A_>::value_type
*\brief Shorthand for application data.
*/
/**\var template<typename T_, int d_=3, class A_> typedef T_* octree_node<T_,d_,A_>::pointer
*\brief Shorthand for a pointer to application data.
*/
/**\var template<typename T_, int d_=3, class A_> typedef T_& octree_node<T_,d_,A_>::reference
*\brief Shorthand for a reference to application data.
*/
/**\var template<typename T_, int d_=3, class A_> typedef const T_* octree_node<T_,d_,A_>::const_pointer
*\brief Shorthand for a pointer to immutable application data.
*/
/**\var template<typename T_, int d_=3, class A_> typedef const T_& octree_node<T_,d_,A_>::const_reference
*\brief Shorthand for a reference to immutable application data.
*/
/**\var template<typename T_, int d_=3, class A_> octree_node_pointer octree_node<T_,d_,A_>::_M_parent
*\brief The parent octree node that owns this node.
*/
/**\var template<typename T_, int d_=3, class A_> octree_node_pointer octree_node<T_,d_,A_>::_M_children
*\brief A pointer to an array of \f$2^{\mathrm{\texttt{\d_}}}\f$ children, or NULL if the node is a leaf node.
*/
/**\var template<typename T_, int d_=3, class A_> value_type octree_node<T_,d_,A_>::_M_data
*\brief Application-specific data.
*/
/**\brief Default constructor.
*
* The node will be a leaf node (i.e. have no children).
* The node's application-specific data will not be initialized by this constructor.
* The node will not have an owning octree -- which means that this constructor should never be used except
* possibly for serialization.
*/
template< typename T_, int d_, typename A_ >
octree_node<T_,d_,A_>::octree_node()
{
this->_M_parent = 0;
this->_M_children = 0;
}
/**\brief Root node constructor.
*
* The node will be a leaf node (i.e. have no children).
* The node's application-specific data will be initialized to the value you pass.
* This form of the constructor is used by the octree to create the root node of the tree.
*
* @param[in] parent The octree node owning this node
* @param[in] data Application-specific data to copy and store at this node.
*/
template< typename T_, int d_, typename A_ >
octree_node<T_,d_,A_>::octree_node( octree_node_pointer parent, const value_type& data )
: _M_parent( parent ), _M_data( data )
{
this->_M_children = 0;
}
/**\brief Destructor.
*/
template< typename T_, int d_, typename A_ >
octree_node<T_,d_,A_>::~octree_node()
{
if ( this->_M_children )
this->remove_children();
}
/**\fn template< typename T_, int d_, typename A_ > bool octree_node<T_,d_,A_>::is_leaf_node()
*\brief Test whether the node has any children.
*
* @retval True if the node is a leaf node (no children), false if the node has children.
*/
/**\fn template< typename T_, int d_, typename A_ > int octree_node<T_,d_,A_>::num_children()
*\brief Return the number of direct children of this node.
*
* For leaf nodes, this returns 0. Otherwise it will return \f$2^{\mathrm{\texttt{\d_}}}\f$.
*
* @retval The number of children.
*/
/**\brief Create children of this node if they did not already exist.
*
* Note that the application-specific data is not initialized by this call; you are responsible for any initialization.
* Use this variant when the default constructor of your application-specific data does some meaningful initialization.
* @retval True if children were created, false if they already existed.
*/
template< typename T_, int d_, typename A_ >
bool octree_node<T_,d_,A_>::add_children()
{
if ( this->_M_children )
{
return false;
}
this->_M_children = new octree_node<T_,d_,A_>[1<<d_];
for ( int i = 0; i < (1<<d_); ++i )
{
octree_node_pointer child = this->_M_children + i;
child->_M_parent = this;
}
return true;
}
/**\brief Create children of this node if they did not already exist.
*
* Note that the application-specific data is not initialized by this call; you are responsible for any initialization.
* Use this variant when you need to provide a default value for the children's application-specific data.
* This is useful when the application-specific data is a pointer or some other basic type that does not
* normally get initialized.
* @retval True if children were created, false if they already existed.
*/
template< typename T_, int d_, typename A_ >
bool octree_node<T_,d_,A_>::add_children( const T_& child_initializer )
{
if ( this->_M_children )
{
return false;
}
this->_M_children = new octree_node<T_,d_,A_>[1<<d_];
for ( int i = 0; i < (1<<d_); ++i )
{
octree_node_pointer child = this->_M_children + i;
child->_M_parent = this->_M_parent;
child->_M_data = child_initializer;
}
return true;
}
/**\brief Remove any child nodes from this node (if any existed to begin with).
*
* @retval True if children were removed, false if the node had none to begin with.
*/
template< typename T_, int d_, typename A_ >
bool octree_node<T_,d_,A_>::remove_children()
{
if ( this->_M_children )
{
int i;
for ( i = 0; i < ( 1 << d_ ); ++ i )
{
this->_M_children[i]._M_parent = 0; // prevent updates from propagating up the portion of the tree being deleted.
this->_M_children[i].remove_children();
}
delete [] this->_M_children;
this->_M_children = 0;
return true;
}
return false;
}
/**\fn template< typename T_, int d_, typename A_ > reference octree_node<T_,d_,A_>::value()
*\brief Retrieve the application-specific data stored at a node.
*
* @retval A reference to the application-specific data.
*/
/**\fn template< typename T_, int d_, typename A_ > const reference octree_node<T_,d_,A_>::value() const
*\brief Retrieve a reference to immutable application-specific data stored at a node.
*
* @retval A reference to immutable application-specific data.
*/
/**\brief Return a (const) reference to a child node.
*
* @param child An integer in \f$[0,2^{\mathrm{\texttt{\d_}}}]\f$ indicating which child node to return.
*/
template< typename T_, int d_, typename A_ >
const octree_node<T_,d_,A_>& octree_node<T_,d_,A_>::operator [] ( int child ) const
{
if ( ! this->_M_children )
{
throw vtkstd::domain_error( "Attempt to access children of an octree leaf node." );
}
return this->_M_chilren[child];
}
/**\brief Return a reference to a child node.
*
* @param child An integer in \f$[0,2^{\mathrm{\texttt{\d_}}}]\f$ indicating which child node to return.
*/
template< typename T_, int d_, typename A_ >
octree_node<T_,d_,A_>& octree_node<T_,d_,A_>::operator [] ( int child )
{
if ( ! this->_M_children )
{
throw vtkstd::domain_error( "Attempt to access children of an octree leaf node." );
}
return this->_M_children[child];
}
/**\fn template<typename T_, int d_=3, class A_> reference octree_node<T_,d_,A_>::operator * ()
*\brief Provide access to the application-specific data.
*/
/**\fn template<typename T_, int d_=3, class A_> const_reference octree_node<T_,d_,A_>::operator * () const
*\brief Provide read-only access to the application-specific data.
*/
|
