文章/答案/技术大牛

发布

社区首页 >问答首页 >简单八叉树实现

问简单八叉树实现
EN

Code Review用户

提问于 2016-04-05 21:47:52

回答 2查看 7.8K关注 0票数 5

我已经实现了一个非常简单的八叉树，但是我觉得编码风格或某些实现没有那么好。特别是，我使用了一些讨厌的void指针和额外的news，因为我找不到工会，我希望能替换它(我想也许模板可以解决这个问题，但任何反馈都是值得赞赏的)。

有几种方法我不太感兴趣，它们都在接口中，但还没有实现。可以随意忽略它们，因为它们不应该对代码的其余部分产生实质性影响。

最后，我并不是要对八叉树的结构进行彻底的修改--我将在稍后的时间实现一些其他版本(即无后置二元论，一些其他有趣的版本)，所以请检查这个结构，其中每个节点都有一个指向8个子节点的指针。

Octree.h

/*
    file - octree.h

    Templated implementation of an octree for a cpu

 */


#ifndef OCTREE_CPU_H
#define OCTREE_CPU_H

#include <algorithm>
#include <array>
#include <cstddef>
#include <iterator>
#include <limits>
#include <utility>
#include <type_traits>

#include "boundingbox.h"

using Point = std::array<double, 3>;

template <typename InputIterator, class PointExtractor, 
          size_t max_per_node = 16, size_t max_depth = 100>
class Octree {
 public:
  using tree_type = Octree<InputIterator, PointExtractor, max_per_node, max_depth>;

  Octree();

  Octree(InputIterator begin, InputIterator end);

  Octree(InputIterator begin, InputIterator end, PointExtractor f);

  Octree(const tree_type& rhs);

  template <size_t max_per_node_>
  Octree(const Octree<InputIterator, PointExtractor, max_per_node_, max_depth>& rhs);

  template <size_t max_depth_>
  Octree(const Octree<InputIterator, PointExtractor, max_per_node, max_depth_>& rhs);

  template <size_t max_per_node_, size_t max_depth_>
  Octree(const Octree<InputIterator, PointExtractor, max_per_node_, max_depth_>& rhs);

  Octree(tree_type&& rhs);

  void swap(tree_type& rhs);

  template <typename OutputIterator>
  bool search(const BoundingBox& box, OutputIterator& it) const;

  tree_type& operator=(tree_type rhs);

  tree_type& operator=(tree_type&& rhs);

  ~Octree();

  size_t size() const;

 private:  
  class Node;

  enum NodeContents {
    LEAF = 1,
    MAX_DEPTH_LEAF = 2,
    INTERNAL = 4
  };

  struct LeafNodeValues {
    std::array<std::pair<InputIterator, Point>, max_per_node> values_;
    size_t size_;
  };

  using childNodeArray = std::array<Node*, 8>;
  using maxItemNode = std::vector<std::pair<InputIterator, Point>>;

  class Node {
   public:    
    Node(const std::vector<std::pair<InputIterator, Point>>& input_values);

    Node(const std::vector<std::pair<InputIterator, Point>>& input_values, 
         const BoundingBox& box,
         size_t current_depth);

    ~Node();

    template <typename OutputIterator>
    bool search(const BoundingBox& box, OutputIterator& it) const;

   private:
    void* value_;
    BoundingBox extrema_;
    NodeContents tag_;

    void init_max_depth_leaf(const std::vector<std::pair<InputIterator, Point>>& input_values);

    void init_leaf(const std::vector<std::pair<InputIterator, Point>>& input_values);

    void init_internal(
        const std::vector<std::pair<InputIterator, Point>>& input_values,
        size_t current_depth);

    unsigned int getOctantIndex(const Point& p) const;

    struct InnerIterator {
      using wrapped_type = typename std::vector<std::pair<InputIterator, Point>>::const_iterator;
      wrapped_type it_;

      InnerIterator(wrapped_type it) : it_(it) {}

      Point operator*() const {
        return std::get<1>(*it_);
      }

      InnerIterator& operator++() {
        ++it_;
        return *this;
      }

      InnerIterator operator++(int) {
        InnerIterator other = *this;
        ++it_;
        return other;
      }

