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   // Bounding box of a tree
 119   box_type*      myBox;
 120
 121 private:
 122   // Build the children recursively
 123   void                   buildChildren();
 124
 125   // Level of the Tree
 126   int            myLevel;
 127 };
 128
 129 //===========================================================================
 130 /*!
 131  * Constructor. limit must be provided at tree root construction.
 132  * limit will be deleted by SMESH_Tree.
 133  */
 134 //===========================================================================
 135
 136 template< class BND_BOX, int NB_CHILDREN>
 137 SMESH_Tree<BND_BOX,NB_CHILDREN>::SMESH_Tree (SMESH_TreeLimit* limit):
 138   myChildren(0),
 139   myFather(0),
 140   myIsLeaf( false ),
 141   myLimit( limit ),
 142   myLevel(0),
 143   myBox(0)
 144 {
 145   //if ( !myLimit ) myLimit = new SMESH_TreeLimit();
 146 }
 147
 148 //================================================================================
 149 /*!
 150  * \brief Compute the Tree
 151  */
 152 //================================================================================
 153
 154 template< class BND_BOX, int NB_CHILDREN>
 155 void SMESH_Tree<BND_BOX,NB_CHILDREN>::compute()
 156 {
 157   if ( myLevel==0 )
 158   {
 159     if ( !myLimit ) myLimit = new SMESH_TreeLimit();
 160     myBox = buildRootBox();
 161     if ( myLimit->myMinBoxSize > 0. && maxSize() <= myLimit->myMinBoxSize )
 162       myIsLeaf = true;
 163     else
 164       buildChildren();
 165   }
 166 }
 167
 168 //======================================
 169 /*!
 170  * \brief SMESH_Tree Destructor
 171  */
 172 //======================================
 173
 174 template< class BND_BOX, int NB_CHILDREN>
 175 SMESH_Tree<BND_BOX,NB_CHILDREN>::~SMESH_Tree ()
 176 {
 177   if ( myChildren )
 178   {
 179     if ( !isLeaf() )
 180     {
 181       for(int i = 0; i<NB_CHILDREN; i++)
 182         delete myChildren[i];
 183       delete[] myChildren;
 184       myChildren = 0;
 185     }
 186   }
 187   if ( myBox )
 188     delete myBox;
 189   myBox = 0;
 190   if ( level() == 0 )
 191     delete myLimit;
 192   myLimit = 0;
 193 }
 194
 195 //=================================================================
 196 /*!
 197  * \brief Build the children boxes and call buildChildrenData()
 198  */
 199 //=================================================================
 200
 201 template< class BND_BOX, int NB_CHILDREN>
 202 void SMESH_Tree<BND_BOX,NB_CHILDREN>::buildChildren()
 203 {
 204   if ( isLeaf() ) return;
 205
 206   myChildren = new SMESH_Tree*[NB_CHILDREN];
 207
 208   // get the whole model size
 209   double rootSize = 0;
 210   {
 211     SMESH_Tree* root = this;
 212     while ( root->myLevel > 0 )
 213       root = root->myFather;
 214     rootSize = root->maxSize();
 215   }
 216   for (int i = 0; i < NB_CHILDREN; i++)
 217   {
 218     // The child is of the same type than its father (For instance, a SMESH_OctreeNode)
 219     // We allocate the memory we need for the child
 220     myChildren[i] = newChild();
 221     // and we assign to him its box.
 222     myChildren[i]->myFather = this;
 223     if (myChildren[i]->myLimit)
 224       delete myChildren[i]->myLimit;
 225     myChildren[i]->myLimit = myLimit;
 226     myChildren[i]->myLevel = myLevel + 1;
 227     myChildren[i]->myBox = newChildBox( i );
 228     myChildren[i]->myBox->Enlarge( rootSize * 1e-10 );
 229     if ( myLimit->myMinBoxSize > 0. && myChildren[i]->maxSize() <= myLimit->myMinBoxSize )
 230       myChildren[i]->myIsLeaf = true;
 231   }
 232
 233   // After building the NB_CHILDREN boxes, we put the data into the children.
 234   buildChildrenData();
 235
 236   //After we pass to the next level of the Tree
 237   for (int i = 0; i<NB_CHILDREN; i++)
 238     myChildren[i]->buildChildren();
 239 }
 240
 241 //================================================================================
 242 /*!
 243  * \brief Tell if Tree is a leaf or not
 244  *        An inheriting class can influence it via myIsLeaf protected field
 245  */
 246 //================================================================================
 247
 248 template< class BND_BOX, int NB_CHILDREN>
 249 bool SMESH_Tree<BND_BOX,NB_CHILDREN>::isLeaf() const
 250 {
 251   return myIsLeaf || ((myLimit->myMaxLevel > 0) ? (level() >= myLimit->myMaxLevel) : false );
 252 }
 253
 254 //================================================================================
 255 /*!
 256  * \brief Return height of the tree, full or from this level to topest leaf
 257  */
 258 //================================================================================
 259
 260 template< class BND_BOX, int NB_CHILDREN>
 261 int SMESH_Tree<BND_BOX,NB_CHILDREN>::getHeight(const bool full) const
 262 {
 263   if ( full && myFather )
 264     return myFather->getHeight( true );
 265
 266   if ( isLeaf() )
 267     return 1;
 268
 269   int heigth = 0;
 270   for (int i = 0; i<NB_CHILDREN; i++)
 271   {
 272     int h = myChildren[i]->getHeight( false );
 273     if ( h > heigth )
 274       heigth = h;
 275   }
 276   return heigth + 1;
 277 }
 278
 279 #endif