Depth and point clouds

Lesson 02 handed us the machinery to place things in 3D — rotate and translate cameras and objects on the manifold of valid motions, SE(3). But you can only place data you have. This lesson answers the most concrete question in the whole track — where does 3D data actually come from? — and then performs the single operation that turns a sensor's raw output into the rawest representation from lesson 01: a point cloud. That operation, back-projection through K^-1, is the bridge that makes "depth map" and "point cloud" two views of the same thing.

The plan

Four moves. (1) Survey how we acquire 3D — every sensor, passive or active, ultimately reports per-pixel depth or range; we sort the families (stereo, structured light, time-of-flight, LiDAR) by principle, range, density, and where they fail. (2) The key operation: back-projection, lifting a depth map D(u,v) through the inverse intrinsics into camera-frame 3D points, then into world coordinates with the SE(3) pose from lesson 02 — with worked numbers. (3) Depth parameterizations — metric depth, disparity, inverse depth — and the arithmetic reason far is hard: triangulation error grows like Z², which is why inverse depth is the state variable of choice in SLAM and bundle adjustment. (4) The point cloud representation itself — an unordered set with no connectivity — and its core operations: neighbor search, normal estimation, voxel downsampling, outlier removal. Those normals are the input to lesson 04's ICP and lesson 05's surface reconstruction, so this lesson quietly sets up the next two.

1 · How we acquire 3D — the sensor families

There is a unifying fact that makes the sensor zoo tractable: every 3D sensor, however it works, ultimately produces per-pixel (or per-return) depth or range. It does not hand you a mesh, an SDF, or a scene graph — it hands you distances. What differs is how the distance is measured, and that "how" decides the range, the density, the failure modes, and the price. Split the field by whether the sensor emits its own light.

Passive sensors use only ambient light — ordinary cameras.

Stereo. Two cameras a known baseline B apart see the same point at slightly different pixel columns; that shift is the disparity d. From CV lesson 05, similar triangles give depth directly:
Z = f·B / d .
Near objects have large disparity (easy, precise); far objects have vanishing disparity (hard, then hopeless — the seed of §3). Passive stereo needs texture to match on and inherits the whole correspondence problem.
Multi-view. Generalize stereo to many cameras (structure-from-motion, MVS from CV lesson 05). More views, better conditioning, but the same passive-triangulation physics underneath.

Active sensors emit light and measure what comes back — which buys them the ability to work on textureless surfaces and, for some, in the dark.

Structured light. Project a known pattern — stripes, or a dense speckle of dots — and watch how it deforms on the surface. Each observed pattern element, matched to its known emitted position, gives a triangulation baseline between projector and camera, so depth is recovered exactly as in stereo but with the projector playing the role of the second camera (and solving the correspondence problem for free, since the pattern is designed to be identifiable). This is the original Kinect v1. It fails in sunlight (ambient IR swamps the projected pattern) and on shiny, very dark, or transparent surfaces (the pattern reflects specularly, is absorbed, or passes through).
Time-of-flight (ToF). Emit a light pulse or modulated wave and measure the round-trip time (or the phase shift of the returning modulation) per pixel; distance is Z = c·t/2. This is the Kinect v2. It gives a dense depth image and works in the dark, but suffers multipath (light bouncing via a second surface arrives late and biases the reading, rounding off concave corners) and motion errors (a moving object smears across the exposure). Phase-based ToF also has a periodic ambiguity range beyond which distances wrap around.
LiDAR. A pulsed laser plus scanning — mechanical (a spinning head) or solid-state — sweeps the beam and times each return. Long range, works outdoors in full sun, and is geometrically precise. The costs: it is sparse (a ring of points, not a dense image) and expensive. And because a spinning sensor takes tens of milliseconds to complete a sweep, a LiDAR on a moving vehicle scans different points from different sensor poses — the cloud is rolling-distorted and must be motion-compensated by transforming each return with the pose at its own timestamp (using exactly the SE(3) interpolation from lesson 02).

The families on the axes that decide which one a system reaches for:

Sensor	Principle	Range	Density	Outdoor?	Cost / notes
Stereo	passive triangulation of disparity, Z=fB/d	near–mid (falls off as Z²)	dense where textured	yes	cheap; needs texture; correspondence problem
Structured light	project known pattern, triangulate its deformation	short (≈0.5–4 m)	dense	no (sun swamps IR)	cheap (Kinect v1); fails on shiny/dark/clear
Time-of-flight	round-trip time / phase of emitted light, per pixel	short–mid	dense	limited	mid (Kinect v2); multipath, motion blur, wrap
LiDAR	pulsed laser + scanning, time each return	long (10s–100s m)	sparse	yes	expensive; needs motion compensation when moving

