LiDAR SLAM & the Mapping Pipeline

3.1What a LiDAR Actually Gives You

Chapter 2 covered the sensor physics: time of flight, beam divergence, dual returns, the noise model. Here we only need what the pipeline consumes. Ten or twenty times a second, a spinning 3D lidar hands you a scan: a cloud of tens of thousands to hundreds of thousands of 3D points in the sensor's own frame, each with centimeter-grade range. A Velodyne VLP-16 produces about 300,000 points per second on 16 beams; an Ouster OS1-64 roughly 1.3 million on 64; a Livox Avia paints a flower-petal pattern that never repeats, which breaks any code assuming fixed scan lines.

The point fields matter as much as the points. A useful driver gives you, per point: x, y, z, an intensity (return strength, useful for place recognition and for spotting retroreflective tape), a ring index (which vertical beam fired it), and a per-point timestamp. That last field is the one people lose in transport. Some drivers, bag conversions, and DDS configurations silently drop it, and without it you cannot deskew. Check your PointCloud2 fields before you blame the algorithm.

What the lidar gives you is shape. What it cannot give you is color, meaning, or your own position. That last part is this chapter's job.

Scan / sweep

One full revolution of the sensor, typically 100 ms at 10 Hz. Everything inside it was captured at slightly different times.

Ring

The set of points fired by one vertical beam. Feature extractors like LOAM compute curvature along a ring, so shuffled or missing ring indices break them.

Intensity

Return signal strength. Lane markings, signs, and reflective tape pop out in intensity even when geometry is bland.

Deskew

Undoing the robot's motion during the sweep so the scan looks like a single-instant snapshot. Section 3.3.

3.2The Skeleton, One Diagram to Memorize

Every laser SLAM system is a variation on six boxes. When an interviewer asks "how does lidar SLAM work?", you walk this diagram left to right, one sentence per box. The rest of the chapter earns you the right to do that.

3.3Deskew, the Rolling-Shutter Problem of Lasers

A spinning lidar takes about 100 ms to complete one revolution. The scan is not a photograph; it is a 100 ms exposure. If the robot moved during the sweep, points captured early and points captured late live in different frames, and treating them as one rigid snapshot smears the geometry.

How bad is it? Run the numbers. At 1 m/s of straight-line motion, the sensor moves 10 cm during the sweep. Walls come out 10 cm thick instead of 2 cm, and scan-to-map matching mostly soaks it up; you lose accuracy, not the mission. Rotation is another animal. At 15 rad/s (a drone flipping, or a handheld scanner being waved carelessly), the frame turns about 86 degrees within one sweep. A point 10 m away appears displaced by roughly 13 m from where it belongs. No matcher recovers from that.

sweep time      0.1 s  (10 Hz spinning lidar)
translation:    smear ≈ v · 0.1 s
                1 m/s  → 10 cm      annoying, survivable
rotation:       smear ≈ 2 r sin(ω · 0.05 s)   at range r
                1 rad/s,  r = 10 m → 1.0 m    matcher struggles
                15 rad/s, r = 10 m → 13.6 m   matcher dead

The practical rule falls out of the table: translation degrades deskew-free scans linearly and gently, rotation destroys them, and the damage scales with range.

The fix is to estimate the motion during the sweep and re-project every point to a common instant, usually the sweep end. Three grades of sophistication:

Constant velocity. Assume the last inter-scan twist held during this sweep, interpolate each point's pose by its timestamp. Free, no extra sensor, and what KISS-ICP ships with. Fails exactly when acceleration is high, which is when you needed it most.

IMU-aided. Integrate the 200 to 400 Hz gyro and accelerometer across the sweep and interpolate each point's correction from that trajectory. This is the standard in every serious system (LIO-SAM, FAST-LIO2), and it is why a $10 IMU is non-negotiable on a lidar robot. Chapter 2 covers the calibration and time-sync you need for the IMU samples to line up with the point timestamps.

