Detecting a Sparse or Noisy Region in a Point Cloud Before Processing

A reconstruction comes back with a smooth billowing surface where a wall should be, or a blob bridging two objects that are metres apart. Nothing errored. The cause is almost always a region of the input cloud that was too sparse for the algorithm’s own resolution, and it is detectable in seconds before the expensive stage runs.

The symptom

The characteristic failures all look like the algorithm inventing geometry, because that is what it did.

• A membrane across an opening. Poisson reconstruction always returns a watertight surface, so where there were no points it extrapolates smoothly and confidently. A doorway gets skinned over.
• Blobs and webbing connecting objects that are not connected, where the sampling was too sparse for the solver to tell two surfaces apart.
• Normals pointing in random directions across one region, which then propagates into a surface that folds through itself.
• A registration that reports a small residual and is visibly wrong, because the overlap region was sparse and contributed few correspondences.
• Segmentation producing thousands of tiny components in one part of the scene and sensible objects everywhere else.

What these share is that the failure is regional and the diagnostics are global. A mean point spacing over the whole cloud looks fine because 95% of the cloud is fine.

Tracing it back

Work backwards through the pipeline and the cause is nearly always in the capture, not the algorithm.

1. Locate the invented geometry in the mesh and note its bounding box.
2. Crop the input cloud to that box and count the points. If there are very few, the reconstruction did the only thing it could.
3. Ask why the region is sparse. Grazing incidence, so the spacing was stretched by the cosine factor derived on the density page. Range, since spacing grows linearly with it. Occlusion, so nothing was measured at all. A dark, wet or specular surface that returned no signal. Or, for photogrammetry, a textureless wall that produced no matches.
4. Check whether the density was ever adequate. If the original scan had the points and something downstream removed them — a voxel downsample, an aggressive outlier filter, a crop — the fix is in the pipeline. If the scan never had them, the fix is another setup.

The distinction in that last step is the whole value of the investigation. An outlier filter with std_ratio set too tight removes genuine points in sparse regions preferentially, because “far from its neighbours” is exactly what a legitimate point in a sparse region looks like. That is a self-inflicted version of this failure and it is common.

The one metric that matters

Point density has several definitions and only one is convenient and robust: the distance from each point to its nearest neighbour. It needs no radius parameter, adapts automatically to whatever the local scale is, and is a single k-d tree query per point.

Read it as a distribution, never as a mean. The median tells you the typical spacing; the 95th percentile tells you how bad the sparse tail is; and the fraction above a threshold tells you how much of the cloud is at risk. A mean conflates all three and is dragged around by outliers.

Two related quantities are worth computing in the same pass. Local surface variation — the smallest eigenvalue of the neighbourhood covariance divided by the sum of all three — is near zero on a clean plane and rises with noise, curvature or two surfaces mixing, which makes it the natural noise measure. And the residual of a local plane fit gives noise directly in metres, which is the number to compare against the scanner’s specification.

Deriving the threshold rather than picking it

A threshold chosen by feel is a threshold that will be wrong on the next project. Derive it from the algorithm you are about to run.

Poisson reconstruction solves on an octree of depth d over the bounding box, so its finest cell is the extent divided by 2^d. A cell containing no points contributes no constraint, and the solver interpolates through it. So the requirement is that the local point spacing be smaller than the leaf size:

bounding box extent 20 m, octree depth 10
  leaf size = 20 / 2^10 = 20 / 1024 = 19.5 mm

  -> any region whose nearest-neighbour spacing
     exceeds 19.5 mm has cells the solver must guess

same box at depth 11
  leaf size = 20 / 2048 = 9.8 mm
  -> finer output, and twice as much of the cloud
     now counts as too sparse

same box at depth 8
  leaf size = 20 / 256 = 78 mm
  -> coarser output, but almost nothing is invented

for a ball-pivoting reconstruction with radius r,
the requirement is stricter: spacing must be below
r or the sphere falls through and leaves a hole,
while a radius large enough to cover the sparse
region will bridge genuine gaps elsewhere.