Whatever the row, the output reduces to the same object: a map from image location to a distance. The next section turns that map into geometry.

2 · Depth map → point cloud (back-projection)

This is the operation the whole lesson turns on. A depth map D(u,v) stores, at each pixel (u,v), the metric depth of the surface seen there — depth along the optical axis, i.e. the Z coordinate in the camera frame. Projection (CV lesson 04) collapsed a 3D point onto a pixel and threw its depth away; back-projection restores it, because the depth map hands the missing Z right back.

Recall the pinhole forward model with intrinsics

K = [ f_x, 0, c_x ; 0, f_y, c_y ; 0, 0, 1 ] ,

which maps a camera-frame point (X,Y,Z) to a pixel by u = f_x·X/Z + c_x, v = f_y·Y/Z + c_y. Invert those two equations for the point, given that we now know Z = D(u,v):

X = (u − c_x)/f_x · D , Y = (v − c_y)/f_y · D , Z = D .

The pattern "subtract the principal point, divide by the focal length, scale by depth" is exactly the action of K^-1 on the homogeneous pixel. In vector form the whole operation is one line:

p_cam = D · K^-1 [ u ; v ; 1 ] .

Read K^-1[u,v,1]^ᵀ as the direction of the viewing ray through that pixel (in camera coordinates), and D as how far to walk along it. Do this for every pixel and you have converted the entire depth image into a camera-frame point cloud — one 3D point per pixel. This is the bridge: a depth map is a point cloud in disguise (a structured, gridded one), and a point cloud is a depth map that has forgotten its pixel grid. Meshing tools, ICP (lesson 04), and surface reconstruction (lesson 05) all consume the cloud; the grid was just how the sensor happened to deliver it.

To put the cloud in world coordinates — so that clouds from different viewpoints live in one frame and can be fused or aligned — apply the camera-to-world pose T=(R,t) built in lesson 02:

p_world = R·p_cam + t .

That is the entire pipeline from sensor to placed 3D geometry: D(u,v) \xrightarrow{K^{-1}} p_{cam} \xrightarrow{(R,t)} p_{world}. Everything downstream in the track is operations on the resulting set of points.

Worked number

Take f_x=f_y=500, c_x=320, c_y=240 (a 640×480 camera), and the pixel (u,v)=(420,240) observed at depth D=2.0 m. Then X = (420−320)/500 · 2.0 = (100/500)·2.0 = 0.40 m, Y = (240−240)/500 · 2.0 = 0, and Z = D = 2.0 m. The point is (0.40, 0, 2.0) m in the camera frame: it sits on the horizontal centre line (because v=c_y), two metres ahead, and 40 cm to the right of the optical axis. Sanity check by re-projecting: u = 500·(0.40/2.0)+320 = 500·0.20+320 = 420 ✓.

The trap — a wrong K silently shears the whole cloud

Back-projection is only as correct as K. Plug in the wrong focal length — say the calibrated f=500 but you resized the image to half resolution and forgot to halve f and the principal point — and every X,Y is scaled by the wrong factor. The result is not random noise; it is a systematic shear/scale of the entire reconstruction: straight walls come out slanted, right angles come out oblique, and the cloud looks plausible enough that nobody notices until it fails to register (lesson 04) or the metric measurements are quietly off. Intrinsics that don't match the actual image the pixels came from are the twin of lesson 02's forgotten-R^ᵀ frame bug: a silent, consistent distortion, not a crash. The widget below lets you feed a wrong f and watch the cloud shear.

Depth-along-Z vs range-along-ray. One convention trap worth stating explicitly. The formulas above assume D is depth — the Z component, measured along the optical axis. Some sensors (notably LiDAR and some ToF) natively report range r — the Euclidean distance along the ray from the sensor to the point. These differ: a point off-axis is farther in range than in depth. To use range in the formulas, convert it to depth by dividing out the ray length,

Z = r / ‖K^-1[u,v,1]^ᵀ‖ ,

which projects the along-ray distance onto the axis. Treating a range image as a depth image (or vice versa) bows a flat wall toward the camera at the edges — another silent, systematic error.

