Non-pointer based hierarchical recursive searching. More...

#include <indexedOctree.H>

Inheritance diagram for indexedOctree< Type >:

[legend]

Collaboration diagram for indexedOctree< Type >:

Public Member Functions
	indexedOctree (const Type &shapes)
	Construct null.
	indexedOctree (const Type &shapes, const List< node > &nodes, const List< labelList > &contents)
	Construct from components.
	indexedOctree (const Type &shapes, const treeBoundBox &bb, const label maxLevels, const scalar maxLeafRatio, const scalar maxDuplicity)
	Construct from shapes.
	indexedOctree (const Type &shapes, Istream &is)
	Construct from Istream.
autoPtr< indexedOctree< Type > >	clone () const
	Clone.
const Type &	shapes () const noexcept
	Reference to shape.
const List< node > &	nodes () const noexcept
	List of all nodes.
const List< labelList > &	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.
label	nLeafs () const
	Return the number of leaf nodes.
pointIndexHit	findNearest (const point &sample, const scalar nearestDistSqr) const
template<class FindNearestOp>
pointIndexHit	findNearest (const point &sample, const scalar nearestDistSqr, const FindNearestOp &fnOp) const
	Calculate nearest point on nearest shape.
template<class FindNearestOp>
void	findNearest (const label nodeI, const point &, scalar &nearestDistSqr, label &nearestShapeI, point &nearestPoint, const FindNearestOp &fnOp) const
	Low level: calculate nearest starting from subnode.
pointIndexHit	findNearest (const linePointRef &ln, treeBoundBox &tightest, point &linePoint) const
	Find nearest to line.
template<class FindNearestOp>
pointIndexHit	findNearest (const linePointRef &ln, treeBoundBox &tightest, point &linePoint, const FindNearestOp &fnOp) const
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.
template<class FindIntersectOp>
pointIndexHit	findLine (const point &start, const point &end, const FindIntersectOp &fiOp) const
	Find nearest intersection of line between start and end.
template<class FindIntersectOp>
pointIndexHit	findLineAny (const point &start, const point &end, const FindIntersectOp &fiOp) 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 indexedOctree< Type > &tree2, CompareOp &cop) const
	Find near pairs and apply CompareOp to them.
void	writeOBJ (Ostream &os) const
	Write (non-empty) tree boxes in 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
template<class FindIntersectOp>
Foam::pointIndexHit	findLine (const bool findAny, const point &treeStart, const point &treeEnd, const label startNodeI, const direction startOctant, const FindIntersectOp &fiOp, const bool verbose) const
template<class FindIntersectOp>
Foam::pointIndexHit	findLine (const bool findAny, const point &start, const point &end, const FindIntersectOp &fiOp) const
template<class FindNearestOp>
Foam::pointIndexHit	findNearest (const point &sample, const scalar startDistSqr, const FindNearestOp &fnOp) const
template<class FindNearestOp>
Foam::pointIndexHit	findNearest (const linePointRef &ln, treeBoundBox &tightest, point &linePoint, const FindNearestOp &fnOp) const
template<class FindIntersectOp>
Foam::pointIndexHit	findLine (const point &start, const point &end, const FindIntersectOp &fiOp) const
template<class FindIntersectOp>
Foam::pointIndexHit	findLineAny (const point &start, const point &end, const FindIntersectOp &fiOp) const
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 indexedOctree< Type > &)

Additional Inherited Members
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::indexedOctree< Type >

Non-pointer based hierarchical recursive searching.

Source files

Definition at line 295 of file indexedOctree.H.

Constructor & Destructor Documentation

◆ indexedOctree() [1/4]

template<class Type>

indexedOctree ( const Type & shapes )

Construct null.

Definition at line 2111 of file indexedOctree.C.

References shapes().

Referenced by findNear().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ indexedOctree() [2/4]

template<class Type>

indexedOctree	(	const Type &	shapes,
		const List< node > &	nodes,
		const List< labelList > &	contents )

Construct from components.

Definition at line 2121 of file indexedOctree.C.

References contents(), nodes(), and shapes().

Here is the call graph for this function:

◆ indexedOctree() [3/4]

template<class Type>

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

Construct from shapes.

Definition at line 2136 of file indexedOctree.C.

References bb(), contents(), Foam::endl(), Foam::identity(), Foam::max(), Foam::min(), Foam::nl, nodes(), Foam::Pout, shapes(), memInfo::size(), and while().

