Constructor that allows the use of prebuilt KdTree containers. More...

#include <kdTree.h>

Inheritance diagram for Ponca::KdTreeBase< _Traits >:

Collaboration diagram for Ponca::KdTreeBase< _Traits >:

Classes
struct	DefaultConverter
	Convert a custom point container to the KdTree PointContainer using DataPoint default constructor. More...

Public Types
using	Base = StaticKdTreeBase<_Traits>
using	Traits = _Traits
	Traits of the KdTree.
using	DataPoint = typename Traits::DataPoint
	DataPoint given by user via Traits.
using	IndexType = typename Traits::IndexType
	Type used to index points into the PointContainer.
using	LeafSizeType = typename Traits::LeafSizeType
	Type used to store the size of leaf nodes.
using	PointContainer = typename Traits::PointContainer
	Container for DataPoint used inside the KdTree.
using	IndexContainer = typename Traits::IndexContainer
	Container for indices used inside the KdTree.
using	NodeIndexType = typename Traits::NodeIndexType
	Type used to index nodes into the NodeContainer.
using	NodeType = typename Traits::NodeType
	Type of nodes used inside the KdTree.
using	NodeContainer = typename Traits::NodeContainer
	Container for nodes used inside the KdTree.
using	Scalar = typename DataPoint::Scalar
	Scalar given by user via DataPoint.
using	VectorType = typename DataPoint::VectorType
	VectorType given by user via DataPoint.
using	AabbType = typename NodeType::AabbType
	Bounding box type given by user via NodeType.
Public Types inherited from Ponca::StaticKdTreeBase< _Traits >
using	Traits = _Traits
	Traits of the KdTree.
using	DataPoint = typename Traits::DataPoint
	DataPoint given by user via Traits.
using	IndexType = typename Traits::IndexType
	Type used to index points into the PointContainer.
using	LeafSizeType = typename Traits::LeafSizeType
	Type used to store the size of leaf nodes.
using	PointContainer = typename Traits::PointContainer
	Container for DataPoint used inside the KdTree.
using	IndexContainer = typename Traits::IndexContainer
	Container for indices used inside the KdTree.
using	NodeIndexType = typename Traits::NodeIndexType
	Type used to index nodes into the NodeContainer.
using	NodeType = typename Traits::NodeType
	Type of nodes used inside the KdTree.
using	NodeContainer = typename Traits::NodeContainer
	Container for nodes used inside the KdTree.
using	Scalar = typename DataPoint::Scalar
	Scalar given by user via DataPoint.
using	VectorType = typename DataPoint::VectorType
	VectorType given by user via DataPoint.
using	AabbType = typename NodeType::AabbType
	Bounding box type given by user via NodeType.

Public Member Functions
template<typename PointUserContainer, typename PointConverter>
void	build (PointUserContainer &&points, PointConverter c)
	Generate a tree from a custom contained type converted using the specified converter.
template<typename PointUserContainer>
void	build (PointUserContainer &&points)
	Generate a tree from a custom contained type converted using DefaultConverter.
template<typename PointUserContainer, typename PointConverter>
PONCA_MULTIARCH_HOST void	build (PointUserContainer &&points, PointConverter c)
template<typename PointUserContainer, typename IndexUserContainer, typename PointConverter>
PONCA_MULTIARCH_HOST void	buildWithSampling (PointUserContainer &&points, IndexUserContainer &&sampling, PointConverter c)
Public Member Functions inherited from Ponca::StaticKdTreeBase< _Traits >
	StaticKdTreeBase (Buffers &buf)
	Constructor that allows the use of prebuilt KdTree containers.
NodeIndexType	nodeCount () const
	Get the number of nodes in the KdTree.
IndexType	sampleCount () const
	Get the number of indices.
IndexType	pointCount () const
	Get the number of points.
NodeIndexType	leafCount () const
	Get the number of leafs in the KdTree.
PointContainer &	points ()
	Get the internal point container.
const PointContainer &	points () const
	Get the internal point container.
const NodeContainer &	nodes () const
	Get the internal node container.
const IndexContainer &	samples () const
	Get the internal indice container.
const Buffers &	buffers () const
	Get access to the internal buffer, for instance to prepare GPU binding.
LeafSizeType	minCellSize () const
	Read leaf min size.
void	setMinCellSize (LeafSizeType min_cell_size)
	Write leaf min size.
IndexType	pointFromSample (IndexType sample_index) const
	Return the point index associated with the specified sample index.
DataPoint &	pointDataFromSample (IndexType sample_index)
	Return the DataPoint associated with the specified sample index.
const DataPoint &	pointDataFromSample (IndexType sample_index) const
	Return the DataPoint associated with the specified sample index.
KdTreeKNearestPointQuery< Traits >	kNearestNeighbors (const VectorType &point, IndexType k) const
	Computes a Query object to iterate over the k-nearest neighbors of a point. The returned object can be reset and reused with the () operator (using the same argument types as parameters).
