]> SALOME platform Git repositories - modules/smesh.git/blob - src/SMESHUtils/SMESH_Tree.hxx
Salome HOME
Merge branch 'master' into gni/adaptation
[modules/smesh.git] / 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 //================================================================================
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 height = 0;
272   for (int i = 0; i<NB_CHILDREN; i++)
273   {
274     int h = myChildren[i]->getHeight( false );
275     if ( h > height )
276       height = h;
277   }
278   return height + 1;
279 }
280
281 #endif