Octree.h

Go to the documentation of this file.

 
 
#pragma once
 
#include <Triangulation.h>
#include <cassert>
#include <iostream>
#include <stack>
#include <unordered_map>
#include <vector>
 
class OctreeNode {
public:
  OctreeNode() {
    locCode_ = 0;
    childExists_ = 0;
  }
  OctreeNode(uint32_t location) {
    locCode_ = location;
    childExists_ = 0;
  }
 
  ~OctreeNode() = default;
 
protected:
  uint32_t locCode_;
  uint8_t childExists_;
  std::vector<ttk::SimplexId> vertexIds_;
  std::vector<ttk::SimplexId> cellIds_;
 
  friend class Octree;
};
 
class Octree : public virtual ttk::Debug {
public:
  Octree(const ttk::AbstractTriangulation *t);
  Octree(const ttk::AbstractTriangulation *t, const int k);
  ~Octree() override;
  void initialize(const ttk::AbstractTriangulation *t, const int k);
 
  bool empty();
 
  size_t getNodeTreeDepth(const OctreeNode *node);
 
  OctreeNode *getParentNode(OctreeNode *node);
 
  void visitAll(const OctreeNode *node);
 
  int verifyTree(ttk::SimplexId &vertexNum);
 
  int insertVertex(ttk::SimplexId &vertexId);
 
  int insertCell(ttk::SimplexId &cellId);
 
  void reindex(std::vector<ttk::SimplexId> &vertices,
               std::vector<ttk::SimplexId> &nodes,
               std::vector<ttk::SimplexId> &cells);
 
private:
  const ttk::AbstractTriangulation *triangulation_;
  std::unordered_map<uint32_t, OctreeNode> allNodes_;
  int capacity_;
  std::array<float, 3> center_{}, size_{};
 
  inline OctreeNode *lookupNode(uint32_t locCode) {
    const auto iter = allNodes_.find(locCode);
    return (iter == allNodes_.end() ? nullptr : &(iter->second));
  }
 
  void computeCenterSize(uint32_t location,
                         std::array<float, 3> &centerArr,
                         std::array<float, 3> &sizeArr);
 
  uint32_t getChildLocation(uint32_t parLoc,
                            ttk::SimplexId vertexId,
                            const std::array<float, 3> &centerArr);
 
  void subdivide(OctreeNode *node);
};