Program Listing for File OcTreeBaseImpl.hxx
↰ Return to documentation for file (/tmp/ws/src/octomap/octomap/include/octomap/OcTreeBaseImpl.hxx)
/*
* OctoMap - An Efficient Probabilistic 3D Mapping Framework Based on Octrees
* https://octomap.github.io/
*
* Copyright (c) 2009-2013, K.M. Wurm and A. Hornung, University of Freiburg
* All rights reserved.
* License: New BSD
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of the University of Freiburg nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#undef max
#undef min
#include <limits>
#ifdef _OPENMP
#include <omp.h>
#endif
namespace octomap {
template <class NODE,class I>
OcTreeBaseImpl<NODE,I>::OcTreeBaseImpl(double in_resolution) :
I(), root(NULL), tree_depth(16), tree_max_val(32768),
resolution(in_resolution), tree_size(0)
{
init();
// no longer create an empty root node - only on demand
}
template <class NODE,class I>
OcTreeBaseImpl<NODE,I>::OcTreeBaseImpl(double in_resolution, unsigned int in_tree_depth, unsigned int in_tree_max_val) :
I(), root(NULL), tree_depth(in_tree_depth), tree_max_val(in_tree_max_val),
resolution(in_resolution), tree_size(0)
{
init();
// no longer create an empty root node - only on demand
}
template <class NODE,class I>
OcTreeBaseImpl<NODE,I>::~OcTreeBaseImpl(){
clear();
}
template <class NODE,class I>
OcTreeBaseImpl<NODE,I>::OcTreeBaseImpl(const OcTreeBaseImpl<NODE,I>& rhs) :
root(NULL), tree_depth(rhs.tree_depth), tree_max_val(rhs.tree_max_val),
resolution(rhs.resolution), tree_size(rhs.tree_size)
{
init();
// copy nodes recursively:
if (rhs.root)
root = new NODE(*(rhs.root));
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::init(){
this->setResolution(this->resolution);
for (unsigned i = 0; i< 3; i++){
max_value[i] = -(std::numeric_limits<double>::max( ));
min_value[i] = std::numeric_limits<double>::max( );
}
size_changed = true;
// create as many KeyRays as there are OMP_THREADS defined,
// one buffer for each thread
#ifdef _OPENMP
#pragma omp parallel
#pragma omp critical
{
if (omp_get_thread_num() == 0){
this->keyrays.resize(omp_get_num_threads());
}
}
#else
this->keyrays.resize(1);
#endif
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::swapContent(OcTreeBaseImpl<NODE,I>& other){
NODE* this_root = root;
root = other.root;
other.root = this_root;
size_t this_size = this->tree_size;
this->tree_size = other.tree_size;
other.tree_size = this_size;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::operator== (const OcTreeBaseImpl<NODE,I>& other) const{
if (tree_depth != other.tree_depth || tree_max_val != other.tree_max_val
|| resolution != other.resolution || tree_size != other.tree_size){
return false;
}
// traverse all nodes, check if structure the same
typename OcTreeBaseImpl<NODE,I>::tree_iterator it = this->begin_tree();
typename OcTreeBaseImpl<NODE,I>::tree_iterator end = this->end_tree();
typename OcTreeBaseImpl<NODE,I>::tree_iterator other_it = other.begin_tree();
typename OcTreeBaseImpl<NODE,I>::tree_iterator other_end = other.end_tree();
for (; it != end; ++it, ++other_it){
if (other_it == other_end)
return false;
if (it.getDepth() != other_it.getDepth()
|| it.getKey() != other_it.getKey()
|| !(*it == *other_it))
{
return false;
}
}
if (other_it != other_end)
return false;
return true;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::setResolution(double r) {
resolution = r;
resolution_factor = 1. / resolution;
tree_center(0) = tree_center(1) = tree_center(2)
= (float) (((double) tree_max_val) / resolution_factor);
// init node size lookup table:
sizeLookupTable.resize(tree_depth+1);
for(unsigned i = 0; i <= tree_depth; ++i){
sizeLookupTable[i] = resolution * double(1 << (tree_depth - i));
}
size_changed = true;
}
template <class NODE,class I>
NODE* OcTreeBaseImpl<NODE,I>::createNodeChild(NODE* node, unsigned int childIdx){
assert(childIdx < 8);
if (node->children == NULL) {
allocNodeChildren(node);
}
assert (node->children[childIdx] == NULL);
NODE* newNode = new NODE();
node->children[childIdx] = static_cast<AbstractOcTreeNode*>(newNode);
tree_size++;
size_changed = true;
return newNode;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::deleteNodeChild(NODE* node, unsigned int childIdx){
assert((childIdx < 8) && (node->children != NULL));
assert(node->children[childIdx] != NULL);
delete static_cast<NODE*>(node->children[childIdx]); // TODO delete check if empty
node->children[childIdx] = NULL;
tree_size--;
size_changed = true;
}
template <class NODE,class I>
NODE* OcTreeBaseImpl<NODE,I>::getNodeChild(NODE* node, unsigned int childIdx) const{
assert((childIdx < 8) && (node->children != NULL));
assert(node->children[childIdx] != NULL);
return static_cast<NODE*>(node->children[childIdx]);
}
template <class NODE,class I>
const NODE* OcTreeBaseImpl<NODE,I>::getNodeChild(const NODE* node, unsigned int childIdx) const{
assert((childIdx < 8) && (node->children != NULL));
assert(node->children[childIdx] != NULL);
return static_cast<const NODE*>(node->children[childIdx]);
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::isNodeCollapsible(const NODE* node) const{
// all children must exist, must not have children of
// their own and have the same occupancy probability
if (!nodeChildExists(node, 0))
return false;
const NODE* firstChild = getNodeChild(node, 0);
if (nodeHasChildren(firstChild))
return false;
for (unsigned int i = 1; i<8; i++) {
// comparison via getChild so that casts of derived classes ensure
// that the right == operator gets called
if (!nodeChildExists(node, i) || nodeHasChildren(getNodeChild(node, i)) || !(*(getNodeChild(node, i)) == *(firstChild)))
return false;
}
return true;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::nodeChildExists(const NODE* node, unsigned int childIdx) const{
assert(childIdx < 8);
if ((node->children != NULL) && (node->children[childIdx] != NULL))
return true;
else
return false;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::nodeHasChildren(const NODE* node) const {
if (node->children == NULL)
return false;
for (unsigned int i = 0; i<8; i++){
if (node->children[i] != NULL)
return true;
}
return false;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::expandNode(NODE* node){
assert(!nodeHasChildren(node));
for (unsigned int k=0; k<8; k++) {
NODE* newNode = createNodeChild(node, k);
newNode->copyData(*node);
}
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::pruneNode(NODE* node){
if (!isNodeCollapsible(node))
return false;
// set value to children's values (all assumed equal)
node->copyData(*(getNodeChild(node, 0)));
// delete children (known to be leafs at this point!)
for (unsigned int i=0;i<8;i++) {
deleteNodeChild(node, i);
}
delete[] node->children;
node->children = NULL;
return true;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::allocNodeChildren(NODE* node){
// TODO NODE*
node->children = new AbstractOcTreeNode*[8];
for (unsigned int i=0; i<8; i++) {
node->children[i] = NULL;
}
}
template <class NODE,class I>
inline key_type OcTreeBaseImpl<NODE,I>::coordToKey(double coordinate, unsigned depth) const{
assert (depth <= tree_depth);
int keyval = ((int) floor(resolution_factor * coordinate));
unsigned int diff = tree_depth - depth;
if(!diff) // same as coordToKey without depth
return keyval + tree_max_val;
else // shift right and left => erase last bits. Then add offset.
return ((keyval >> diff) << diff) + (1 << (diff-1)) + tree_max_val;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::coordToKeyChecked(double coordinate, key_type& keyval) const {
// scale to resolution and shift center for tree_max_val
int scaled_coord = ((int) floor(resolution_factor * coordinate)) + tree_max_val;
// keyval within range of tree?
if (( scaled_coord >= 0) && (((unsigned int) scaled_coord) < (2*tree_max_val))) {
keyval = scaled_coord;
return true;
}
return false;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::coordToKeyChecked(double coordinate, unsigned depth, key_type& keyval) const {
// scale to resolution and shift center for tree_max_val
int scaled_coord = ((int) floor(resolution_factor * coordinate)) + tree_max_val;
// keyval within range of tree?
if (( scaled_coord >= 0) && (((unsigned int) scaled_coord) < (2*tree_max_val))) {
keyval = scaled_coord;
keyval = adjustKeyAtDepth(keyval, depth);
return true;
}
return false;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::coordToKeyChecked(const point3d& point, OcTreeKey& key) const{
for (unsigned int i=0;i<3;i++) {
if (!coordToKeyChecked( point(i), key[i])) return false;
}
return true;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::coordToKeyChecked(const point3d& point, unsigned depth, OcTreeKey& key) const{
for (unsigned int i=0;i<3;i++) {
if (!coordToKeyChecked( point(i), depth, key[i])) return false;
}
return true;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::coordToKeyChecked(double x, double y, double z, OcTreeKey& key) const{
if (!(coordToKeyChecked(x, key[0])
&& coordToKeyChecked(y, key[1])
&& coordToKeyChecked(z, key[2])))
{
return false;
} else {
return true;
}
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::coordToKeyChecked(double x, double y, double z, unsigned depth, OcTreeKey& key) const{
if (!(coordToKeyChecked(x, depth, key[0])
&& coordToKeyChecked(y, depth, key[1])
&& coordToKeyChecked(z, depth, key[2])))
{
return false;
} else {
return true;
}
}
template <class NODE,class I>
key_type OcTreeBaseImpl<NODE,I>::adjustKeyAtDepth(key_type key, unsigned int depth) const{
unsigned int diff = tree_depth - depth;
if(diff == 0)
return key;
else
return (((key-tree_max_val) >> diff) << diff) + (1 << (diff-1)) + tree_max_val;
}
template <class NODE,class I>
double OcTreeBaseImpl<NODE,I>::keyToCoord(key_type key, unsigned depth) const{
assert(depth <= tree_depth);
// root is centered on 0 = 0.0
if (depth == 0) {
return 0.0;
} else if (depth == tree_depth) {
return keyToCoord(key);
} else {
return (floor( (double(key)-double(this->tree_max_val)) /double(1 << (tree_depth - depth)) ) + 0.5 ) * this->getNodeSize(depth);
}
}
template <class NODE,class I>
NODE* OcTreeBaseImpl<NODE,I>::search(const point3d& value, unsigned int depth) const {
OcTreeKey key;
if (!coordToKeyChecked(value, key)){
OCTOMAP_ERROR_STR("Error in search: ["<< value <<"] is out of OcTree bounds!");
return NULL;
}
else {
return this->search(key, depth);
}
}
template <class NODE,class I>
NODE* OcTreeBaseImpl<NODE,I>::search(double x, double y, double z, unsigned int depth) const {
OcTreeKey key;
if (!coordToKeyChecked(x, y, z, key)){
OCTOMAP_ERROR_STR("Error in search: ["<< x <<" "<< y << " " << z << "] is out of OcTree bounds!");
return NULL;
}
else {
return this->search(key, depth);
}
}
template <class NODE,class I>
NODE* OcTreeBaseImpl<NODE,I>::search (const OcTreeKey& key, unsigned int depth) const {
assert(depth <= tree_depth);
if (root == NULL)
return NULL;
if (depth == 0)
depth = tree_depth;
// generate appropriate key_at_depth for queried depth
OcTreeKey key_at_depth = key;
if (depth != tree_depth)
key_at_depth = adjustKeyAtDepth(key, depth);
NODE* curNode (root);
int diff = tree_depth - depth;
// follow nodes down to requested level (for diff = 0 it's the last level)
for (int i=(tree_depth-1); i>=diff; --i) {
unsigned int pos = computeChildIdx(key_at_depth, i);
if (nodeChildExists(curNode, pos)) {
// cast needed: (nodes need to ensure it's the right pointer)
curNode = getNodeChild(curNode, pos);
} else {
// we expected a child but did not get it
// is the current node a leaf already?
if (!nodeHasChildren(curNode)) { // TODO similar check to nodeChildExists?
return curNode;
} else {
// it is not, search failed
return NULL;
}
}
} // end for
return curNode;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::deleteNode(const point3d& value, unsigned int depth) {
OcTreeKey key;
if (!coordToKeyChecked(value, key)){
OCTOMAP_ERROR_STR("Error in deleteNode: ["<< value <<"] is out of OcTree bounds!");
return false;
}
else {
return this->deleteNode(key, depth);
}
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::deleteNode(double x, double y, double z, unsigned int depth) {
OcTreeKey key;
if (!coordToKeyChecked(x, y, z, key)){
OCTOMAP_ERROR_STR("Error in deleteNode: ["<< x <<" "<< y << " " << z << "] is out of OcTree bounds!");
return false;
}
else {
return this->deleteNode(key, depth);
}
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::deleteNode(const OcTreeKey& key, unsigned int depth) {
if (root == NULL)
return true;
if (depth == 0)
depth = tree_depth;
return deleteNodeRecurs(root, 0, depth, key);
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::clear() {
if (this->root){
deleteNodeRecurs(root);
this->tree_size = 0;
this->root = NULL;
// max extent of tree changed:
this->size_changed = true;
}
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::prune() {
if (root == NULL)
return;
for (unsigned int depth=tree_depth-1; depth > 0; --depth) {
unsigned int num_pruned = 0;
pruneRecurs(this->root, 0, depth, num_pruned);
if (num_pruned == 0)
break;
}
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::expand() {
if (root)
expandRecurs(root,0, tree_depth);
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::computeRayKeys(const point3d& origin,
const point3d& end,
KeyRay& ray) const {
// see "A Faster Voxel Traversal Algorithm for Ray Tracing" by Amanatides & Woo
// basically: DDA in 3D
ray.reset();
OcTreeKey key_origin, key_end;
if ( !OcTreeBaseImpl<NODE,I>::coordToKeyChecked(origin, key_origin) ||
!OcTreeBaseImpl<NODE,I>::coordToKeyChecked(end, key_end) ) {
OCTOMAP_WARNING_STR("coordinates ( "
<< origin << " -> " << end << ") out of bounds in computeRayKeys");
return false;
}
if (key_origin == key_end)
return true; // same tree cell, we're done.
ray.addKey(key_origin);
// Initialization phase -------------------------------------------------------
point3d direction = (end - origin);
float length = (float) direction.norm();
direction /= length; // normalize vector
int step[3];
double tMax[3];
double tDelta[3];
OcTreeKey current_key = key_origin;
for(unsigned int i=0; i < 3; ++i) {
// compute step direction
if (direction(i) > 0.0) step[i] = 1;
else if (direction(i) < 0.0) step[i] = -1;
else step[i] = 0;
// compute tMax, tDelta
if (step[i] != 0) {
// corner point of voxel (in direction of ray)
double voxelBorder = this->keyToCoord(current_key[i]);
voxelBorder += (float) (step[i] * this->resolution * 0.5);
tMax[i] = ( voxelBorder - origin(i) ) / direction(i);
tDelta[i] = this->resolution / fabs( direction(i) );
}
else {
tMax[i] = std::numeric_limits<double>::max( );
tDelta[i] = std::numeric_limits<double>::max( );
}
}
// Incremental phase ---------------------------------------------------------
bool done = false;
while (!done) {
unsigned int dim;
// find minimum tMax:
if (tMax[0] < tMax[1]){
if (tMax[0] < tMax[2]) dim = 0;
else dim = 2;
}
else {
if (tMax[1] < tMax[2]) dim = 1;
else dim = 2;
}
// advance in direction "dim"
current_key[dim] += step[dim];
tMax[dim] += tDelta[dim];
assert (current_key[dim] < 2*this->tree_max_val);
// reached endpoint, key equv?
if (current_key == key_end) {
done = true;
break;
}
else {
// reached endpoint world coords?
// dist_from_origin now contains the length of the ray when traveled until the border of the current voxel
double dist_from_origin = std::min(std::min(tMax[0], tMax[1]), tMax[2]);
// if this is longer than the expected ray length, we should have already hit the voxel containing the end point with the code above (key_end).
// However, we did not hit it due to accumulating discretization errors, so this is the point here to stop the ray as we would never reach the voxel key_end
if (dist_from_origin > length) {
done = true;
break;
}
else { // continue to add freespace cells
ray.addKey(current_key);
}
}
assert ( ray.size() < ray.sizeMax() - 1);
} // end while
return true;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::computeRay(const point3d& origin, const point3d& end,
std::vector<point3d>& _ray) {
_ray.clear();
if (!computeRayKeys(origin, end, keyrays.at(0))) return false;
for (KeyRay::const_iterator it = keyrays[0].begin(); it != keyrays[0].end(); ++it) {
_ray.push_back(keyToCoord(*it));
}
return true;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::deleteNodeRecurs(NODE* node){
assert(node);
// TODO: maintain tree size?
if (node->children != NULL) {
for (unsigned int i=0; i<8; i++) {
if (node->children[i] != NULL){
this->deleteNodeRecurs(static_cast<NODE*>(node->children[i]));
}
}
delete[] node->children;
node->children = NULL;
} // else: node has no children
delete node;
}
template <class NODE,class I>
bool OcTreeBaseImpl<NODE,I>::deleteNodeRecurs(NODE* node, unsigned int depth, unsigned int max_depth, const OcTreeKey& key){
if (depth >= max_depth) // on last level: delete child when going up
return true;
assert(node);
unsigned int pos = computeChildIdx(key, this->tree_depth-1-depth);
if (!nodeChildExists(node, pos)) {
// child does not exist, but maybe it's a pruned node?
if ((!nodeHasChildren(node)) && (node != this->root)) { // TODO double check for exists / root exception?
// current node does not have children AND it's not the root node
// -> expand pruned node
expandNode(node);
// tree_size and size_changed adjusted in createNodeChild(...)
} else { // no branch here, node does not exist
return false;
}
}
// follow down further, fix inner nodes on way back up
bool deleteChild = deleteNodeRecurs(getNodeChild(node, pos), depth+1, max_depth, key);
if (deleteChild){
// TODO: lazy eval?
// TODO delete check depth, what happens to inner nodes with children?
this->deleteNodeChild(node, pos);
if (!nodeHasChildren(node))
return true;
else{
node->updateOccupancyChildren(); // TODO: occupancy?
}
}
// node did not lose a child, or still has other children
return false;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::pruneRecurs(NODE* node, unsigned int depth,
unsigned int max_depth, unsigned int& num_pruned) {
assert(node);
if (depth < max_depth) {
for (unsigned int i=0; i<8; i++) {
if (nodeChildExists(node, i)) {
pruneRecurs(getNodeChild(node, i), depth+1, max_depth, num_pruned);
}
}
} // end if depth
else {
// max level reached
if (pruneNode(node)) {
num_pruned++;
}
}
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::expandRecurs(NODE* node, unsigned int depth,
unsigned int max_depth) {
if (depth >= max_depth)
return;
assert(node);
// current node has no children => can be expanded
if (!nodeHasChildren(node)){
expandNode(node);
}
// recursively expand children
for (unsigned int i=0; i<8; i++) {
if (nodeChildExists(node, i)) { // TODO double check (node != NULL)
expandRecurs(getNodeChild(node, i), depth+1, max_depth);
}
}
}
template <class NODE,class I>
std::ostream& OcTreeBaseImpl<NODE,I>::writeData(std::ostream &s) const{
if (root)
writeNodesRecurs(root, s);
return s;
}
template <class NODE,class I>
std::ostream& OcTreeBaseImpl<NODE,I>::writeNodesRecurs(const NODE* node, std::ostream &s) const{
node->writeData(s);
// 1 bit for each children; 0: empty, 1: allocated
std::bitset<8> children;
for (unsigned int i=0; i<8; i++) {
if (nodeChildExists(node, i))
children[i] = 1;
else
children[i] = 0;
}
char children_char = (char) children.to_ulong();
s.write((char*)&children_char, sizeof(char));
// std::cout << "wrote: " << value << " "
// << children.to_string<char,std::char_traits<char>,std::allocator<char> >()
// << std::endl;
// recursively write children
for (unsigned int i=0; i<8; i++) {
if (children[i] == 1) {
this->writeNodesRecurs(getNodeChild(node, i), s);
}
}
return s;
}
template <class NODE,class I>
std::istream& OcTreeBaseImpl<NODE,I>::readData(std::istream &s) {
if (!s.good()){
OCTOMAP_WARNING_STR(__FILE__ << ":" << __LINE__ << "Warning: Input filestream not \"good\"");
}
this->tree_size = 0;
size_changed = true;
// tree needs to be newly created or cleared externally
if (root) {
OCTOMAP_ERROR_STR("Trying to read into an existing tree.");
return s;
}
root = new NODE();
readNodesRecurs(root, s);
tree_size = calcNumNodes(); // compute number of nodes
return s;
}
template <class NODE,class I>
std::istream& OcTreeBaseImpl<NODE,I>::readNodesRecurs(NODE* node, std::istream &s) {
node->readData(s);
char children_char;
s.read((char*)&children_char, sizeof(char));
std::bitset<8> children ((unsigned long long) children_char);
//std::cout << "read: " << node->getValue() << " "
// << children.to_string<char,std::char_traits<char>,std::allocator<char> >()
// << std::endl;
for (unsigned int i=0; i<8; i++) {
if (children[i] == 1){
NODE* newNode = createNodeChild(node, i);
readNodesRecurs(newNode, s);
}
}
return s;
}
template <class NODE,class I>
unsigned long long OcTreeBaseImpl<NODE,I>::memoryFullGrid() const{
if (root == NULL)
return 0;
double size_x, size_y, size_z;
this->getMetricSize(size_x, size_y,size_z);
// assuming best case (one big array and efficient addressing)
// we can avoid "ceil" since size already accounts for voxels
// Note: this can be larger than the adressable memory
// - size_t may not be enough to hold it!
return (unsigned long long)((size_x/resolution) * (size_y/resolution) * (size_z/resolution)
* sizeof(root->getValue()));
}
// non-const versions,
// change min/max/size_changed members
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::getMetricSize(double& x, double& y, double& z){
double minX, minY, minZ;
double maxX, maxY, maxZ;
getMetricMax(maxX, maxY, maxZ);
getMetricMin(minX, minY, minZ);
x = maxX - minX;
y = maxY - minY;
z = maxZ - minZ;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::getMetricSize(double& x, double& y, double& z) const{
double minX, minY, minZ;
double maxX, maxY, maxZ;
getMetricMax(maxX, maxY, maxZ);
getMetricMin(minX, minY, minZ);
x = maxX - minX;
y = maxY - minY;
z = maxZ - minZ;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::calcMinMax() {
if (!size_changed)
return;
// empty tree
if (root == NULL){
min_value[0] = min_value[1] = min_value[2] = 0.0;
max_value[0] = max_value[1] = max_value[2] = 0.0;
size_changed = false;
return;
}
for (unsigned i = 0; i< 3; i++){
max_value[i] = -std::numeric_limits<double>::max();
min_value[i] = std::numeric_limits<double>::max();
}
for(typename OcTreeBaseImpl<NODE,I>::leaf_iterator it = this->begin(),
end=this->end(); it!= end; ++it)
{
double size = it.getSize();
double halfSize = size/2.0;
double x = it.getX() - halfSize;
double y = it.getY() - halfSize;
double z = it.getZ() - halfSize;
if (x < min_value[0]) min_value[0] = x;
if (y < min_value[1]) min_value[1] = y;
if (z < min_value[2]) min_value[2] = z;
x += size;
y += size;
z += size;
if (x > max_value[0]) max_value[0] = x;
if (y > max_value[1]) max_value[1] = y;
if (z > max_value[2]) max_value[2] = z;
}
size_changed = false;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::getMetricMin(double& x, double& y, double& z){
calcMinMax();
x = min_value[0];
y = min_value[1];
z = min_value[2];
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::getMetricMax(double& x, double& y, double& z){
calcMinMax();
x = max_value[0];
y = max_value[1];
z = max_value[2];
}
// const versions
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::getMetricMin(double& mx, double& my, double& mz) const {
mx = my = mz = std::numeric_limits<double>::max( );
if (size_changed) {
// empty tree
if (root == NULL){
mx = my = mz = 0.0;
return;
}
for(typename OcTreeBaseImpl<NODE,I>::leaf_iterator it = this->begin(),
end=this->end(); it!= end; ++it) {
double halfSize = it.getSize()/2.0;
double x = it.getX() - halfSize;
double y = it.getY() - halfSize;
double z = it.getZ() - halfSize;
if (x < mx) mx = x;
if (y < my) my = y;
if (z < mz) mz = z;
}
} // end if size changed
else {
mx = min_value[0];
my = min_value[1];
mz = min_value[2];
}
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::getMetricMax(double& mx, double& my, double& mz) const {
mx = my = mz = -std::numeric_limits<double>::max( );
if (size_changed) {
// empty tree
if (root == NULL){
mx = my = mz = 0.0;
return;
}
for(typename OcTreeBaseImpl<NODE,I>::leaf_iterator it = this->begin(),
end=this->end(); it!= end; ++it) {
double halfSize = it.getSize()/2.0;
double x = it.getX() + halfSize;
double y = it.getY() + halfSize;
double z = it.getZ() + halfSize;
if (x > mx) mx = x;
if (y > my) my = y;
if (z > mz) mz = z;
}
}
else {
mx = max_value[0];
my = max_value[1];
mz = max_value[2];
}
}
template <class NODE,class I>
size_t OcTreeBaseImpl<NODE,I>::calcNumNodes() const {
size_t retval = 0; // root node
if (root){
retval++;
calcNumNodesRecurs(root, retval);
}
return retval;
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::calcNumNodesRecurs(NODE* node, size_t& num_nodes) const {
assert (node);
if (nodeHasChildren(node)) {
for (unsigned int i=0; i<8; ++i) {
if (nodeChildExists(node, i)) {
num_nodes++;
calcNumNodesRecurs(getNodeChild(node, i), num_nodes);
}
}
}
}
template <class NODE,class I>
size_t OcTreeBaseImpl<NODE,I>::memoryUsage() const{
size_t num_leaf_nodes = this->getNumLeafNodes();
size_t num_inner_nodes = tree_size - num_leaf_nodes;
return (sizeof(OcTreeBaseImpl<NODE,I>) + memoryUsageNode() * tree_size + num_inner_nodes * sizeof(NODE*[8]));
}
template <class NODE,class I>
void OcTreeBaseImpl<NODE,I>::getUnknownLeafCenters(point3d_list& node_centers, point3d pmin, point3d pmax, unsigned int depth) const {
assert(depth <= tree_depth);
if (depth == 0)
depth = tree_depth;
point3d pmin_clamped = this->keyToCoord(this->coordToKey(pmin, depth), depth);
point3d pmax_clamped = this->keyToCoord(this->coordToKey(pmax, depth), depth);
float diff[3];
unsigned int steps[3];
float step_size = this->resolution * pow(2, tree_depth-depth);
for (int i=0;i<3;++i) {
diff[i] = pmax_clamped(i) - pmin_clamped(i);
steps[i] = static_cast<unsigned int>(floor(diff[i] / step_size));
// std::cout << "bbx " << i << " size: " << diff[i] << " " << steps[i] << " steps\n";
}
point3d p = pmin_clamped;
NODE* res;
for (unsigned int x=0; x<steps[0]; ++x) {
p.x() += step_size;
for (unsigned int y=0; y<steps[1]; ++y) {
p.y() += step_size;
for (unsigned int z=0; z<steps[2]; ++z) {
// std::cout << "querying p=" << p << std::endl;
p.z() += step_size;
res = this->search(p,depth);
if (res == NULL) {
node_centers.push_back(p);
}
}
p.z() = pmin_clamped.z();
}
p.y() = pmin_clamped.y();
}
}
template <class NODE,class I>
size_t OcTreeBaseImpl<NODE,I>::getNumLeafNodes() const {
if (root == NULL)
return 0;
return getNumLeafNodesRecurs(root);
}
template <class NODE,class I>
size_t OcTreeBaseImpl<NODE,I>::getNumLeafNodesRecurs(const NODE* parent) const {
assert(parent);
if (!nodeHasChildren(parent)) // this is a leaf -> terminate
return 1;
size_t sum_leafs_children = 0;
for (unsigned int i=0; i<8; ++i) {
if (nodeChildExists(parent, i)) {
sum_leafs_children += getNumLeafNodesRecurs(getNodeChild(parent, i));
}
}
return sum_leafs_children;
}
template <class NODE,class I>
double OcTreeBaseImpl<NODE,I>::volume() {
double x, y, z;
getMetricSize(x, y, z);
return x*y*z;
}
}