1 /*---------------------------------------------------------------------------*\
3 \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
5 \\ / A nd | Copyright (C) 1991-2009 OpenCFD Ltd.
7 -------------------------------------------------------------------------------
9 This file is part of OpenFOAM.
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 the
13 Free Software Foundation; either version 2 of the License, or (at your
14 option) any later version.
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
21 You should have received a copy of the GNU General Public License
22 along with OpenFOAM; if not, write to the Free Software Foundation,
23 Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
29 Octree, templated on type of shapes it refers to.
31 Uses the octreeData class, which is a list of 1D, 2D or 3D shapes.
32 Various implementations of octreeData which know about cell&meshes,
33 patches&meshes and points.
35 The octree can be used to
36 - find the "nearest" shape to a point
37 - find the shape which contains a point (only sensible for 3D shapes)
38 - find intersections of line with shapes
41 - treeNode : holds sub-treeNodes or treeLeaves
42 - treeLeaf : is the one that actually holds data
44 The data is stored purely as a list of indices into octreeData.
46 The construction on the depth of the tree is:
47 - one can specify a minimum depth
48 (though the tree will never be refined if all leaves contain <=1
50 - after the minimum depth two statistics are used to decide further
52 - average number of entries per leaf (leafRatio). Since inside a
53 leaf most algorithms are n or n^2 this value has to be small.
54 - average number of leaves a shape is in. Because of bounding boxes,
55 a single shape can be in multiple leaves. If the bbs are large
56 compared to the leaf size this multiplicity can become extremely
57 large and will become larger with more levels.
59 Note: the octree gets constructed with an overall bounding box. If your
60 mesh is regular it is a good idea to make this overall bb a bit wider than
61 the bb of the shapes itself. Otherwise lots of shapes end up exactly on the
62 edge of a bb and hence go into more than one subcube.
64 E.g. octree of face centres of lid driven cavity.
66 -# bb exact -> total 1457 leaves (every point in 7.1 leaves)
67 -# bb.max incremented by 1% -> total 80 leaves
68 (every point in exactly 1 leaf)
70 @par Ideas for parallel implementation:
72 The data inserted into the octree (the
73 'octreeData') has to be local to the processor. The data to be looked
74 for (usually a sample point) can be global to the domain.
76 - search for all my points
77 - collect results which have to do with a processor patch
78 - global sum all these. If 0 exit.
79 - exchange data on all processor patches
82 So data transfers one processor per iteration. One could think of having
83 an extra search mechanism one level above which does an initial search
84 knowing the average shape of a processor distribution (square/cube for
85 most decomposition methods) and can assign sample points to the (almost)
86 correct processor at once.
91 \*---------------------------------------------------------------------------*/
96 #include "treeBoundBoxList.H"
98 #include "pointIndexHit.H"
99 #include "linePointRef.H"
101 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
106 // Forward declaration of classes
107 template<class Type> class treeNode;
109 // Forward declaration of friend functions and operators
112 Ostream& operator<<(Ostream&, const octree<Type>&);
115 /*---------------------------------------------------------------------------*\
116 Class octreeName Declaration
117 \*---------------------------------------------------------------------------*/
119 TemplateName(octree);
123 /*---------------------------------------------------------------------------*\
124 Class octree Declaration
125 \*---------------------------------------------------------------------------*/
127 template <class Type>
134 //- Top treeNode. Modified by lower levels.
135 treeNode<Type>* topNode_;
140 //- Overall bb of octree
141 const treeBoundBox octreeBb_;
143 //- Refinement crit: size of leaves. Average number of entries per
144 // leaf. Should be fine enough for efficient searching at lowest level.
145 const scalar maxLeafRatio_;
147 //- Refinement crit: multiplicity of entries (so in how many leaves
148 // each shape is mentioned)
149 const scalar maxShapeRatio_;
151 //- Refinement crit: min no. of levels
152 const label minNLevels_;
157 //- Total number of (references to) shapes in octree
158 // (shapes can be stored in more than one treeLeaf)
161 //- Total number of treeNodes
164 //- Total number of treeLeaves
168 // Static data members
169 //- Refinement crit: max number of level
170 static const label maxNLevels = 20;
174 // Private Member Functions
190 // Static data members
192 //- for debugging:return printable representation of volumeType
193 static string volType(const label);
195 //- Code the vector with respect to the geometry. geomNormal guaranteed
197 static label getVolType
199 const vector& geomNormal,
205 //- Construct from components
208 const treeBoundBox& octreeBb,
210 const label minNLevels, // minimum number of levels
211 const scalar maxLeafRatio, // max avg. size of leaves
212 const scalar maxShapeRatio // max avg. duplicity.
225 const Type& shapes() const
230 const treeBoundBox& octreeBb() const
235 scalar maxShapeRatio() const
237 return maxShapeRatio_;
240 scalar maxLeafRatio() const
242 return maxLeafRatio_;
245 label minNLevels() const
250 // After construction: octree statistics
252 treeNode<Type>* topNode() const
257 label deepestLevel() const
259 return deepestLevel_;
262 label nEntries() const
272 label nLeaves() const
277 void setEntries(const label n)
282 void setNodes(const label n)
287 void setLeaves(const label n)
294 //- Returns type of sample with respect to nearest shape.
295 // Meaning of type is determined by shapes.getSampleType().
296 // Normally based on outwards pointing normal. For e.g.
297 // octreeDataFace returns one of
298 // inside : on other side of normal on nearest face
299 // outside : on same side as normal on nearest face
300 // unknown : not above nearest face; surface probably not
302 // mixed : should never happen
303 label getSampleType(const point& sample) const;
305 //- Find shape containing point in tree
306 // Returns -1 if not in found. Uses Type::contains.
307 label find(const point& sample) const;
309 //- Calculate tightest fitting bounding box. Uses
310 // Type::findTightest.
314 treeBoundBox& tightest
317 //- Find nearest shape. Returns index of shape or -1 if not found.
318 // tightestDist is both input and output. Uses Type::calcNearest.
322 treeBoundBox& tightest,
326 //- Find nearest to line. Returns -1 or index of shape and
328 // - tightest (is both input and output).
329 // - linePoint : point on line (-GREAT,-GREAT,-GREAT if not found)
330 // - shapePoint : point on shape (GREAT, GREAT, GREAT if not found)
331 // Uses Type::calcNearest.
334 const linePointRef& ln,
335 treeBoundBox& tightest,
340 //- Find (in no particular order) indices of all shapes inside or
341 // overlapping bounding box (i.e. all shapes not outside box)
342 labelList findBox(const boundBox& bb) const;
344 //- Find intersected shape along line. pointIndexHit contains index
345 // of nearest shape intersected and the intersection point. Uses
347 pointIndexHit findLine(const point& start, const point& end) const;
349 //- Like above but just tests whether line hits anything. So
350 // returns first intersection found, not nessecarily nearest.
351 pointIndexHit findLineAny(const point& start, const point& end)
354 //- Find leaf along line. Set leafIntPoint to leave point of
356 const treeLeaf<Type>* findLeafLine
366 //- Dump graphical representation in .obj format
367 void writeOBJ(Ostream& os, label& vertNo) const;
369 //- Print some stats on octree
370 void printStats(Ostream& os) const;
376 friend class iterator;
378 //- An STL iterator for octree
383 //- Reference to the octree this is an iterator for
386 //- List of pointers to treeLeaves
387 List<treeLeaf<Type>*> leaves_;
389 //- Current treeLeaf index
394 //- Construct for a given octree
397 //- Contruct for a given octree, at a certain position
398 iterator(octree& oc, const label index);
403 void operator=(const iterator&);
405 bool operator==(const iterator&) const;
406 bool operator!=(const iterator&) const;
408 treeLeaf<Type>& operator*();
410 iterator& operator++();
411 iterator operator++(int);
414 //- iterator set to the begining of the octree
417 //- iterator set to beyond the end of the octree
418 const iterator& end();
421 // STL const_iterator
423 class const_iterator;
424 friend class const_iterator;
426 //- An STL const_iterator for octree
431 //- Reference to the list this is an iterator for
432 const octree& octree_;
434 //- List of treeLeafs
435 List<const treeLeaf<Type>*> leaves_;
437 //- Current treeLeaf index
442 //- Construct for a given octree
443 const_iterator(const octree&);
445 //- Construct for a given octree and index
446 const_iterator(const octree&, label);
450 void operator=(const const_iterator&);
452 bool operator==(const const_iterator&) const;
453 bool operator!=(const const_iterator&) const;
455 const treeLeaf<Type>& operator*();
457 const_iterator& operator++();
458 const_iterator operator++(int);
462 //- const_iterator set to the begining of the octree
463 inline const_iterator begin() const;
464 inline const_iterator cbegin() const;
466 //- const_iterator set to beyond the end of the octree
467 inline const const_iterator& end() const;
468 inline const const_iterator& cend() const;
471 // IOstream Operators
473 friend Ostream& operator<< <Type>(Ostream&, const octree<Type>&);
478 //- iterator returned by end()
481 //- const_iterator returned by end()
482 const_iterator endConstIter_;
486 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
488 } // End namespace Foam
490 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
496 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
500 // ************************************************************************* //