src/SMESHUtils/SMESH_Tree.hxx

   1 // Copyright (C) 2007-2013  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   6 // This library is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU Lesser General Public
   8 // License as published by the Free Software Foundation; either
   9 // version 2.1 of the License.
  10 //
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // Lesser General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Lesser General Public
  17 // License along with this library; if not, write to the Free Software
  18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22 \r
  23 //  SMESH SMESH_Tree : tree implementation\r
  24 //  File      : SMESH_Tree.hxx\r
  25 //  Created   : Tue Jan 16 16:00:00 2007\r
  26 //  Author    : Nicolas Geimer & Aurélien Motteux (OCC)\r
  27 //  Module    : SMESH\r
  28 //\r
  29 #ifndef _SMESH_Tree_HXX_\r
  30 #define _SMESH_Tree_HXX_\r
  31 \r
  32 #include "SMESH_Utils.hxx"\r
  33 \r
  34 //================================================================================\r
  35 // Data limiting the tree height\r
  36 struct SMESH_TreeLimit {\r
  37   // MaxLevel of the Tree\r
  38   int    myMaxLevel;\r
  39   // Minimal size of the Box\r
  40   double myMinBoxSize;\r
  41 \r
  42   // Default:\r
  43   // maxLevel-> 8^8 = 16777216 terminal trees at most\r
  44   // minSize -> box size not checked\r
  45   SMESH_TreeLimit(int maxLevel=8, double minSize=0.):myMaxLevel(maxLevel),myMinBoxSize(minSize) {}\r
  46   virtual ~SMESH_TreeLimit() {} // it can be inherited\r
  47 };\r
  48 \r
  49 //================================================================================\r
  50 /*!\r
  51  * \brief Base class for 2D and 3D trees\r
  52  */\r
  53 //================================================================================\r
  54 \r
  55 template< class BND_BOX,\r
  56           int   NB_CHILDREN>\r
  57 class SMESH_Tree\r
  58 {\r
  59  public:\r
  60 \r
  61   typedef BND_BOX box_type;\r
  62 \r
  63   // Constructor. limit must be provided at tree root construction.\r
  64   // limit will be deleted by SMESH_Tree\r
  65   SMESH_Tree (SMESH_TreeLimit* limit=0);\r
  66 \r
  67   // Destructor\r
  68   virtual ~SMESH_Tree ();\r
  69 \r
  70   // Compute the Tree. Must be called by constructor of inheriting class\r
  71   void                   compute();\r
  72 \r
  73   // Tell if Tree is a leaf or not.\r
  74   // An inheriting class can influence it via myIsLeaf protected field\r
  75   bool                   isLeaf() const;\r
  76 \r
  77   // Return its level\r
  78   int                    level() const { return myLevel; }\r
  79 \r
  80   // Return Bounding Box of the Tree\r
  81   const box_type*        getBox() const { return myBox; }\r
  82 \r
  83   // Return height of the tree, full or from this level to topest leaf\r
  84   int                    getHeight(const bool full=true) const;\r
  85 \r
  86   static int             nbChildren() { return NB_CHILDREN; }\r
  87 \r
  88   // Compute the bigger dimension of my box\r
  89   virtual double         maxSize() const = 0;\r
  90 \r
  91 protected:\r
  92   // Return box of the whole tree\r
  93   virtual box_type*      buildRootBox() = 0;\r
  94 \r
  95   // Allocate a child\r
  96   virtual SMESH_Tree*    newChild() const = 0;\r
  97 \r
  98   // Allocate a bndbox according to childIndex. childIndex is zero based\r
  99   virtual box_type*      newChildBox(int childIndex) const = 0;\r
 100 \r
 101   // Fill in data of the children\r
 102   virtual void           buildChildrenData() = 0;\r
 103 \r
 104   // members\r
 105 \r
 106   // Array of children\r
 107   SMESH_Tree**   myChildren;\r
 108 \r
 109   // Point the father, NULL for the level 0\r
 110   SMESH_Tree*    myFather;\r
 111 \r
 112   // Tell us if the Tree is a leaf or not\r
 113   bool           myIsLeaf;\r
 114 \r
 115   // Tree limit\r
 116   const SMESH_TreeLimit* myLimit;\r
 117 \r
 118 private:\r
 119   // Build the children recursively\r
 120   void                   buildChildren();\r
 121 \r
 122   // Level of the Tree\r
 123   int            myLevel;\r
 124 \r
 125   box_type*      myBox;\r
 126 };\r
 127 \r
 128 //===========================================================================\r
 129 /*!\r
 130  * Constructor. limit must be provided at tree root construction.\r
 131  * limit will be deleted by SMESH_Tree.\r
 132  */\r
 133 //===========================================================================\r
 134 \r
 135 template< class BND_BOX, int NB_CHILDREN>\r
 136 SMESH_Tree<BND_BOX,NB_CHILDREN>::SMESH_Tree (SMESH_TreeLimit* limit):\r
 137   myChildren(0),\r
 138   myFather(0),\r
 139   myIsLeaf( false ),\r
 140   myLimit( limit ),\r
 141   myLevel(0),\r
 142   myBox(0)\r
 143 {\r
 144   if ( !myLimit ) myLimit = new SMESH_TreeLimit();\r
 145 }\r
 146 \r
 147 //================================================================================\r
 148 /*!\r
 149  * \brief Compute the Tree\r
 150  */\r
 151 //================================================================================\r
 152 \r
 153 template< class BND_BOX, int NB_CHILDREN>\r
 154 void SMESH_Tree<BND_BOX,NB_CHILDREN>::compute()\r
 155 {\r
 156   if ( myLevel==0 )\r
 157   {\r
 158     myBox = buildRootBox();\r
 159     if ( myLimit->myMinBoxSize > 0. && maxSize() <= myLimit->myMinBoxSize )\r
 160       myIsLeaf = true;\r
 161     else\r
 162       buildChildren();\r
 163   }\r
 164 }\r
 165 \r
 166 //======================================\r
 167 /*!\r
 168  * \brief SMESH_Tree Destructor\r
 169  */\r
 170 //======================================\r
 171 \r
 172 template< class BND_BOX, int NB_CHILDREN>\r
 173 SMESH_Tree<BND_BOX,NB_CHILDREN>::~SMESH_Tree ()\r
 174 {\r
 175   if ( myChildren )\r
 176   {\r
 177     if ( !isLeaf() )\r
 178     {\r
 179       for(int i = 0; i<NB_CHILDREN; i++)\r
 180         delete myChildren[i];\r
 181       delete[] myChildren;\r
 182       myChildren = 0;\r
 183     }\r
 184   }\r
 185   if ( myBox )\r
 186     delete myBox;\r
 187   myBox = 0;\r
 188   if ( level() == 0 )\r
 189     delete myLimit;\r
 190   myLimit = 0;\r
 191 }\r
 192 \r
 193 //=================================================================\r
 194 /*!\r
 195  * \brief Build the children boxes and call buildChildrenData()\r
 196  */\r
 197 //=================================================================\r
 198 \r
 199 template< class BND_BOX, int NB_CHILDREN>\r
 200 void SMESH_Tree<BND_BOX,NB_CHILDREN>::buildChildren()\r
 201 {\r
 202   if ( isLeaf() ) return;\r
 203 \r
 204   myChildren = new SMESH_Tree*[NB_CHILDREN];\r
 205 \r
 206   // get the whole model size\r
 207   double rootSize = 0;\r
 208   {\r
 209     SMESH_Tree* root = this;\r
 210     while ( root->myLevel > 0 )\r
 211       root = root->myFather;\r
 212     rootSize = root->maxSize();\r
 213   }\r
 214   for (int i = 0; i < NB_CHILDREN; i++)\r
 215   {\r
 216     // The child is of the same type than its father (For instance, a SMESH_OctreeNode)\r
 217     // We allocate the memory we need for the child\r
 218     myChildren[i] = newChild();\r
 219     // and we assign to him its box.\r
 220     myChildren[i]->myFather = this;\r
 221     myChildren[i]->myLimit = myLimit;\r
 222     myChildren[i]->myLevel = myLevel + 1;\r
 223     myChildren[i]->myBox = newChildBox( i );\r
 224     myChildren[i]->myBox->Enlarge( rootSize * 1e-10 );\r
 225     if ( myLimit->myMinBoxSize > 0. && myChildren[i]->maxSize() <= myLimit->myMinBoxSize )\r
 226       myChildren[i]->myIsLeaf = true;\r
 227   }\r
 228 \r
 229   // After building the NB_CHILDREN boxes, we put the data into the children.\r
 230   buildChildrenData();\r
 231 \r
 232   //After we pass to the next level of the Tree\r
 233   for (int i = 0; i<NB_CHILDREN; i++)\r
 234     myChildren[i]->buildChildren();\r
 235 }\r
 236 \r
 237 //================================================================================\r
 238 /*!\r
 239  * \brief Tell if Tree is a leaf or not\r
 240  *        An inheriting class can influence it via myIsLeaf protected field\r
 241  */\r
 242 //================================================================================\r
 243 \r
 244 template< class BND_BOX, int NB_CHILDREN>\r
 245 bool SMESH_Tree<BND_BOX,NB_CHILDREN>::isLeaf() const\r
 246 {\r
 247   return myIsLeaf || ((myLimit->myMaxLevel > 0) ? (level() >= myLimit->myMaxLevel) : false );\r
 248 }\r
 249 \r
 250 //================================================================================\r
 251 /*!\r
 252  * \brief Return height of the tree, full or from this level to topest leaf\r
 253  */\r
 254 //================================================================================\r
 255 \r
 256 template< class BND_BOX, int NB_CHILDREN>\r
 257 int SMESH_Tree<BND_BOX,NB_CHILDREN>::getHeight(const bool full) const\r
 258 {\r
 259   if ( full && myFather )\r
 260     return myFather->getHeight( true );\r
 261 \r
 262   if ( isLeaf() )\r
 263     return 1;\r
 264 \r
 265   int heigth = 0;\r
 266   for (int i = 0; i<NB_CHILDREN; i++)\r
 267   {\r
 268     int h = myChildren[i]->getHeight( false );\r
 269     if ( h > heigth )\r
 270       heigth = h;\r
 271   }\r
 272   return heigth + 1;\r
 273 }\r
 274 \r
 275 #endif\r