Skip to the lesson
FixTheRobot Explore Robotics / Localization & SLAM / M5 LiDAR SLAM / M5-T11

Localization & SLAM · Theory · M5

M5-T11 — Dense Map Representations

A trajectory and a cloud of landmarks tell a robot where it is. They do not tell it what is solid, what is empty and what it has never seen.

  • Lesson 11 of 11
  • Module 5: LiDAR SLAM
  • Theory · mapping
  • About 14 minutes to read

The maps of the last lessons serve localization: features, scans attached to keyframes, a voxel-filtered cloud. A planner, a manipulator or an inspector needs more. It needs surfaces, free space and the boundary of the unknown, in three dimensions and at a resolution of centimetres. This lesson covers the four families of dense map in use: occupancy octrees, signed distance fields, surfels and meshes. For each it gives the update rule, the memory it costs and the question that decides most designs: what happens to the map when the back end corrects the poses it was built from.

Learning objectives

After this lesson, you should be able to:

  • State what an occupancy octree, a truncated signed distance field and a surfel map store per element, and write the update rule of the first two.
  • Estimate the memory of a dense 3D grid and explain how octrees and voxel hashing avoid it.
  • Fuse several range measurements into a TSDF and locate the surface from the zero crossing.
  • Choose a representation for a task: collision checking, planning, reconstruction or localization.
  • Explain why a loop closure is harder for a dense map than for a pose graph, and name three ways systems handle it.

The problem and the intuition

The 2D occupancy grid of M3-T1 answers three questions for every cell: occupied, free, or never observed. Take it to three dimensions at 5 cm and a building of 100 m by 100 m by 10 m needs 2000 × 2000 × 200 = 800 million cells: 3.2 GB at four bytes each, nearly all of it air or the inside of walls. Dense mapping is the set of ideas for storing only what matters, which is the thin shell around surfaces and the free space a robot may move through.

There are two ways to describe a surface. You can label space: this voxel is solid, that one is empty. Or you can store, at every point near the surface, how far away the surface is and on which side. The second description, a signed distance, has a useful property: averaging many noisy measurements of it gives a smooth, sub-voxel estimate of where the surface is, the way averaging readings of a ruler gives a better length. A third way gives up the grid altogether and stores small oriented discs lying on the surface.

Sparse maps are for knowing where you are. Dense maps are for knowing what you would hit, where you can go and what the world looks like.

A truncated signed distance function along one sensor rayFive voxels along a ray between 1.90 and 2.10 metres from the sensor. Each stores a value between plus one in front of the surface and minus one behind it. The values fall from 0.93 to minus 0.75, and the straight line between the third and fourth voxel crosses zero at 2.01 metres, which is the estimated surface. The true wall is at 2.00 metres. +10−1 1.90 m1.95 m2.00 m2.05 m2.10 m wall 2.00 zero crossing 2.01 free side: positivebehind the surface: negative distance from the sensor along the ray; one stored value per voxel
A signed distance stored in five voxels along one ray. The surface is where the interpolated value crosses zero: between voxels, not at one.

Four representations and their update rules

Occupancy in 3D: the octree

An octree divides a cube into eight children, and each child again, only where the content differs. A large empty or unknown region is one node; detail is spent near surfaces. OctoMap (Hornung et al., 2013) stores in each leaf the log-odds of occupancy and updates it exactly as the 2D grid does, once per measurement that ends in the voxel (hit) or passes through it (miss):

log-odds update with clamping
L(n)←clamp⁡(L(n)+lhit or lmiss, lmin⁡, lmax⁡)L(n)\leftarrow \operatorname{clamp}(L(n)+l_{\text{hit}}\,\text{or}\,l_{\text{miss}},\,l_{\min},\,l_{\max})
l=ln⁡(p1−p)l=\ln (\frac{p}{1-p})

The clamp bounds the confidence. Without it, a wall seen a thousand times would need a thousand contrary observations before the map accepted that a door had opened. With it, a bounded number of observations flips the state, and eight children that have all reached the same clamped value are pruned into their parent, which is where the compression comes from. Unknown space is simply the absence of a node, so the map distinguishes free from unobserved, which exploration and safe planning both need.

