Modern Map Representations

Octrees, TSDFs, distance fields, meshes, and radiance fields — five ways to store what the robot saw, and one recursive estimator hiding inside every one of them.

The map that cannot answer the question

Here is the concrete failure. Rusty has a 5 cm occupancy grid of the Apartment — 43,200 cells, 43 kB, every one of them a well-calibrated posterior over occupancy. A planner asks: what is the clearance at $(7.3, 4.1)$?

The grid cannot answer. It can tell you about the cell containing that point, and about any other cell you name, but "distance to the nearest occupied cell" is not stored anywhere — it has to be searched for, ring by expanding ring, until an occupied cell turns up. Measured on this chapter's Apartment log, that search costs about 16 µs per query against 0.3 µs for an occupancy lookup: a factor of fifty, paid on every one of the millions of collision checks a sampling planner performs.

So store the distance instead of the bit. That single decision is what the rest of the chapter falls out of.

Watch one lap before reading on. Three things are happening, and each is a section of this chapter.

The field is signed, and truncated. Blue is positive — free space in front of a surface — and orange is negative, behind it. Neither extends far: past $\tau = 15$ cm from the nearest observed surface the field simply stops being maintained, because a projective range measurement stops being a good estimate of true distance out there. Truncation is not a memory optimization. It is an honesty policy.

The surface is not stored; it is extracted. The purple contour is the zero level set $\{\mathbf{x} : D(\mathbf{x}) = 0\}$, pulled out of the numbers by marching squares every few frames at sub-cell accuracy. Nothing in the field is "a wall". Walls are where the estimate changes sign.

Every cell is running a filter. Click any cell and the inspector shows three numbers: the prior $D_{t-1}$, the projective sample $d_t$ this scan delivered, and the fused posterior $D_t$ — with the gain $K_t$ that produced it. That gain is Chapter 6's Kalman gain, and the weight $W$ beside it is Chapter 6's information $\Omega$. This is the chapter's thesis, and it is visible before we prove it.

Now press move the chair and watch the ghost. At $W_{\max} = 64$ the abandoned chair loses half its error only every 45 re-observations, so it is still there most of a lap later; drag the slider to 4 and the half-life falls to three, the ghost evaporates — and the rest of the map turns visibly noisy. That trade has a closed form, derived in §3.3, and it is the same trade Chapter 6 called the noise ratio.

Building intuition: four maps, one log

