TetrahedralTree.hh

Go to the documentation of this file.

#ifndef TETRAHEDRAL_TREE_H
#define TETRAHEDRAL_TREE_H
 
#include <vector>
 
#define BLOCK_CAPACITY 10  // k_v
 
namespace Garfield {
 
// TODO: replace this class with ROOT's TVector3 class
 
struct Vec3 {
  float x, y, z;
 
  Vec3() {}
  Vec3(float _x, float _y, float _z) : x(_x), y(_y), z(_z) {}
 
  Vec3 operator+(const Vec3& r) const {
    return Vec3(x + r.x, y + r.y, z + r.z);
  }
 
  Vec3 operator-(const Vec3& r) const {
    return Vec3(x - r.x, y - r.y, z - r.z);
  }
 
  Vec3& operator+=(const Vec3& r) {
    x += r.x;
    y += r.y;
    z += r.z;
    return *this;
  }
 
  Vec3& operator-=(const Vec3& r) {
    x -= r.x;
    y -= r.y;
    z -= r.z;
    return *this;
  }
 
  Vec3 operator*(float r) const { return Vec3(x * r, y * r, z * r); }
 
  Vec3 operator/(float r) const { return Vec3(x / r, y / r, z / r); }
};
 
/**
 
\brief Helper class for searches in field maps.
 
This class stores the mesh nodes and elements in an Octree data
structure to optimize the element search operations
 
Author: Ali Sheharyar
 
Organization: Texas A&M University at Qatar
 
*/
class TetrahedralTree {
 
 private:
  // Physical position/size. This implicitly defines the bounding
  // box of this node
  Vec3 m_origin;         // The physical center of this node
  Vec3 m_halfDimension;  // Half the width/height/depth of this node
 
  Vec3 min, max;  // storing min and max points for convenience
 
  // The tree has up to eight children and can additionally store
  // a list of mesh nodes and mesh elements (Tetrahedron)
  TetrahedralTree* children[8];  // Pointers to child octants
 
  // Children follow a predictable pattern to make accesses simple.
  // Here, - means less than 'origin' in that dimension, + means greater than.
  // child: 0 1 2 3 4 5 6 7
  // x:      - - - - + + + +
  // y:      - - + + - - + +
  // z:      - + - + - + - +
 
  struct OctreeBlockElem {
    Vec3 point;
    int nodeIndex;
 
    OctreeBlockElem(const Vec3& _point, const int _ni)
        : point(_point), nodeIndex(_ni) {}
  };
 
  std::vector<OctreeBlockElem> iBlockElems;
  std::vector<int> tetList;
 
 public:
  // Constructor
  TetrahedralTree(const Vec3& origin, const Vec3& halfDimension);
 
  // Destructor
  ~TetrahedralTree();
 
  // Insert a mesh node (a vertex/point) to the tree
  void InsertMeshNode(Vec3 point, const int nodeIndex);
 
  // Insert the mesh element (a tetrahedron) to the tree
  void InsertTetrahedron(const double elemBoundingBox[6], const int elemIndex);
 
  // Get all tetrahedra linked to a block corresponding to the given point
  std::vector<int> GetTetListInBlock(const Vec3& point);
 
 private:
  // Check if the given box overlaps with the box corresponding to this tree
  // node
  bool DoesBoxOverlap(const Vec3& b_min, const Vec3& b_max) const;
 
  int GetOctantContainingPoint(const Vec3& point) const;
 
  // Check if the tree node is full
  bool IsFull() const;
 
  // Check if the tree node is empty
  bool IsEmpty() const;
 
  // Check if this tree node is a leaf or intermediate node
  bool IsLeafNode() const;
 
  // Get a block containing the input point
  const TetrahedralTree* GetBlockFromPoint(const Vec3& point);
 
  // A helper function used by the function above. 
  // Called recursively on the child nodes.
  const TetrahedralTree* GetBlockFromPointHelper(const Vec3& point);
};
}
 
#endif