Version: 9.12.0
SMESH_Tree.hxx
Go to the documentation of this file.
1 // Copyright (C) 2007-2023 CEA, EDF, 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
39  // MaxLevel of the Tree
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 //================================================================================
55 //================================================================================
56 
57 template< class BND_BOX,
58  int NB_CHILDREN>
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
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
113 
114  // Point the father, NULL for the level 0
116 
117  // Tell us if the Tree is a leaf or not
118  bool myIsLeaf;
119 
120  // Tree limit
122 
123  // Bounding box of a tree
125 
126  // Level of the Tree
127  int myLevel;
128 
129  // Build the children recursively
131 };
132 
133 //===========================================================================
138 //===========================================================================
139 
140 template< class BND_BOX, int NB_CHILDREN>
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 //================================================================================
156 //================================================================================
157 
158 template< class BND_BOX, int NB_CHILDREN>
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 //======================================
177 //======================================
178 
179 template< class BND_BOX, int NB_CHILDREN>
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 //=================================================================
204 //=================================================================
205 
206 template< class BND_BOX, int NB_CHILDREN>
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 //================================================================================
251 //================================================================================
252 
253 template< class BND_BOX, int NB_CHILDREN>
255 {
256  return myIsLeaf || ((myLimit->myMaxLevel > 0) ? (level() >= myLimit->myMaxLevel) : false );
257 }
258 
259 //================================================================================
263 //================================================================================
264 
265 template< class BND_BOX, int NB_CHILDREN>
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
const double theEnlargeFactor
Definition: SMESH_Tree.hxx:34
Base class for 2D and 3D trees.
Definition: SMESH_Tree.hxx:60
virtual SMESH_Tree * newChild() const =0
static int nbChildren()
Definition: SMESH_Tree.hxx:88
virtual ~SMESH_Tree()
SMESH_Tree Destructor.
Definition: SMESH_Tree.hxx:180
SMESH_Tree * myFather
Definition: SMESH_Tree.hxx:115
SMESH_Tree ** myChildren
Definition: SMESH_Tree.hxx:112
virtual box_type * buildRootBox()=0
virtual void buildChildrenData()=0
const box_type * getBox() const
Definition: SMESH_Tree.hxx:83
void compute()
Compute the Tree.
Definition: SMESH_Tree.hxx:159
SMESH_Tree(SMESH_TreeLimit *limit=0)
Constructor.
Definition: SMESH_Tree.hxx:141
BND_BOX box_type
Definition: SMESH_Tree.hxx:63
const SMESH_TreeLimit * myLimit
Definition: SMESH_Tree.hxx:121
virtual double maxSize() const =0
int level() const
Definition: SMESH_Tree.hxx:80
bool isLeaf() const
Tell if Tree is a leaf or not An inheriting class can influence it via myIsLeaf protected field.
Definition: SMESH_Tree.hxx:254
bool myIsLeaf
Definition: SMESH_Tree.hxx:118
virtual void enlargeByFactor(box_type *box, double factor) const =0
void buildChildren()
Build the children boxes and call buildChildrenData()
Definition: SMESH_Tree.hxx:207
int myLevel
Definition: SMESH_Tree.hxx:127
virtual box_type * newChildBox(int childIndex) const =0
box_type * myBox
Definition: SMESH_Tree.hxx:124
int getHeight(const bool full=true) const
Return height of the tree, full or from this level to topest leaf.
Definition: SMESH_Tree.hxx:266
Definition: SMESH_Tree.hxx:38
SMESH_TreeLimit(int maxLevel=8, double minSize=0.)
Definition: SMESH_Tree.hxx:47
double myMinBoxSize
Definition: SMESH_Tree.hxx:42
int myMaxLevel
Definition: SMESH_Tree.hxx:40
virtual ~SMESH_TreeLimit()
Definition: SMESH_Tree.hxx:48