3 · Depth parameterizations, and why far is hard

Depth can be written three ways, and the choice is not cosmetic — it decides how error behaves and whether an optimizer stays well-conditioned.

Metric depth Z — distance in metres. Intuitive, but its uncertainty is wildly non-uniform (below).
Disparity d ∝ 1/Z — the raw stereo measurement, d = fB/Z. This is what the sensor actually observes with roughly uniform noise.
Inverse depth ρ = 1/Z — the reciprocal, proportional to disparity. This is the standard state variable in modern SLAM and bundle-adjustment back-ends, for three concrete reasons.

(a) Error is uniform in disparity, so metric error grows like Z². Stereo matching localizes disparity to roughly a constant Δd (about a fixed fraction of a pixel), independent of distance. Propagate that constant disparity error through Z = fB/d. Differentiating, dZ/dd = −fB/d² = −Z²/(fB), so

ΔZ ≈ (Z² / (f·B)) · Δd .

Depth uncertainty grows with the square of depth: precise near, hopeless far. In inverse-depth coordinates this same fact reads as uniform uncertainty — ρ = d/(fB) so Δρ = Δd/(fB) is constant — which is exactly why estimators parameterize points by ρ: the noise model is Gaussian in ρ, not in Z.

Worked number — the Z² blow-up

A typical stereo rig: f=500 px, baseline B=0.10 m, disparity precision Δd=0.25 px, so fB = 50 px·m. At Z=2 m: ΔZ ≈ (2²/50)·0.25 = (4/50)·0.25 = 0.02 m — 2 cm, excellent. At Z=10 m: ΔZ ≈ (100/50)·0.25 = 0.5 m — half a metre. At Z=20 m: ΔZ ≈ (400/50)·0.25 = 2.0 m. Same sensor, same disparity noise: the depth error went from 2 cm to 2 m as depth grew 10×, exactly the Z² law. Doubling the baseline or focal length halves every one of these.

(b) Inverse depth represents points at infinity gracefully. A distant landmark — a mountain, a star, the vanishing point of a corridor — has Z → ∞, which blows up any metric-depth state. But ρ = 1/Z → 0 is perfectly finite and well-behaved. Inverse depth lets a SLAM system carry a bearing-only, effectively-infinite landmark as ρ = 0 (a pure direction with no parallax yet) and smoothly "pull it in" to a finite depth as parallax accumulates over frames. Metric depth cannot even express such a point.