The third grade treats the trajectory as a continuous-time function, a spline or Gaussian process over SE(3), and lets every point query its exact capture pose while the optimizer fits the spline to both IMU and lidar residuals. Elastic-style pipelines and DLIO's coarse-to-fine motion correction live here. It is the cleanest formulation, costs more compute, and shines on non-repetitive-pattern lidars like Livox where "one sweep" is a fuzzy concept anyway.

3.4Scan Matching, the Engine of LiDAR Odometry

Given a fresh (deskewed) scan and a reference (the previous scan, or better, the accumulated local map), find the rigid transform T ∈ SE(3) that lines them up. That transform is your motion estimate. Everything in lidar odometry is a variation on how you define "lines up" and how you search for correspondences.

Point-to-Point ICP, the Ancestor

Iterative Closest Point, Besl and McKay, 1992. The loop:

given: source scan P, target map Q, initial guess T0
repeat:
  1. transform:    P' = T · P
  2. correspond:   for each p' in P', find nearest q in Q   (kd-tree)
  3. reject:       drop pairs with ||p' - q|| > threshold
  4. solve:        T* = argmin_T  Σ ||T·p - q||²             (closed form: SVD)
  5. update:       T = T*
until change in error < epsilon, or max iterations

Step 4 has a closed-form solution (subtract centroids, SVD of the cross-covariance, rotation from the orthogonal factors). The loop converges because each step provably does not increase the error. What it converges to depends entirely on the initial guess, which is the subject of the warfield box below.

Point-to-Plane, Why It Wins on Real Buildings

The physical objection to point-to-point: the lidar never samples the same physical point twice. Your source point and its "nearest neighbor" are different samples of the same wall, so pulling them together point-to-point fights the sampling pattern. Point-to-plane (Chen and Medioni, 1992) instead penalizes only the offset along the local surface normal n: minimize Σ (n · (T·p − q))². Sliding along the wall is free, exactly as it should be. On structured scenes this converges in a handful of iterations where point-to-point takes dozens, because whole planar regions stop generating fake tangential residuals. The cost function loses its closed form and needs a small Gauss-Newton solve per iteration, which nobody minds.

GICP and NDT, Two Ways to Get Probabilistic

GICP (Segal et al., RSS 2009) generalizes both: model every point, source and target, as a small Gaussian whose covariance is estimated from its neighbors (flat disc on a wall, cigar on an edge), then minimize the Mahalanobis distance between matched distributions. Plane-to-plane matching falls out as a special case. It is the workhorse inside DLO/DLIO and half the localization stacks in industry, usually via the small_gicp or fast_gicp libraries.

NDT, the Normal Distributions Transform (Biber and Strasser 2003, 3D by Magnusson 2007), flips the data structure: chop the map into voxels of 1 to 2 m, fit one Gaussian per voxel, and align the scan by maximizing its likelihood under that mixture. No per-point nearest-neighbor search at all, just a voxel lookup, and the cost surface is smooth and differentiable, so it tolerates worse initial guesses than vanilla ICP. The price is voxel-boundary artifacts and sensitivity to the cell size. NDT is the traditional matcher in autonomous-driving localization, including Autoware's classic ndt_matching.

Feature-Based Matching, the LOAM Idea

LOAM's contribution was to not match all the points. Compute a curvature score along each ring: points where the ring bends sharply are edges (poles, door frames, rack corners), points where it stays flat are planes (walls, floor). Keep a few hundred of each, match edges to map edge-lines with point-to-line residuals and planes to map planes with point-to-plane residuals, and you get LOAM-class accuracy at a fraction of the compute of dense ICP. The cost: the feature extractor is tuned to spinning-lidar ring geometry, and it throws information away, which is exactly the assumption FAST-LIO2 later attacked (Section 3.8).

A cheat sheet for choosing among them:

Where Correspondences Come From

Nearest-neighbor search is where scan matchers actually spend their milliseconds, so the data structure holding the map is a first-class design decision.

