P5-T1 — 3D Point-Cloud Representations

Learning objectives

After this lesson, you should be able to:

• Describe raw points, range images, voxel grids, height maps and meshes and what each makes easy.
• Compute the voxel index of a point, the effect of voxel downsampling and its quantisation error.
• Explain how a k-d tree speeds up neighbour search and when a range image avoids the need for one.
• Estimate the memory and data rate of a LiDAR and of a dense grid, and choose a representation for a task.

The idea: structure turns a pile of points into answers

Handed a bag of one hundred thousand 3D points, questions like “what is near this point?”, “is the space ahead free?” or “where is the ground?” all require a search through the whole bag. Organising the points avoids that. The right organisation depends on the question.

Choose the representation for the question, and keep the raw points while you can: every other form is derived from them and cannot be turned back.

How this relates to the Sensors labs

The Sensors track already has three labs on point clouds: understanding and visualising a point cloud, cleaning, filtering, transforming and downsampling it and detecting obstacles and deciding to stop. This module does not repeat them. It adds local geometry (normals, planarity), robust ground estimation on slopes and range-aware clustering with oriented boxes, and the reasons behind each.

The mathematics: voxels, neighbours and size

Voxel index and downsampling

A voxel grid of side s assigns a point p = (x, y, z) to the cell

Downsampling replaces all points in a cell by one, usually their centroid. The representative is then at most about s√3/2 ≈ 0.87 s from any original point (the half-diagonal of the cell), and for points spread uniformly in the cell the root-mean-square position error per axis is

s

the voxel side length in metres: the resolution of the representation.

⌊·⌋

the floor function: round down to an integer.

(i, j, k)

the integer cell coordinates; stored in a hash table so that only occupied cells use memory.

σ_quantisation

the error introduced by replacing points with a cell representative, small when s is smaller than the sensor noise.

Neighbour search

The k nearest neighbours or all points within radius r of a query are needed for normals, clustering and filtering. Brute force costs O(N) per query, so O(N²) for all points. A k-d tree recursively splits the points by the median along one axis, so a query visits about O(log N) nodes; building it costs O(N log N). A voxel hash gives constant-time lookup of the 27 cells around a point when the radius is about one voxel. An organised cloud (range image) needs no structure: the neighbours of pixel (u, v) are the pixels around it, though a neighbouring pixel can be far in 3D across a depth edge.

Data rate and memory

A sensor with R rings and A azimuth steps at f sweeps per second produces

A dense 3D grid over a volume X × Y × Z with side s has X·Y·Z/s³ cells: halving the voxel size multiplies the memory by eight. Real maps are sparse (most space is empty), which is why hash tables, octrees and sparse voxel structures are used.

A worked example: how much data, and how much does downsampling lose?

A LiDAR has 64 rings and 1024 azimuth steps per revolution at 10 Hz.

655,360 points per second is more than a robot’s planner or a low-power processor can handle if every point is used, so the cloud is almost always downsampled first. A voxel filter of side 0.2 m keeps far fewer points; how many fewer depends strongly on the scene, because nearby surfaces are dense and many of their points fall into the same voxel, while distant surfaces are sparse and each point tends to fall into its own voxel.

Quantisation

With voxels of 0.2 m, the error introduced by taking the cell centre is 0.2 / √12 = 5.8 cm per axis. With voxels of 0.02 m it is 0.58 cm. The sensor’s own range noise (about 2 to 3 cm) is the natural scale: a voxel much finer than the noise stores noise, and one much coarser throws away measured detail. If the centroid of the points in the cell is used instead of the centre, the error is smaller for cells that hold many points.

Dense grid memory

A grid covering 100 m × 100 m × 10 m at 0.2 m has 12,500,000 cells; at 0.1 m it has 100,000,000 cells (eight times more). At one byte per cell the 0.1 m grid takes 100 MB, and at one bit per cell about 13 MB. A typical outdoor scan fills only a small fraction of those cells, so a sparse structure that stores only the occupied ones is the practical choice.

Choosing for the task

Engineering implications and limitations

Keep timestamps and ring indices. A raw LiDAR point carries its acquisition time and ring. The time lets you correct the distortion caused by the robot moving during the sweep (motion compensation); the ring and azimuth let you rebuild the range image. Dropping them early forecloses both.

Downsample once, early, with a stated resolution. Choose a voxel size from the noise and the smallest object that matters, document it, and keep the raw data in the log. Each stage that downsamples again compounds the loss.

Use sparse structures. Hash tables, octrees and k-d trees keep memory and time proportional to what is occupied. Dense 3D arrays are fine for small local grids and fatal for maps.

Represent unknown space. Points record where something was hit; they say nothing about free or unknown space (Lesson P1-T5). If a decision depends on free space, build an occupancy structure that traces rays and has an unknown state.

Mind the frame. Every representation is defined in a frame: sensor, base or world. Merging clouds from several sensors or times needs the transforms of Lesson P1-T4 and accurate timestamps (Module 8).

Measure before optimising. Profile the pipeline: often the neighbour search, not the geometry, takes the time, and a coarser voxel or a range-image shortcut removes the bottleneck.

Common misconceptions

Engineering takeaways

1. Raw points are complete and unordered; range images, voxel grids, height maps and meshes add structure at the cost of detail or coverage.
2. Voxel index = ⌊p/s⌋; quantisation error is about s/√12 per axis; a sensible s is near the sensor noise.
3. k-d trees reduce neighbour search from O(N) to about O(log N) per query; an organised cloud gets neighbours from the image grid.
4. A 64 × 1024 LiDAR at 10 Hz gives about 655 000 points per second (about 10 MB/s); a dense grid costs X·Y·Z/s³ cells.
5. Choose the representation for the question, keep timestamps and raw data, and represent unknown space explicitly.

References and further reading

Standard references; the data-rate and memory numbers were computed for this lesson.

• Rusu, R. B. and Cousins, S. (2011). 3D is here: Point Cloud Library (PCL). ICRA: point-cloud data structures, filters and k-d trees.
• Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM 18(9): the k-d tree.
• Hornung, A., Wurm, K. M., Bennewitz, M., Stachniss, C. and Burgard, W. (2013). OctoMap: an efficient probabilistic 3D mapping framework based on octrees. Autonomous Robots 34(3).
• Thrun, S., Burgard, W. and Fox, D. (2005). Probabilistic Robotics. MIT Press: occupancy grids and range-sensor models.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: what can be read from a point’s neighbourhood: normals, curvature and how plane, line and scatter differ.

Related content

Nothing below is required to finish this lesson.

• Before
  P4-T6: Repetitive and Textureless Scenes

  Predict and diagnose matching failures from repetition, blur and lack of texture.