Non-pointer based hierarchical recursive searching. Storage is dynamic, so elements can be deleted. More...

#include <dynamicIndexedOctree.H>

Inheritance diagram for dynamicIndexedOctree< Type >:

[legend]

Collaboration diagram for dynamicIndexedOctree< Type >:

Public Member Functions
	dynamicIndexedOctree (const Type &shapes, const treeBoundBox &bb, const label maxLevels, const scalar maxLeafRatio, const scalar maxDuplicity)
	Construct from shapes.
autoPtr< dynamicIndexedOctree< Type > >	clone () const
	Clone.
const Type &	shapes () const noexcept
	Reference to shape.
const List< node > &	nodes () const noexcept
	List of all nodes.
const DynamicList< DynamicList< label > > &	contents () const noexcept
	List of all contents (referenced by those nodes that are contents).
PackedList< 2 > &	nodeTypes () const noexcept
	Per node, per octant whether is fully inside/outside/mixed.
const treeBoundBox &	bb () const
	Top bounding box.
pointIndexHit	findNearest (const point &sample, const scalar nearestDistSqr) const
	Calculate nearest point on nearest shape.
void	findNearest (const label nodeI, const point &, scalar &nearestDistSqr, label &nearestShapeI, point &nearestPoint) const
	Low level: calculate nearest starting from subnode.
pointIndexHit	findNearest (const linePointRef &ln, treeBoundBox &tightest, point &linePoint) const
	Find nearest to line.
pointIndexHit	findLine (const point &start, const point &end) const
	Find nearest intersection of line between start and end.
pointIndexHit	findLineAny (const point &start, const point &end) const
	Find any intersection of line between start and end.
bool	overlaps (const treeBoundBox &bb) const
	True if any shapes overlap the bounding box.
labelList	findBox (const treeBoundBox &bb) const
	Find indices of all shapes inside or overlapping a bounding box (i.e. all shapes not outside box).
label	findBox (const treeBoundBox &bb, labelHashSet &elements) const
	Find indices of all shapes inside or overlapping a bounding box (i.e. all shapes not outside box).
bool	overlaps (const point &centre, const scalar radiusSqr) const
	True if any shapes overlap the bounding sphere.
labelList	findSphere (const point &centre, const scalar radiusSqr) const
	Find indices of all shapes inside or overlapping a bounding sphere (i.e. all shapes not outside a sphere).
label	findSphere (const point &centre, const scalar radiusSqr, labelHashSet &elements) const
	Find indices of all shapes inside or overlapping a bounding sphere (i.e. all shapes not outside sphere).
labelBits	findNode (const label nodeI, const point &) const
	Find deepest node (as parent+octant) containing point. Starts.
label	findInside (const point &) const
	Find shape containing point. Only implemented for certain.
const labelList &	findIndices (const point &) const
	Find the shape indices that occupy the result of findNode.
volumeType	getVolumeType (const point &) const
	Determine type (inside/outside/mixed) for point. unknown if.
template<class CompareOp>
void	findNear (const scalar nearDist, const dynamicIndexedOctree< Type > &tree2, CompareOp &cop) const
	Find near pairs and apply CompareOp to them.
bool	insert (label startIndex, label endIndex)
	Insert a new object into the tree.
bool	insertIndex (const label nodIndex, const label index, label &nLevels)
bool	remove (const label index)
	Remove an object from the tree.
label	removeIndex (const label nodIndex, const label index)
void	writeOBJ (Ostream &os) const
	Write all tree boxes as OBJ format.
void	print (prefixOSstream &, const bool printContents, const label) const
	Print tree. Either print all indices (printContent = true) or.
bool	write (Ostream &os) const
void	writeTreeInfo () const
Public Member Functions inherited from dynamicIndexedOctreeBase
	ClassName ("dynamicIndexedOctree")
	Runtime type information.
	dynamicIndexedOctreeBase ()=default
	Default construct.
Public Member Functions inherited from indexedOctreeBase
	ClassName ("indexedOctree")
	Runtime type information.
	indexedOctreeBase ()=default
	Default construct.

Static Public Member Functions
static volumeType	getSide (const vector &outsideNormal, const vector &vec)
	Helper function to return the side. Returns outside if.
