The node type used by default by the kd-tree. More...

#include <kdTreeTraits.h>

Inheritance diagram for Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >:

Collaboration diagram for Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >:

Public Types
enum	{ MAX_COUNT = std::size_t(2) << InnerType::INDEX_BITS }

using	AabbType = Eigen::AlignedBox< Scalar, DataPoint::Dim >
	The type used to store node bounding boxes.

Public Member Functions
bool	is_leaf () const

void	set_is_leaf (bool is_leaf)

void	configure_range (Index start, Index size, const AabbType &aabb)
	Configures the range of the node in the sample index array of the kd-tree.

void	configure_inner (Scalar split_value, Index first_child_id, Index split_dim)
	Configures the inner node information.

Index	leaf_start () const
	The start index of the range of the leaf node in the sample index array.

LeafSize	leaf_size () const
	The size of the range of the leaf node in the sample index array.

Scalar	inner_split_value () const
	The position of the AABB split of the inner node.

int	inner_split_dim () const
	Which axis the split of the AABB of the inner node was done on.

Index	inner_first_child_id () const
	The index of the first child of the node in the node array of the kd-tree.

Protected Member Functions
LeafType &	getAsLeaf ()

InnerType &	getAsInner ()

const LeafType &	getAsLeaf () const

const InnerType &	getAsInner () const

Detailed Description

template<typename Index, typename NodeIndex, typename DataPoint, typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>
class Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >

The node type used by default by the kd-tree.

It is possible to modify the Inner and Leaf node types by inheritance. For instance, to add a Bounding box to inner nodes, define a custom inner node type:

template <typename NodeIndex, typename Scalar, int DIM, typename _AabbType = Eigen::AlignedBox<Scalar, DIM>>
struct MyKdTreeInnerNode : public Ponca::KdTreeDefaultInnerNode<NodeIndex, Scalar, DIM> {
    using AabbType = _AabbType;
    AabbType m_aabb{};
};

Define a custom node type to use it, and expose custom data (inner/leaf node are not exposed directly):

template <typename Index, typename NodeIndex, typename DataPoint, typename LeafSize = Index>
struct MyKdTreeNode : Ponca::KdTreeCustomizableNode<Index, NodeIndex, DataPoint, LeafSize,
        MyKdTreeInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>> {
 
    using Base = Ponca::KdTreeCustomizableNode<Index, NodeIndex, DataPoint, LeafSize,
            MyKdTreeInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>>;
    using AabbType  = typename Base::AabbType;
 
    void configure_range(Index start, Index size, const AabbType &aabb)
    {
        Base::configure_range(start, size, aabb);
        if (! Base::is_leaf() )
        {
            Base::getAsInner().m_aabb = aabb;
        }
    }
    [[nodiscard]] inline std::optional<AabbType> getAabb() const {
        if (! Base::is_leaf())
            return Base::getAsInner().m_aabb;
        else
            return std::optional<AabbType>();
    }
};

To use in the KdTree, define a type using the custom node:

using CustomKdTree = Ponca::KdTreeDenseBase<Ponca::KdTreeDefaultTraits<DataPoint,MyKdTreeNode>>;

Ponca::KdTreeDenseBase

Customizable base class for dense KdTree datastructure.

Definition: kdTree.h:353

The added attribute can be accessed

    auto bbox = kdtree.nodes()[0].getAabb();
    if (bbox) {
        std::cout << "Root bounding box is as follows: \n"
                  << "  Center:   " << bbox->center()
                  << "  Diagonal: " << bbox->diagonal()
                  << std::endl;
    }

Definition at line 109 of file kdTreeTraits.h.

Member Typedef Documentation

◆ AabbType

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

using Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::AabbType = Eigen::AlignedBox<Scalar, DataPoint::Dim>

The type used to store node bounding boxes.

Must provide diagonal(), and center() functions, all returning a DataPoint::VectorType.

Definition at line 132 of file kdTreeTraits.h.

Member Enumeration Documentation

◆ anonymous enum

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

