22Octree::Iterator::first_node (
void)
24 this->current = this->root;
31Octree::Iterator::first_leaf (
void)
34 while (this->current->children !=
nullptr)
36 this->current = this->current->children;
37 this->level = this->level + 1;
38 this->path = this->path << 3;
44Octree::Iterator::next_node (
void)
46 if (this->current->children ==
nullptr)
47 return this->next_branch();
49 this->current = this->current->children;
50 this->level = this->level + 1;
51 this->path = this->path << 3;
56Octree::Iterator::next_branch (
void)
58 if (this->current->parent ==
nullptr)
60 this->current =
nullptr;
64 if (this->current - this->current->parent->children == 7)
66 this->current = this->current->
parent;
67 this->level = this->level - 1;
68 this->path = this->path >> 3;
69 return this->next_branch();
78Octree::Iterator::next_leaf (
void)
80 if (this->current->children !=
nullptr)
82 while (this->current->children !=
nullptr)
84 this->current = this->current->
children;
85 this->level = this->level + 1;
86 this->path = this->path << 3;
92 if (this->current ==
nullptr)
94 while (this->current->children !=
nullptr)
96 this->current = this->current->children;
97 this->level = this->level + 1;
98 this->path = this->path << 3;
100 return this->current;
104Octree::Iterator::descend (
int octant)
const
109 iter.
path = (iter.
path << 3) | octant;
114Octree::Iterator::descend (uint8_t level, uint64_t path)
const
117 iter.
root = this->root;
121 for (
int i = 0; i < level; ++i)
129 int const octant = (path >> ((level - i - 1) * 3)) & 7;
133 if (iter.
path != path || iter.
level != level)
134 throw std::runtime_error(
"descend(): failed");
140Octree::Iterator::ascend (
void)
const
143 iter.
root = this->root;
145 iter.
path = this->path >> 3;
146 iter.
level = this->level - 1;
155 for (std::size_t i = 0; i < samples.size(); i++)
156 this->insert_sample(samples[i]);
160Octree::insert_sample (
Sample const& sample)
162 if (this->root ==
nullptr)
164 this->root =
new Node();
165 this->root_center = sample.
pos;
166 this->root_size = sample.
scale;
171 while (!this->is_inside_octree(sample.
pos))
172 this->expand_root_for_point(sample.
pos);
175 Node* node =
nullptr;
176 if (sample.
scale >= this->root_size * 2.0)
177 node = this->find_node_expand(sample);
179 node = this->find_node_descend(sample, this->get_iterator_for_root());
181 node->
samples.push_back(sample);
182 this->num_samples += 1;
186Octree::create_children (Node* node)
188 if (node->children !=
nullptr)
189 throw std::runtime_error(
"create_children(): Children exist!");
190 node->children =
new Node[8];
191 this->num_nodes += 8;
192 for (
int i = 0; i < 8; ++i)
193 node->children[i].parent = node;
199 double const len2 = this->root_size / 2.0;
200 for (
int i = 0; i < 3; ++i)
201 if (pos[i] < this->root_center[i] - len2
202 || pos[i] > this->root_center[i] + len2)
208Octree::expand_root_for_point (
math::Vec3d const& pos)
212 for (
int i = 0; i < 3; ++i)
213 if (pos[i] > this->root_center[i])
215 this->root_center[i] += this->root_size / 2.0;
220 this->root_center[i] -= this->root_size / 2.0;
222 this->root_size *= 2.0;
225 Node* new_root =
new Node();
226 this->create_children(new_root);
227 std::swap(new_root->children[octant].children, this->root->children);
228 std::swap(new_root->children[octant].samples, this->root->samples);
230 this->root = new_root;
233 if (this->root->children[octant].children !=
nullptr)
235 Node* children = this->root->children[octant].children;
236 for (
int i = 0; i < 8; ++i)
237 children[i].parent = this->root->children + octant;
242Octree::find_node_descend (Sample
const& sample, Iterator
const& iter)
246 this->node_center_and_size(iter, &node_center, &node_size);
248 if (sample.scale > node_size * 2.0)
249 throw std::runtime_error(
"find_node_descend(): Sanity check failed!");
257 if (node_size <= sample.scale || iter.level >= this->max_level)
262 for (
int i = 0; i < 3; ++i)
263 if (sample.pos[i] > node_center[i])
265 if (iter.current->children ==
nullptr)
266 this->create_children(iter.current);
267 return this->find_node_descend(sample, iter.descend(octant));
271Octree::find_node_expand (Sample
const& sample)
273 if (this->root_size > sample.scale)
274 throw std::runtime_error(
"find_node_expand(): Sanity check failed!");
281 if (sample.scale < this->root_size * 2.0)
284 this->expand_root_for_point(sample.pos);
285 return this->find_node_expand(sample);
289Octree::get_num_levels (Node
const* node)
const
293 if (node->children ==
nullptr)
296 for (
int i = 0; i < 8; ++i)
297 depth = std::max(depth, this->get_num_levels(node->children + i));
302Octree::get_samples_per_level (std::vector<std::size_t>* stats,
303 Node
const* node, std::size_t level)
const
307 if (stats->size() <= level)
308 stats->resize(level + 1, 0);
309 stats->at(level) += node->samples.size();
312 if (node->children ==
nullptr)
314 for (
int i = 0; i < 8; ++i)
315 this->get_samples_per_level(stats, node->children + i, level + 1);
322 *center = this->root_center;
323 *size = this->root_size;
324 for (
int i = 0; i < iter.
level; ++i)
326 int const octant = iter.
path >> ((iter.
level - i - 1) * 3);
327 double const offset = *size / 4.0;
328 for (
int j = 0; j < 3; ++j)
329 (*center)[j] += ((octant & (1 << j)) ? offset : -offset);
335Octree::get_iterator_for_root (
void)
const
337 if (this->root ==
nullptr)
338 throw std::logic_error(
"Iterator request on empty octree");
341 iter.
root = this->root;
347Octree::influence_query (
math::Vec3d const& pos,
double factor,
348 std::vector<Sample const*>* result, Iterator
const& iter,
351 if (iter.current ==
nullptr)
368 uint32_t x = (iter.path & 1) >> 0;
369 uint32_t y = (iter.path & 2) >> 1;
370 uint32_t z = (iter.path & 4) >> 2;
371 double node_size = this->root_size / (1 << iter.level);
372 double offset = (iter.level > 0) * node_size / 2.0;
374 parent_node_center[0] - offset + x * node_size,
375 parent_node_center[1] - offset + y * node_size,
376 parent_node_center[2] - offset + z * node_size);
379 double const min_distance = (pos - node_center).norm()
381 double const max_scale = node_size * 2.0;
382 if (min_distance > max_scale * factor)
386 for (std::size_t i = 0; i < iter.current->samples.size(); ++i)
388 Sample const& s = iter.current->samples[i];
391 result->push_back(&s);
395 if (iter.current->children ==
nullptr)
397 for (
int i = 0; i < 8; ++i)
398 this->influence_query(pos, factor, result, iter.descend(i),
403Octree::refine_octree (
void)
405 if (this->root ==
nullptr)
408 std::list<Node*> queue;
409 queue.push_back(this->root);
410 while (!queue.empty())
412 Node* node = queue.front();
416 this->create_children(node);
418 for (
int i = 0; i < 8; ++i)
419 queue.push_back(node->
children + i);
424Octree::limit_octree_level (
void)
426 std::cout <<
"Limiting octree to "
427 << this->max_level <<
" levels..." << std::endl;
429 if (this->root ==
nullptr)
431 this->limit_octree_level(this->root,
nullptr, 0);
435Octree::limit_octree_level (Node* node, Node* parent,
int level)
437 if (level == this->max_level)
440 if (level > this->max_level)
442 parent->samples.insert(parent->samples.end(),
443 node->samples.begin(), node->samples.end());
444 node->samples.clear();
447 if (node->children !=
nullptr)
448 for (
int i = 0; i < 8; ++i)
449 this->limit_octree_level(node->children + i, parent, level + 1);
451 if (level > this->max_level)
452 this->num_nodes -= 1;
454 if (level == this->max_level)
456 delete [] node->children;
457 node->children =
nullptr;
462Octree::print_stats (std::ostream& out)
464 out <<
"Octree contains " << this->get_num_samples()
465 <<
" samples in " << this->get_num_nodes() <<
" nodes on "
466 << this->get_num_levels() <<
" levels." << std::endl;
468 std::vector<std::size_t> octree_stats;
469 this->get_samples_per_level(&octree_stats);
471 bool printed =
false;
472 for (std::size_t i = 0; i < octree_stats.size(); ++i)
474 if (!printed && octree_stats[i] == 0)
478 out <<
" Level " << i <<
": "
479 << octree_stats[i] <<
" samples" << std::endl;
#define FSSR_NAMESPACE_END
#define FSSR_NAMESPACE_BEGIN
std::vector< Sample > SampleList
Representation of a list of samples.
void swap(mve::Image< T > &a, mve::Image< T > &b)
Specialization of std::swap for efficient image swapping.
Octree iterator that keeps track of level and path through the octree.
Iterator descend(int octant) const
Simple recursive octree node that stores samples in a vector.
std::vector< Sample > samples
Representation of a point sample.