![]() |
|
This file is part of OpenFOAM. OpenFOAM is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. OpenFOAM is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenFOAM; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Octree, templated on type of shapes it refers to. Uses the octreeData class which is a list of 1D, 2D or 3D shapes. Various implementations of octreeData which know about cell&meshes, patches&meshes and points. The octree can be used to - find the "nearest" shape to a point - find the shape which contains a point (only sensible for 3D shapes) - find intersections of line with shapes The tree consists of - treeNode : holds sub-treeNodes or treeLeaves - treeLeaf : is the one that actually holds data The data is stored purely as a list of indices into octreeData. The construction on the depth of the tree is: - one can specify a minimum depth (though the tree will never be refined if all leaves contain <=1 shapes) - after the minimum depth two statistics are used to decide further refinement: - average number of entries per leaf (leafRatio). Since inside a leaf most algorithms are n or n^2 this value has to be small. - average number of leaves a shape is in. Because of bounding boxes, a single shape can be in multiple leaves. If the bbs are large compared to the leaf size this multiplicity can become extremely large and will become larger with more levels. Note: the octree gets constructed with an overall bounding box. If your mesh is regular it is a good idea to make this overall bb a bit wider than the bb of the shapes itself. Otherwise lots of shapes end up exactly on the edge of a bb and hence go into more than one subcube. E.g. octree of face centres of lid driven cavity. 1. bb exact -> total 1457 leaves (every point in 7.1 leaves) 2. bb.max incremented by 1% -> total 80 leaves (every point in exactly 1 leaf) Ideas for parallel implementation: the data inserted into the octree (the 'octreeData') has to be local to the processor. The data to be looked for (usually a sample point) can be global to the domain. The algorithm: - search for all my points - collect results which have to do with a processor patch - global sum all these. If 0 exit. - exchange data on all processor patches - start again So data transfers one processor per iteration. One could think of having an extra search mechanism one level above which does an initial search knowing the average shape of a processor distribution (square/cube for most decomposition methods) and can assign sample points to the (almost) correct processor at once.
Definition in file octree.H.
Go to the source code of this file.
Namespaces | |
namespace | Foam |
Classes | |
class | octree |
class | octree::iterator |
class | octree::const_iterator |
Functions | |
template<class Type> | |
Ostream & | operator<< (Ostream &, const octree< Type > &) |
TemplateName (octree) |
|
|
|
|