Static Public Member Functions inherited from indexedOctreeBase
static bool	isEmpty (labelBits i) noexcept
	An empty node - no content.
static bool	isContent (labelBits i) noexcept
	Node with content (leaf).
static bool	isNode (labelBits i) noexcept
	A parent node.
static label	getContent (labelBits i)
	Return real (dereferenced) index for a content node.
static label	getNode (const labelBits i)
	Return real (dereferenced) index for a parent node.
static direction	getOctant (labelBits i) noexcept
	Return sub-node direction/octant.
static scalar &	perturbTol () noexcept
	Get the perturbation tolerance.
static scalar	perturbTol (scalar tol) noexcept
	Set the perturbation tolerance, return the old value.
static void	writeOBJ (Ostream &os, const treeBoundBox &bb, label &vertIndex, const bool writeLinesOnly=false)
	Write treeBoundBox in OBJ format.

Friends
Ostream &	operator<< (Ostream &, const dynamicIndexedOctree< Type > &)

Additional Inherited Members
Public Types inherited from dynamicIndexedOctreeBase
using	node = indexedOctreeBase::node
	Document that we are using the same types of node.
Static Protected Member Functions inherited from indexedOctreeBase
static labelBits	emptyPlusOctant (direction octant)
	From empty to subNodes_ entry.
static labelBits	contentPlusOctant (label i, direction octant)
	From index into contents_ to subNodes_ entry.
static labelBits	nodePlusOctant (label i, direction octant)
	From index into nodes_ to subNodes_ entry.
Static Protected Attributes inherited from indexedOctreeBase
static scalar	perturbTol_ = 10*SMALL
	Relative perturbation tolerance.

Detailed Description

template<class Type>
class Foam::dynamicIndexedOctree< Type >

Non-pointer based hierarchical recursive searching. Storage is dynamic, so elements can be deleted.

Source files

Definition at line 91 of file dynamicIndexedOctree.H.

Constructor & Destructor Documentation

◆ dynamicIndexedOctree()

template<class Type>

dynamicIndexedOctree	(	const Type &	shapes,
		const treeBoundBox &	bb,
		const label	maxLevels,
		const scalar	maxLeafRatio,
		const scalar	maxDuplicity )

Construct from shapes.

Definition at line 2023 of file dynamicIndexedOctree.C.

References bb(), if(), insert(), shapes(), and writeTreeInfo().

Referenced by findNear(), and operator<<.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

◆ clone()

template<class Type>

autoPtr< dynamicIndexedOctree< Type > > clone ( ) const

inline

Clone.

Definition at line 410 of file dynamicIndexedOctree.H.

References Foam::New().

Here is the call graph for this function:

◆ shapes()

template<class Type>

const Type & shapes ( ) const

inlinenoexcept

Reference to shape.

Definition at line 423 of file dynamicIndexedOctree.H.

References Foam::noexcept.

Referenced by dynamicIndexedOctree(), insertIndex(), removeIndex(), and writeTreeInfo().

Here is the caller graph for this function:

◆ nodes()

template<class Type>

const List< node > & nodes ( ) const

inlinenoexcept

List of all nodes.

Definition at line 428 of file dynamicIndexedOctree.H.

References Foam::noexcept.

◆ contents()

template<class Type>

const DynamicList< DynamicList< label > > & contents ( ) const

inlinenoexcept

List of all contents (referenced by those nodes that are contents).

Definition at line 434 of file dynamicIndexedOctree.H.

References Foam::noexcept.

◆ nodeTypes()

template<class Type>

PackedList< 2 > & nodeTypes ( ) const

inlinenoexcept

Per node, per octant whether is fully inside/outside/mixed.

Definition at line 442 of file dynamicIndexedOctree.H.

References Foam::noexcept.

◆ bb()

template<class Type>

const treeBoundBox & bb ( ) const

inline

Top bounding box.

Definition at line 450 of file dynamicIndexedOctree.H.

References treeBoundBox::null().

Referenced by dynamicIndexedOctree(), findNear(), getVolumeType(), and print().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findNearest() [1/3]

template<class Type>

Foam::pointIndexHit findNearest	(	const point &	sample,
		const scalar	nearestDistSqr ) const