• kd-tree: the default. Build in O(n log n), query in about O(log n). The catch is that it is static; growing the map means rebuilding the tree, and at map scale rebuilds cost more than the matching.
• ikd-tree (Cai, Xu, Zhang, 2021): an incremental kd-tree supporting point insertion, box-wise deletion, and lazy re-balancing in the background. The map structure updates in milliseconds instead of being rebuilt, and this single data structure is a large share of why FAST-LIO2 is fast.
• Voxel hashing: a hash map from integer voxel coordinates to the points (or a Gaussian, or a small array of points) inside. O(1) lookup, trivially incremental, cache-friendly. KISS-ICP and Faster-LIO's iVox both bet on it; the trend since 2022 is voxel hashing quietly replacing trees.

Convergence Basins and the Initial Guess

Every matcher above is a local optimizer. It has a convergence basin: the set of initial guesses from which it reaches the true alignment rather than a nearby impostor. Dense point-to-plane on a structured scene might have a basin of ±1 m and ±20 degrees; drop a repetitive scene (racks, columns, fences) and the basin shrinks to less than the spacing of the repeating structure. Your job is to always start inside the basin, which is what the motion prior is for: integrate the IMU since the last scan (best), or assume constant velocity (fine at car speeds on smooth trajectories). This is also the honest answer to why lidar odometry hates fast rotation: the prior degrades exactly when the basin shrinks.

One vocabulary upgrade worth using in interviews: matching each scan to the previous scan ("scan-to-scan") accumulates error at every step; matching to an accumulated local map ("scan-to-map") is what every modern system does, because the map averages away single-scan noise and gives correspondences a longer memory.

3.5Loop Closure for LiDAR

Odometry drifts, roughly 0.1 to 1 percent of distance traveled for good LIO (Chapter 0 explains why this is structural). Loop closure is the correction mechanism, and for lidar it comes in two stages: propose candidates, then verify them geometrically. Never skip the second stage.

Stage one, proposing. The cheapest proposer is a radius search: if the current pose estimate is within a few meters of an old keyframe pose, try to match against it. This works until drift exceeds your search radius, which on long loops it will. The classic drift-proof answer is Scan Context (Kim and Kim, IROS 2018): flatten the scan into a polar image, rings by sectors, each cell holding the max point height in that bin. The result is a small 2D fingerprint; a fast ring-key lookup shortlists candidates, and comparing column-shifted copies buys rotation invariance for free (a column shift is a yaw rotation). Successors refine the recipe: Scan Context++ adds lateral robustness, STD (stable triangle descriptors) and BTC match triangles of keypoints, which are invariant to viewpoint by construction. Learned descriptors (OverlapTransformer, LoGG3D-Net) are Chapter 7 material.

Stage two, verifying. Run a real registration (ICP or GICP) between the candidate pair, seeded by the descriptor's yaw estimate, and accept only if it converges with a tight fitness score and enough inlier overlap. The reason for the paranoia: a false loop closure welds two different places together, and the graph optimizer will happily bend the entire trajectory to satisfy the lie. One bad loop factor can do more damage than an hour of drift. This is also why the back-end keeps robust kernels and switchable constraints on the loop edges (Chapter 1 covers Huber, Cauchy, and switchable constraints); the verification gate keeps the false-positive rate low, the robust kernel survives the ones that get through.

Place recognition

Answering "have I been here?" from sensor data alone, without trusting the pose estimate. Needed exactly because drift makes the pose estimate untrustworthy on long loops.

Descriptor

A compact fingerprint of a scan (Scan Context's polar image, STD's triangles) built so that similar places give similar fingerprints and comparison is cheap enough to run against thousands of candidates.

Geometric verification

Running a full registration on a proposed loop pair and accepting only on tight convergence with high inlier overlap. The stage that keeps false positives out of the graph.

Fitness score

Mean residual of a converged registration. Necessary but not sufficient evidence: degenerate and repetitive scenes produce great scores for wrong alignments.

3.6The Factor Graph on a LiDAR Robot

Chapter 1 built the machinery; here is what it holds on a real lidar robot. Nodes are keyframe poses (and usually velocity and IMU biases). The factors, in the order you add them:

