OpenFOAM logo
Open Source CFD Toolkit

octree.H File Reference


Detailed Description

View octree.H
License
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
Description
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.

Source files

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)


Function Documentation

Ostream& operator<< Ostream &  ,
const octree< Type > & 
 

TemplateName octree   ) 
 

For further information go to www.openfoam.org