src/SMESHUtils/SMESH_Tree.hxx

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