Here is the call graph for this function:

◆ indexedOctree() [4/4]

template<class Type>

indexedOctree	(	const Type &	shapes,
		Istream &	is )

Construct from Istream.

Definition at line 2315 of file indexedOctree.C.

References shapes().

Here is the call graph for this function:

Member Function Documentation

◆ clone()

template<class Type>

autoPtr< indexedOctree< Type > > clone ( ) const

inline

Clone.

Definition at line 650 of file indexedOctree.H.

◆ shapes()

template<class Type>

const Type & shapes ( ) const

inlinenoexcept

Reference to shape.

Definition at line 663 of file indexedOctree.H.

Referenced by patchFieldProbe::findElements(), mappedPatchBase::findLocalSamples(), refinementFeatures::findNearestRegionEdge(), indexedOctree(), indexedOctree(), indexedOctree(), indexedOctree(), surfaceFeatures::nearestEdges(), surfaceFeatures::nearestFeatEdge(), surfaceFeatures::nearestSamples(), surfaceFeatures::nearestSurfEdge(), and surfaceFeatures::nearestSurfEdge().

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 668 of file indexedOctree.H.

Referenced by distributedTriSurfaceMesh::distribute(), distributedTriSurfaceMesh::getVolumeType(), indexedOctree(), and indexedOctree().

Here is the caller graph for this function:

◆ contents()

template<class Type>

const List< labelList > & contents ( ) const

inlinenoexcept

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

Definition at line 674 of file indexedOctree.H.

Referenced by indexedOctree(), and indexedOctree().

Here is the caller graph for this function:

◆ nodeTypes()

template<class Type>

PackedList< 2 > & nodeTypes ( ) const

inlinenoexcept

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

Definition at line 682 of file indexedOctree.H.

Referenced by distributedTriSurfaceMesh::distribute(), and distributedTriSurfaceMesh::getVolumeType().

Here is the caller graph for this function:

◆ bb()

template<class Type>

const treeBoundBox & bb ( ) const

inline

Top bounding box.

Definition at line 690 of file indexedOctree.H.

Referenced by patchFieldProbe::findElements(), findNear(), getVolumeType(), indexedOctree(), surfaceFeatures::nearestSamples(), and print().

Here is the caller graph for this function:

◆ nLeafs()

template<class Type>

Foam::label nLeafs ( ) const

Return the number of leaf nodes.

Definition at line 2876 of file indexedOctree.C.

◆ findNearest() [1/7]

template<class Type>

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

Definition at line 2331 of file indexedOctree.C.

◆ findNearest() [2/7]

template<class Type>

template<class FindNearestOp>

pointIndexHit findNearest	(	const point &	sample,
		const scalar	nearestDistSqr,
		const FindNearestOp &	fnOp ) const

Calculate nearest point on nearest shape.

Returns

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

◆ findNearest() [3/7]

template<class Type>

template<class FindNearestOp>

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

Low level: calculate nearest starting from subnode.

Definition at line 389 of file indexedOctree.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() [4/7]

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 2380 of file indexedOctree.C.

References Foam::ln().

Here is the call graph for this function:

◆ findNearest() [5/7]

template<class Type>

template<class FindNearestOp>

pointIndexHit findNearest	(	const linePointRef &	ln,
		treeBoundBox &	tightest,
		point &	linePoint,
		const FindNearestOp &	fnOp ) const

◆ findLine() [1/5]

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 2432 of file indexedOctree.C.

◆ findLineAny() [1/3]

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 2449 of file indexedOctree.C.

Referenced by triSurfaceSearch::findLineAny().

Here is the caller graph for this function:

◆ findLine() [2/5]

template<class Type>

template<class FindIntersectOp>

pointIndexHit findLine	(	const point &	start,
		const point &	end,
		const FindIntersectOp &	fiOp ) const

Find nearest intersection of line between start and end.

◆ findLineAny() [2/3]

template<class Type>

template<class FindIntersectOp>

pointIndexHit findLineAny	(	const point &	start,
		const point &	end,
		const FindIntersectOp &	fiOp ) const

Find any intersection of line between start and end.

◆ overlaps() [1/2]

template<class Type>

bool overlaps ( const treeBoundBox & bb ) const

True if any shapes overlap the bounding box.

Definition at line 2492 of file indexedOctree.C.