(c) Inverse depth linearizes the projection. The projection u = f·X/Z + c_x is nonlinear in Z (it's a reciprocal), which makes Jacobians ill-conditioned across a wide depth range. Written in ρ, the map u = f·X·ρ + c_x is linear in ρ — far friendlier for the Gauss–Newton steps that bundle adjustment (CV lesson 05) takes, and consistent with the uniform-in-ρ noise model from point (a). Between the well-behaved uncertainty, the graceful handling of infinity, and the linearized Jacobian, inverse depth is the natural coordinate; metric depth is what you convert to only at the very end for display.

4 · The point cloud representation and its core operations

Back-projection delivered a point cloud; now characterize what we actually have. A point cloud is an unordered set {p_i} ⊂ ℝ³, optionally with per-point color or normal. Its defining properties — and its inconveniences — all follow from what it lacks:

Unordered. No canonical indexing; permuting the points is the same cloud. (This is why networks that consume clouds, e.g. PointNet, must be permutation-invariant.)
Irregular density. Near surfaces are sampled densely, far ones sparsely — a direct consequence of §3's Z² behaviour and perspective. Density carries no meaning; it is a sensor artefact.
No connectivity. Unlike a mesh, points don't know their neighbors; there are no edges or faces.
No "inside." A cloud is a bag of surface samples, not a solid. There is no volume, no notion of interior, no watertight boundary — that is what surface reconstruction (lesson 05) has to build.

Because connectivity and structure are absent, the core operations must first recover local structure from raw coordinates. Four are foundational.

op — spatial index

Neighbor search

op — local geometry

Normal estimation

op — resampling

Voxel downsampling

op — cleaning

Outlier removal

(a) Neighbor search. Almost every operation needs "the points near this point." Brute force is O(n) per query, O(n²) overall — untenable for millions of points. A kd-tree or octree partitions space so that k-nearest-neighbor and radius queries run in O(\log n). This index is the substrate the other three operations (and ICP's correspondence step, lesson 04) are built on.

(b) Normal estimation. A surface normal is needed for shading, for point-to-plane ICP (lesson 04), and for Poisson reconstruction (lesson 05) — but a raw cloud has none, so we estimate it from local geometry. For each point, take its k nearest neighbors (via (a)) and assume that locally the surface is planar. Form the 3×3 covariance matrix of that neighborhood,

C = (1/k) Σ_j (p_j − p̄)(p_j − p̄)^ᵀ , p̄ = mean of the neighbors ,

and take its eigendecomposition. The two large eigenvalues span the local tangent plane (the directions of greatest spread); the eigenvector with the smallest eigenvalue points in the direction of least variance — perpendicular to the best-fit plane. That least-variance eigenvector is the surface normal. (Equivalently: the neighborhood is a flat pancake, and the normal is the thin direction.) The relative sizes of the eigenvalues also diagnose the local shape — three similar values means an isotropic blob (a corner or noise), one tiny value means a clean surface, two tiny values means an edge.

Normal orientation is ambiguous

An eigenvector is defined only up to sign — the covariance can't tell "outward" from "inward," so raw estimated normals point randomly to either side of the surface. They must be flipped to a consistent side, usually by requiring each normal to face toward the sensor/viewpoint (the direction the point was seen from), or by propagating orientation across neighbors so adjacent normals agree. Skip this and point-to-plane ICP and Poisson reconstruction (which both need signed normals) will fight themselves.

(c) Voxel-grid downsampling. To fix the irregular density and cut point counts, overlay a regular 3D grid of voxels of some edge length and keep exactly one point per occupied voxel (its centroid, or a representative). This uniformizes density, bounds the point count regardless of how densely the sensor oversampled near regions, and speeds up everything downstream. The voxel size is the accuracy/size knob.

(d) Statistical outlier removal. Sensors emit stray points — flying pixels at depth discontinuities, multipath returns (§1). For each point, compute the mean distance to its k neighbors; points whose mean neighbor distance is a statistical outlier (say, more than a few standard deviations above the global mean) are isolated flecks and get dropped. This cleans the cloud before it poisons normal estimation or registration.

Note the dependency chain this sets up: neighbor search underlies normals, and normals feed directly into lesson 04 (point-to-plane ICP, which minimizes distance along the surface normal) and lesson 05 (Poisson surface reconstruction, which integrates a normal field into a watertight surface). The unglamorous operations here are the load-bearing inputs to the next two lessons.

Depth map → point cloud back-projection

A synthetic depth map D(u,v) over a 26×26 grid — a slanted ground plane with a raised Gaussian bump — is back-projected with the current focal length f via X=(u−c_x)/f·D, Y=(v−c_y)/f·D, Z=D, then rotated by the azimuth slider and drawn. Points are colored near→far. Drag f away from its calibrated 500 and watch the whole cloud shear and scale — the §2 trap made tangible (a wrong K is a silent, systematic distortion). Rotate the azimuth to confirm it is genuinely 3D; raise the bump to change the scene.

focal f (px): 500 azimuth: 35° bump height: 80

Points in cloud

—

Focal f used

—

Calibrated f

500

Sample pixel → (X,Y,Z) m

—

Show the core JS

// synthetic scene depth: a slanted ground plane + a Gaussian bump, all in metres.
// (u,v) run over a GRID×GRID pixel grid; cx,cy are the principal point.
function depthAt(u, v){
  var base = 2.2 + 0.010*(v - cy);          // ground plane, farther toward the top
  var du = u - (cx + 40), dv = v - (cy - 20);
  var bump = (bumpH/150) * 1.1 * Math.exp(-(du*du + dv*dv)/(2*55*55));
  return base - bump;                        // bump rises toward the camera (smaller Z)
}

// BACK-PROJECTION: lift every pixel to a camera-frame 3D point with the CURRENT f.
// p_cam = D · K^{-1} [u,v,1]^T  ==>  X=(u-cx)/f·D,  Y=(v-cy)/f·D,  Z=D.
for (var v = 0; v < GRID; v++) for (var u = 0; u < GRID; u++){
  var pu = u*stride, pv = v*stride, D = depthAt(pu, pv);
  var X = (pu - cx)/f * D;                    // wrong f  ==>  X,Y scaled  ==>  cloud shears
  var Y = (pv - cy)/f * D;
  var Z = D;
  cloud.push([X, Y, Z]);
}

// render: rotate by azimuth about the vertical axis, then a FIXED orthographic view.
// (reuses lesson 02's project(): drop depth for screen x/y, keep it for draw order & size)
function project(p){
  var x = p[0]*Math.cos(az) + p[2]*Math.sin(az);   // azimuth spin
  var z = -p[0]*Math.sin(az) + p[2]*Math.cos(az);
  var y = p[1];
  var y2 = y*Math.cos(EL) - z*Math.sin(EL);         // fixed elevation tilt
  var z2 = y*Math.sin(EL) + z*Math.cos(EL);
  return { sx: cxScreen + x*scale, sy: cyScreen - y2*scale, depth: z2 };
}
cloud.map(project).sort(function(a,b){ return a.depth - b.depth; })  // painter's order
     .forEach(function(q){ /* colour near→far, radius ~ 1/depth, fillRect/arc */ });

Where this points next

We can now manufacture 3D data: name the sensor, read its depth or range, back-project through K^-1 into a camera-frame cloud, and place it in the world with the SE(3) pose from lesson 02 — armed with normals, a clean density, and the right depth coordinate. But a single scan sees one side of the scene from one viewpoint. Real reconstruction fuses many scans, and those scans arrive in different coordinate frames whose relative pose is unknown. Lesson 04 solves that: registration, and its workhorse ICP (Iterative Closest Point) — alternating "find correspondences via the kd-tree from §4" with "solve for the SE(3) that best aligns them," retracting on the manifold exactly as lesson 02 prescribed. The point-to-plane variant uses the very normals we estimated in §4. This lesson built the pieces; the next one snaps them together. Then CV lesson 05's SLAM and lesson 05's surface reconstruction take over.

Takeaway

Every 3D sensor ultimately reports depth or range per pixel/return: passive stereo/multi-view triangulate disparity (Z=fB/d); active structured light triangulates a projected pattern (fails in sun), ToF times emitted light per pixel (dense, but multipath/motion), and LiDAR scans a laser (long-range, sparse, needs motion compensation). The key operation is back-projection: p_cam = D·K^-1[u,v,1]^ᵀ (i.e. X=(u−c_x)/f_x·D, etc.), then p_world=Rp_cam+t — making depth map and point cloud two views of one thing. A wrong K silently shears the whole cloud, and range must be divided by ray length to become depth. Because triangulation error is uniform in disparity, metric depth error grows like Z², so SLAM/BA use inverse depth ρ=1/Z (uniform noise, handles infinity, linearizes projection). A point cloud is an unordered, connectivity-free, hollow set; its core ops are kd-tree neighbor search, normal estimation (smallest-eigenvalue eigenvector of the neighborhood covariance, sign-disambiguated toward the viewpoint), voxel downsampling, and outlier removal — and those normals are the direct input to ICP (lesson 04) and Poisson reconstruction (lesson 05).

Interview prompts

Name the main 3D sensor families and one failure mode of each. (§1 — stereo: needs texture, error ∝Z²; structured light: dies in sunlight, shiny/dark/clear surfaces; ToF: multipath and motion blur; LiDAR: sparse, needs motion compensation.)
Write the operation that turns a depth map into a point cloud, and to world coordinates. (§2 — X=(u−c_x)/f_x·D, Y=(v−c_y)/f_y·D, Z=D, i.e. p_cam=D·K^-1[u,v,1]^ᵀ; then p_world=Rp_cam+t.)
You resized images by half but reused the original intrinsics — what happens to the reconstruction? (§2 — the wrong f/principal point systematically scales/shears the whole cloud; a silent distortion, not a crash. Also: range vs depth-along-Z must be reconciled by dividing by ray length.)
Why does stereo depth error grow with distance, and how fast? (§3 — disparity noise is roughly constant, and ΔZ ≈ (Z²/fB)·Δd, so error grows like Z²; 10× the depth is 100× the error.)
Why do SLAM and bundle adjustment parameterize points by inverse depth ρ=1/Z? (§3 — uniform (Gaussian) uncertainty in ρ, represents points at infinity as ρ=0 without blowing up, and linearizes the projection for Gauss–Newton.)
How do you estimate a normal on a raw point cloud, and what's the catch? (§4 — take k neighbors, eigendecompose their 3×3 covariance, the smallest-eigenvalue eigenvector is the normal; catch: sign/orientation is ambiguous and must be flipped to face the sensor/viewpoint.)