Before any mathematics, the comparison the whole chapter exists to make. The same 200-scan lap, with the same poses (optimized by Chapter 16's pose graph, so this is a mapping chapter and not a SLAM chapter), fused into four representations at once, with meters underneath measuring what each one actually costs.

The ranking is not stable. That is the point.

• Occupancy probes — "is this point occupied?" The flat grid wins: one multiply, one array index. The quadtree pays for eight pointer hops down its levels and comes second by a hair. Both are so cheap that the difference rarely decides an architecture.
• Distance probes — "how far to the nearest obstacle?" The ESDF wins by sixty times over the grid's ring search and a hundred and seventy times over brute-force distance to the extracted segments. This is the query workload that reorganizes modern mapping stacks.
• Surface extraction — "give me the boundary as a polyline." The mesh wins trivially: it is already the answer. Everything else has to run marching squares first, which costs 15 ms on this grid.

And memory tells a third story that contradicts the first two. The quadtree, the representation whose entire pitch is compression, uses five times more memory than the flat grid it was supposed to beat. That is not a bug in the implementation, and §3.1 derives exactly when it is true.

Notation for this chapter

One deliberate exception to the book's color code lives in this chapter, as it did in Chapter 13. The signed distance field is drawn with a diverging ramp — orange for negative (behind a surface), through transparent at zero, to blue for positive (free) — because the sign is the meaning, and a sequential ramp would hide the only feature the reader is meant to look for. Every other element keeps its role: measurements green, extracted posterior surfaces purple, ground truth gray dashed.

The mathematics

3.1 Hierarchy: the octree is Chapter 13's filter plus a compression theorem

Start with the representation that changes the least. An octree (in 2-D, a quadtree) subdivides space recursively; each leaf stores exactly what a grid cell stored, the log odds $\ell_i$ of occupancy, and each leaf runs exactly the recursion of Chapter 13, with one addition:

The clamp came into Chapter 13 as a patch for the "stubborn map" problem: an unclamped cell that has seen forty consistent readings needs forty contradicting ones to change its mind. Hornung et al. (2013) noticed that the same patch is what makes the tree work, and that observation is the whole of OctoMap.

Line 8 is the only line Chapter 13 did not already have. Line 3's "not yet touched by this scan" is not an optimization either: cells near the sensor lie on many beams, and counting them once per beam would fabricate evidence the scan does not contain — the same per-beam independence lie the Chapter 10 beam model told, arriving here in a new outfit.

3.2 Distance, not occupancy

Now change the state. Instead of a bit per cell, store a number: the signed distance to the nearest surface,

with the surface recovered as the zero level set $\mathcal{S} = \{\mathbf{x} : \phi(\mathbf{x}) = 0\}$. This buys sub-cell surface accuracy for free — a cell holding $\phi = 0.017$ m says the wall is 1.7 cm away, information a binary cell cannot express at any resolution — and it makes surface extraction a root-finding problem instead of a segmentation problem.

It also creates a problem. A range sensor does not measure $\phi$. Standing at $x_t$ and firing a beam that returns at range $z$, the natural estimate for a point at arc length $s$ along that beam is the projective distance $d = z - s$, which equals the true signed distance only where the beam meets the surface head-on. If the surface normal makes an angle $\theta$ with the beam, then $\phi = (z - s)\cos\theta$, so the projective estimate is too large by $1/\cos\theta$ and diverges at grazing incidence.

The standard fix for the divergence is to define the estimand as the truncated signed distance $\Phi(\mathbf{x}) = \mathrm{clamp}(\phi(\mathbf{x}), -\tau, +\tau)$ and to fit it only where $\lvert d \rvert \le \tau$: near the surface, where the approximation holds. Everything else is declared out of scope. Choose $\tau$ at two to four cells and never smaller than the thinnest structure you must reconstruct — a wall thinner than $2\tau$ gets observed from both sides, and the two negative claims cancel into nothing.

3.3 The centerpiece: TSDF fusion is a per-voxel information filter

Curless and Levoy's fusion rule, written the way graphics writes it, is a running weighted average:

Two lines of code, no probability anywhere in sight. It is a Bayes filter, and here is the proof.

Line 2's $s_{\text{start}}$ is the one real decision. Start at $z - \tau$ and the cost is $O(B\tau/r)$ — measured at 0.11 ms per scan on this chapter's log — but the field never learns that the corridor is empty, only that the walls are where they are. Start at the sensor and you also carve free space, at $O(B L/r)$ and a measured 0.54 ms per scan, five times dearer for a contour that is identical to within five segments out of 2,236. You pay that factor of five for one thing only: knowing the difference between free and unknown. Chapter 24 needs it; a pure reconstruction pipeline does not.

A worked example you can check by hand

One voxel, $\tau = 0.20$ m, $W_{\max} = 4$, unit-weight scans except where noted. The voxel starts unobserved: $W_0 = 0$.

Four things are checkable with a pencil, and each one is a claim from D2.

Row 1: the gain is exactly one. No prior information means no reason to keep the prior. The $+\tau$ that unobserved cells are initialized to never enters the answer.

Row 3: the recursion equals the batch estimate. The weighted mean of everything so far is $(1 \cdot 0.10 + 1 \cdot 0.06 + 2 \cdot 0.00)/4 = 0.16/4 = 0.040$, which is what the recursion produced. Up to the clamp, the filter is not approximating the batch solution — it is the batch solution.

Row 4: the clamp breaks that equality on purpose. The batch mean would now be $0.16/5 = 0.032$… which is also what the table says, coincidentally, because $W$ saturated on this exact step. Row 5 is where they part: batch says $0.16/6 = 0.0267$, the clamped filter says $0.0256$.

Rows 4–6: geometric decay at rate $\lambda = 0.8$. $0.040 \to 0.032 \to 0.0256 \to 0.02048$, each $0.8\times$ the last, and $\lambda = W_{\max}/(W_{\max}+w) = 4/5$ as D2's Step 4 promised. The half-life is $\ln 2/\ln 1.25 = 3.1$ scans.

use approx::assert_relative_eq;
use ch19_maps::tsdf::{Tsdf2, Tsdf2Config};

/// The chapter's worked table, pinned. If this test fails the book is wrong.
#[test]
fn worked_example_ch19_voxel_filter() {
    let mut f = Tsdf2::new(Tsdf2Config {
        cells: (1, 1),
        resolution: 1.0,
        origin: nalgebra::Point2::origin(),
        truncation: 0.20,
        w_max: 4.0,
    });

    // (observation, weight, expected gain, expected D, expected W)
    let script = [
        (0.10, 1.0, 1.0, 0.100_00, 1.0),
        (0.06, 1.0, 0.5, 0.080_00, 2.0),
        (0.00, 2.0, 0.5, 0.040_00, 4.0),
        (0.00, 1.0, 0.2, 0.032_00, 4.0), // clamp engages: W stays at W_max
        (0.00, 1.0, 0.2, 0.025_60, 4.0),
        (0.00, 1.0, 0.2, 0.020_48, 4.0),
    ];

    for (d, w, want_k, want_d, want_w) in script {
        let ev = f.fuse((0, 0), d, w);
        assert_relative_eq!(ev.gain, want_k, epsilon = 1e-9);
        assert_relative_eq!(ev.after, want_d, epsilon = 1e-9);
        assert_relative_eq!(ev.weight_after, want_w, epsilon = 1e-9);
    }

    // Up to the clamp, recursive == batch. This is D2 Step 1 and Step 2 agreeing.
    let batch = (1.0 * 0.10 + 1.0 * 0.06 + 2.0 * 0.00) / 4.0;
    assert_relative_eq!(batch, 0.040, epsilon = 1e-12);

    // After the clamp, the error decays geometrically at λ = W_max/(W_max + w).
    let lambda = 4.0 / 5.0;
    assert_relative_eq!(0.032 * lambda, 0.025_60, epsilon = 1e-9);
    assert_relative_eq!(0.025_60 * lambda, 0.020_48, epsilon = 1e-9);
}

The TypeScript port in lib/mapping/tsdf.ts runs the identical arithmetic, which is why the voxel inspector in w19.1 prints these gains when you click a cell: the table, the Rust test, and the number under your cursor are the same computation three times.

3.4 From the field to a surface, and from the field to a plan

A TSDF is not directly usable by anything. Two extraction steps make it so, and they answer two different questions.

Marching squares answers where is the boundary? Walk the dual grid; at each cell, the signs of the four corner samples select one of 16 cases; on every edge whose endpoints disagree, place a crossing by linear interpolation,

which is exact for the piecewise-linear field the samples define — not an approximation of it. Two of the sixteen cases (the diagonal ones, 0101 and 1010) are genuinely ambiguous: two crossings on four edges are consistent with two different topologies, and the table must simply pick one. In three dimensions that same ambiguity is what puts holes in a naive marching-cubes mesh, and the literature since Lorensen and Cline (1987) is largely about disambiguating it.

Line 2 is the honest line. A cell with no evidence has no sign, and extracting a surface from it is inventing geometry — the failure mode that makes unvalidated reconstructions look confident in exactly the places they are guessing.

The distance transform answers how far to the boundary, from anywhere? This is the query the TSDF conspicuously cannot serve: past $\tau$ its value is a constant, and a constant has no gradient.

That widget is the section in one image. Toggle it off and the rings stop at 30 cm, the arrows vanish, and the probe freezes: a truncated field is not a distance field with smaller numbers in it, it is a distance field with a hole where the planner lives.

Two properties make the result worth its 173 kB. Away from the medial axis a true distance field satisfies the eikonal equation $\norm{\nabla\,\mathrm{esdf}} = 1$, so its gradient is a pure direction — "this way is away from the nearest obstacle" — with no magnitude to tune. The widget's meter reads a median $\norm{\nabla d} = 0.93$ over a grid of probes, against $0.01$ for the raw TSDF: the shortfall from 1 is discretization plus the medial-axis points where the gradient genuinely does vanish. And both the value and the gradient are $O(1)$ bilinear reads. That pair, $(d, \nabla d)$ in constant time, is the contract Chapter 20 and Chapter 23 are written against.

The honesty note this field deserves: the transform measures distance to the extracted contour, and marching squares refuses to emit a contour where a cell has unobserved corners. Where those two disagree — the lip of a doorway seen from one side only — the ESDF reports a distance that is too small. Measured on the Apartment at 5 cm: median error 3.0 cm, 99th percentile 7.5 cm, worst case 28 cm, and the worst case is conservative. For a collision cost, being wrong in the safe direction is the correct way to be wrong; for a reconstruction metric it would be a bug. The representation is not neutral about what it is for.

Implementation in Rust

Three types, one trait, and a benchmark harness that is also the chapter's argument.

The trait first, because it is the thesis in code: four representations, four different answers to the same four questions, and a None where a representation genuinely cannot answer in constant time. Nothing is faked — a grid returning a searched distance would hide the whole point.

use nalgebra::Point2;
use crate::{Scan, Se2};

/// The chapter's thesis as an interface: a map is what it can answer cheaply.
pub trait MapRepr {
    /// Fold one scan in, with a known pose (Chapter 16's optimized graph).
    fn integrate_scan(&mut self, pose: &Se2, scan: &Scan);

    /// P(occupied) at a point. `None` = never observed, which is *not* 0.5.
    fn occupancy(&self, p: Point2<f64>) -> Option<f64>;

    /// Distance to the nearest surface, in O(1). `None` = this representation
    /// cannot answer without a search, and saying so is the honest API.
    fn distance(&self, p: Point2<f64>) -> Option<f64>;

    /// Measured, not estimated: what the harness reports in w19.2.
    fn memory_bytes(&self) -> usize;
}

Then the field itself. Two f32 planes — one for the estimate, one for its accumulated precision — and a fuse that is six lines because D2 says it should be six lines.

use nalgebra::{Point2, Vector2};
use ndarray::Array2;

/// A 2-D truncated signed distance field: Curless & Levoy (1996), read as a
/// per-voxel information filter (Chapter 19, D2).
pub struct Tsdf2 {
    /// D_t(v): fused signed distance in metres. Unobserved cells hold +τ.
    d: Array2<f32>,
    /// W_t(v): accumulated weight = accumulated precision, up to σ².
    w: Array2<f32>,
    resolution: f64,
    origin: Point2<f64>,
    truncation: f64,
    /// The fading-memory knob. `f32::INFINITY` recovers the batch estimator.
    w_max: f32,
}

/// One fusion event, returned so a widget (or a test) can inspect the filter.
#[derive(Copy, Clone, Debug)]
pub struct FusionEvent {
    pub before: f64,
    pub weight_before: f64,
    pub observation: f64,
    pub after: f64,
    pub weight_after: f64,
    /// K_t = w_t / (W_{t−1} + w_t) — Chapter 6's Kalman gain, verbatim.
    pub gain: f64,
}

impl Tsdf2 {
    #[inline]
    fn cell_center(&self, ij: (usize, usize)) -> Point2<f64> {
        Point2::new(
            self.origin.x + (ij.0 as f64 + 0.5) * self.resolution,
            self.origin.y + (ij.1 as f64 + 0.5) * self.resolution,
        )
    }

    /// The whole chapter in six lines: precision-weighted averaging, clamped.
    ///
    /// W = 0 gives K = 1, so an unobserved voxel adopts its first observation
    /// outright — no special case, just infinite prior variance doing its job.
    pub fn fuse(&mut self, ij: (usize, usize), d_obs: f64, w_obs: f64) -> FusionEvent {
        let before = self.d[ij] as f64;
        let weight_before = self.w[ij] as f64;
        let denom = weight_before + w_obs;
        let gain = if denom > 0.0 { w_obs / denom } else { 1.0 };
        let after = before + gain * (d_obs - before);

        self.d[ij] = after as f32;
        self.w[ij] = denom.min(self.w_max as f64) as f32;

        FusionEvent { before, weight_before, observation: d_obs,
                      after, weight_after: self.w[ij] as f64, gain }
    }

    /// `tsdf_integrate`: march each beam through the truncation band.
    ///
    /// The visited set is per *scan*, not per beam. Cells near the sensor sit on
    /// many beams' paths, and fusing them once per beam would manufacture
    /// evidence the scan does not contain.
    pub fn integrate(&mut self, pose: &Se2, scan: &Scan, carve: bool) {
        let tau = self.truncation;
        let step = self.resolution * 0.5;
        let mut visited = std::collections::HashSet::new();

        for (&z, &bearing) in scan.ranges.iter().zip(scan.bearings.iter()) {
            let hit = z < scan.max_range;
            let dir = Vector2::new((pose.theta + bearing).cos(), (pose.theta + bearing).sin());
            let s0 = if carve { step * 0.5 } else { (z - tau).max(step * 0.5) };
            let s1 = if hit { z + tau } else { scan.max_range };

            let mut s = s0;
            while s <= s1 {
                let p = pose.translation() + s * dir;
                let Some(ij) = self.world_to_cell(p) else { s += step; continue };
                if !visited.insert(ij) { s += step; continue }

                let sdf = if hit { z - s } else { tau };
                if sdf >= -tau {
                    // Weight tapers to zero behind the surface: a beam says
                    // progressively less about what lies past what it hit.
                    let w = if sdf >= 0.0 { 1.0 } else { 1.0 + sdf / tau };
                    if w > 0.0 {
                        self.fuse(ij, sdf.clamp(-tau, tau), w);
                    }
                }
                s += step;
            }
        }
    }
}

Then the distance transform. The inner loop is the one piece of this chapter that looks like nothing else in the book — no probability, no geometry, just a stack of parabolas — and it is worth typing out once in your life.

use ndarray::{Array2, Axis};

const BIG: f64 = 1e12;

/// `dt_1d` — Felzenszwalb & Huttenlocher's lower envelope of parabolas.
///
/// Every index is pushed once and popped at most once, so this is Θ(n). The
/// arithmetic is exact in f64 for grids far larger than any robot needs.
fn distance_transform_1d(f: &[f64], out: &mut [f64]) {
    let n = f.len();
    let mut v = vec![0usize; n];     // parabolas currently on the envelope
    let mut z = vec![0.0f64; n + 1]; // where consecutive ones cross
    let mut k = 0usize;
    v[0] = 0;
    // The sentinel −∞ is not decoration: it is what stops `k` underflowing in
    // the pop loop below, since no finite crossing can be left of it.
    z[0] = -BIG;
    z[1] = BIG;

    for q in 1..n {
        let mut s = intersect(f, q, v[k]);
        while s <= z[k] {
            k -= 1;                   // the top parabola is now fully hidden
            s = intersect(f, q, v[k]);
        }
        k += 1;
        v[k] = q;
        z[k] = s;
        z[k + 1] = BIG;
    }

    k = 0;
    for q in 0..n {
        while z[k + 1] < q as f64 {
            k += 1;
        }
        let dq = q as f64 - v[k] as f64;
        out[q] = dq * dq + f[v[k]];
    }
}

#[inline]
fn intersect(f: &[f64], p: usize, q: usize) -> f64 {
    let (pf, qf) = (p as f64, q as f64);
    ((f[p] + pf * pf) - (f[q] + qf * qf)) / (2.0 * pf - 2.0 * qf)
}

/// `esdf_from_tsdf` — seed with the TSDF's own sub-cell offsets, then sweep.
///
/// Seeding with (D/r)² rather than with a binary mask is what buys sub-cell
/// accuracy: a cell holding D = 1.7 cm is 1.7 cm from the surface, not 0.
pub fn esdf_from_tsdf(tsdf: &Tsdf2, min_weight: f32, band_cells: f64) -> Esdf2 {
    let r = tsdf.resolution();
    let band = band_cells * r;
    let mut f = Array2::from_elem(tsdf.dim(), BIG);

    for (ij, &d) in tsdf.values().indexed_iter() {
        if tsdf.weight(ij) < min_weight || (d as f64).abs() > band {
            continue;
        }
        let sub = d as f64 / r;
        f[ij] = sub * sub;
    }

    sweep(&mut f, Axis(0));  // rows …
    sweep(&mut f, Axis(1));  // … then columns: separability makes this exact
    Esdf2::from_squared(f, tsdf, r)
}

impl Esdf2 {
    /// The Chapter 20 / 23 contract: distance and gradient, both O(1).
    pub fn distance(&self, p: Point2<f64>) -> f64 { self.bilinear(p) }

    /// Away from the medial axis ‖∇d‖ = 1, so this is a pure direction.
    pub fn gradient(&self, p: Point2<f64>) -> Vector2<f64> {
        let h = self.resolution;
        Vector2::new(
            (self.bilinear(p + Vector2::x() * h) - self.bilinear(p - Vector2::x() * h)) / (2.0 * h),
            (self.bilinear(p + Vector2::y() * h) - self.bilinear(p - Vector2::y() * h)) / (2.0 * h),
        )
    }
}

Finally the cross-check, because a distance field that is subtly wrong is worse than no distance field at all. parry2d will compute exact point-to-polyline distance with a BVH; the ESDF must agree with it.

use parry2d::query::PointQuery;
use parry2d::shape::Polyline;

/// The ESDF approximates distance-to-contour. `parry2d` computes it exactly.
/// Where they disagree by more than a cell, the ESDF must be *conservative* —
/// too small — because a planner that overestimates clearance kills robots.
#[test]
fn esdf_matches_parry_within_a_cell_and_errs_safe() {
    let (tsdf, contour) = crate::fixtures::apartment_5cm();     // 200 scans, seed 0xC0FFEE
    let esdf = ch19_maps::esdf::esdf_from_tsdf(&tsdf, 0.5, 1.5);
    let mesh = Polyline::new(contour.vertices, Some(contour.indices));

    let mut worst = 0.0f32;
    for p in crate::fixtures::observed_free_probes(4_000) {
        let ours = esdf.distance(p.cast::<f64>()) as f32;
        let truth = mesh.distance_to_local_point(&p, /* solid = */ false);
        let err = ours - truth;
        assert!(err < 0.05, "ESDF overestimated clearance by {err} m at {p}");
        worst = worst.max(err.abs());
    }
    // Measured: median 0.030 m, p99 0.075 m, max 0.282 m at one doorway lip.
    assert!(worst < 0.30);
}

The frontier: rendering as a measurement model

Everything so far estimates geometry from ranges. The last five years of mapping research have been about estimating geometry and appearance from images, using neural radiance fields (Mildenhall et al., ECCV 2020) and 3D Gaussian splatting (Kerbl et al., SIGGRAPH 2023). The literature reads like a different subject. It is not.

The toy is 80 bins, ten rays, and plain gradient descent — no network, no rasterizer, a couple of hundred lines — and it reproduces the three behaviors that dominate the literature. Density sharpens only where transmittance survives. The fitted residual falls to the noise floor while the held-out rays sometimes do not, which is the geometry–appearance ambiguity in its simplest possible form. And on an unlucky initialization the field parks density in the wrong place and stays there, because Step 5's gradient cannot see past an opaque bin it invented.

Putting it together: the artifact Part VI consumes

Everything above, measured on one log — Rusty's 200-scan lap of the Apartment at 5 cm, seed 0xC0FFEE, poses from Chapter 16's optimized graph — with the port that runs the widgets on this page.

Read the bold entries: four different winners in four columns. The cheapest map on the page is the extracted contour, which cannot answer either probe cheaply. The fastest to update is the quadtree, which costs five times the memory of the flat grid it was supposed to compress. The fastest occupancy lookup is the flat grid, which cannot answer a distance query without searching. And the query that actually runs a planner belongs to the distance field, which costs twelve times the grid's memory to buy a sixtyfold speedup on it. There is no row that dominates, and there was never going to be.

The handoff. What Part VI receives from this chapter is one file — esdf.bin, 173 kB, a f32 plane plus an origin and a resolution — and one guarantee: $(d, \nabla d)$ in $O(1)$, eikonal to within about 7% away from the medial axis, and conservative where it is wrong. Chapter 20 uses it as a collision oracle, Chapter 23 differentiates it as an obstacle cost, and Chapter 24 uses the weight plane $W$ — the thing that makes this a filter rather than a picture — to find frontiers.

The honesty note this chapter owes you. Per-voxel independence is Chapter 13's structural lie, and every representation here inherits it: OctoMap estimates each node alone, TSDF fusion estimates each voxel alone, and neither has a way to say "these two cells are both wrong in the same direction because the pose was off." The principled alternative is a correlated field — Gaussian process implicit surfaces, and in particular the log-GP formulation of Wu et al. (2021), which recovers a genuine Euclidean distance field with calibrated uncertainty by solving the eikonal equation in the transformed space. It costs a dense covariance and is currently practical at room scale rather than building scale. When someone makes it cheap, this chapter changes.

Exercises

1. Foundation exerciseFDifficulty 2 of 3Finish D2: the steady-state variance of a clamped voxel

   D2 stops after showing that the clamp turns fusion into an exponentially weighted average with forgetting factor $\lambda = W_{\max}/(W_{\max}+w)$. Complete it. (a) Show that the fused estimate under repeated unit-weight observations of a static truth has steady-state variance $\Var[D_\infty] = \sigma^2 / (2W_{\max} + w)$. (b) Compare with the unclamped filter's $\sigma^2/W_t$ and state, in one sentence, what the clamp costs you and what it buys. (c) At which $W_{\max}$ does a $W_{\max}$-clamped voxel have the same variance as an unclamped voxel after 50 unit-weight scans?

   Hint

   Write the recursion as $D_t = (1-K)D_{t-1} + K d_t$ with $K$ constant, take variances of both sides assuming independent observations, and solve the resulting fixed point $V = (1-K)^2 V + K^2 \sigma^2/w$.

2. Foundation exerciseFDifficulty 2 of 3Where hierarchy pays

   Using D1's ratio $b_{\text{node}} c_d S r / V$: (a) reproduce the Apartment's crossover $r^\star = 1.5$ cm from $S = 180.6$ m, $V = 108$ m², $b_{\text{node}} = 20$ B; (b) redo it in three dimensions for a 3 m ceiling, where a node needs eight child indices; (c) find the environment shape (as a ratio $V/S$) at which a 5 cm octree first beats a dense byte array, and name a real robot workspace that qualifies.

3. Foundation exerciseFDifficulty 3 of 3Why the zero crossing survives a biased observation

   §3.2 claims the projective observation $d = z - s$ is biased by $1/\cos\theta$ away from the surface but unbiased at it. (a) Prove the claim for a single planar surface and a single beam. (b) Now fuse two beams meeting the same plane at $\theta_1 = 0$ and $\theta_2 = 60°$ with equal weights, and find the zero crossing of the fused linear field along a line perpendicular to the surface. Is it still exact? (c) What does your answer predict about reconstruction error on walls seen only at a grazing angle — and how does Voxblox's $\cos\theta$ weight term address it?

4. Conceptual exerciseCDifficulty 1 of 3Predict the ghost, then watch it

   Using $\lambda = W_{\max}/(W_{\max}+w)$ from D2, predict how many re-observations it takes for the teleported chair's ghost to lose half its distance error at $W_{\max} \in \{4, 24, 64\}$. Now open w19.1, click the chair's cell to inspect it, press move the chair, and count. Where does your prediction fail, and why? (The weight a carving update contributes is not 1.)

5. Conceptual exerciseCDifficulty 2 of 3Make each representation win

   In w19.2, find a query workload under which each of the four panes is the winner at some point, and write a one-sentence description of a real robot task with that workload. One pane never takes the green frame under any of the three workloads: name it, and say — using D1, and the cost of descending a tree instead of indexing an array — exactly what it is paying for and what it would take to make that payment worthwhile.

6. Practical exercisePDifficulty 2 of 3A fifth representation

   Implement MapRepr for a k-d tree over raw scan endpoints and add it to the gallery harness. It should win the distance query at low point counts and lose it as the cloud grows. Report the crossover against the ESDF, and then answer the real question: why do production systems keep point clouds as the log and never as the primary map?

7. Practical exercisePDifficulty 3 of 3Two channels beat one

   Extend the 1-D renderer from depth-only to depth plus reflectance. Show that on the seed where the depth-only fit parks density in the wrong place (w19.4, re-roll until the held-out error stays high while the training residual collapses), the two-channel version escapes — and explain which term of D4 Step 5's gradient the extra channel repaired. Then find a seed where two channels are still not enough, and say what a third would have to measure.

References

1. Curless, B. and Levoy, M. (1996) A Volumetric Method for Building Complex Models from Range Images. SIGGRAPH '96, 303–312.doi:10.1145/237170.237269 (opens in a new tab)

   The origin of TSDF fusion, and the source of this chapter's epigraph. Appendix A sketches the least-squares optimality that D2 turns into a recursive filter.

2. Lorensen, W. E. and Cline, H. E. (1987) Marching Cubes: A High Resolution 3D Surface Construction Algorithm. SIGGRAPH '87, Computer Graphics 21(4), 163–169.doi:10.1145/37401.37422 (opens in a new tab)

   The extraction step of §3.4, in three dimensions. The ambiguous cases this chapter dodges in 2-D are the reason the follow-up literature exists.

3. Felzenszwalb, P. F. and Huttenlocher, D. P. (2012) Distance Transforms of Sampled Functions. Theory of Computing 8(19), 415–428.link to Distance Transforms of Sampled Functions (opens in a new tab)

   D3's lower-envelope algorithm, with the amortized Θ(n) argument. The clearest exposition of the trick that makes ESDFs affordable.

4. 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), 189–206.doi:10.1007/s10514-012-9321-0 (opens in a new tab)

   The hierarchical representation of §3.1, including the clamping-and-pruning argument D1 formalizes and the node layout the memory bound counts.