• Prior factor on the first pose, pinning the gauge freedom so the problem has a unique solution.
• Odometry factors: relative-pose constraints between consecutive keyframes, produced by the scan matcher, with covariance taken from the matcher's Hessian (honest covariances here are what make degeneracy handling possible).
• IMU preintegration factors: hundreds of IMU samples between two keyframes compressed into one constraint on relative pose, velocity, and bias (Forster et al.). These also make gravity observable, which is what keeps your map's roll and pitch pinned to the horizon over kilometers.
• Loop factors: relative poses from verified loop closures, wrapped in a robust kernel.
• GPS factors (outdoor): unary position constraints, added sparsely, typically only when the GPS covariance is small and the graph has drifted enough to make them informative. LIO-SAM does exactly this.

Keyframing policy is the quiet decision that controls cost. You do not add every scan to the graph; you add a keyframe when the robot has moved enough for the new scan to say something new. Typical thresholds: 1 m of translation or 10 to 15 degrees of rotation, plus a time cap so a parked robot does not go silent. Too dense and the graph balloons with redundant, correlated factors; too sparse and loop closures have nothing nearby to latch onto and deskew priors get stale. Solvers are GTSAM's iSAM2 (incremental, re-linearizes only what changed) or Ceres in batch; see GTSAM and Ceres. When a loop closure fires and the whole map visibly snaps into place in the viewer, what you are watching is this graph relaxing.

Keyframe

A scan promoted to a graph node because it was sufficiently far, in distance or angle, from the previous one. Everything else is used for odometry and discarded.

IMU preintegration

The trick (Forster et al., 2015) of summarizing all IMU samples between two keyframes into a single factor whose value can be corrected for bias changes without re-integrating. It is what makes IMUs usable in graph back-ends.

Gauge freedom

A pure relative-constraint graph can slide and rotate as a whole with no cost change. The prior factor nails it down.

3.7The Classic Systems

These four still come up by name in interviews, and each earned its slot with one idea.

LOAM (Zhang and Singh, RSS 2014) mattered because it made real-time 6-DoF lidar odometry work on a laptop by refusing to match all the points, and by splitting the problem into a fast loop for responsiveness and a slow loop for accuracy. Every system since inherits at least one of those two moves. In an interview, credit it for the edge/plane feature idea and the two-speed architecture, then note that its assumptions (fixed ring geometry, no IMU in the core loop) are what the modern era dismantled.

LeGO-LOAM (Shan and Englot, IROS 2018) is LOAM made honest for ground robots: since a UGV's lidar sees mostly ground, segment that ground explicitly, use it to solve the three DoF it actually constrains (height, roll, pitch), then solve the remaining three from wall features. Cheaper and more stable on rough terrain than vanilla LOAM. Say "two-step optimization exploiting the ground prior" and you have said the whole paper.

Cartographer (Hess et al., ICRA 2016) matters for the back half of the pipeline. Scans match into small local submaps (probability grids), which cap local drift; loop closure searches all past submaps with a branch-and-bound scheme over a precomputed multi-resolution stack of the grid, pruning hopeless regions wholesale at coarse resolution. The result is an exact global search that runs in real time, with no learned components. If an interviewer asks for an algorithm you admire, this is a strong and slightly unusual pick, and you can explain the bound in two sentences: the coarse grid stores the max score of the cells beneath it, so the score of any coarse cell upper-bounds every alignment inside it.

hdl_graph_slam (Koide et al., 2019) never claimed algorithmic novelty; it mattered because it was the first widely used codebase where the whole skeleton is visible in one place: interchangeable odometry front-end, explicit g2o graph, floor-plane factors to keep multistory maps sane, optional GPS. When you need to explain the pipeline to a new engineer, this is still the code to open. Repo: github.com/koide3/hdl_graph_slam.

3.8The Modern Era