      bool operator==(const InnerIterator& rhs) const {
        return it_ == rhs.it_;
      }

      bool operator!=(const InnerIterator& rhs) const {
        return !operator==(rhs);
      }
    };
  };

  PointExtractor functor_;
  Node* head_;
  size_t size_;
};

// convenience macros to avoid typing so much
#define OCTREE Octree<InputIterator, PointExtractor, max_per_node, max_depth>
#define OCTREE_TEMPLATE typename InputIterator, class PointExtractor, size_t max_per_node, size_t max_depth

template <OCTREE_TEMPLATE>
OCTREE::Octree(): functor_(PointExtractor()), head_(nullptr), size_(0) {}

template <OCTREE_TEMPLATE>
OCTREE::Octree(InputIterator begin, InputIterator end)
  : Octree(begin, end, PointExtractor()) { }

template <OCTREE_TEMPLATE>
OCTREE::Octree(InputIterator begin, InputIterator end, PointExtractor f)
    : functor_(f), head_(nullptr), size_(0) {

  std::vector<std::pair<InputIterator, Point>> v;
  v.reserve(std::distance(begin, end));

  for (auto it = begin; it != end; ++it) {
    v.push_back(std::pair<InputIterator, Point>(it, functor_(*it)));
  }

  size_ = v.size();
  head_ = new Node(v);
}

template <OCTREE_TEMPLATE>
OCTREE::Octree(OCTREE::tree_type&& rhs) 
  : functor_(rhs.functor), head_(rhs.head_), size_(rhs.size_) { }

template <OCTREE_TEMPLATE>
void OCTREE::swap(OCTREE::tree_type& rhs) {
  std::swap(head_, rhs.head_);
  std::swap(functor_, rhs.functor_);
  std::swap(size_, rhs.size_);
}

template <OCTREE_TEMPLATE>
template <typename OutputIterator>
bool OCTREE::search(const BoundingBox& box, OutputIterator& it) const {
  return head_->search(box, it);
}

template <OCTREE_TEMPLATE>
typename OCTREE::tree_type& OCTREE::operator=(typename OCTREE::tree_type rhs) {
  swap(rhs);
  return *this;
}

template <OCTREE_TEMPLATE>
typename OCTREE::tree_type& OCTREE::operator=(typename OCTREE::tree_type&& rhs) {
  swap(rhs);
  return *this;
}

template <OCTREE_TEMPLATE>
OCTREE::~Octree() {
  delete head_;
}

template <OCTREE_TEMPLATE>
size_t OCTREE::size() const {
  return size_;
}

template <OCTREE_TEMPLATE>
OCTREE::Node::Node(const std::vector<std::pair<InputIterator, Point>>& input_values)
  : Node(input_values, 
         BoundingBox(InnerIterator(input_values.begin()), InnerIterator(input_values.end())),
         0) { }

template <OCTREE_TEMPLATE>
OCTREE::Node::Node(
    const std::vector<std::pair<InputIterator, Point>>& input_values, 
    const BoundingBox& box,
    size_t current_depth) : value_(nullptr), extrema_(box)  {
  if (current_depth > max_depth) {
    init_max_depth_leaf(input_values);
  } else if (input_values.size() <= max_per_node) {
    init_leaf(input_values);
  } else {
    init_internal(input_values, current_depth);
  }
}

template <OCTREE_TEMPLATE>
OCTREE::Node::~Node() {
  if (tag_ == NodeContents::INTERNAL) {
    childNodeArray* children = static_cast<childNodeArray*>(value_);
    for (size_t i = 0; i < 8; ++i) {
      delete children[0][i];
      children[0][i] = nullptr;
    }
    delete children;
  } else if (tag_ == NodeContents::LEAF) {
    delete static_cast<LeafNodeValues*>(value_);
  } else if (tag_ == NodeContents::MAX_DEPTH_LEAF) {
    delete static_cast<maxItemNode*>(value_);
  }

  value_ = nullptr;
}