Calculate nearest point on nearest shape.

Returns

bool : any point found nearer than nearestDistSqr
label: index in shapes
point: actual nearest point found

Definition at line 2060 of file dynamicIndexedOctree.C.

References Foam::Zero.

◆ findNearest() [2/3]

template<class Type>

void findNearest	(	const label	nodeI,
		const point &	sample,
		scalar &	nearestDistSqr,
		label &	nearestShapeI,
		point &	nearestPoint ) const

Low level: calculate nearest starting from subnode.

Definition at line 341 of file dynamicIndexedOctree.C.

References indexedOctreeBase::node::bb_, indexedOctreeBase::getContent(), indexedOctreeBase::getNode(), indexedOctreeBase::isContent(), indexedOctreeBase::isNode(), treeBoundBox::overlaps(), treeBoundBox::searchOrder(), indexedOctreeBase::node::subNodes_, and treeBoundBox::subOverlaps().

Here is the call graph for this function:

◆ findNearest() [3/3]

template<class Type>

Foam::pointIndexHit findNearest	(	const linePointRef &	ln,
		treeBoundBox &	tightest,
		point &	linePoint ) const

Find nearest to line.

Returns

bool : any point found?
label: index in shapes
point: actual nearest point found sets:
linePoint : corresponding nearest point on line

Definition at line 2088 of file dynamicIndexedOctree.C.

References Foam::ln(), and Foam::Zero.

Here is the call graph for this function:

◆ findLine()

template<class Type>

Foam::pointIndexHit findLine	(	const point &	start,
		const point &	end ) const

Find nearest intersection of line between start and end.

Definition at line 2117 of file dynamicIndexedOctree.C.

◆ findLineAny()

template<class Type>

Foam::pointIndexHit findLineAny	(	const point &	start,
		const point &	end ) const

Find any intersection of line between start and end.

Definition at line 2128 of file dynamicIndexedOctree.C.

◆ overlaps() [1/2]

template<class Type>

bool overlaps ( const treeBoundBox & bb ) const

True if any shapes overlap the bounding box.

Definition at line 2139 of file dynamicIndexedOctree.C.

Referenced by insertIndex(), and removeIndex().

Here is the caller graph for this function:

◆ findBox() [1/2]

template<class Type>

Foam::labelList findBox ( const treeBoundBox & bb ) const

Find indices of all shapes inside or overlapping a bounding box (i.e. all shapes not outside box).

Returns: the indices (in no particular order)

Parameters

bb	bound box limits

Definition at line 2173 of file dynamicIndexedOctree.C.

References HashTable< T, Key, Hash >::toc().

Here is the call graph for this function:

◆ findBox() [2/2]

template<class Type>

Foam::label findBox	(	const treeBoundBox &	bb,
		labelHashSet &	elements ) const

Find indices of all shapes inside or overlapping a bounding box (i.e. all shapes not outside box).

Returns: the number of elements found

Parameters

	bb	bound box limits
[out]	elements	elements found

Definition at line 2150 of file dynamicIndexedOctree.C.

References HashTable< T, Key, Hash >::clear(), Foam::max(), HashTable< T, Key, Hash >::reserve(), and HashTable< T, Key, Hash >::size().

Here is the call graph for this function:

◆ overlaps() [2/2]

template<class Type>

bool overlaps	(	const point &	centre,
		const scalar	radiusSqr ) const

True if any shapes overlap the bounding sphere.

Parameters

centre	centre of bound sphere
radiusSqr	radius^2 of sphere

Definition at line 2193 of file dynamicIndexedOctree.C.

◆ findSphere() [1/2]

template<class Type>

Foam::labelList findSphere	(	const point &	centre,
		const scalar	radiusSqr ) const

Find indices of all shapes inside or overlapping a bounding sphere (i.e. all shapes not outside a sphere).

Returns: the indices (in no particular order)

Parameters

centre	centre of bound sphere
radiusSqr	radius^2 of sphere

Definition at line 2229 of file dynamicIndexedOctree.C.

References HashTable< T, Key, Hash >::toc().

Here is the call graph for this function:

◆ findSphere() [2/2]

template<class Type>

