Octree, templated on type of shapes it refers to. More...
#include <meshTools/octree.H>
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
The tree consists of
The data is stored purely as a list of indices into octreeData.
The construction on the depth of the tree is:
average number of entries per leaf (leafRatio). Since inside a leaf most algorithms are n or n^2 this value has to be small.
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.
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:
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 at line 127 of file octree.H.
Collaboration diagram for octree< Type >:Classes | |
| class | const_iterator |
| An STL const_iterator for octree. More...
| |
| class | iterator |
| An STL iterator for octree. More...
| |
Public Types | |
| enum | volumeType { UNKNOWN, MIXED, INSIDE, OUTSIDE } |
volume types More... | |
Public Member Functions | |
| octree (const treeBoundBox &octreeBb, const Type &shapes, const label minNLevels, const scalar maxLeafRatio, const scalar maxShapeRatio) | |
| Construct from components.
| |
| ~octree () | |
| const Type & | shapes () const |
| const treeBoundBox & | octreeBb () const |
| scalar | maxShapeRatio () const |
| scalar | maxLeafRatio () const |
| label | minNLevels () const |
| treeNode< Type > * | topNode () const |
| label | deepestLevel () const |
| label | nEntries () const |
| label | nNodes () const |
| label | nLeaves () const |
| void | setEntries (const label n) |
| void | setNodes (const label n) |
| void | setLeaves (const label n) |
| label | getSampleType (const point &sample) const |
| Returns type of sample with respect to nearest shape.
| |
| label | find (const point &sample) const |
| Find shape containing point in tree.
| |
| bool | findTightest (const point &sample, treeBoundBox &tightest) const |
| Calculate tightest fitting bounding box. Uses.
| |
| label | findNearest (const point &sample, treeBoundBox &tightest, scalar &tightestDist) const |
| Find nearest shape. Returns index of shape or -1 if not found.
| |
| label | findNearest (const linePointRef &ln, treeBoundBox &tightest, point &linePoint, point &shapePoint) const |
| Find nearest to line. Returns -1 or index of shape and.
| |
| labelList | findBox (const boundBox &bb) const |
| Find (in no particular order) indices of all shapes inside or.
| |
| pointIndexHit | findLine (const point &start, const point &end) const |
| Find intersected shape along line. pointIndexHit contains index.
| |
| pointIndexHit | findLineAny (const point &start, const point &end) const |
| Like above but just tests whether line hits anything. So.
| |
| const treeLeaf< Type > * | findLeafLine (const point &start, const point &end, point &leafIntPoint) const |
| Find leaf along line. Set leafIntPoint to leave point of.
| |
| void | writeOBJ (Ostream &os, label &vertNo) const |
| Dump graphical representation in .obj format.
| |
| void | printStats (Ostream &os) const |
| Print some stats on octree.
| |
| iterator | begin () |
| iterator set to the begining of the octree
| |
| const iterator & | end () |
| iterator set to beyond the end of the octree
| |
| const_iterator | begin () const |
| const_iterator set to the begining of the octree
| |
| const_iterator | cbegin () const |
| const const_iterator & | end () const |
| const_iterator set to beyond the end of the octree
| |
| const const_iterator & | cend () const |
Static Public Member Functions | |
| static string | volType (const label) |
| for debugging:return printable representation of volumeType
| |
| static label | getVolType (const vector &geomNormal, const vector &vec) |
| Code the vector with respect to the geometry. geomNormal guaranteed.
| |
Friends | |
| class | iterator |
| class | const_iterator |
| Ostream & | operator (Ostream &, const octree< Type > &) |
| enum volumeType |
| octree | ( | const treeBoundBox & | octreeBb, |
| const Type & | shapes, | ||
| const label | minNLevels, | ||
| const scalar | maxLeafRatio, | ||
| const scalar | maxShapeRatio | ||
| ) |
Construct from components.
Definition at line 92 of file octree.C.
References cpuTime::cpuTimeIncrement(), Foam::endl(), and Foam::Pout.
| Foam::string volType | ( | const label | type ) | [static]
|
for debugging:return printable representation of volumeType
Definition at line 39 of file octree.C.
References Foam::abort(), Foam::FatalError, and FatalErrorIn.
Referenced by treeNode< Type >::getSampleType(), treeNode< Type >::printNode(), and treeNode< Type >::setSubNodeType().
Code the vector with respect to the geometry. geomNormal guaranteed.
to point outside.
Definition at line 70 of file octree.C.
References sign().
Referenced by octreeDataTriSurface::getSampleType(), octreeDataFace::getSampleType(), and octreeDataFaceList::getSampleType().
| const Type& shapes | ( | ) | const [inline]
|
Definition at line 224 of file octree.H.
Referenced by surfaceFeatures::nearestEdges().
| const treeBoundBox& octreeBb | ( | ) | const [inline]
|
Definition at line 229 of file octree.H.
Referenced by surfaceFeatures::nearestSamples().
| scalar maxLeafRatio | ( | ) | const [inline]
|
Definition at line 239 of file octree.H.
Referenced by treeLeaf< Type >::redistribute().
| label nEntries | ( | ) | const [inline]
|
Definition at line 261 of file octree.H.
Referenced by treeNode< Type >::distribute(), and treeNode< Type >::redistribute().
| label nNodes | ( | ) | const [inline]
|
Definition at line 266 of file octree.H.
Referenced by treeLeaf< Type >::redistribute().
| label nLeaves | ( | ) | const [inline]
|
Definition at line 271 of file octree.H.
Referenced by treeNode< Type >::distribute(), octree< Type >::iterator::operator==(), and treeNode< Type >::redistribute().
| void setEntries | ( | const label | n ) | [inline]
|
Definition at line 276 of file octree.H.
Referenced by treeNode< Type >::distribute(), and treeNode< Type >::redistribute().
| void setNodes | ( | const label | n ) | [inline]
|
Definition at line 281 of file octree.H.
Referenced by treeLeaf< Type >::redistribute().
| void setLeaves | ( | const label | n ) | [inline]
|
Definition at line 286 of file octree.H.
Referenced by treeNode< Type >::distribute(), and treeNode< Type >::redistribute().
| Foam::label getSampleType | ( | const point & | sample ) | const |
Returns type of sample with respect to nearest shape.
Meaning of type is determined by shapes.getSampleType(). Normally based on outwards pointing normal. For e.g. octreeDataFace returns one of inside : on other side of normal on nearest face outside : on same side as normal on nearest face unknown : not above nearest face; surface probably not closed. mixed : should never happen
| Foam::label find | ( | const point & | sample ) | const |
| bool findTightest | ( | const point & | sample, |
| treeBoundBox & | tightest | ||
| ) | const |
| Foam::label findNearest | ( | const point & | sample, |
| treeBoundBox & | tightest, | ||
| scalar & | tightestDist | ||
| ) | const |
Find nearest shape. Returns index of shape or -1 if not found.
tightestDist is both input and output. Uses Type::calcNearest.
Definition at line 275 of file octree.C.
References Foam::endl(), and Foam::Pout.
Referenced by boundaryMesh::getNearest(), octreeDataTriSurface::getSampleType(), octreeDataFace::getSampleType(), octreeDataFaceList::getSampleType(), surfaceFeatures::nearestEdges(), surfaceFeatures::nearestSamples(), and surfaceFeatures::nearestSurfEdge().
| Foam::label findNearest | ( | const linePointRef & | ln, |
| treeBoundBox & | tightest, | ||
| point & | linePoint, | ||
| point & | shapePoint | ||
| ) | const |
| Foam::labelList findBox | ( | const boundBox & | bb ) | const |
Find (in no particular order) indices of all shapes inside or.
overlapping bounding box (i.e. all shapes not outside box)
Definition at line 342 of file octree.C.
References HashTable< T, Key, Hash >::toc().
| Foam::pointIndexHit findLine | ( | const point & | start, |
| const point & | end | ||
| ) | const |
Find intersected shape along line. pointIndexHit contains index.
of nearest shape intersected and the intersection point. Uses findLeafLine.
Definition at line 355 of file octree.C.
References forAll, PointIndexHit< Point >::hit(), treeLeaf< Type >::indices(), PointIndexHit< Point >::setHit(), PointIndexHit< Point >::setIndex(), and PointIndexHit< Point >::setPoint().
| Foam::pointIndexHit findLineAny | ( | const point & | start, |
| const point & | end | ||
| ) | const |
Like above but just tests whether line hits anything. So.
returns first intersection found, not nessecarily nearest.
Definition at line 436 of file octree.C.
References forAll, PointIndexHit< Point >::hit(), treeLeaf< Type >::indices(), p, PointIndexHit< Point >::setHit(), PointIndexHit< Point >::setIndex(), and PointIndexHit< Point >::setPoint().
| const Foam::treeLeaf< Type > * findLeafLine | ( | const point & | start, |
| const point & | end, | ||
| point & | leafIntPoint | ||
| ) | const |
Find leaf along line. Set leafIntPoint to leave point of.
Definition at line 506 of file octree.C.
References Foam::endl(), and Foam::Pout.
| void writeOBJ | ( | Ostream & | os, |
| label & | vertNo | ||
| ) | const |
Dump graphical representation in .obj format.
Definition at line 569 of file octree.C.
References Foam::endl().
| void printStats | ( | Ostream & | os ) | const |
Print some stats on octree.
Definition at line 617 of file octree.C.
References Foam::endl(), and Foam::nl.
| Foam::octree< Type >::iterator begin | ( | ) |
| const Foam::octree< Type >::iterator & end | ( | ) |
| Foam::octree< Type >::const_iterator begin | ( | ) | const [inline]
|
const_iterator set to the begining of the octree
| Foam::octree< Type >::const_iterator cbegin | ( | ) | const [inline]
|
| const Foam::octree< Type >::const_iterator & end | ( | ) | const [inline]
|
const_iterator set to beyond the end of the octree
| const Foam::octree< Type >::const_iterator & cend | ( | ) | const [inline]
|
friend class const_iterator [friend]
|