Signed distance: the TSDF

A truncated signed distance field (Curless and Levoy, 1996) stores in each voxel a distance D to the nearest surface, positive in front of it and negative behind, cut off at a truncation distance τ, and a weight W. For a measurement of range r along a ray, a voxel at distance dv from the sensor along that ray receives:

TSDF integration: a weighted running average
sdf=r−dv\mathrm{sdf}=r-d_{v}
d=clamp⁡(sdfτ, −1, 1)d=\operatorname{clamp}(\frac{\mathrm{sdf}}{\tau },\,-1,\,1)
(skip the voxel if sdf < −τ)
D←W D+w dW+wD\leftarrow \frac{W\,D+w\,d}{W+w}
W←min⁡(W+w, Wmax⁡)W\leftarrow \min (W+w,\,W_{\max})

Voxels far in front of the surface receive +1 (known free space); voxels more than τ behind it are not touched, because the sensor cannot see there. The surface is the set of points where D = 0, found by interpolating between neighbouring voxels: a mesh is extracted with marching cubes, or an image is rendered by marching rays until the sign changes. KinectFusion (Newcombe et al., 2011) did both in real time on a GPU and tracked the camera by aligning each new depth image to the rendered surface, the dense form of scan-to-map registration (M5-T4).

  • Truncation τ is a few voxels and at least a few standard deviations of the range noise. Too small and noisy measurements fall outside the band; too large and thin objects are merged with what lies behind them.
  • Weight cap Wmax plays the role of the clamp: it lets the map follow a changed scene.
  • Voxel hashing (Nießner et al., 2013) allocates blocks of 8³ voxels only inside the truncation band and finds them through a hash table. Memory follows the surface area, not the volume, and the map has no fixed bounds.
  • Euclidean distance fields (ESDF), as in Voxblox (Oleynikova et al., 2017), are computed from the TSDF and store the true distance to the nearest obstacle everywhere in free space. That is what a trajectory optimiser asks for: distance and its gradient.

Surfels

A surfel is a small disc: a position, a normal, a radius, a confidence and often a colour and a time stamp. The map is an unordered list of them. A new measurement is matched to an existing surfel (similar position and normal) and averaged into it, raising its confidence; otherwise it starts a new one. Unstable surfels that are never confirmed are deleted, which removes most moving objects. ElasticFusion (Whelan et al., 2016) uses surfels for RGB-D, and SuMa (Behley and Stachniss, 2018) for rotating LiDAR. There is no grid, so resolution adapts to the distance of the sensor, but free space is not represented at all.

Meshes and point clouds

A voxel-filtered point cloud is the simplest dense map and the usual output of LiDAR SLAM (M5-T10): cheap, but it has no surface, no free space and no notion of confidence. A triangle mesh is the usual product for people and simulators; it is extracted from a TSDF or built incrementally, and is rarely the structure a robot updates directly.

RepresentationStoresFree spaceMemory followsTypical use
Occupancy octreelog-odds per leafyes, and unknownsurface and observed free spacecollision checking, exploration, 3D navigation
TSDF (hashed)signed distance and weightwithin the truncation bandsurface areareconstruction, dense tracking, meshing
ESDFdistance to nearest obstacleyesobserved volumetrajectory optimisation
Surfelsdisc: position, normal, radius, confidencenosurface area, adaptivedense SLAM with map deformation
Point cloudpointsnopoints keptregistration target, visualisation

The loop-closure problem

A dense map is built by placing measurements into the world with the poses known at the time. When the back end later moves those poses (M4-T5), a pose graph simply holds new numbers; a voxel that averaged a hundred measurements cannot be un-averaged. Systems choose one of three answers:

  • Rebuild or re-integrate. Keep the raw depth data, and after a correction remove each affected frame from the volume and integrate it again at its new pose (BundleFusion; Dai et al., 2017). Exact, and expensive in memory and time.
  • Submaps. Build small volumes over short intervals in which drift is negligible, attach each to a pose-graph node, and move whole submaps when the graph is optimised (Voxgraph; Reijgwart et al., 2020; Cartographer does the same with 2D and 3D grids). Overlaps are fused or blended on demand.
  • Deform the map. Attach surfels or mesh vertices to a deformation graph and bend the surface so that both sides of the loop meet (ElasticFusion). No pose graph is needed, but large loops deform poorly.
