src/libengrid/octree.h

   1 // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   2 // +                                                                      +
   3 // + This file is part of enGrid.                                         +
   4 // +                                                                      +
   5 // + Copyright 2008-2014 enGits GmbH                                      +
   6 // +                                                                      +
   7 // + enGrid is free software: you can redistribute it and/or modify       +
   8 // + it under the terms of the GNU General Public License as published by +
   9 // + the Free Software Foundation, either version 3 of the License, or    +
  10 // + (at your option) any later version.                                  +
  11 // +                                                                      +
  12 // + enGrid is distributed in the hope that it will be useful,            +
  13 // + but WITHOUT ANY WARRANTY; without even the implied warranty of       +
  14 // + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the        +
  15 // + GNU General Public License for more details.                         +
  16 // +                                                                      +
  17 // + You should have received a copy of the GNU General Public License    +
  18 // + along with enGrid. If not, see <http://www.gnu.org/licenses/>.       +
  19 // +                                                                      +
  20 // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  21 #ifndef OCTREE_H
  22 #define OCTREE_H
  23
  24 class Octree;
  25
  26 #include "egvtkobject.h"
  27
  28 // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  29
  30 class OctreeNode
  31 {
  32
  33   friend class Octree;
  34
  35   vec3_t m_Position;
  36
  37 public:
  38
  39   vec3_t& getPosition()                { return m_Position; }
  40   void    setPosition(const vec3_t& x) { m_Position = x; }
  41
  42 };
  43
  44 // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  45
  46 /**
  47   * A cell of an octree.<br/>
  48   * <br/>
  49   * <b>The node numbering is as follows:</b><br/>
  50   * <pre>
  51   * 0: i,  j,  k
  52   * 1: i+1,j,  k
  53   * 2: i,  j+1,k
  54   * 3: i+1,j+1 k
  55   * 4: i,  j,  k+1
  56   * 5: i+1,j,  k+1
  57   * 6: i,  j+1,k+1
  58   * 7: i+1,j+1,k+1
  59   * </pre>
  60   * <b>The face numbering is as follows:</b><br/>
  61   * <pre>
  62   * 0: 0,4,6,2
  63   * 1: 1,3,7,5
  64   * 2: 0,1,5,4
  65   * 3: 3,2,6,7
  66   * 4: 0,2,3,1
  67   * 5: 4,5,7,6
  68   * </pre>
  69   * Child cells are numbered in the same way as the nodes.
  70   */
  71 class OctreeCell
  72 {
  73
  74   friend class Octree;
  75
  76   int m_Node[8];
  77   int m_Child[8];
  78   int m_Neighbour[6];
  79   int m_Parent;
  80   int m_Level;
  81
  82 public:
  83
  84   OctreeCell();
  85
  86   int  getNode     (int i) { return m_Node[i]; }
  87   bool hasChildren ()      { return m_Child[0] != -1; }
  88   int  getParent   ()      { return m_Parent; }
  89   int  getNeighbour(int i) { return m_Neighbour[i]; }
  90
  91   /**
  92     * Find a node by global index.
  93     * @param octree the octree which holds this cell
  94     * @param the global node index in the octree
  95     * @return the local node index (0-7)
  96     */
  97   int findNode(int i_node);
  98
  99   /**
 100     * Get the 'middle' node of an edge.
 101     * @param octree the octree which holds this cell
 102     * @param n1 the first node of the edge in local coordinates (0 <= n1 <= 7)
 103     * @param n2 the second node of the edge in local coordinates (0 <= n2 <= 7)
 104     * @param this_cell_only if set to true the search will be restricted to this cell
 105     */
 106   int  getEdgeNode(Octree* octree, int n1, int n2, bool this_cell_only = false);
 107
 108   void getFaceNodes(int i, Octree* octree, QVector<int>& face_nodes, bool reverse = false);
 109
 110   void getFaceNodes(int i, Octree* octree, QVector<QVector<int> >& face_nodes, bool reverse = false);
 111
 112 };
 113
 114
 115 // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 116
 117 class Octree : public EgVtkObject
 118 {
 119
 120   friend class OctreeCell;
 121
 122 private: // types
 123
 124   struct node_t
 125   {
 126     vec3_t x;
 127     vtkIdType id;
 128   };
 129
 130 private: // attributes
 131
 132   vec3_t m_Origin;  ///< origin of internal coordinate system
 133   mat3_t m_Base;    ///< base vectors of internal coordinate system
 134   mat3_t m_InvBase; ///< inverted base of internal coordiante system
 135   vec3_t m_Corner1; ///< first corner of extend box of the whole domain (in internal coordinates)
 136   vec3_t m_Corner2; ///< second corner of extend box of the whole domain (in internal coordinates)
 137   double m_Dx;      ///< extend in x direction
 138   double m_Dy;      ///< extend in y direction
 139   double m_Dz;      ///< extend in z direction
 140
 141   bool   m_SmoothTransition;
 142
 143   QVector<OctreeNode>  m_Nodes;
 144   QVector<OctreeCell>  m_Cells;
 145   QVector<bool>        m_ToRefine;
 146   QVector<int>         m_SameNodes;
 147   int                  m_MaxCells;
 148   QVector<QList<int> > m_Node2Cell;
 149
 150 private: // methods
 151
 152   void mergeNodes_identifyDuplicates();
 153   void mergeNodes_compactNodes();
 154   void mergeNodes_updateCells();
 155   void mergeNodes();
 156   void checkNeighbours();
 157   void buildNode2Cell();
 158
 159   int  opposingFace(int i);
 160
 161
 162 public: // methods
 163
 164   Octree();
 165
 166   void setOrigin(vec3_t x0);
 167   void setBase(vec3_t g1, vec3_t g2, vec3_t g3);
 168   void setBounds(vec3_t corner1, vec3_t corner2, int num_i = 1, int num_j = 1, int num_k = 1);
 169
 170   int  getNeighbour(int cell, int neigh) { return m_Cells[cell].m_Neighbour[neigh]; }
 171   void getFinestChildren(int cell, QList<int> &finest_children);
 172
 173   void markToRefine(int cell);
 174   void markAllToRefine();
 175   bool markedForRefine(int cell) { return m_ToRefine[cell]; }
 176   int  refineAll();
 177   void resetRefineMarks();
 178   void setSmoothTransitionOn()  { m_SmoothTransition = true; }
 179   void setSmoothTransitionOff() { m_SmoothTransition = false; }
 180
 181   vec3_t getCellCentre(int cell);
 182   vec3_t getFaceCentre(int i_cells, int i_faces);
 183   vec3_t getNodePosition(int cell, int node) { return m_Nodes[m_Cells[cell].m_Node[node]].m_Position; }
 184   vec3_t getNodePosition(int node) { return m_Nodes[node].m_Position; }
 185   int    getNode(int cell, int node) { return m_Cells[cell].m_Node[node]; }
 186   int    getNumCells() { return m_Cells.size(); }
 187   int    getNumNodes() { return m_Nodes.size(); }
 188   void   getEdges(int cell, QVector<SortedPair<int> >& edges);
 189   int    getLevel(int cell) { return m_Cells[cell].m_Level; }
 190   double getDx(int cell);
 191   double getDy(int cell);
 192   double getDz(int cell);
 193   double getDx(const OctreeCell& cell);
 194   double getDy(const OctreeCell& cell);
 195   double getDz(const OctreeCell& cell);
 196   bool   hasChildren(int i_cells) { return m_Cells[i_cells].m_Child[0] != -1; }
 197   int    getParent(int cell) { return m_Cells[cell].m_Parent; }
 198   int    findCell(vec3_t x);
 199   bool   intersectsFace(int cell, int face, vec3_t x1, vec3_t x2, double scale, double &k, double tol = 1e-4);
 200   void   setMaxCells(int n) { m_MaxCells = n; }
 201   bool   isInsideBounds(vec3_t x);
 202   bool   isInsideCell(int cell, vec3_t x, double overlap = 0);
 203
 204   /**
 205     * Convert the octree into a vtkUnstructuredGrid with hanging nodes.
 206     * @param grid the resulting vtkUnstructuredGrid (object needs to be allocated before, but no space for cells and nodes)
 207     * @param create_fields if this is set to true, the basic enGrid fields will be created
 208     */
 209   void toVtkGridHangingNodes(vtkUnstructuredGrid *grid, bool create_fields = false);
 210
 211   /**
 212     * Convert the octree into a vtkUnstructuredGrid without hanging nodes.
 213     * This method does currently not work for cells on the border of the octree domain.
 214     * @param grid the resulting vtkUnstructuredGrid (object needs to be allocated before, but no space for cells and nodes)
 215     * @param create_fields if this is set to true, the basic enGrid fields will be created
 216     */
 217   void toVtkGridConforming(vtkUnstructuredGrid *grid, bool create_fields = false);
 218
 219   /**
 220     * Convert the octree into a vtkUnstructuredGrid with polyhedral cells.
 221     * This method does currently not work for cells on the border of the octree domain.
 222     * @param grid the resulting vtkUnstructuredGrid (object needs to be allocated before, but no space for cells and nodes)
 223     * @param create_fields if this is set to true, the basic enGrid fields will be created
 224     */
 225   void toVtkGridPolyhedral(vtkUnstructuredGrid *grid, bool create_fields = false);
 226
 227   /**
 228    * @brief Check if a triangle intersects a cell.
 229    * @param cell the index of the octree cell
 230    * @param tri the nodes of the triangle
 231    * @return true if the triangle intersects the cell
 232    */
 233   bool triangleIntersectsCell(int cell, QVector<vec3_t> tri, double scale);
 234
 235   /**
 236    * @brief get all cells which share at least one node with the current cell (and have no children)
 237    * @param cell the index of the octree cell
 238    * @param neighbour_cells a list which the neighbour cells will be added to
 239    */
 240   void getNeighbourRegion(int cell, QList<int> &neighbour_cells);
 241
 242 };
 243
 244
 245 inline double Octree::getDx(int cell)
 246 {
 247   double dx = m_Dx;
 248   for (int i = 0; i < m_Cells[cell].m_Level; ++i) {
 249     dx *= 0.5;
 250   }
 251   return dx;
 252 }
 253
 254 inline double Octree::getDx(const OctreeCell& cell)
 255 {
 256   double dx = m_Dx;
 257   for (int i = 0; i < cell.m_Level; ++i) {
 258     dx *= 0.5;
 259   }
 260   return dx;
 261 }
 262
 263 inline double Octree::getDy(int cell)
 264 {
 265   double dy = m_Dy;
 266   for (int i = 0; i < m_Cells[cell].m_Level; ++i) {
 267     dy *= 0.5;
 268   }
 269   return dy;
 270 }
 271
 272 inline double Octree::getDy(const OctreeCell& cell)
 273 {
 274   double dy = m_Dy;
 275   for (int i = 0; i < cell.m_Level; ++i) {
 276     dy *= 0.5;
 277   }
 278   return dy;
 279 }
 280
 281 inline double Octree::getDz(int cell)
 282 {
 283   double dz = m_Dz;
 284   for (int i = 0; i < m_Cells[cell].m_Level; ++i) {
 285     dz *= 0.5;
 286   }
 287   return dz;
 288 }
 289
 290 inline double Octree::getDz(const OctreeCell& cell)
 291 {
 292   double dz = m_Dz;
 293   for (int i = 0; i < cell.m_Level; ++i) {
 294     dz *= 0.5;
 295   }
 296   return dz;
 297 }
 298
 299 #endif // OCTREE_H