Sampling and Resampling

When a billion points will not fit in memory or in a downstream algorithm's time budget, what should you keep, and what can you afford to throw away? That is the question this chapter answers, and the answer is that the choice is governed by what each method preserves rather than by how many points it removes. Two clouds reduced to the same final count can carry entirely different information, because one sampler keeps the density distribution, another keeps spatial coverage, another keeps orientation diversity, and another keeps the sharp features. The methods in this chapter are not interchangeable: each one preserves a different property of the cloud, and the choice determines which features survive into later processing and which are discarded.

The scale of the problem is concrete. A single TLS station inside a stone-vaulted nave returns between 50 and 80 million points, and a multi-station campaign that covers the whole church passes a billion before any post-processing. The density is also radically uneven, far higher on a column three metres from the scanner than on the apse vault thirty metres away, because terrestrial scan density falls off with the square of the range. An ALS tile, by contrast, arrives at roughly 10 points per square metre and asks for almost no thinning, which tells us that any general statement about downsampling is meaningless without naming the sensor and the scene.

Sampling is the first transformation the pipeline applies. It consumes the raw clouds delivered by the acquisition systems of Chapter 3 and leans on the spatial indexes of Chapter 4 for the radius and nearest-neighbour queries that every method below issues. Its output sets the terms for everything that follows: the filters of Chapter 6 and the normal estimation of Chapter 7 operate on the thinned cloud, normal-space sampling conditions the ICP registration of Chapter 8, and farthest point sampling is the downsampling backbone of the deep networks of Chapter 18. The chapter moves from the simplest strategy to the most scene-aware (random, voxel grid, farthest point, Poisson disk, normal-space, octree-adaptive, and edge-aware sampling) before closing with the converse problem of upsampling a cloud that is too sparse.

Motivation for sampling

Raw point clouds straight from the scanner exhibit three properties that make direct processing problematic.

1. Excessive volume. A single ALS survey can contain billions of points. Many algorithms (normal estimation, surface reconstruction, ICP registration) require neighbourhood queries at every point. Even with an $O(\log n)$ spatial index, the total cost scales with $n$. Reducing $n$ by a factor of 10 speeds up processing by roughly the same factor.
2. Non-uniform density. Scan geometry creates systematic density variations. ALS data are denser at nadir than at the swath edges, TLS density falls off as $1/r^2$ with range, and MLS density is highest close to the vehicle. These variations bias algorithms that assume locally uniform density, for example density-based clustering and adaptive-radius normal estimation.
3. Redundant oversampling. In high-density scans, neighbouring points carry nearly identical geometric information. Retaining all of them wastes storage and computation time without improving accuracy.