L(n)
log-odds of occupancy of octree node n.
lhit, lmiss
log-odds increments for a measurement ending in, or passing through, a voxel.
D, W
stored signed distance (in units of τ) and accumulated weight of a TSDF voxel.
τ
truncation distance: the half-width of the band around the surface that is stored.
r, dv
measured range along a ray; distance of the voxel centre from the sensor along that ray.
ESDF
Euclidean signed distance field: untruncated distance to the nearest surface.

A worked example: three measurements of one wall

A depth sensor looks at a wall 2.00 m away. Along one ray the voxels are 5 cm apart with centres at 1.90, 1.95, 2.00, 2.05 and 2.10 m. Truncation τ = 0.10 m, weight 1 per measurement. Three depth readings arrive: 2.03, 1.98 and 2.02 m (noise of about 2 cm).

  1. First reading, r = 2.03. sdf = r − dv gives 0.13, 0.08, 0.03, −0.02, −0.07; divided by τ and clamped: D = (1.0, 0.8, 0.3, −0.2, −0.7), all weights 1.
  2. Second reading, r = 1.98. The new values are (0.8, 0.3, −0.2, −0.7) for the first four voxels. The fifth has sdf = −0.12, more than τ behind the surface: it is skipped. Averaging: D = (0.9, 0.55, 0.05, −0.45, −0.7), weights (2, 2, 2, 2, 1).
  3. Third reading, r = 2.02. New values (1.0, 0.7, 0.2, −0.3, −0.8). Averaging with the stored weights: D = (0.933, 0.6, 0.1, −0.4, −0.75), weights (3, 3, 3, 3, 2).
  4. Find the surface. The sign changes between the voxels at 2.00 (D = 0.1) and 2.05 (D = −0.4). Linear interpolation puts the zero at 2.00 + 0.05 × 0.1 / (0.1 + 0.4) = 2.01 m.
  5. Read the result. 2.01 m is the mean of the three readings (2.03 + 1.98 + 2.02) / 3, so the field has averaged the noise and placed the surface one fifth of a voxel from a centre: 1 cm of error with 5 cm voxels. An occupancy grid of the same resolution could only say that the voxels at 2.00 or 2.05 are occupied.

The same wall in an octree. With the OctoMap defaults (hit probability 0.7, miss 0.4, clamps at 0.12 and 0.97) the increments are lhit = ln(0.7/0.3) = 0.85 and lmiss = ln(0.4/0.6) = −0.41, and the clamps are −1.99 and 3.48. Starting from 0, five hits reach the upper clamp. If the wall is then removed, nine misses bring the log-odds below zero and the voxel is free again. Without the clamp, a hundred hits would have accumulated 84.7 and it would take 209 misses.

Engineering implications and limitations

Engineering implications

  • Choose by the consumer of the map. A local planner wants an ESDF or an occupancy octree; an inspection product wants a TSDF mesh; the localizer wants the sparse or point-cloud map it already has. Many robots keep two maps for this reason.
  • Resolution is cubic. Halving the voxel size multiplies memory and integration time by about eight for a full grid and about four for a surface-following structure. Set it from the smallest gap the robot must pass or the smallest feature it must see, not from what looks good.
  • Ray casting dominates the cost. Every measurement updates every voxel along its ray. Systems limit the range, group rays that fall in the same voxel, and update free space at a coarser resolution than surfaces.
  • Pose error becomes map error. A dense map is only as sharp as the trajectory: a few centimetres of drift between passes doubles walls. Check a map by looking for doubled or thickened surfaces before trusting any metric.
  • Dynamic objects leave traces. Clamping and weight caps let the map forget, but slowly; a person standing still is integrated as a surface. M8-T1 covers filtering them before integration.
  • Decide the loop-closure strategy at design time. A single global volume cannot be corrected later. If the mission includes loops, use submaps or keep the data needed to re-integrate.
  • Use existing implementations: OctoMap and Voxblox have ROS integrations, and Open3D provides TSDF integration for RGB-D data.

