![]() |
|
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 // ************************************************************************* //