Foam::label findSphere	(	const point &	centre,
		const scalar	radiusSqr,
		labelHashSet &	elements ) const

Find indices of all shapes inside or overlapping a bounding sphere (i.e. all shapes not outside sphere).

Returns: the number of elements found

Parameters

	centre	centre of bound sphere
	radiusSqr	radius^2 of sphere
[out]	elements	elements found

Definition at line 2205 of file dynamicIndexedOctree.C.

References HashTable< T, Key, Hash >::clear(), Foam::max(), HashTable< T, Key, Hash >::reserve(), and HashTable< T, Key, Hash >::size().

Here is the call graph for this function:

◆ findNode()

template<class Type>

Foam::labelBits findNode	(	const label	nodeI,
		const point &	sample ) const

Find deepest node (as parent+octant) containing point. Starts.

off from starting index in nodes_ (use 0 to start from top) Use getNode and getOctant to extract info, or call findIndices.

Definition at line 2250 of file dynamicIndexedOctree.C.

References Foam::abort(), indexedOctreeBase::node::bb_, treeBoundBox::contains(), Foam::FatalError, FatalErrorInFunction, findNode(), indexedOctreeBase::getNode(), indexedOctreeBase::isContent(), indexedOctreeBase::isNode(), indexedOctreeBase::nodePlusOctant(), indexedOctreeBase::node::subNodes_, and treeBoundBox::subOctant().

Referenced by findIndices(), findInside(), and findNode().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findInside()

template<class Type>

Foam::label findInside ( const point & sample ) const

Find shape containing point. Only implemented for certain.

shapes.

Definition at line 2297 of file dynamicIndexedOctree.C.

References findNode(), forAll, indexedOctreeBase::getContent(), indexedOctreeBase::getNode(), Foam::getOctant(), indexedOctreeBase::isContent(), and indexedOctreeBase::node::subNodes_.

Here is the call graph for this function:

◆ findIndices()

template<class Type>

const Foam::labelList & findIndices ( const point & sample ) const

Find the shape indices that occupy the result of findNode.

Definition at line 2329 of file dynamicIndexedOctree.C.

References findNode(), indexedOctreeBase::getContent(), indexedOctreeBase::getNode(), Foam::getOctant(), indexedOctreeBase::isContent(), List< label >::null(), and indexedOctreeBase::node::subNodes_.

Here is the call graph for this function:

◆ getVolumeType()

template<class Type>

Foam::volumeType getVolumeType ( const point & sample ) const

Determine type (inside/outside/mixed) for point. unknown if.

cannot be determined (e.g. non-manifold surface)

Definition at line 2351 of file dynamicIndexedOctree.C.

References Foam::abort(), bb(), Foam::endl(), Foam::FatalError, FatalErrorInFunction, forAll, volumeType::INSIDE, volumeType::MIXED, volumeType::OUTSIDE, Foam::Pout, and volumeType::UNKNOWN.

Here is the call graph for this function:

◆ getSide()

template<class Type>

Foam::volumeType getSide	(	const vector &	outsideNormal,
		const vector &	vec )

static

Helper function to return the side. Returns outside if.

outsideNormal&vec >= 0, inside otherwise

Definition at line 323 of file dynamicIndexedOctree.C.

References volumeType::INSIDE, and volumeType::OUTSIDE.

◆ findNear()

template<class Type>

template<class CompareOp>

void findNear	(	const scalar	nearDist,
		const dynamicIndexedOctree< Type > &	tree2,
		CompareOp &	cop ) const

Find near pairs and apply CompareOp to them.

tree2 can be *this or different tree.

Definition at line 2421 of file dynamicIndexedOctree.C.

References bb(), dynamicIndexedOctree(), and indexedOctreeBase::nodePlusOctant().

Here is the call graph for this function:

◆ insert()

template<class Type>

bool insert	(	label	startIndex,
		label	endIndex )

Insert a new object into the tree.

Definition at line 2444 of file dynamicIndexedOctree.C.

References Foam::divide(), insertIndex(), Foam::max(), and success.

Referenced by dynamicIndexedOctree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insertIndex()

template<class Type>

bool insertIndex	(	const label	nodIndex,
		const label	index,
		label &	nLevels )