Limits

A TSDF assumes it sees a surface from the front: thin structures seen from both sides, such as a sheet of paper or a wire fence, cancel themselves when positive and negative values are averaged. Sparse LiDAR rays leave holes that a depth camera would fill, so the weighting and the truncation must be adapted to the sensor. Occupancy octrees treat voxels as independent, which is false along a surface and makes thin obstacles vanish under the misses of neighbouring rays. None of these structures stores uncertainty of the surface position itself, only confidence that something is there. The neural and Gaussian-splat maps of M8-T7 replace the grid by a learned or optimised function; they improve appearance and completion, and inherit the same dependence on pose accuracy and the same loop-closure problem.

Common misconceptions

“A dense point cloud is a dense map.”

It records where returns were measured. It has no surface, no free space and no unknown space, so it cannot answer whether a path is clear.

“A TSDF needs the whole volume in memory.”

Only the truncation band around observed surfaces holds information. Voxel hashing allocates just that.

“Finer voxels always give a better map.”

Below the noise and pose accuracy of the system, finer voxels store noise at eight times the cost and leave holes where too few rays arrive.

“After a loop closure the dense map is corrected like the trajectory.”

Not unless the system was designed for it. Fused voxels keep the old poses baked in; they must be re-integrated, moved as submaps, or deformed.

“Unknown and free are the same for planning.”

Treating unknown as free is how robots drive into unseen obstacles. Octrees and distance fields keep the two apart; surfels and point clouds do not.

Engineering takeaways

  1. A dense 3D grid at centimetre resolution is too large; octrees and voxel hashing store only observed space near surfaces.
  2. An occupancy octree stores clamped log-odds per leaf and separates occupied, free and unknown.
  3. A TSDF stores a truncated signed distance and a weight; fusion is a running average and the surface is the zero crossing, with sub-voxel accuracy.
  4. Surfels are oriented discs without a grid: adaptive and deformable, with no free space.
  5. A dense map bakes in the poses it was built with; loops require re-integration, submaps or deformation.

References and further reading

Established methods with their primary papers. The learned successors are in M8-T7. More courses, books and code are on the resources page.

Knowledge check

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

Question 1

A robot maps a corridor with a single global TSDF, drives a 200 m loop and returns with 30 cm of drift. The back end closes the loop. What does the map show at the start of the corridor, and what should the system have done?

Explanation

The trajectory is corrected, but the volume still holds the walls where the drifted poses put them, so the corridor appears twice, 30 cm apart, or as thickened, smeared walls where the two were averaged. The system needed a design that can follow a correction: submaps attached to pose-graph nodes and moved with them, re-integration of the affected frames from stored depth data, or a deformable surfel map.

Question 2

Why does a TSDF locate a wall more precisely than an occupancy grid with the same voxel size?

Explanation

Each voxel stores a continuous distance to the surface, and the surface is the interpolated zero crossing between voxels. Averaging several noisy measurements averages that distance, so the estimate moves continuously with the data; in the example three readings place the wall at 2.01 m with 5 cm voxels. An occupancy voxel holds one probability, so the surface is known only to within a voxel.

Question 3

A planner must fly a drone through a building that is only partly mapped. Which representation would you give it, and what is wrong with a surfel map for this task?

Explanation

An occupancy octree or an ESDF built from a TSDF: both distinguish free space from space never observed, and the ESDF also gives the distance to the nearest obstacle and its gradient for trajectory optimisation. A surfel map stores only observed surfaces. Empty space and unobserved space look the same in it, so the planner cannot tell a clear passage from one no sensor has looked at.

What’s next

That completes the theory of LiDAR SLAM. The labs now ask you to repair preprocessing, diagnose registration, build a LOAM-style step, attribute drift and investigate a failed run.

Next lesson

M6-T1 — Camera Models and Image Features

Write the pinhole projection with intrinsics and distortion and describe corners, descriptors and what makes a feature good.

Nothing below is required to finish this lesson.