KdTreeKNearestIndexQuery< Traits >	kNearestNeighbors (IndexType index, IndexType k) const
	Computes a Query object to iterate over the k-nearest neighbors of a point. The returned object can be reset and reused with the () operator (using the same argument types as parameters).
KdTreeKNearestPointQuery< Traits >	kNearestNeighborsQuery () const
	Convenience function that provides an empty k-nearest neighbors Query object.
KdTreeKNearestIndexQuery< Traits >	kNearestNeighborsIndexQuery () const
	Convenience function that provides an empty k-nearest neighbors Query object.
KdTreeNearestPointQuery< Traits >	nearestNeighbor (const VectorType &point) const
	Computes a Query object that contains the nearest point. The returned object can be reset and reused with the () operator (using the same argument types as parameters).
KdTreeNearestIndexQuery< Traits >	nearestNeighbor (IndexType index) const
	Computes a Query object that contains the nearest point. The returned object can be reset and reused with the () operator (using the same argument types as parameters).
KdTreeNearestIndexQuery< Traits >	nearestNeighborQuery () const
	Convenience function that provides an empty nearest neighbor Query object.
KdTreeNearestIndexQuery< Traits >	nearestNeighborIndexQuery () const
	Convenience function that provides an empty nearest neighbor Query object.
KdTreeRangePointQuery< Traits >	rangeNeighbors (const VectorType &point, Scalar r) const
	Computes a Query object to iterate over the neighbors that are inside a given radius. The returned object can be reset and reused with the () operator (using the same argument types as parameters).
KdTreeRangeIndexQuery< Traits >	rangeNeighbors (IndexType index, Scalar r) const
	Computes a Query object to iterate over the neighbors that are inside a given radius. The returned object can be reset and reused with the () operator (using the same argument types as parameters).
KdTreeRangePointQuery< Traits >	rangeNeighborsQuery () const
	Convenience function that provides an empty range neighbor Query object.
KdTreeRangeIndexQuery< Traits >	rangeNeighborsIndexQuery () const
	KdTreeBase::rangeNeighborsQuery.
bool	valid () const
void	print (std::ostream &os, bool verbose=false) const

Protected Member Functions
template<typename PointUserContainer, typename IndexUserContainer, typename PointConverter>
void	buildWithSampling (PointUserContainer &&points, IndexUserContainer &&sampling, PointConverter c)
	Generate a tree sampled from a custom contained type converted using a Converter.
template<typename PointUserContainer, typename IndexUserContainer>
void	buildWithSampling (PointUserContainer &&points, IndexUserContainer &&sampling)
	Generate a tree sampled from a custom contained type converted using a KdTreeBase::DefaultConverter.

Additional Inherited Members
Static Public Attributes inherited from Ponca::StaticKdTreeBase< _Traits >
static constexpr std::size_t	MAX_NODE_COUNT = NodeType::MAX_COUNT
	The maximum number of nodes that the kd-tree can have.
static constexpr std::size_t	MAX_POINT_COUNT = std::size_t(2) << sizeof(IndexType) * 8
	The maximum number of points that can be stored in the kd-tree.
static constexpr int	MAX_DEPTH = Traits::MAX_DEPTH
	The maximum depth of the kd-tree.
static constexpr bool	SUPPORTS_SUBSAMPLING = false
Protected Attributes inherited from Ponca::StaticKdTreeBase< _Traits >
Buffers	m_bufs
	Buffers used to store the KdTree.
LeafSizeType	m_min_cell_size {64}
	Minimal number of points per leaf.
NodeIndexType	m_leaf_count {0}
	Number of leaves in the Kdtree (computed during construction).

Detailed Description

template<typename _Traits>
class Ponca::KdTreeBase< _Traits >

Constructor that allows the use of prebuilt KdTree containers.

Base kdtree class that implements the basic build functionalities of the KdTree.

See also: KdTreeBase::build

This class is the basis for the KdTree Dense and Sparse type

See also: Ponca::KdTreeDense; Ponca::KdTreeSparse

Warning: Variants of this class are not usable on a CUDA device, because it relies on STL-like internal containers to build the kdtree.

Template Parameters

Traits Traits type providing the types and constants used by the kd-tree. Must have the same interface as the default traits type.

See also: KdTreeDefaultTraits for the trait interface documentation.

Definition at line 456 of file kdTree.h.

Member Typedef Documentation

◆ AabbType

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::AabbType = typename NodeType::AabbType

Bounding box type given by user via NodeType.

Definition at line 460 of file kdTree.h.

◆ Base

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::Base = StaticKdTreeBase<_Traits>

Definition at line 459 of file kdTree.h.

◆ DataPoint

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::DataPoint = typename Traits::DataPoint

DataPoint given by user via Traits.

Definition at line 460 of file kdTree.h.

◆ IndexContainer

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::IndexContainer = typename Traits::IndexContainer

Container for indices used inside the KdTree.

Definition at line 460 of file kdTree.h.

◆ IndexType

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::IndexType = typename Traits::IndexType