◆ 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 2526 of file indexedOctree.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 2503 of file indexedOctree.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 2546 of file indexedOctree.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 2583 of file indexedOctree.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 2558 of file indexedOctree.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 2604 of file indexedOctree.C.

References indexedOctreeBase::node::bb_, 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 2641 of file indexedOctree.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 2675 of file indexedOctree.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 2702 of file indexedOctree.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 370 of file indexedOctree.C.

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

Referenced by treeDataFace::getVolumeType(), and treeDataPrimitivePatch< primitivePatch >::findSelfIntersectOp::operator()().

Here is the caller graph for this function:

◆ findNear()

template<class Type>

template<class CompareOp>

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

Find near pairs and apply CompareOp to them.

tree2 can be *this or different tree.

Definition at line 2772 of file indexedOctree.C.

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

Here is the call graph for this function:

◆ writeOBJ()

template<class Type>

void writeOBJ ( Ostream & os ) const

Write (non-empty) tree boxes in OBJ format.

Definition at line 2097 of file indexedOctree.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 2798 of file indexedOctree.C.

References bb(), indexedOctreeBase::node::bb_, Foam::endl(), forAll, indexedOctreeBase::getContent(), indexedOctreeBase::getNode(), indexedOctreeBase::isContent(), indexedOctreeBase::isNode(), 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 2889 of file indexedOctree.C.

References os().

Here is the call graph for this function:

◆ findLine() [3/5]

template<class Type>

template<class FindIntersectOp>

Foam::pointIndexHit findLine	(	const bool	findAny,
		const point &	treeStart,
		const point &	treeEnd,
		const label	startNodeI,
		const direction	startOctant,
		const FindIntersectOp &	fiOp,
		const bool	verbose ) const

Definition at line 1414 of file indexedOctree.C.

◆ findLine() [4/5]

template<class Type>

template<class FindIntersectOp>

Foam::pointIndexHit findLine	(	const bool	findAny,
		const point &	start,
		const point &	end,
		const FindIntersectOp &	fiOp ) const

Definition at line 1606 of file indexedOctree.C.

◆ findNearest() [6/7]

template<class Type>

template<class FindNearestOp>

Foam::pointIndexHit findNearest	(	const point &	sample,
		const scalar	startDistSqr,
		const FindNearestOp &	fnOp ) const

Definition at line 2348 of file indexedOctree.C.

◆ findNearest() [7/7]

template<class Type>

template<class FindNearestOp>

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

Definition at line 2399 of file indexedOctree.C.

◆ findLine() [5/5]

template<class Type>

template<class FindIntersectOp>

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

Definition at line 2467 of file indexedOctree.C.

◆ findLineAny() [3/3]

template<class Type>

template<class FindIntersectOp>

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

Definition at line 2480 of file indexedOctree.C.

◆ operator<<

template<class Type>

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

friend

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

src/meshTools/indexedOctree/treeDataPrimitivePatch.H
src/OpenFOAM/algorithms/indexedOctree/indexedOctree.H
src/OpenFOAM/algorithms/indexedOctree/indexedOctree.C

Public Member Functions

Static Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ indexedOctree() [1/4]

◆ indexedOctree() [2/4]

◆ indexedOctree() [3/4]

◆ indexedOctree() [4/4]

Member Function Documentation

◆ clone()

◆ shapes()

◆ nodes()

◆ contents()

◆ nodeTypes()

◆ bb()

◆ nLeafs()

◆ findNearest() [1/7]

◆ findNearest() [2/7]

◆ findNearest() [3/7]

◆ findNearest() [4/7]

◆ findNearest() [5/7]

◆ findLine() [1/5]

◆ findLineAny() [1/3]

◆ findLine() [2/5]

◆ findLineAny() [2/3]

◆ overlaps() [1/2]

◆ findBox() [1/2]

◆ findBox() [2/2]

◆ overlaps() [2/2]

◆ findSphere() [1/2]

◆ findSphere() [2/2]

◆ findNode()

◆ findInside()

◆ findIndices()

◆ getVolumeType()

◆ getSide()

◆ findNear()

◆ writeOBJ()

◆ print()

◆ write()

◆ findLine() [3/5]

◆ findLine() [4/5]

◆ findNearest() [6/7]

◆ findNearest() [7/7]

◆ findLine() [5/5]

◆ findLineAny() [3/3]

Friends And Related Symbol Documentation

◆ operator<<