Point clouds
A point cloud is simply a set of points in space, with no connectivity, orientation, or inside/outside notion. Unlike a surface mesh, there is therefore no signed distance to a point cloud – only unsigned distances between points. The operations of interest are proximity queries:
Closest point. Given an arbitrary query point, find the cloud point nearest to it.
k nearest. Find the \(k\) closest cloud points to a query, in ascending order of distance.
k-nearest-neighbor graph. For every point in the cloud, find its \(k\) nearest other points – the classic all-nearest-neighbors problem.
Answering one query by scanning all \(N\) points is \(\mathcal{O}(N)\), so the all-nearest-neighbors graph is \(\mathcal{O}(N^2)\) – infeasible for large clouds. As with mesh distance queries, the cost is reduced by a spatial acceleration structure that lets a query rule out the vast majority of points without ever measuring the distance to them. EBGeometry offers two such structures, built on two different ideas.
Hierarchical partitioning
The first idea is to build a tree over the points, recursively subdividing them into spatially tight groups – exactly the bounding volume hierarchy described in Bounding volume hierarchies, with the points (or small groups of them) as the primitives. A query then descends the tree, at each node visiting the nearer child first and pruning any subtree whose bounding volume is already farther than the best match found so far. Because the subdivision follows the points themselves, the tree adapts to the cloud’s density – it stays balanced whether the points are uniform, lie on a surface, or clump into clusters – and a query touches only \(\mathcal{O}(\log N)\) nodes on average.
Uniform grid
The second idea dispenses with the tree entirely and lays a single regular grid of fixed-size cells over the cloud, bucketing each point into the cell that contains it. A query starts in the cell containing the query point and searches outward one shell of cells at a time (Chebyshev radius 0, 1, 2, …). It can stop as soon as the best distance found so far is closer than the nearest edge of the next unvisited shell – no closer point can lie beyond that shell, so the search terminates exactly, never missing a neighbor. If the cells are sized to hold about one point each, a query resolves in the first shell or two.
The grid trades adaptivity for simplicity. A single global cell size fits a near-uniform cloud best – there, both building the grid (a counting sort) and querying it are cheaper than a tree. For a strongly clustered or multi-scale cloud a single cell size is a poor compromise (too coarse where the cloud is dense, too fine where it is sparse), and the density-adaptive hierarchy is the better choice.
Self queries
The all-nearest-neighbors graph is a special case worth calling out: every query point is itself a member of the cloud. A point therefore already knows which cell or leaf it lives in, so its search can be seeded from that group – giving a tight pruning bound immediately – and must exclude the point itself (otherwise it would trivially find itself at distance zero). This makes a batch of self queries strictly cheaper than the same number of independent external queries.