Everything since 2020 is a fight about coupling and data structures. Two definitions first, because "tightly-coupled" gets waved around loosely. Loosely coupled: each sensor pipeline produces its own pose estimate, and you blend the outputs, typically in an EKF (this is what robot_localization does). Tightly coupled: raw measurements from all sensors enter one joint estimator, so when the lidar goes weak for two seconds in a corridor, the IMU's raw constraints keep the shared state honest instead of merging with an already-broken lidar pose. Tighter is more accurate exactly when one sensor is briefly bad, at the price of one bigger, touchier estimator.

LIO-SAM (Shan et al., IROS 2020) is the reference factor-graph design: IMU preintegration factors, lidar odometry factors from a LOAM-style matcher, optional GPS factors and loop factors, all in one GTSAM graph solved incrementally with iSAM2. The IMU also runs a fast prediction loop between keyframes so the controller gets 200 Hz odometry. Study its factor-graph figure; it is the cleanest picture in the literature of how the factors of Section 3.6 coexist.

FAST-LIO2 (Xu et al., 2021) is the default since about 2022, and for two reasons you should be able to state precisely. First, no feature extraction: register raw points directly to the map with point-to-plane residuals, because feature extraction discards information and breaks on non-spinning lidars. Second, the map lives in an ikd-tree, so inserting a scan and querying neighbors are both incremental and cheap. Fusion is an iterated error-state extended Kalman filter: iterate the measurement update like a Gauss-Newton solve until the linearization point converges, which buys near-optimizer accuracy at filter cost, with a formulation that keeps the Kalman gain computation in the dimension of the state rather than the (huge) measurement. Wrap-up numbers for the interview: full-rate odometry on a laptop CPU at 100 Hz with thousands of points per update.

Faster-LIO (Bai et al., RA-L 2022) keeps the FAST-LIO2 estimator and swaps the ikd-tree for iVox, an incremental sparse voxel hash. Same accuracy, roughly 1.5 to 2x the throughput, and evidence for the claim that the data structure, not the filter, was the bottleneck.

KISS-ICP (Vizzo et al., RA-L 2023) is the counterpoint, and its title is the thesis: point-to-point ICP, a constant-velocity motion prior, adaptive-threshold correspondence rejection, a voxel-hash map, no IMU, and essentially no parameters to tune. It embarrasses far more complicated systems on cars, drones, handhelds, and segways with the same config. It is the correct first baseline on any new platform, and the correct interview answer to "what would you try first?": if KISS-ICP works, you may not need the complexity; if it fails, the way it fails tells you what to add.

DLO / DLIO (Chen et al., 2022 and 2023): GICP-based direct matching with a clever submap built from keyframe neighborhoods, then (DLIO) a continuous-time motion correction where deskew and integration come from one analytically integrated trajectory, giving each point its exact pose cheaply. Strong on aggressive handheld and drone motion. Point-LIO (He et al., 2023) goes further and updates the filter per point rather than per scan, so there is no scan-accumulation latency at all; it survives spinning-drone abuse and outputs odometry at kilohertz rates. GLIM (Koide et al., 2024) and MOLA are the modular back-end frameworks to name when the question is about extensible architecture; GLIM in particular does GPU-accelerated matching and a proper global optimization layer.

The landscape in one table, for the interview minute where you place the systems relative to each other:

pip install "kiss-icp[all]"    # [all] adds the built-in visualizer

# grab data: a KITTI odometry sequence is the classic starting point
# (kitti odometry "velodyne laser data", sequence 00, ~4 GB)
# any folder of .bin / .ply / .pcd scans also works
kiss_icp_pipeline --visualize ~/data/kitti-odometry/dataset/sequences/00

# config.yaml
data:
    deskew: true            # motion-compensate each scan; needs per-point timestamps
    max_range: 100.0        # clamp to the sensor's honest range
    min_range: 3.0          # drop returns off the robot's own body
mapping:
    voxel_size: 1.0         # local map resolution, meters; the main speed/accuracy dial
    max_points_per_voxel: 20
adaptive_threshold:
    initial_threshold: 2.0  # ICP correspondence gate, adapts as you drive

3.9Degeneracy, the LiDAR Killer

