src/SMESHUtils/SMESH_Tree.hxx

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