That gives a defensible gate: reject, or flag for review, any tile where more than a stated fraction of points have a nearest-neighbour distance above the leaf size. The fraction is a policy decision; the distance is not, and having one derived number instead of two guessed ones is most of the benefit.

The gate

This runs before the expensive stage and reports where the problem is, not merely that there is one. Reporting the location is the part that makes it actionable.

import numpy as np
import open3d as o3d

POISSON_DEPTH = 10
MAX_SPARSE_FRACTION = 0.02
CELL = 1.0                     # metres, for the report grid

pcd = o3d.io.read_point_cloud("scan.ply")
pts = np.asarray(pcd.points)
print("points:", len(pts))

# 1. nearest-neighbour spacing, one k-d tree query per point
nn = np.asarray(pcd.compute_nearest_neighbor_distance())
print("median spacing: %.4f m" % np.median(nn))
print("p95 spacing:    %.4f m" % np.percentile(nn, 95))
print("max spacing:    %.4f m" % nn.max())

# 2. the threshold, derived from the reconstruction itself
extent = float(np.max(pts.max(axis=0) - pts.min(axis=0)))
leaf = extent / (2 ** POISSON_DEPTH)
print("extent: %.2f m, poisson leaf: %.4f m" % (extent, leaf))

sparse = nn > leaf
frac = float(sparse.mean())
print("fraction above leaf size: %.4f" % frac)

# 3. WHERE. bin into cells and report the worst ones.
cells = np.floor(pts / CELL).astype(np.int64)
keys, inv = np.unique(cells, axis=0, return_inverse=True)
worst = []
for i in range(len(keys)):
    m = inv == i
    n = int(m.sum())
    if n < 50:                 # ignore near-empty cells
        continue
    worst.append((float(np.median(nn[m])), n, keys[i] * CELL))
worst.sort(reverse=True)

print("worst 10 cells (median spacing, count, corner):")
for s, n, c in worst[:10]:
    print("  %.4f m  %7d pts  at %s" % (s, n, c))

if frac > MAX_SPARSE_FRACTION:
    raise SystemExit(
        "gate failed: %.2f %% of points are sparser than the "
        "poisson leaf size. reconstruct at a lower depth, or "
        "rescan the cells listed above." % (frac * 100))
print("gate passed")

The cell report is what turns this from a pass/fail into a work instruction. A surveyor can be sent back to a coordinate; they cannot be sent back to a percentage.

The other defects worth gating on

• Mixed pixels. When a beam straddles the edge of an object, part of the energy returns from the foreground and part from the background, and the reported range is a blend — placing a point in empty space between the two. Every object edge in a LiDAR scan has a thin veil of these. They are not statistical outliers, because they form a coherent structure, and the reliable removal is by return geometry and incidence angle rather than by neighbour distance.
• Registration doubling. A slightly wrong alignment leaves two copies of every surface a few centimetres apart. The tell is the distribution of the residual to a locally fitted plane: on a clean surface it is a single narrow peak at zero, and on a doubled one it is bimodal with peaks at plus and minus half the offset. Testing for bimodality here catches an alignment error that the registration’s own residual reported as acceptable — see why that residual can lie.
• Reflective ghosts. A mirror or a wet floor produces a plausible-looking copy of the room behind the surface. Locally the geometry is perfect, so no density or noise metric finds it. The practical check is a bounding-box test against the known extent of the site: points outside the building are suspicious regardless of how clean they look.
• Moving objects. A person walking through a scan leaves a smear rather than a body. In a multi-scan setup the reliable detector is disagreement between setups: a surface present in one scan and absent in another that had line of sight to it was not there the whole time.
• Excess density where it does not help. The mirror image of the sparse problem. A region sampled far below the beam footprint costs storage and processing without resolving anything — the density page derives that limit. Gating on both ends of the distribution is cheaper than gating on one.

Run all of this before the expensive stage rather than after. A gate costs one k-d tree pass; a reconstruction, a review and a rescan cost orders of magnitude more, and the arithmetic behind that claim is on the processing cost page.