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