Octree

The octree functionality is encapsulated in the namespace EBGeometry::Octree. For the full API, see the doxygen API. Currently, only full octrees are supported (i.e., using a pointer-based representation).

Octrees are encapsulated by a class

  template <typename Meta, typename Data = void>
  class Node : public std::enable_shared_from_this<Node<Meta, Data>>

where the template parameters are:

• Meta Meta-information contained in the node (e.g. upper/lower corners).

• Data Data contained in the node.

Node describes both regular and leaf nodes in the octree.

Warning

Octree::Node<Meta, Data> should only be used as std::shared_ptr<Octree::Node<Meta, Data>>.

Construction

Constructing the octree is done by first initializing the root node and then building it in either depth-first or breadth-first ordering.

  template <typename Meta, typename Data = void>
  class Node : public std::enable_shared_from_this<Node<Meta, Data>>
  {
    using StopFunction = std::function<bool(const Node<Meta, Data>& a_node)>;
    using MetaConstructor = std::function<Meta(const OctantIndex& a_index, const Meta& a_parentMeta)>;
    using DataConstructor =
      std::function<std::shared_ptr<Data>(const OctantIndex& a_index, const std::shared_ptr<Data>& a_parentData)>;
    using Updater = std::function<void(const Node<Meta, Data>& a_node)>;
    using Visiter = std::function<bool(const Node<Meta, Data>& a_node)>;
    using Sorter = std::function<void(std::array<std::shared_ptr<const Node<Meta, Data>>, 8>& a_children)>;

    inline void
    buildDepthFirst(const StopFunction&    a_stopFunction,
                    const MetaConstructor& a_metaConstructor,
                    const DataConstructor& a_dataConstructor) noexcept;

    inline void
    buildBreadthFirst(const StopFunction&    a_stopFunction,
                      const MetaConstructor& a_metaConstructor,
                      const DataConstructor& a_dataConstructor) noexcept;

  };
} // namespace Octree

The input functions to buildDepthFirst and buildBreadthFirst are as follows:

1. StopFunction determines if the node should be split or not. If it returns true, the node will not be split.

2. MetaConstructor constructs meta-data in the child nodes. This can/should include the physical corners of the node, but this is not a requirement.

3. DataConstructor constructs data in the child node. This can e.g. be a partitioning of the parent data.

Tree traversal

  template <typename Meta, typename Data = void>
  class Node : public std::enable_shared_from_this<Node<Meta, Data>>
  {
    inline void
    traverse(
      const Updater& a_updater,
      const Visiter& a_visiter,
      const Sorter&  a_sorter = [](std::array<std::shared_ptr<const Node<Meta, Data>>, 8>& a_children) -> void {
        return;
      }) const noexcept;

The input functions to traverse are as follows:

1. Updater executes a user-specified update rule when visiting a leaf node.

2. Visiter determines if the node should be visited during the traversal or not.

3. Sorter permits the user to sort the nodes in the current subtrees and visit them in a specified pattern. By default, no sorting is done and the nodes are visited in lexicographical order.

Example

An example of how to use the Octree functionality is given in EBGeometry_ImplicitFunctionImplem.hpp where the octree functionality is used for spatial partitioning of an implicit function. This includes both the octree construction and traversal.