template <OCTREE_TEMPLATE>
template <typename OutputIterator>
bool OCTREE::Node::search(const BoundingBox& p, OutputIterator& it) const {
  bool success = false;
  if (tag_ == NodeContents::INTERNAL) {
    childNodeArray& children = *static_cast<childNodeArray*>(value_);
    for (auto child : children) {
      if (child) {
        success = child->search(p, it) || success;
      }
    }
  } else if (tag_ == NodeContents::LEAF) {
    LeafNodeValues& children = *static_cast<LeafNodeValues*>(value_);
    for (size_t i = 0; i < children.size_; ++i) {
      Point& point = std::get<1>(children.values_[i]);
      if (p.contains(point)) {
        *it = std::get<0>(children.values_[i]);
        ++it;
        success = true;
      }
    }
  } else if (tag_ == NodeContents::MAX_DEPTH_LEAF) {
    maxItemNode& children = *static_cast<maxItemNode*>(value_);
    for (auto child : children) {
      Point& point = std::get<1>(child);
      if (p.contains(point)) {
        *it = std::get<0>(child);
        ++it;
        success = true;
      }
    }
  }
  return success;
}

template <OCTREE_TEMPLATE>
void OCTREE::Node::init_max_depth_leaf(
    const std::vector<std::pair<InputIterator, Point>>& input_values) {  
  value_ = new std::vector<std::pair<InputIterator, Point>>(input_values);
  tag_ = NodeContents::MAX_DEPTH_LEAF;
}

template <OCTREE_TEMPLATE>
void OCTREE::Node::init_leaf(
    const std::vector<std::pair<InputIterator, Point>>& input_values)  {
  std::array<std::pair<InputIterator, Point>, max_per_node> a;
  std::copy(input_values.begin(), input_values.end(), a.begin());
  value_ = new LeafNodeValues{a, input_values.size()};
  tag_ = NodeContents::LEAF;
}

template <OCTREE_TEMPLATE>
void OCTREE::Node::init_internal(
    const std::vector<std::pair<InputIterator, Point>>& input_values,
    size_t current_depth)  {
  std::array<std::vector<std::pair<InputIterator, Point>>, 8> childVectors;
  std::array<BoundingBox, 8> boxes = extrema_.partition();
  std::array<Node*, 8> children;

  for (unsigned child = 0; child < 8; ++child) {
    std::vector<std::pair<InputIterator, Point>>& childVector = childVectors[child];
    childVector.reserve(input_values.size() / 8);

    std::copy_if(
      input_values.begin(), 
      input_values.end(), 
      std::back_inserter(childVector),
      [&boxes, child](const std::pair<InputIterator, Point>& element) -> bool {
        Point p = std::get<1>(element);
        return boxes[child].contains(p);
      }
    );

    children[child] = childVector.empty()
        ? nullptr
        : new Node(childVector, boxes[child], ++current_depth);
  }

  value_ = new std::array<Node*, 8>(children);
  tag_ = NodeContents::INTERNAL;
}

template <OCTREE_TEMPLATE>
unsigned int OCTREE::Node::getOctantIndex(const Point& p) const {
  // children are ordered left to right, front to back, bottom to top.

  double xmid = (extrema_.xhi - extrema_.xlo) / 2.;
  double ymid = (extrema_.yhi - extrema_.ylo) / 2.;
  double zmid = (extrema_.zhi - extrema_.zlo) / 2.;
  bool left = p[0] < xmid && p[0] >= extrema_.xlo;
  bool front = p[1] < ymid && p[1] >= extrema_.ylo;
  bool bottom = p[2] < zmid && p[2] >= extrema_.zlo;

  if (bottom && left && front) {
    return 0;
  } else if (bottom && !left && front) {
    return 1;
  } else if (bottom && left && !front) {
    return 2;
  } else if (bottom && !left && !front) {
    return 3;
  } else if (!bottom && left && front) {
    return 4;
  } else if (!bottom && !left && front) {
    return 5;
  } else if (!bottom && left && !front) {
    return 6;
  } else {
    return 7;
  }
}

#endif // DEFINED OCTREE_CPU_H

boundingbox.h

#ifndef BOUNDINGBOX_H
#define BOUNDINGBOX_H

#include <array>
#include <limits>
#include <cmath>
#include <iostream>

