Spatial Partitioning: User Manual

Table of Contents

• Introduction
  • Datastructures
  • Queries
• KdTree
  • Specifications
  • Basic usage
    • Construction
    • Queries
    • Samples and indexing
  • Usage in Cuda kernels
  • Customizing the KdTree using <tt>Traits</tt>
  • Usage of the convenience classes KdTree and KdTreeBase
• KnnGraph
  • Basic usage
    • Construction
    • Queries

[Go back to user manual]

Introduction

This module provides spatial datastructures to speed up spatial queries (e.g., neighbors search).

Datastructures

• Ponca::KdTreeDense and Ponca::KdTreeSparse: binary search trees (https://en.wikipedia.org/wiki/K-d_tree). Both classes inherit from Ponca::KdTree. KdTrees can be also used in cuda kernels.
• Ponca::KnnGraph : a nearest neighbor graph (https://en.wikipedia.org/wiki/nearestNeighbor_graph). Constructed from a Ponca::KdTree.

All datastructures are available in arbitrary dimensions.

Queries

Ponca queries are defined according to their input type (QueryInputIsIndex, or QueryInputIsPosition) and their output type (closest point with QueryOutputIsNearest, k-neighborhood with QueryOutputIsKNearest, and range neighborhood with QueryOutputIsRange):

QueryType	Closest Point	k-neighborhood	Range neighborhood
Index	NearestIndexQuery	KNearestIndexQuery	RangeIndexQuery
Coordinate	NearestPointQuery	KNearestPointQuery	RangePointQuery

These classes provide a consistent API for all datastructures, where the results are exposed as Range and thus accessed through iterators, ie.:

#pragma omp parallel for
for (int i = 0; i < nbVert; ++i) // for all the vertices of the point cloud
  for (int neiId : myDataStructure.kNearestNeighbors(i, k)) // collect k-nearest neighbors
  {
    // process neighbor at index neiId
  }

Note

As queries are objets that are independent from the datastructure, they can be created and used in parallel from multiple threads. The queries are always constructed by the datastructure.

Thanks to the iterator formalism, queries can be seamlessly combined with Basket::computeWithIds:

Fit fit;
fit.setNeighborFilter({fitInitPos, scale});
fit.computeWithIds( myDataStructure.rangeNeighbors(fitInitPos, scale), vectorPoints );

Warning

Queries from an index (NearestIndexQuery, KNearestIndexQuery and RangeIndexQuery) do not iterate on the queried index.

KdTree

Specifications

In Ponca, the kd-tree is a binary search tree that

• is balanced (cuts at the median at each node),
• cuts along the dimension that extends the most at each node,
• has a maximal depth (KdTreeBase::MAX_DEPTH),
• has a minimal number of points per leaf (KdTreeBase::m_min_cell_size),
• only stores points in the leafs,
• uses depth-first search with a static stack for queries,
• keeps the initial order of points.

Basic usage

The class Ponca::KdTreeDense provides methods to construct a tree and query points neighborhoods. The class Ponca::KdTreeSparse provides the same functionalities as its dense counterpart, but allows construction from a subset of points. They both share the same API with their abstract base class KdTree.

Construction

As for the other modules, the point type is defined by a template parameter DataPoint. At construction time, the coordinates are copied in the tree from a container provided by the caller. For instance, to generate a tree from a random point cloud:

    std::vector<DataPoint> points(N);
    std::generate(points.begin(), points.end(), [](){
        return DataPoint{100 * DataPoint::VectorType::Random()};
    });
    // build the k-d tree
    Ponca::KdTreeDense<DataPoint> kdtreeDense(points);

For convenience, it is possible to convert the custom input points to DataPoint using a converter.

When using a Ponca::KdTreeSparse, it is possible to provide a set of indices to sample a subset of the input point during the construction. Here, to randomly select half of the points:

    std::vector<int> indices(N);
    std::vector<int> sampling(N / 2);
    std::iota(indices.begin(), indices.end(), 0);
    std::sample(indices.begin(), indices.end(), sampling.begin(), N / 2, std::mt19937(seed));
    Ponca::KdTreeSparse<DataPoint> kdtreeSparse(points, sampling);

Queries

As for other datastructures, queries are objects generated by the KdTree, and are designed as Range: accessing the neighbors requires to iterate over the query. Here an example of the k nearest neighbors search of the point of index query_idx using the kd tree

    std::cout << "The " << k << "-nearest neighbors of the point at index " << query_idx << " are at indices: ";
    for(int neighbor_idx : kdtreeDense.kNearestNeighbors(query_idx, k)) { // Iterates over the neighbors of query_idx
        std::cout << neighbor_idx << ", ";
    }

Queries are mutable and can be reused. Here is an example of a query being reused with a different evaluation point index, second_query_idx.

    constexpr DataPoint::Scalar radius = 5.25;
    auto rangeNeighbors = kdtreeDense.rangeNeighbors(query_idx, radius); // First query
 
    std::cout << "The neighbors of the point at index " << second_query_idx << " at a distance " << radius << " are at indices: ";
    for(int neighbor_idx : rangeNeighbors(second_query_idx, radius)) { // Iterate over a new rangeNeighbors query
        std::cout << neighbor_idx << ", ";
    }

It is also possible to call for an empty query, and then perform the query call on it.

    auto posRangeNeighbors = kdtreeDense.rangeNeighborsQuery(); // Empty query
 
    std::cout << "The neighbors of the point (" << query_pt.transpose() << ") at a distance " << radius << " are at indices: ";
    for(auto neighbor_idx : posRangeNeighbors(query_pt, radius)) {
        std::cout << neighbor_idx << ", ";
    }

The previous query is restricted to position based range query. To perform an index based research, a new query needs to be created. This is due to the fact that query returns object of it's own type, e.g., PointQuery or IndexQuery.

Several query types are provided (see KdTreeBase for related method list):

• KdTreeKNearestQueryBase, specialized by KdTreeKNearestIndexQuery and KdTreeKNearestPointQuery
• KdTreeNearestQueryBase, specialized by KdTreeNearestIndexQuery and KdTreeNearestPointQuery
• KdTreeRangeQueryBase, specialized by KdTreeRangeIndexQuery and KdTreeRangePointQuery

Several KdTree queries are illustrated in the example Ponca::KdTree neighbor searches. KdTree usage is also demonstrated both in tests and examples:

• tests/src/basket.cpp
• tests/src/queries_knearest.cpp
• tests/src/queries_nearest.cpp
• tests/src/queries_range.cpp
• examples/cpp/nanoflann/ponca_nanoflann.cpp

Samples and indexing

There are two main ways of iterating over a KdTree: over points or over samples. Points are the underlying data storage, which the KdTree does not modify, while samples are a set of indices into the point storage that the KdTree reorders internally when it is constructed to keep track of spatial partitions.

We call indices into the underlying point storage point indices and indices into the sample storage sample indices. Note that the sample storage stores point indices: sample number 0 may, for example, refer to point number 25. The point storage can be accessed with KdTreeBase::points, while the array of samples can be accessed with KdTreeBase::samples.

While most of the KdTree API is built on using point indices, it can still be useful to iterate over samples instead (e.g. when using a Ponca::KdTreeSparse). If you ever need to convert sample indices to point indices, see KdTreeBase::pointFromSample (see also KdTreeBase::pointDataFromSample).

Usage in Cuda kernels

Ponca allows to build a KdTree on the CPU, bind its buffers to the GPU, and build objects of that bind the KdTree API in top of the mapped buffers.

This is illustrated in the example examples/cuda/ponca_fit_kdtree.cu:

• [host] Generate KdTree on the CPU:

      Ponca::KdTreeDense<DataPoint> kdtree(points);

• [host] Copy the KdTree buffers to the GPU:

      using BuffersGPU = typename KdTreeGPU<DataPoint>::Buffers;
      BuffersGPU* kdtreeBuffersDevice;
      CUDA_CHECK(cudaMalloc(&kdtreeBuffersDevice, sizeof(BuffersGPU)));
      BuffersGPU hostBuffersHoldingDevicePointers; // Host Buffers referencing data on the device, used to free memory
      deepCopyBuffersToDevice<Ponca::KdTreePointerTraits<DataPoint>>(kdtree.buffers(), hostBuffersHoldingDevicePointers, kdtreeBuffersDevice);

• [device] In the kernel, create and query the KdTree:

      KdTreeGPU<DataPoint> kdtree(*buffers);

      fit.computeWithIds(kdtree.rangeNeighbors(i, analysisScale), kdtree.points());

• [host] Free GPU memory.

The type KdTreeGPU is defined as

/*! \brief A KdTree Type that can be run on the GPU
 *
 * \warning The KdTreeBase::build function cannot be used in the CUDA kernel,
 * because it still expects an STL-like container as an input.
 * This KdTree type is used to avoid the building process.
 */
template <typename DataPoint>
using KdTreeGPU = Ponca::StaticKdTreeBase<Ponca::KdTreePointerTraits<DataPoint>>;

Internally, the class StaticKdTreeBase is the base class of KdTreeBase, and provide all the querying API without the building functionalities (except from an already existing set of StaticKdTreeBase::Buffers). In order to be able to handle raw pointers in the Cuda kernels, the KdTreeGPU uses KdTreePointerTraits, which defines all the internal containers as raw pointers. In the above example, these pointers are generated by copying the content of a std::vector using CudaMalloc and CudaMemcpy (see method deepCopyBuffersToDevice in examples/cuda/cuda_utils.cu).

Customizing the KdTree using <tt>Traits</tt>

The trees can be customized using Traits, to change containers and nodes types. KdTreeDefaultTraits provides general-purpose Traits that fit most usages, and is directly used by Ponca::KdTree, Ponca::KdTreeDense and Ponca::KdTreeSparse:

template <typename DataPoint>
struct KdTree : public Ponca::KdTreeBase<KdTreeDefaultTraits<DataPoint>>{};

template <typename DataPoint>
struct KdTreeDense : public Ponca::KdTreeDenseBase<KdTreeDefaultTraits<DataPoint>>{};

template <typename DataPoint>
struct KdTreeSparse : Ponca::KdTreeSparseBase<KdTreeDefaultTraits<DataPoint>>{};

To use your own type of Traits, see KdTreeDefaultTraits and KdTreeCustomizableNode APIs. See also:

• examples/cpp/ponca_customize_kdtree.cpp

Usage of the convenience classes KdTree and KdTreeBase

KdTree provides the common interface of KdTreeDense and KdTreeSparse. This class can be used to store or pass references/pointers that can be of either child type, see for instance:

    // Abstract pointer type that can receive KdTreeSparse or KdTreeDense objects
    Ponca::KdTree<DataPoint> *kdtree {nullptr};

    // Assign sparse
    kdtree = &kdtreeSparse; // Or kdtree = new Ponca::KdTreeSparse<DataPoint> (points, sampling);

    // Assign dense
    kdtree = &kdtreeDense; // Or kdtree = new Ponca::KdTreeDense<DataPoint> (points, sampling);

KdTreeBase and its base class StaticKdTreeBase provide abstractions for arbitrary types of traits (constructible or read-only, respectively). When the type of Traits is arbitrary (but known at compile time), it is recommended to use one of these classes to declare functions parameters or variables. In the class KdTreeQuery<Traits> for instance, the link to the KdTree is stored as follows:

    const StaticKdTreeBase<Traits>* m_kdtree { nullptr };

Here, the variable m_kdtree can be either dense or sparse, and have any type of Traits.

KnnGraph

Basic usage

The class Ponca::KnnGraph provides methods to construct a neighbor graph and query points neighborhoods.

Construction

The graph is constructed from an existing KdTree, and the point collection is accessed through it (with no copy). Here an example from the test-suite where a graph is constructed, where only closest neighbors are connected:

    Ponca::KnnGraph<DataPoint> knnGraph(kdtreeDense, k);

Warning

At the moment, a KnnGraph can only be constructed from a Ponca::KdTreeDense. This will change in a future release.

Queries

As for other datastructures, queries are objects generated by KdTrees, and are designed as Range: accessing the neighbors requires to iterate over the query.

    std::cout << "The nearest neighbors of the point at index " << query_idx << " are at indices: ";
    for(int neighbor_idx : knnGraph.kNearestNeighbors(query_idx)) {
        std::cout << neighbor_idx << ", ";
    }

Note

By construction, the KnnGraph can be queried only from an index.

Queries from KnnGraph are also mutable, and can be reused. Here is an example that creates an empty query, and then iterates over the rangeNeighbors index search.

    auto knnRangeNeighbors = knnGraph.rangeNeighborsIndexQuery(); // Empty query
 
    std::cout << "The neighbors of the point (" << query_pt.transpose() << ") at a distance " << radius << " are at indices: ";
    for(auto neighbor_idx : knnRangeNeighbors(query_idx, radius)) { // Iterates over the neighbors of query_idx
        std::cout << neighbor_idx << ", ";
    }

Two types of queries are provided (see KnnGraphBase for related method list):

• KnnGraphRangeQuery
• KnnGraphKNearestQuery: the number of neighbors is defined at construction-time: a k-neighbor graph gives access to k-neighborhoods only.

  Note

  The query KnnGraphNearestQuery does not need to exist explicitly as it boils down to KnnGraphKNearestQuery with k=1.

  [Go back to user manual]