Type used to index points into the PointContainer.

Definition at line 460 of file kdTree.h.

◆ LeafSizeType

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::LeafSizeType = typename Traits::LeafSizeType

Type used to store the size of leaf nodes.

Definition at line 460 of file kdTree.h.

◆ NodeContainer

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::NodeContainer = typename Traits::NodeContainer

Container for nodes used inside the KdTree.

Definition at line 460 of file kdTree.h.

◆ NodeIndexType

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::NodeIndexType = typename Traits::NodeIndexType

Type used to index nodes into the NodeContainer.

Definition at line 460 of file kdTree.h.

◆ NodeType

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::NodeType = typename Traits::NodeType

Type of nodes used inside the KdTree.

Definition at line 460 of file kdTree.h.

◆ PointContainer

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::PointContainer = typename Traits::PointContainer

Container for DataPoint used inside the KdTree.

Definition at line 460 of file kdTree.h.

◆ Scalar

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::Scalar = typename DataPoint::Scalar

Scalar given by user via DataPoint.

Definition at line 460 of file kdTree.h.

◆ Traits

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::Traits = _Traits

Traits of the KdTree.

Definition at line 460 of file kdTree.h.

◆ VectorType

template<typename _Traits>

using Ponca::KdTreeBase< _Traits >::VectorType = typename DataPoint::VectorType

VectorType given by user via DataPoint.

Definition at line 460 of file kdTree.h.

Member Function Documentation

◆ build() [1/3]

template<typename _Traits>

template<typename PointUserContainer>

void Ponca::KdTreeBase< _Traits >::build ( PointUserContainer && points )

inline

Generate a tree from a custom contained type converted using DefaultConverter.

Template Parameters

PointUserContainer Input point container, transformed to PointContainer

Parameters

points Input points

Definition at line 489 of file kdTree.h.

◆ build() [2/3]

template<typename Traits>

template<typename PointUserContainer, typename PointConverter>

void Ponca::KdTreeBase< Traits >::build	(	PointUserContainer &&	points,
		PointConverter	c )

inline

Generate a tree from a custom contained type converted using the specified converter.

Template Parameters

PointUserContainer	Input point container, transformed to PointContainer
PointConverter	Cast/Convert input container type to point container data type

Parameters

points	Input points
c	Cast/Convert input point type to DataType

Definition at line 12 of file kdTree.h.

◆ build() [3/3]

template<typename _Traits>

template<typename PointUserContainer, typename PointConverter>

PONCA_MULTIARCH_HOST void Ponca::KdTreeBase< _Traits >::build	(	PointUserContainer &&	points,
		PointConverter	c )

inline

Definition at line 11 of file kdTree.hpp.

◆ buildWithSampling() [1/3]

template<typename _Traits>

template<typename PointUserContainer, typename IndexUserContainer>

void Ponca::KdTreeBase< _Traits >::buildWithSampling	(	PointUserContainer &&	points,
		IndexUserContainer &&	sampling )

inlineprotected

Generate a tree sampled from a custom contained type converted using a KdTreeBase::DefaultConverter.

Template Parameters

PointUserContainer	Input points, transformed to PointContainer
IndexUserContainer	Input sampling, transformed to IndexContainer

Parameters

points	Input points
sampling	Samples used in the tree

Definition at line 513 of file kdTree.h.

◆ buildWithSampling() [2/3]

template<typename Traits>

template<typename PointUserContainer, typename IndexUserContainer, typename PointConverter>

void Ponca::KdTreeBase< Traits >::buildWithSampling	(	PointUserContainer &&	points,
		IndexUserContainer &&	sampling,
		PointConverter	c )

inlineprotected

Generate a tree sampled from a custom contained type converted using a Converter.

Template Parameters

PointUserContainer	Input point, transformed to PointContainer
IndexUserContainer	Input sampling, transformed to IndexContainer
PointConverter	Cast/Convert input container type to point container data type

Parameters

points	Input points
sampling	Indices of points used in the tree
c	Cast/Convert input point type to DataType

Definition at line 119 of file kdTree.h.

◆ buildWithSampling() [3/3]

template<typename _Traits>

template<typename PointUserContainer, typename IndexUserContainer, typename PointConverter>

PONCA_MULTIARCH_HOST void Ponca::KdTreeBase< _Traits >::buildWithSampling	(	PointUserContainer &&	points,
		IndexUserContainer &&	sampling,
		PointConverter	c )

inline

Definition at line 118 of file kdTree.hpp.

Classes

Public Types

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ AabbType

◆ Base

◆ DataPoint

◆ IndexContainer

◆ IndexType

◆ LeafSizeType

◆ NodeContainer

◆ NodeIndexType

◆ NodeType

◆ PointContainer

◆ Scalar

◆ Traits

◆ VectorType

Member Function Documentation

◆ build() [1/3]

◆ build() [2/3]

◆ build() [3/3]

◆ buildWithSampling() [1/3]

◆ buildWithSampling() [2/3]

◆ buildWithSampling() [3/3]