// An axis aligned bounding boxed (AABB)
struct BoundingBox {
  BoundingBox() = default;
  template <typename InputIterator>
  BoundingBox(InputIterator begin, InputIterator end);
  BoundingBox(std::initializer_list<double> l);
  BoundingBox(BoundingBox&& rhs);
  BoundingBox(const BoundingBox&) = default;

  BoundingBox& operator=(BoundingBox&) = default;
  BoundingBox& operator=(BoundingBox&& rhs);
  BoundingBox& operator=(const BoundingBox& rhs);

  ~BoundingBox() = default;

  bool contains(const BoundingBox& other) const;
  bool contains(const std::array<double, 3>& point) const;

  bool overlap(const BoundingBox& other, BoundingBox* out) const;

  std::array<BoundingBox, 8> partition() const;

  bool operator==(const BoundingBox& rhs) const;

  bool operator!=(const BoundingBox& rhs) const;

  friend
  std::ostream& operator<<(std::ostream& stream, const BoundingBox& rhs);

  double xhi, xlo, yhi, ylo, zhi, zlo;
};

const BoundingBox initial = BoundingBox{
    std::numeric_limits<double>::min(), std::numeric_limits<double>::max(),
    std::numeric_limits<double>::min(), std::numeric_limits<double>::max(),
    std::numeric_limits<double>::min(), std::numeric_limits<double>::max()
};

const BoundingBox invalid = BoundingBox{
    std::numeric_limits<double>::quiet_NaN(), std::numeric_limits<double>::quiet_NaN(), 
    std::numeric_limits<double>::quiet_NaN(), std::numeric_limits<double>::quiet_NaN(), 
    std::numeric_limits<double>::quiet_NaN(), std::numeric_limits<double>::quiet_NaN()
};

template <typename InputIterator>
BoundingBox::BoundingBox(InputIterator begin, InputIterator end) : BoundingBox(initial) {
  for (; begin != end; ++begin) {
    const std::array<double, 3>& point = *begin;

    if (point[0] < xlo) {
      xlo = point[0];
    } else if (point[0] > xhi) {
      xhi = point[0];
    }

    if (point[1] < ylo) {
      ylo = point[1];
    } else if (point[1] > yhi) {
      yhi = point[1];
    }

    if (point[2] < zlo) {
      zlo = point[2];
    } else if (point[2] > zhi) {
      zhi = point[2];
    }
  }
}

#endif // defined BOUNDINGBOX_H

boundingbox.cc

#include "boundingbox.h"

#include <algorithm>
#include <array>
#include <limits>
#include <cmath>
#include <iostream>
#include <utility>

using std::array;
using std::initializer_list;

BoundingBox::BoundingBox(BoundingBox&& rhs) {
  xhi = std::move(rhs.xhi);
  xlo = std::move(rhs.xlo);
  yhi = std::move(rhs.yhi);
  ylo = std::move(rhs.ylo);
  zhi = std::move(rhs.zhi);
  zlo = std::move(rhs.zlo);
}

BoundingBox::BoundingBox(initializer_list<double> l) {
  std::copy(l.begin(), l.end(), &xhi);
}

BoundingBox& BoundingBox::operator=(const BoundingBox& rhs) {
  std::copy(&rhs.xhi, &rhs.xhi + 6, &xhi);
  return *this;
}

BoundingBox& BoundingBox::operator=(BoundingBox&& rhs) {
  xhi = std::move(rhs.xhi);
  xlo = std::move(rhs.xlo);
  yhi = std::move(rhs.yhi);
  ylo = std::move(rhs.ylo);
  zhi = std::move(rhs.zhi);
  zlo = std::move(rhs.zlo);
  return *this;
}

bool BoundingBox::contains(const BoundingBox& other) const {
  return xlo <= other.xlo && xhi >= other.xhi &&
         ylo <= other.ylo && yhi >= other.yhi &&
         zlo <= other.zlo && zhi >= other.zhi;
}

bool BoundingBox::contains(const std::array<double, 3>& point) const {
  return xlo <= point[0] && xhi > point[0] &&
         ylo <= point[1] && yhi > point[1] &&
         zlo <= point[2] && zhi > point[2];
}