Scan matching estimates 6 numbers from geometry. Sometimes the geometry only constrains 5 of them, or 3. A long featureless corridor: both walls are parallel planes, and sliding the scan along the corridor axis changes nothing about how well it matches. A tunnel adds a second free axis if it is smooth-bored. An open field constrains z, roll, and pitch through the ground plane and almost nothing else. The optimizer does not crash in these cases. It confidently returns a number for the unconstrained direction, and that number is fiction driven by noise.

Detection is a solved problem and a favorite interview follow-up. The scan matcher's Gauss-Newton step builds a 6x6 Hessian (JᵀJ); eigen-decompose it. A well-constrained problem has six healthy eigenvalues. A near-zero eigenvalue flags a degenerate direction, and its eigenvector tells you which direction. Zhang, Kaess, and Singh formalized this at ICRA 2016 ("On Degeneracy of Optimization-based State Estimation Problems") along with solution remapping: solve the update only in the well-conditioned subspace and let the prior carry the sick direction. Thresholds are sensor and scene dependent; calibrate on your own corridors, and log the minimum eigenvalue as a health metric in production.

Survival means fusing something that observes what the lidar cannot. Wheel odometry observes along-corridor translation well (corridors are flat, wheels barely slip). The IMU observes short-term velocity, enough to bridge tens of meters before its own drift takes over, which is a real argument for tight coupling: in a tightly coupled filter the IMU constraint is already in the estimator, correctly weighted, when the lidar goes blind. Outdoors, GPS or a radar odometry channel plays the same role. And a loop closure at the corridor's far end retroactively repairs whatever error leaked through.

3.102D SLAM Still Pays Salaries

A planar lidar on a flat floor is a solved problem with mature tooling, and a large share of deployed AMRs, cleaning robots, and warehouse fleets run exactly this. Do not let the 3D literature convince you 2D is beneath you; it is cheaper in every dimension that matters commercially: a $100 2D lidar versus a $4,000 3D one, single-digit percent CPU, and a map every grid planner consumes directly with zero conversion (Chapter 9).

gmapping is the name your interviewer over 40 will mention. It is a Rao-Blackwellized particle filter (Chapter 1): each particle carries a full map hypothesis, and importance weighting plus resampling keep the plausible ones alive. It worked, it shipped on the PR2 and a thousand robots after, and its weaknesses (particle depletion on big loops, memory per particle, no life-long operation) are exactly what its successor fixed. Treat it as history you can explain, not something you deploy in 2026.

The modern open-source reference is SLAM Toolbox (Macenski), a C++ codebase built from Karto's scan matcher plus a Ceres pose graph. Its production features are the reason it won: lifelong mapping (open yesterday's map, keep refining it today), serialized pose graphs (save the graph itself, not just a rendered image, so the map stays editable and extendable), a localization mode (freeze the graph, keep matching against it), and tools to delete bad nodes from a map you otherwise like. Whatever stack you assemble, those four features are the checklist a production 2D mapper has to meet.

When is 2D the wrong call? Ramps and multi-floor sites (the planar assumption breaks), overhanging obstacles the scan plane misses (forklift tines at chest height are the canonical incident report), and outdoor terrain. The moment any of those appear, you pay the 3D tax. Until then, 2D wins on cost, compute, and maturity.

import open3d as o3d
import numpy as np

# three overlapping indoor fragments from Open3D's bundled demo data
paths = o3d.data.DemoICPPointClouds().paths
clouds = [o3d.io.read_point_cloud(p).voxel_down_sample(0.05) for p in paths]
for c in clouds:
    c.estimate_normals(o3d.geometry.KDTreeSearchParamHybrid(0.1, 30))

def register(src, dst):
    # point-to-plane ICP, section 3.4 in one call
    result = o3d.pipelines.registration.registration_icp(
        src, dst, max_correspondence_distance=0.15,
        estimation_method=o3d.pipelines.registration
            .TransformationEstimationPointToPlane())
    info = o3d.pipelines.registration.get_information_matrix_from_point_clouds(
        src, dst, 0.15, result.transformation)
    return result.transformation, info

