FreeFOAM The Cross-Platform CFD Toolkit
octree.H
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration |
5  \\ / A nd | Copyright (C) 1991-2010 OpenCFD Ltd.
6  \\/ M anipulation |
7 -------------------------------------------------------------------------------
8 License
9  This file is part of OpenFOAM.
10 
11  OpenFOAM is free software: you can redistribute it and/or modify it
12  under the terms of the GNU General Public License as published by
13  the Free Software Foundation, either version 3 of the License, or
14  (at your option) any later version.
15 
16  OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
17  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18  FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19  for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
23 
24 Class
25  Foam::octree
26 
27 Description
28  Octree, templated on type of shapes it refers to.
29 
30  Uses the octreeData class, which is a list of 1D, 2D or 3D shapes.
31  Various implementations of octreeData which know about cell&meshes,
32  patches&meshes and points.
33 
34  The octree can be used to
35  - find the "nearest" shape to a point
36  - find the shape which contains a point (only sensible for 3D shapes)
37  - find intersections of line with shapes
38 
39  The tree consists of
40  - treeNode : holds sub-treeNodes or treeLeaves
41  - treeLeaf : is the one that actually holds data
42 
43  The data is stored purely as a list of indices into octreeData.
44 
45  The construction on the depth of the tree is:
46  - one can specify a minimum depth
47  (though the tree will never be refined if all leaves contain <=1
48  shapes)
49  - after the minimum depth two statistics are used to decide further
50  refinement:
51  - average number of entries per leaf (leafRatio). Since inside a
52  leaf most algorithms are n or n^2 this value has to be small.
53  - average number of leaves a shape is in. Because of bounding boxes,
54  a single shape can be in multiple leaves. If the bbs are large
55  compared to the leaf size this multiplicity can become extremely
56  large and will become larger with more levels.
57 
58  Note: the octree gets constructed with an overall bounding box. If your
59  mesh is regular it is a good idea to make this overall bb a bit wider than
60  the bb of the shapes itself. Otherwise lots of shapes end up exactly on the
61  edge of a bb and hence go into more than one subcube.
62 
63  E.g. octree of face centres of lid driven cavity.
64 
65  -# bb exact -> total 1457 leaves (every point in 7.1 leaves)
66  -# bb.max incremented by 1% -> total 80 leaves
67  (every point in exactly 1 leaf)
68 
69  @par Ideas for parallel implementation:
70 
71  The data inserted into the octree (the
72  'octreeData') has to be local to the processor. The data to be looked
73  for (usually a sample point) can be global to the domain.
74  The algorithm:
75  - search for all my points
76  - collect results which have to do with a processor patch
77  - global sum all these. If 0 exit.
78  - exchange data on all processor patches
79  - start again
80 
81  So data transfers one processor per iteration. One could think of having
82  an extra search mechanism one level above which does an initial search
83  knowing the average shape of a processor distribution (square/cube for
84  most decomposition methods) and can assign sample points to the (almost)
85  correct processor at once.
86 
87 SourceFiles
88  octree.C
89 
90 \*---------------------------------------------------------------------------*/
91 
92 #ifndef octree_H
93 #define octree_H
94 
95 #include "treeBoundBoxList.H"
96 #include "treeLeaf.H"
97 #include "pointIndexHit.H"
98 #include <OpenFOAM/linePointRef.H>
99 
100 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
101 
102 namespace Foam
103 {
104 
105 // Forward declaration of classes
106 template<class Type> class treeNode;
107 
108 // Forward declaration of friend functions and operators
109 
110 template<class Type>
111 Ostream& operator<<(Ostream&, const octree<Type>&);
112 
113 
114 /*---------------------------------------------------------------------------*\
115  Class octreeName Declaration
116 \*---------------------------------------------------------------------------*/
117 
118 TemplateName(octree);
119 
120 
121 
122 /*---------------------------------------------------------------------------*\
123  Class octree Declaration
124 \*---------------------------------------------------------------------------*/
125 
126 template <class Type>
127 class octree
128 :
129  public octreeName
130 {
131  // Private data
132 
133  //- Top treeNode. Modified by lower levels.
134  treeNode<Type>* topNode_;
135 
136  //- all shapes
137  const Type shapes_;
138 
139  //- Overall bb of octree
140  const treeBoundBox octreeBb_;
141 
142  //- Refinement crit: size of leaves. Average number of entries per
143  // leaf. Should be fine enough for efficient searching at lowest level.
144  const scalar maxLeafRatio_;
145 
146  //- Refinement crit: multiplicity of entries (so in how many leaves
147  // each shape is mentioned)
148  const scalar maxShapeRatio_;
149 
150  //- Refinement crit: min no. of levels
151  const label minNLevels_;
152 
153  //- Actual depth
154  label deepestLevel_;
155 
156  //- Total number of (references to) shapes in octree
157  // (shapes can be stored in more than one treeLeaf)
158  label nEntries_;
159 
160  //- Total number of treeNodes
161  label nNodes_;
162 
163  //- Total number of treeLeaves
164  label nLeaves_;
165 
166 
167  // Static data members
168  //- Refinement crit: max number of level
169  static const label maxNLevels = 20;
170 
171 
172 
173  // Private Member Functions
174 
175 public:
176 
177  // Data types
178 
179  //- volume types
181  {
186  };
187 
188 
189  // Static data members
190 
191  //- for debugging:return printable representation of volumeType
192  static string volType(const label);
193 
194  //- Code the vector with respect to the geometry. geomNormal guaranteed
195  // to point outside.
196  static label getVolType
197  (
198  const vector& geomNormal,
199  const vector& vec
200  );
201 
202  // Constructors
203 
204  //- Construct from components
205  octree
206  (
207  const treeBoundBox& octreeBb,
208  const Type& shapes,
209  const label minNLevels, // minimum number of levels
210  const scalar maxLeafRatio, // max avg. size of leaves
211  const scalar maxShapeRatio // max avg. duplicity.
212  );
213 
214 
215  // Destructor
216 
217  ~octree();
218 
219 
220  // Member Functions
221 
222  // Access
223 
224  const Type& shapes() const
225  {
226  return shapes_;
227  }
228 
229  const treeBoundBox& octreeBb() const
230  {
231  return octreeBb_;
232  }
233 
234  scalar maxShapeRatio() const
235  {
236  return maxShapeRatio_;
237  }
238 
239  scalar maxLeafRatio() const
240  {
241  return maxLeafRatio_;
242  }
243 
244  label minNLevels() const
245  {
246  return minNLevels_;
247  }
248 
249  // After construction: octree statistics
250 
252  {
253  return topNode_;
254  }
255 
256  label deepestLevel() const
257  {
258  return deepestLevel_;
259  }
260 
261  label nEntries() const
262  {
263  return nEntries_;
264  }
265 
266  label nNodes() const
267  {
268  return nNodes_;
269  }
270 
271  label nLeaves() const
272  {
273  return nLeaves_;
274  }
275 
276  void setEntries(const label n)
277  {
278  nEntries_ = n;
279  }
280 
281  void setNodes(const label n)
282  {
283  nNodes_ = n;
284  }
285 
286  void setLeaves(const label n)
287  {
288  nLeaves_ = n;
289  }
290 
291  // Queries
292 
293  //- Returns type of sample with respect to nearest shape.
294  // Meaning of type is determined by shapes.getSampleType().
295  // Normally based on outwards pointing normal. For e.g.
296  // octreeDataFace returns one of
297  // inside : on other side of normal on nearest face
298  // outside : on same side as normal on nearest face
299  // unknown : not above nearest face; surface probably not
300  // closed.
301  // mixed : should never happen
302  label getSampleType(const point& sample) const;
303 
304  //- Find shape containing point in tree
305  // Returns -1 if not in found. Uses Type::contains.
306  label find(const point& sample) const;
307 
308  //- Calculate tightest fitting bounding box. Uses
309  // Type::findTightest.
310  bool findTightest
311  (
312  const point& sample,
313  treeBoundBox& tightest
314  ) const;
315 
316  //- Find nearest shape. Returns index of shape or -1 if not found.
317  // tightestDist is both input and output. Uses Type::calcNearest.
318  label findNearest
319  (
320  const point& sample,
321  treeBoundBox& tightest,
322  scalar& tightestDist
323  ) const;
324 
325  //- Find nearest to line. Returns -1 or index of shape and
326  // sets:
327  // - tightest (is both input and output).
328  // - linePoint : point on line (-GREAT,-GREAT,-GREAT if not found)
329  // - shapePoint : point on shape (GREAT, GREAT, GREAT if not found)
330  // Uses Type::calcNearest.
331  label findNearest
332  (
333  const linePointRef& ln,
334  treeBoundBox& tightest,
335  point& linePoint,
336  point& shapePoint
337  ) const;
338 
339  //- Find (in no particular order) indices of all shapes inside or
340  // overlapping bounding box (i.e. all shapes not outside box)
341  labelList findBox(const boundBox& bb) const;
342 
343  //- Find intersected shape along line. pointIndexHit contains index
344  // of nearest shape intersected and the intersection point. Uses
345  // findLeafLine.
346  pointIndexHit findLine(const point& start, const point& end) const;
347 
348  //- Like above but just tests whether line hits anything. So
349  // returns first intersection found, not nessecarily nearest.
350  pointIndexHit findLineAny(const point& start, const point& end)
351  const;
352 
353  //- Find leaf along line. Set leafIntPoint to leave point of
354  // treeLeaf.
356  (
357  const point& start,
358  const point& end,
359  point& leafIntPoint
360  ) const;
361 
362 
363  // Write
364 
365  //- Dump graphical representation in .obj format
366  void writeOBJ(Ostream& os, label& vertNo) const;
367 
368  //- Print some stats on octree
369  void printStats(Ostream& os) const;
370 
371 
372  // STL iterator
373 
374  class iterator;
375  friend class iterator;
376 
377  //- An STL iterator for octree
378  class iterator
379  {
380  // Private data
381 
382  //- Reference to the octree this is an iterator for
383  octree& octree_;
384 
385  //- List of pointers to treeLeaves
386  List<treeLeaf<Type>*> leaves_;
387 
388  //- Current treeLeaf index
389  label curLeaf_;
390 
391  public:
392 
393  //- Construct for a given octree
394  iterator(octree&);
395 
396  //- Contruct for a given octree, at a certain position
397  iterator(octree& oc, const label index);
398 
399 
400  // Member operators
401 
402  void operator=(const iterator&);
403 
404  bool operator==(const iterator&) const;
405  bool operator!=(const iterator&) const;
406 
408 
409  iterator& operator++();
410  iterator operator++(int);
411  };
412 
413  //- iterator set to the begining of the octree
414  iterator begin();
415 
416  //- iterator set to beyond the end of the octree
417  const iterator& end();
418 
419 
420  // STL const_iterator
421 
423  friend class const_iterator;
424 
425  //- An STL const_iterator for octree
427  {
428  // Private data
429 
430  //- Reference to the list this is an iterator for
431  const octree& octree_;
432 
433  //- List of treeLeafs
434  List<const treeLeaf<Type>*> leaves_;
435 
436  //- Current treeLeaf index
437  label curLeaf_;
438 
439  public:
440 
441  //- Construct for a given octree
442  const_iterator(const octree&);
443 
444  //- Construct for a given octree and index
445  const_iterator(const octree&, label);
446 
447  // Member operators
448 
449  void operator=(const const_iterator&);
450 
451  bool operator==(const const_iterator&) const;
452  bool operator!=(const const_iterator&) const;
453 
454  const treeLeaf<Type>& operator*();
455 
458  };
459 
460 
461  //- const_iterator set to the begining of the octree
462  inline const_iterator begin() const;
463  inline const_iterator cbegin() const;
464 
465  //- const_iterator set to beyond the end of the octree
466  inline const const_iterator& end() const;
467  inline const const_iterator& cend() const;
468 
469 
470  // IOstream Operators
471 
472  friend Ostream& operator<< <Type>(Ostream&, const octree<Type>&);
473 
474 
475 private:
476 
477  //- iterator returned by end()
478  iterator endIter_;
479 
480  //- const_iterator returned by end()
481  const_iterator endConstIter_;
482 };
483 
484 
485 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
486 
487 } // End namespace Foam
488 
489 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
490 
491 #ifdef NoRepository
492 # include "octree.C"
493 #endif
494 
495 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
496 
497 #endif
498 
499 // ************************ vim: set sw=4 sts=4 et: ************************ //