bool BoundingBox::overlap(const BoundingBox& other, BoundingBox* out) const {
  // trivial cases
  if (contains(other)) {
    *out = other;
    return true;
  } else if (other.contains(*this)) {
    *out = *this;
    return true;
  } 

  // Check if there is no intersection
  if (xhi < other.xlo || xlo > other.xhi ||
      yhi < other.ylo || ylo > other.yhi ||
      zhi < other.zlo || zlo > other.zhi) {
    *out = invalid;
    return false;
  }

  // Actually calculate the bounds
  double upperX = std::min(xhi, other.xhi);
  double upperY = std::min(yhi, other.yhi);
  double upperZ = std::min(zhi, other.zhi);

  double lowerX = std::max(xlo, other.xlo);
  double lowerY = std::max(ylo, other.ylo);
  double lowerZ = std::max(zlo, other.zlo);

  *out = BoundingBox{upperX, lowerX, upperY, lowerY, upperZ, lowerZ};
  return true;
}

array<BoundingBox, 8> BoundingBox::partition() const {
  double xmid = (xhi - xlo) / 2.;
  double ymid = (yhi - ylo) / 2.;
  double zmid = (zhi - zlo) / 2.;

  std::array<BoundingBox, 8> ret{{
    BoundingBox{xmid, xlo, ymid, ylo, zmid, zlo}, // bottom left front
    BoundingBox{xhi, xmid, ymid, ylo, zmid, zlo}, // bottom right front
    BoundingBox{xmid, xlo, yhi, ymid, zmid, zlo}, // bottom left back
    BoundingBox{xhi, xmid, yhi, ymid, zmid, zlo}, // bottom right back
    BoundingBox{xmid, xlo, ymid, ylo, zhi, zmid}, // top left front
    BoundingBox{xhi, xmid, ymid, ylo, zhi, zmid}, // top right front
    BoundingBox{xmid, xlo, yhi, ymid, zhi, zmid}, // top left back
    BoundingBox{xhi, xmid, yhi, ymid, zhi, zmid}  // top right back
  }};
  return ret;
}

bool BoundingBox::operator==(const BoundingBox& rhs) const {
  // They're all equal, or they're all NaNs
  return (xhi == rhs.xhi && xlo == rhs.xlo &&
          yhi == rhs.yhi && ylo == rhs.ylo &&
          zhi == rhs.zhi && zlo == rhs.zlo) ||
         (std::isnan(xhi) && std::isnan(rhs.xhi) &&
          std::isnan(xlo) && std::isnan(rhs.xlo) &&
          std::isnan(yhi) && std::isnan(rhs.yhi) &&
          std::isnan(ylo) && std::isnan(rhs.ylo) &&
          std::isnan(zhi) && std::isnan(rhs.zhi) &&
          std::isnan(zlo) && std::isnan(rhs.zlo));
}

bool BoundingBox::operator!=(const BoundingBox& rhs) const {
  return !operator==(rhs);
}

std::ostream& operator<<(std::ostream& stream, const BoundingBox& rhs) {
  stream << "{" << rhs.xhi << ", " << rhs.xlo << ", "
                << rhs.yhi << ", " << rhs.ylo << ", "
                << rhs.zhi << ", " << rhs.zlo << ", "
         << "}";
  return stream;
}

c++

c++11

tree

coordinate-system

回答 2

Code Review用户

发布于 2016-04-06 03:32:54

我只看BoundingBox课程。有很多有趣的清理可以应用于它：

丢弃构造函数

BoundingBox是普通老数据(过氧化物酶)类型。它只包含少量的doubles，因此编译器将提供所有必要的默认构造函数和操作符，包括：

复制构造函数
赋值算子
无操作析构函数

移动操作符和移动-分配是没有意义的。您不能移动double，它适合机器寄存器，所以您实现的寄存器基本上与复制构造函数相同。您的复制/赋值代码本质上是在执行不安全的内存副本，甚至可能比编译器省略它们时生成的默认值效率更低。

但我们还有这两个：

BoundingBox(InputIterator begin，InputIterator end)；BoundingBox(std::initializer_list l)；

初始化程序列表构造函数很酷，它允许您编写如下代码：

BoundingBox bb = { 1.0, 2.0, 3.0,  4.0, 5.0, 6.0 };

