MVE - Multi-View Environment mve-devel
Loading...
Searching...
No Matches
octree.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 2015, Simon Fuhrmann
3 * TU Darmstadt - Graphics, Capture and Massively Parallel Computing
4 * All rights reserved.
5 *
6 * This software may be modified and distributed under the terms
7 * of the BSD 3-Clause license. See the LICENSE.txt file for details.
8 */
9
10#ifndef FSSR_OCTREE_HEADER
11#define FSSR_OCTREE_HEADER
12
13#include <vector>
14#include <string>
15#include <cstdint>
16
17#include "math/vector.h"
18#include "mve/mesh.h"
19#include "fssr/defines.h"
20#include "fssr/sample.h"
21
23
29class Octree
30{
31public:
38 struct Node
39 {
40 public:
41 Node (void);
42 virtual ~Node (void);
43
44 public:
48 std::vector<Sample> samples;
49 };
50
57 struct Iterator
58 {
59 public:
60 Iterator (void);
61 Node* first_node (void);
62 Node* first_leaf (void);
63 Node* next_node (void);
64 Node* next_branch (void);
65 Node* next_leaf (void);
66 Iterator descend (int octant) const;
67 Iterator descend (uint8_t level, uint64_t path) const;
68 Iterator ascend (void) const;
69
70 public:
73 uint64_t path;
74 uint8_t level;
75 };
76
77public:
78 Octree (void);
79 virtual ~Octree (void);
80
82 void clear (void);
83
85 void clear_samples (void);
86
90 void insert_samples (SampleList const& samples);
91
100 void insert_sample (Sample const& s);
101
103 std::size_t get_num_samples (void) const;
104
108 std::size_t get_num_nodes (void) const;
109
115 int get_num_levels (void) const;
116
122 void get_samples_per_level (std::vector<std::size_t>* stats) const;
123
125 void node_center_and_size (Iterator const& iter,
126 math::Vec3d* center, double* size) const;
127
129 Node const* get_root_node (void) const;
130
132 math::Vec3d const& get_root_node_center (void) const;
133
135 double get_root_node_size (void) const;
136
138 Iterator get_iterator_for_root (void) const;
139
145 void influence_query (math::Vec3d const& pos, double factor,
146 std::vector<Sample const*>* result) const;
147
151 void refine_octree (void);
152
157 void limit_octree_level (void);
158
163 void set_max_level (int max_level);
164
169 int get_max_level (void) const;
170
172 void print_stats (std::ostream& out);
173
174private:
175 /* Octree functions. */
176 void create_children (Node* node);
177 bool is_inside_octree (math::Vec3d const& pos);
178 void expand_root_for_point (math::Vec3d const& pos);
179
180 /* Octree recursive functions. */
181 Node* find_node_descend (Sample const& sample, Iterator const& iter);
182 Node* find_node_expand (Sample const& sample);
183 int get_num_levels (Node const* node) const;
184 void get_samples_per_level (std::vector<std::size_t>* stats,
185 Node const* node, std::size_t level) const;
186 void influence_query (math::Vec3d const& pos, double factor,
187 std::vector<Sample const*>* result, Iterator const& iter,
188 math::Vec3d const& parent_node_center) const;
189 void limit_octree_level (Node* node, Node* parent, int level);
190
191private:
192 /* The root node with its center and side length. */
193 Node* root;
194 math::Vec3d root_center;
195 double root_size;
196
197 /* The number of samples and nodes in the octree. */
198 std::size_t num_samples;
199 std::size_t num_nodes;
200
201 /* Limit the octree depth. Maximum level is 20 (see voxel.h). */
202 int max_level;
203};
204
205/* ------------------------- Implementation ---------------------------- */
206
207inline
208Octree::Node::Node (void)
209 : children(nullptr), parent(nullptr)
210{
211}
212
213inline
215{
216 delete [] this->children;
217}
218
219/* -------------------------------------------------------------------- */
220
221inline
223 : current(nullptr)
224 , root(nullptr)
225 , path(0)
226 , level(0)
227{
228}
229
230/* ---------------------------------------------------------------- */
231
232inline
234 : root(nullptr)
235{
236 this->clear();
237}
238
239inline
241{
242 delete this->root;
243}
244
245inline void
247{
248 delete this->root;
249 this->root = nullptr;
250 this->root_size = 0.0;
251 this->root_center = math::Vec3d(0.0);
252 this->num_samples = 0;
253 this->num_nodes = 0;
254 this->max_level = 20;
255}
256
257inline void
259{
260 Iterator iter = this->get_iterator_for_root();
261 for (iter.first_node(); iter.current != nullptr; iter.next_node())
262 iter.current->samples.clear();
263 this->num_samples = 0;
264}
265
266inline std::size_t
268{
269 return this->num_samples;
270}
271
272inline std::size_t
274{
275 return this->num_nodes;
276}
277
278inline int
280{
281 return this->get_num_levels(this->root);
282}
283
284inline void
285Octree::get_samples_per_level (std::vector<std::size_t>* stats) const
286{
287 stats->clear();
288 this->get_samples_per_level(stats, this->root, 0);
289}
290
291inline Octree::Node const*
293{
294 return this->root;
295}
296
297inline math::Vec3d const&
299{
300 return this->root_center;
301}
302
303inline double
305{
306 return this->root_size;
307}
308
309inline void
310Octree::influence_query (math::Vec3d const& pos, double factor,
311 std::vector<Sample const*>* result) const
312{
313 result->resize(0);
314 this->influence_query(pos, factor, result, this->get_iterator_for_root(),
315 this->root_center);
316}
317
318inline void
320{
321 this->max_level = std::max(0, std::min(20, max_level));
322}
323
324inline int
326{
327 return this->max_level;
328}
329
331
332#endif // FSSR_OCTREE_HEADER
A regular octree data structure (each node has zero or eight child nodes).
Definition octree.h:30
void clear(void)
Resets the octree to its initial state.
Definition octree.h:246
void get_samples_per_level(std::vector< std::size_t > *stats) const
Returns octree level statistics (WARNING: traverses whole tree).
Definition octree.h:285
int get_max_level(void) const
Returns the maximum level on which voxels are generated.
Definition octree.h:325
void influence_query(math::Vec3d const &pos, double factor, std::vector< Sample const * > *result) const
Queries all samples that influence the given point.
Definition octree.h:310
math::Vec3d const & get_root_node_center(void) const
Returns the center of the root node.
Definition octree.h:298
void set_max_level(int max_level)
Sets the maximum level on which voxels are generated.
Definition octree.h:319
double get_root_node_size(void) const
Returns the size of the root node.
Definition octree.h:304
Octree(void)
Definition octree.h:233
std::size_t get_num_nodes(void) const
Returns the number of nodes in the octree.
Definition octree.h:273
Iterator get_iterator_for_root(void) const
Returns an octree iterator for the root.
Definition octree.cc:335
void clear_samples(void)
Clears all samples in all nodes.
Definition octree.h:258
int get_num_levels(void) const
Returns the number of levels (WARNING: traverses whole tree).
Definition octree.h:279
virtual ~Octree(void)
Definition octree.h:240
Node const * get_root_node(void) const
Returns the root node (read-only).
Definition octree.h:292
std::size_t get_num_samples(void) const
Returns the number of samples in the octree.
Definition octree.h:267
#define FSSR_NAMESPACE_END
Definition defines.h:14
#define FSSR_NAMESPACE_BEGIN
Definition defines.h:13
std::vector< Sample > SampleList
Representation of a list of samples.
Definition sample.h:31
Vector< double, 3 > Vec3d
Definition vector.h:39
Octree iterator that keeps track of level and path through the octree.
Definition octree.h:58
Node * first_node(void)
Definition octree.cc:22
Node * next_node(void)
Definition octree.cc:44
Simple recursive octree node that stores samples in a vector.
Definition octree.h:39
virtual ~Node(void)
Definition octree.h:214
std::vector< Sample > samples
Definition octree.h:48
Node * children
Definition octree.h:45
Representation of a point sample.
Definition sample.h:22