anonymous enum

Enumerator
MAX_COUNT	The maximum number of nodes that a kd-tree can have when using this node type.

Definition at line 117 of file kdTreeTraits.h.

Member Function Documentation

◆ configure_inner()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

void Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::configure_inner	(	Scalar	split_value,
		Index	first_child_id,
		Index	split_dim
	)

inline

Configures the inner node information.

See also: the inner node accessors for a more detailed explanation of each argument.

Called after set_is_leaf and configure_range during kd-tree construction.

Definition at line 167 of file kdTreeTraits.h.

◆ configure_range()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

void Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::configure_range	(	Index	start,
		Index	size,
		const AabbType &	aabb
	)

inline

Configures the range of the node in the sample index array of the kd-tree.

See also: the leaf node accessors for a more detailed explanation of each argument.

Note: The AABB is not required by the implementation, so nodes don't have to make it available.

Called after set_is_leaf during kd-tree construction.

Definition at line 149 of file kdTreeTraits.h.

◆ getAsInner() [1/2]

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

InnerType & Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::getAsInner ( )

inlineprotected

Definition at line 209 of file kdTreeTraits.h.

◆ getAsInner() [2/2]

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

const InnerType & Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::getAsInner ( ) const

inlineprotected

Definition at line 211 of file kdTreeTraits.h.

◆ getAsLeaf() [1/2]

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

LeafType & Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::getAsLeaf ( )

inlineprotected

Definition at line 208 of file kdTreeTraits.h.

◆ getAsLeaf() [2/2]

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

const LeafType & Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::getAsLeaf ( ) const

inlineprotected

Definition at line 210 of file kdTreeTraits.h.

◆ inner_first_child_id()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

Index Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::inner_first_child_id ( ) const

inline

The index of the first child of the node in the node array of the kd-tree.

Note: The second child is stored directly after the first in the array (i.e. first_child_id + 1).

Definition at line 205 of file kdTreeTraits.h.

◆ inner_split_dim()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

int Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::inner_split_dim ( ) const

inline

Which axis the split of the AABB of the inner node was done on.

Definition at line 196 of file kdTreeTraits.h.

◆ inner_split_value()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

Scalar Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::inner_split_value ( ) const

inline

The position of the AABB split of the inner node.

Definition at line 191 of file kdTreeTraits.h.

◆ is_leaf()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

bool Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::is_leaf ( ) const

inline

Definition at line 134 of file kdTreeTraits.h.

◆ leaf_size()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

LeafSize Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::leaf_size ( ) const

inline

The size of the range of the leaf node in the sample index array.

Definition at line 186 of file kdTreeTraits.h.

◆ leaf_start()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

Index Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::leaf_start ( ) const

inline

The start index of the range of the leaf node in the sample index array.

Definition at line 181 of file kdTreeTraits.h.

◆ set_is_leaf()

template<typename Index , typename NodeIndex , typename DataPoint , typename LeafSize = Index, typename _InnerNodeType = KdTreeDefaultInnerNode<NodeIndex, typename DataPoint::Scalar, DataPoint::Dim>, typename _LeafNodeType = KdTreeDefaultLeafNode<Index, LeafSize>>

void Ponca::KdTreeCustomizableNode< Index, NodeIndex, DataPoint, LeafSize, _InnerNodeType, _LeafNodeType >::set_is_leaf ( bool is_leaf )

inline

Definition at line 135 of file kdTreeTraits.h.

Public Types

Public Member Functions

Protected Member Functions

Detailed Description

Member Typedef Documentation

◆ AabbType

Member Enumeration Documentation

◆ anonymous enum

Member Function Documentation

◆ configure_inner()

◆ configure_range()

◆ getAsInner() [1/2]

◆ getAsInner() [2/2]

◆ getAsLeaf() [1/2]

◆ getAsLeaf() [2/2]

◆ inner_first_child_id()

◆ inner_split_dim()

◆ inner_split_value()

◆ is_leaf()

◆ leaf_size()

◆ leaf_start()

◆ set_is_leaf()