但事实证明，你甚至不需要定义一个。如果您移除所有其他构造函数，并将所有数据公有，就像现在一样，您可以用这个语法初始化一个struct实例。

但是要使聚合式初始化正常工作，我们需要删除所有用户定义的构造函数，因此begin/end范围构造函数必须删除。考虑到这将大大简化代码，我认为这是一个公平的交易，因此，可以考虑将构造函数转换为助手函数：

template <typename InputIterator>
BoundingBox makeBoundingBox(InputIterator begin, InputIterator end);

BoundingBox的复制成本很低，因此该函数应该与构造函数一样快，前提是它不是内联的(这很可能，因为它是一个模板)。

类型是您的朋友

因此，不要害怕结交新朋友(即创建其他助手类型) ;)

该成员的数据：

双喜、乐、志、卓；

应该是一种类型，如Point3D：

struct Point3D {
    double x;
    double y;
    double z;
};

我可以看到，通过使用由3个元素组成的std::array，您已经拥有了一个准Point3D，但是我建议将它作为一个结构本身，这样它就可以有方法，也可以拥有比v[0], v[1], v[2]更好的v.x, v.y v.z语法。

Miscellaneous

流输出操作符不必是朋友函数。该结构没有私有数据。仅当您希望允许访问所述类型的私有数据时，才使用friend。只是让它成为一个独立的功能。
比较操作符太大了。假设我们采用了Point3D的想法，它可以重写如下: bool BoundingBox::operator == (const BoundingBox& rhs) const { const bool allEqual = (mins == rhs.mins & maxs == rhs.maxs)；if (allEqual)返回true；const bool allNaN = (mins.isNaN() & rhs.mins.isNaN() & maxs.isNaN() && rhs.maxs.isNaN() && rhs.maxs.isNaN()；if (allNaN)返回true；返回false；}上面的几个注释：
- 我使用了mins和maxs这两个名字作为边框范围。对于这个特定的数据结构，这是一个非常常见的符号，所以我建议坚持这样做。
- 还请注意，将浮点数与==进行比较并不是非常可靠的。它们容易出现浮点四舍五入错误，因此您可能会得到两个非常接近的数字，对于所有目的来说，这些数字都是相等的，但最终会比较不相等。看看如何比较给定epsilon内的浮动是否相等上的堆栈溢出。

总之，在建议的更改之后，这就是您的轴对齐边界框的样子：

struct Point3D {
    double x;
    double y;
    double z;

    bool isNaN() const;
    bool operator == (const Point3D& other) const;
};

struct BoundingBox {
    Point3D mins;
    Point3D maxs;

    bool contains(const BoundingBox& other) const;
    bool contains(const Point3D& point) const;

    bool overlap(const BoundingBox& other, BoundingBox* out) const;
    std::array<BoundingBox, 8> partition() const;

    bool operator == (const BoundingBox& rhs) const;
    bool operator != (const BoundingBox& rhs) const;
};

template <typename InputIterator>
BoundingBox makeBoundingBox(InputIterator begin, InputIterator end);
std::ostream& operator << (std::ostream& stream, const BoundingBox& rhs);

票数 6

Code Review用户

发布于 2016-04-05 23:11:52

这绝不是一个完整的回顾(有大量的代码)，只是很少的笔记，在第一次阅读跳出。

getOctantCode以非常长的方式计算结果。考虑返回(！底部<< 2) \！左<< 1) \{e76f}\x{e76f}(前面)；
我不认为特殊的大小写“琐碎情况”在任何方面都简化了BoundingBox::overlap。
我不确定是否有任何保证xhi, xlo, yhi, ylo, zhi, zlo;将如何部署在内存中。代码：：copy( &rhs.xhi，&rhs.xhi+ 6，&xhi)；

似乎假设它们是顺序的，并且作为数组访问它们是安全的。也许这是正常的，并要求标准，但一个审查员肯定是绊倒。

票数 3

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/124883

复制

相似问题

问简单八叉树实现
EN

回答 2

Code Review用户

丢弃构造函数

类型是您的朋友

Miscellaneous

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问简单八叉树实现EN

回答 2

Code Review用户

丢弃构造函数

类型是您的朋友

Miscellaneous

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问简单八叉树实现
EN