Definition at line 2482 of file dynamicIndexedOctree.C.

References indexedOctreeBase::contentPlusOctant(), indexedOctreeBase::getContent(), indexedOctreeBase::getNode(), insertIndex(), indexedOctreeBase::isContent(), indexedOctreeBase::isNode(), indexedOctreeBase::node::nChildren, overlaps(), shapes(), and treeBoundBox::subBbox().

Referenced by insert(), and insertIndex().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove()

template<class Type>

bool remove ( const label index )

Remove an object from the tree.

Definition at line 2554 of file dynamicIndexedOctree.C.

References removeIndex().

Here is the call graph for this function:

◆ removeIndex()

template<class Type>

Foam::label removeIndex	(	const label	nodIndex,
		const label	index )

Definition at line 2568 of file dynamicIndexedOctree.C.

References UList< T >::empty(), indexedOctreeBase::emptyPlusOctant(), forAll, indexedOctreeBase::getContent(), indexedOctreeBase::getNode(), indexedOctreeBase::isContent(), indexedOctreeBase::isNode(), indexedOctreeBase::node::nChildren, overlaps(), DynamicList< T, SizeMin >::push_back(), removeIndex(), shapes(), DynamicList< T, SizeMin >::shrink(), UList< T >::size(), treeBoundBox::subBbox(), and DynamicList< T, SizeMin >::transfer().

Referenced by remove(), and removeIndex().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ writeOBJ()

template<class Type>

void writeOBJ ( Ostream & os ) const

Write all tree boxes as OBJ format.

Definition at line 2009 of file dynamicIndexedOctree.C.

References os().

Here is the call graph for this function:

◆ print()

template<class Type>

void print	(	prefixOSstream &	os,
		const bool	printContents,
		const label	nodeI ) const

Print tree. Either print all indices (printContent = true) or.

just size of contents nodes.

Definition at line 2651 of file dynamicIndexedOctree.C.

References bb(), indexedOctreeBase::node::bb_, Foam::endl(), forAll, indexedOctreeBase::getContent(), indexedOctreeBase::getNode(), indexedOctreeBase::isContent(), indexedOctreeBase::isNode(), indexedOctreeBase::node::nChildren, Foam::nl, indexedOctreeBase::nodePlusOctant(), os(), indexedOctreeBase::node::parent_, print(), UList< T >::size(), and indexedOctreeBase::node::subNodes_.

Referenced by print().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ write()

template<class Type>

bool write ( Ostream & os ) const

Definition at line 2750 of file dynamicIndexedOctree.C.

References os().

Here is the call graph for this function:

◆ writeTreeInfo()

template<class Type>

void writeTreeInfo ( ) const

Definition at line 2724 of file dynamicIndexedOctree.C.

References Foam::endl(), Foam::nl, Foam::Pout, and shapes().

Referenced by dynamicIndexedOctree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator<<

template<class Type>

Ostream & operator<<	(	Ostream &	,
		const dynamicIndexedOctree< Type > &	)

friend

References dynamicIndexedOctree().

The documentation for this class was generated from the following files:

src/OpenFOAM/algorithms/dynamicIndexedOctree/dynamicIndexedOctree.H
src/OpenFOAM/algorithms/dynamicIndexedOctree/dynamicIndexedOctree.C

Public Member Functions

Static Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ dynamicIndexedOctree()

Member Function Documentation

◆ clone()

◆ shapes()

◆ nodes()

◆ contents()

◆ nodeTypes()

◆ bb()

◆ findNearest() [1/3]

◆ findNearest() [2/3]

◆ findNearest() [3/3]

◆ findLine()

◆ findLineAny()

◆ overlaps() [1/2]

◆ findBox() [1/2]

◆ findBox() [2/2]

◆ overlaps() [2/2]

◆ findSphere() [1/2]

◆ findSphere() [2/2]

◆ findNode()

◆ findInside()

◆ findIndices()

◆ getVolumeType()

◆ getSide()

◆ findNear()

◆ insert()

◆ insertIndex()

◆ remove()

◆ removeIndex()

◆ writeOBJ()

◆ print()

◆ write()

◆ writeTreeInfo()

Friends And Related Symbol Documentation

◆ operator<<