OpenFOAM logo
Open Source CFD Toolkit

octree.H

Go to the documentation of this file.
00001 /*---------------------------------------------------------------------------*\
00002   =========                 |
00003   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
00004    \\    /   O peration     |
00005     \\  /    A nd           | Copyright (C) 1991-2005 OpenCFD Ltd.
00006      \\/     M anipulation  |
00007 -------------------------------------------------------------------------------
00008 License
00009     This file is part of OpenFOAM.
00010 
00011     OpenFOAM is free software; you can redistribute it and/or modify it
00012     under the terms of the GNU General Public License as published by the
00013     Free Software Foundation; either version 2 of the License, or (at your
00014     option) any later version.
00015 
00016     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
00017     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00018     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
00019     for more details.
00020 
00021     You should have received a copy of the GNU General Public License
00022     along with OpenFOAM; if not, write to the Free Software Foundation,
00023     Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
00024 
00025 Class
00026     octree
00027 
00028 Description
00029     Octree, templated on type of shapes it refers to. Uses the octreeData class
00030     which is a list of 1D, 2D or 3D shapes. Various implementations of
00031     octreeData which know about cell&meshes, patches&meshes and points.
00032 
00033     The octree can be used to
00034     - find the "nearest" shape to a point
00035     - find the shape which contains a point (only sensible for 3D shapes)
00036     - find intersections of line with shapes
00037 
00038     The tree consists of
00039         - treeNode : holds sub-treeNodes or treeLeaves
00040         - treeLeaf : is the one that actually holds data
00041 
00042     The data is stored purely as a list of indices into octreeData.
00043 
00044     The construction on the depth of the tree is:
00045     - one can specify a minimum depth
00046       (though the tree will never be refined if all leaves contain <=1
00047        shapes)
00048     - after the minimum depth two statistics are used to decide further
00049       refinement:
00050         - average number of entries per leaf (leafRatio). Since inside a 
00051           leaf most algorithms are n or n^2 this value has to be small.
00052         - average number of leaves a shape is in. Because of bounding boxes,
00053           a single shape can be in multiple leaves. If the bbs are large
00054           compared to the leaf size this multiplicity can become extremely
00055           large and will become larger with more levels.
00056 
00057     Note: the octree gets constructed with an overall bounding box. If your
00058     mesh is regular it is a good idea to make this overall bb a bit wider than
00059     the bb of the shapes itself. Otherwise lots of shapes end up exactly on the
00060     edge of a bb and hence go into more than one subcube.
00061 
00062     E.g. octree of face centres of lid driven cavity.
00063 
00064     1. bb exact -> total 1457 leaves (every point in 7.1 leaves)
00065     2. bb.max incremented by 1% -> total 80 leaves (every point in exactly
00066          1 leaf)
00067 
00068     Ideas for parallel implementation: the data inserted into the octree (the 
00069     'octreeData') has to be local to the processor. The data to be looked
00070     for (usually a sample point) can be global to the domain.
00071     The algorithm:
00072         - search for all my points
00073         - collect results which have to do with a processor patch
00074         - global sum all these. If 0 exit.
00075         - exchange data on all processor patches
00076         - start again
00077 
00078     So data transfers one processor per iteration. One could think of having
00079     an extra search mechanism one level above which does an initial search
00080     knowing the average shape of a processor distribution (square/cube for
00081     most decomposition methods) and can assign sample points to the (almost)
00082     correct processor at once.
00083 
00084 SourceFiles
00085     octree.C
00086 
00087 \*---------------------------------------------------------------------------*/
00088 
00089 #ifndef octree_H
00090 #define octree_H
00091 
00092 #include "treeBoundBoxList.H"
00093 #include "treeLeaf.H"
00094 #include "pointIndexHit.H"
00095 #include "linePointRef.H"
00096 
00097 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00098 
00099 namespace Foam
00100 {
00101 
00102 // Class forward declarations
00103 template<class Type> class treeNode;
00104 
00105 // * * * * * * Forward declaration of template friend functions  * * * * * * //
00106 
00107 template<class Type>
00108 Ostream& operator<<(Ostream&, const octree<Type>&);
00109 
00110 
00111 /*---------------------------------------------------------------------------*\
00112                         Class octreeName Declaration
00113 \*---------------------------------------------------------------------------*/
00114 
00115 TemplateName(octree);
00116 
00117 
00118 
00119 /*---------------------------------------------------------------------------*\
00120                            Class octree Declaration
00121 \*---------------------------------------------------------------------------*/
00122 
00123 template <class Type>
00124 class octree
00125 :
00126     public octreeName
00127 {
00128     // Private data
00129 
00130         //- Top treeNode. Modified by lower levels.
00131         treeNode<Type>* topNode_;
00132 
00133         //- all shapes
00134         const Type shapes_;
00135 
00136         //- Overall bb of octree
00137         const treeBoundBox octreeBb_;
00138 
00139         //- Refinement crit: size of leaves. Average number of entries per
00140         //  leaf. Should be fine enough for efficient searching at lowest level.
00141         const scalar maxLeafRatio_;
00142 
00143         //- Refinement crit: multiplicity of entries (so in how many leaves
00144         //  each shape is mentioned)
00145         const scalar maxShapeRatio_;
00146 
00147         //- Refinement crit: min no. of levels
00148         const label minNLevels_;
00149 
00150         //- Actual depth
00151         label deepestLevel_;
00152 
00153         //- Total number of (references to) shapes in octree
00154         //  (shapes can be stored in more than one treeLeaf)
00155         label nEntries_;
00156 
00157         //- Total number of treeNodes
00158         label nNodes_;
00159 
00160         //- Total number of treeLeaves
00161         label nLeaves_;
00162 
00163 
00164     // Static data members
00165         //- Refinement crit: max number of level
00166         static const label maxNLevels = 20;
00167 
00168         
00169 
00170     // Private Member Functions
00171 
00172 public:
00173 
00174     // Data types
00175 
00176         //- volume types
00177         enum volumeType
00178         {
00179             UNKNOWN,
00180             MIXED,
00181             INSIDE,
00182             OUTSIDE
00183         };
00184 
00185 
00186     // Static data members
00187 
00188         //- for debugging:return printable representation of volumeType
00189         static string volType(const label);
00190 
00191         //- Code the vector with respect to the geometry. geomNormal guaranteed
00192         //  to point outside.
00193         static label getVolType
00194         (
00195             const vector& geomNormal,
00196             const vector& vec
00197         );
00198 
00199     // Constructors
00200 
00201         //- Construct from components
00202         octree
00203         (
00204             const treeBoundBox& octreeBb,
00205             const Type& shapes,
00206             const label minNLevels,     // minimum number of levels
00207             const scalar maxLeafRatio,  // max avg. size of leaves
00208             const scalar maxShapeRatio  // max avg. duplicity.
00209         );
00210 
00211 
00212     // Destructor
00213 
00214         ~octree();
00215 
00216 
00217     // Member Functions
00218 
00219         // Access
00220 
00221             const Type& shapes() const
00222             {
00223                 return shapes_;
00224             }
00225 
00226             const treeBoundBox& octreeBb() const
00227             {
00228                 return octreeBb_;
00229             }
00230 
00231             scalar maxShapeRatio() const
00232             {
00233                 return maxShapeRatio_;
00234             }
00235 
00236             scalar maxLeafRatio() const
00237             {
00238                 return maxLeafRatio_;
00239             }
00240 
00241             label minNLevels() const
00242             {
00243                 return minNLevels_;
00244             }
00245 
00246         // After construction: octree statistics
00247 
00248             treeNode<Type>* topNode() const
00249             {
00250                 return topNode_;
00251             }
00252 
00253             label deepestLevel() const
00254             {
00255                 return deepestLevel_;
00256             }
00257 
00258             label nEntries() const
00259             {
00260                 return nEntries_;
00261             }
00262 
00263             label nNodes() const
00264             {
00265                 return nNodes_;
00266             }
00267 
00268             label nLeaves() const
00269             {
00270                 return nLeaves_;
00271             }
00272 
00273             void setEntries(const label n)
00274             {
00275                 nEntries_ = n;
00276             }
00277 
00278             void setNodes(const label n)
00279             {
00280                 nNodes_ = n;
00281             }
00282 
00283             void setLeaves(const label n)
00284             {
00285                 nLeaves_ = n;
00286             }
00287 
00288         // Queries
00289 
00290             //- Returns type of sample with respect to nearest shape.        
00291             //  Meaning of type is determined by shapes.getSampleType().
00292             //  Normally based on outwards pointing normal. For e.g.
00293             //  octreeDataFace returns one of
00294             //      inside  : on other side of normal on nearest face
00295             //      outside : on same side as normal on nearest face
00296             //      unknown : not above nearest face; surface probably not
00297             //                closed.
00298             //      mixed   : should never happen
00299             label getSampleType(const point& sample) const;
00300 
00301             //- Find shape containing point in tree
00302             //  Returns -1 if not in found. Uses Type::contains.
00303             label find(const point& sample) const;
00304 
00305             //- Calculate tightest fitting bounding box. Uses
00306             //  Type::findTightest.
00307             bool findTightest
00308             (
00309                 const point& sample,
00310                 treeBoundBox& tightest
00311             ) const;
00312 
00313             //- Find nearest shape. Returns index of shape or -1 if not found.
00314             //  tightestDist is both input and output. Uses Type::calcNearest.
00315             label findNearest
00316             (
00317                 const point& sample,
00318                 treeBoundBox& tightest,
00319                 scalar& tightestDist
00320             ) const;
00321 
00322             //- Find nearest to line. Returns -1 or index of shape and
00323             //  sets:
00324             //  - tightest (is both input and output).
00325             //  - linePoint : point on line (-GREAT,-GREAT,-GREAT if not found)
00326             //  - shapePoint : point on shape (GREAT, GREAT, GREAT if not found)
00327             //  Uses Type::calcNearest.
00328             label findNearest
00329             (
00330                 const linePointRef& ln,
00331                 treeBoundBox& tightest,
00332                 point& linePoint,
00333                 point& shapePoint
00334             ) const;
00335 
00336             //- Find (in no particular order) indices of all shapes inside or
00337             //  overlapping bounding box (i.e. all shapes not outside box)
00338             labelList findBox(const boundBox& bb) const;
00339 
00340             //- Find intersected shape along line. pointIndexHit contains index
00341             //  of nearest shape intersected and the intersection point. Uses
00342             //  findLeafLine.
00343             pointIndexHit findLine(const point& start, const point& end) const;
00344 
00345             //- Like above but just tests whether line hits anything. So
00346             //   returns first intersection found, not nessecarily nearest.
00347             pointIndexHit findLineAny(const point& start, const point& end)
00348              const;
00349 
00350             //- Find leaf along line. Set leafIntPoint to leave point of
00351             //  treeLeaf.
00352             const treeLeaf<Type>* findLeafLine
00353             (
00354                 const point& start,
00355                 const point& end,
00356                 point& leafIntPoint
00357             ) const;
00358 
00359 
00360         // Write
00361 
00362             //- Dump graphical representation in .obj format
00363             void writeOBJ(Ostream& os, label& vertNo) const;
00364 
00365             //- Print some stats on octree
00366             void printStats(Ostream& os) const;
00367 
00368 
00369     // STL iterator
00370 
00371         class iterator;
00372         friend class iterator;
00373 
00374         class iterator
00375         {
00376             // Private data
00377 
00378                 //- Reference to the octree this is an iterator for
00379                 octree& octree_;
00380 
00381                 //- List of pointers to treeLeaves
00382                 List<treeLeaf<Type>*> leaves_;
00383 
00384                 //- Current treeLeaf index
00385                 label curLeaf_;
00386 
00387         public:
00388 
00389             //- Construct for a given octree
00390             iterator(octree&);
00391 
00392             //- Contruct for a given octree, at a certain position
00393             iterator(octree& oc, const label index);
00394 
00395 
00396             // Member operators
00397 
00398                 void operator=(const iterator&);
00399 
00400                 bool operator==(const iterator&) const;
00401                 bool operator!=(const iterator&) const;
00402 
00403                 treeLeaf<Type>& operator*();
00404 
00405                 iterator& operator++();
00406                 iterator operator++(int);
00407         };
00408 
00409         //- iterator set to the begining of the octree
00410         iterator begin();
00411 
00412         //- iterator set to beyond the end of the octree
00413         const iterator& end();
00414 
00415 
00416     // STL const_iterator
00417 
00418         class const_iterator;
00419         friend class const_iterator;
00420 
00421         class const_iterator
00422         {
00423             // Private data
00424 
00425                 //- Reference to the list this is an iterator for
00426                 const octree& octree_;
00427 
00428                 //- List of treeLeafs
00429                 List<const treeLeaf<Type>*> leaves_;
00430 
00431                 //- Current treeLeaf index
00432                 label curLeaf_;
00433 
00434         public:
00435 
00436             //- Construct for a given octree
00437             const_iterator(const octree&);
00438 
00439             //- Construct for a given octree and index
00440             const_iterator(const octree&, label);
00441 
00442             // Member functions
00443 
00444                 const_iterator begin() const;
00445 
00446             // Member operators
00447 
00448                 void operator=(const const_iterator&);
00449 
00450                 bool operator==(const const_iterator&) const;
00451                 bool operator!=(const const_iterator&) const;
00452 
00453                 const treeLeaf<Type>& operator*();
00454 
00455                 const_iterator& operator++();
00456                 const_iterator operator++(int);
00457         };
00458 
00459 
00460         //- const_iterator set to the begining of the octree
00461         inline const_iterator begin() const;
00462 
00463         //- const_iterator set to beyond the end of the octree
00464         inline const const_iterator& end() const;
00465 
00466 
00467     // IOstream Operators
00468 
00469         friend Ostream& operator<< <Type>(Ostream&, const octree<Type>&);
00470 
00471 
00472 private:
00473 
00474         //- iterator returned by end()
00475         iterator endIter_;
00476 
00477         //- const_iterator returned by end()
00478         const_iterator endConstIter_;
00479 };
00480 
00481 
00482 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00483 
00484 } // End namespace Foam
00485 
00486 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00487 
00488 #ifdef NoRepository
00489 #   include "octree.C"
00490 #endif
00491 
00492 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00493 
00494 #endif
00495 
00496 // ************************************************************************* //
For further information go to www.openfoam.org