# odometry chain: 0->1, 1->2   (consecutive scan matching)
graph = o3d.pipelines.registration.PoseGraph()
graph.nodes.append(o3d.pipelines.registration.PoseGraphNode(np.eye(4)))
odom = np.eye(4)
for i in range(len(clouds) - 1):
    T, info = register(clouds[i], clouds[i + 1])
    odom = T @ odom
    graph.nodes.append(o3d.pipelines.registration.PoseGraphNode(np.linalg.inv(odom)))
    graph.edges.append(o3d.pipelines.registration.PoseGraphEdge(
        i, i + 1, T, info, uncertain=False))

# loop closure: 0->2 directly (the long-range spring from section 3.6)
T02, info02 = register(clouds[0], clouds[2])
graph.edges.append(o3d.pipelines.registration.PoseGraphEdge(
    0, 2, T02, info02, uncertain=True))

# relax the spring network
o3d.pipelines.registration.global_optimization(
    graph,
    o3d.pipelines.registration.GlobalOptimizationLevenbergMarquardt(),
    o3d.pipelines.registration.GlobalOptimizationConvergenceCriteria(),
    o3d.pipelines.registration.GlobalOptimizationOption(
        max_correspondence_distance=0.15, edge_prune_threshold=0.25))

merged = o3d.geometry.PointCloud()
for node, cloud in zip(graph.nodes, clouds):
    merged += o3d.geometry.PointCloud(cloud).transform(node.pose)
o3d.visualization.draw_geometries([merged])

3.11Map Products

The pose trajectory is half the deliverable. The other half is a map some other module can use, and "use" means different things to a graph-search planner, a trajectory optimizer, and a fleet dashboard. Two big families, plus two pragmatic in-betweens.

Occupancy: May I Enter This Cell?

OctoMap (Hornung et al., 2013) is the classic 3D answer: an octree (each cube splits into 8 children) storing per-cell occupancy as log-odds, a running score nudged up when a beam hits in the cell and down for every cell a beam passes through (found by raycasting), clamped so cells can change their mind later. It distinguishes free from unknown space, which planners and exploration modules need. Its weakness after a decade is mechanical: pointer-chasing through a deep tree is slow on modern cache-hungry CPUs.

Bonxai (Faconti, 2023) is the modern replacement: a VDB-style hierarchical voxel grid (the structure movie-VFX volumetrics run on) with no per-node pointers, cache-friendly and drop-in faster. wavemap (ETH, 2023) compresses occupancy with wavelets, storing coarse where the world is boring and fine where it is not.

Distance Fields: How Far Is the Nearest Surface?

A TSDF (truncated signed distance field) stores, in a narrow band around surfaces, the signed distance to the surface: negative inside, positive outside, zero at the wall. Integrate outward and you get an ESDF (Euclidean SDF) where every cell knows its distance to the nearest obstacle, and the gradient points away from trouble, which is exactly the quantity trajectory optimizers consume. The reference pipeline is Voxblox (Oleynikova et al., 2016); its GPU descendant nvblox (NVIDIA) runs real time on a Jetson and is the name to drop when the target platform is NVIDIA edge hardware.

The Pragmatic Middle: 2.5D and Meshes

Legged and off-road robots often want an elevation map (a 2.5D grid: one height, or a small height distribution, per cell), via grid_map and elevation_mapping from ANYbotics. It is dramatically cheaper than full 3D and matches how walking controllers think. Meshes, extracted from a TSDF by marching cubes or fitted by Poisson reconstruction, are the product for humans: inspection reports, digital twins, game-engine simulation. Few planners consume meshes directly.

Concrete numbers anchor this in interviews. Back-of-envelope storage for one 100 m x 100 m warehouse with 8 m ceilings:

The research frontier makes the map a small neural network holding an implicit SDF: PIN-SLAM (2024) and SHINE-Mapping. That thread continues in Chapter 7.

3.12Reading List, in Priority Order

3.13Interview Questions, Answer Out Loud First