src/libengrid/octree.h

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