]> SALOME platform Git repositories - modules/smesh.git/blob - src/SMESHUtils/SMESH_Tree.hxx
Salome HOME
22316: EDF 2719 SMESH: Split hexas into prisms
[modules/smesh.git] / src / SMESHUtils / SMESH_Tree.hxx
1 // Copyright (C) 2007-2014  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   // 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   // Level of the Tree
122   int            myLevel;
123
124   // Build the children recursively
125   void                   buildChildren();
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     if (myChildren[i]->myLimit)
223       delete myChildren[i]->myLimit;
224     myChildren[i]->myLimit = myLimit;
225     myChildren[i]->myLevel = myLevel + 1;
226     myChildren[i]->myBox = newChildBox( i );
227     myChildren[i]->myBox->Enlarge( rootSize * 1e-10 );
228     if ( myLimit->myMinBoxSize > 0. && myChildren[i]->maxSize() <= myLimit->myMinBoxSize )
229       myChildren[i]->myIsLeaf = true;
230   }
231
232   // After building the NB_CHILDREN boxes, we put the data into the children.
233   buildChildrenData();
234
235   //After we pass to the next level of the Tree
236   for (int i = 0; i<NB_CHILDREN; i++)
237     myChildren[i]->buildChildren();
238 }
239
240 //================================================================================
241 /*!
242  * \brief Tell if Tree is a leaf or not
243  *        An inheriting class can influence it via myIsLeaf protected field
244  */
245 //================================================================================
246
247 template< class BND_BOX, int NB_CHILDREN>
248 bool SMESH_Tree<BND_BOX,NB_CHILDREN>::isLeaf() const
249 {
250   return myIsLeaf || ((myLimit->myMaxLevel > 0) ? (level() >= myLimit->myMaxLevel) : false );
251 }
252
253 //================================================================================
254 /*!
255  * \brief Return height of the tree, full or from this level to topest leaf
256  */
257 //================================================================================
258
259 template< class BND_BOX, int NB_CHILDREN>
260 int SMESH_Tree<BND_BOX,NB_CHILDREN>::getHeight(const bool full) const
261 {
262   if ( full && myFather )
263     return myFather->getHeight( true );
264
265   if ( isLeaf() )
266     return 1;
267
268   int heigth = 0;
269   for (int i = 0; i<NB_CHILDREN; i++)
270   {
271     int h = myChildren[i]->getHeight( false );
272     if ( h > heigth )
273       heigth = h;
274   }
275   return heigth + 1;
276 }
277
278 #endif