5. Oleynikova, H., Taylor, Z., Fehr, M., Siegwart, R., and Nieto, J. (2017) Voxblox: Incremental 3D Euclidean Signed Distance Fields for On-Board MAV Planning. IEEE/RSJ IROS 2017, 1366–1373.doi:10.1109/IROS.2017.8202315 (opens in a new tab)

   The system that made ESDF-from-TSDF standard practice in robotics, and the source of the weighting choices (inverse-square range, incidence angle) that D2 Step 5 reads as variance modeling.

6. Reijgwart, V., Cadena, C., Siegwart, R., and Ott, L. (2023) Efficient Volumetric Mapping of Multi-Scale Environments Using Wavelet-Based Compression. Robotics: Science and Systems XIX.doi:10.15607/RSS.2023.XIX.065 (opens in a new tab)

   Where §3.1 goes next: wavelets instead of a plain octree, keeping multi-resolution queries while fixing the memory constant that makes this chapter's quadtree lose.

7. Millane, A., Oleynikova, H., Wirbel, E., Steiner, R., Ramasamy, V., Tingdahl, D., and Siegwart, R. (2024) nvblox: GPU-Accelerated Incremental Signed Distance Field Mapping. IEEE ICRA 2024.link to nvblox: GPU-Accelerated Incremental Signed Distance Field Mapping (opens in a new tab)

   The production path for everything in §3.3 and §3.4: the same recursion, moved to the GPU, with measured speedups of two orders of magnitude on ESDF construction.

8. Tosi, F., Zhang, Y., Gong, Z., Sandström, E., Mattoccia, S., Oswald, M. R., and Poggi, M. (2024) How NeRFs and 3D Gaussian Splatting are Reshaping SLAM: a Survey. arXiv:2402.13255.link to How NeRFs and 3D Gaussian Splatting are Reshaping SLAM: a Survey (opens in a new tab)

   The frontier map for this chapter's last section. Read it instead of any single system paper: it is maintained, and it states each system's assumptions in the terms D4 uses.