Networks that eat 3D

Lesson 11 ended on a prior too big to store as a matrix and a fitted map that broke when the same nine readings arrived in another order. A point cloud is a set, so its answer cannot depend on order, and the form that guarantees this is a shared per-point map followed by an order-free pool, which lesson 11's closed form already has. A volume is almost empty, so work should follow the occupied cells, and a driving scene has a vertical axis worth collapsing. Such a network returns one vector per input, and when two answers fit the data that vector is their average, an object that does not exist.

The thesis, here

A network should not have to learn what the data already guarantee. A point cloud has no order, a volume is mostly empty, a road has an up. Put them into the form of the network (a shared per-point map and a symmetric pool, work only where something is, a collapsed vertical axis) and its examples and its arithmetic go to everything else. What it then returns is one answer per input, and trained by squared error that answer is the mean of everything that fits.

Linear position

Forced by: The missing information comes from a prior learned over many scenes, and a prior has to live in a network. But a 3D input is not an image: a point cloud is an unordered set, a voxel grid is almost entirely empty, a LiDAR sweep has a different length every time. What must a network respect to learn from 3D data, and what can it then answer?
New idea: build the symmetries of 3D data into the network's form: f(X) = ρ(pool_i φ(x_i)) for a set, work only at occupied sites for emptiness, a collapsed vertical axis for driving scenes. Trained by squared error, such a network answers with one vector per input, the mean of what fits.
Forces next: A trained network returns one answer per input, the average of everything compatible with what it saw. That is fine for "where is the car" and wrong for "what is behind the mug": the average of two plausible backs is a back that cannot exist. How do we produce a scene that agrees with the data and is also a valid sample of the kinds of scenes there are?

The plan

Six moves. (1) Give a plain network a point cloud and reorder it. (2) Derive the form a set function must have, and find it already inside lesson 11. (3) Read what the max pool keeps and what it cannot see. (4) Count what a grid costs when space is empty. (5) Collapse the axis gravity picked. (6) Ask the network a question that has two answers.

1 · A plain network, and an order it should not care about

Lesson 11's fitted map read nine numbers in a fixed order. A sensor returns something else: points, each an (x, z), in whatever order its driver emits them, and a different number each sweep. Take two kinds of object built from lesson 11's traits, ovals (the elongated trait) and trefoils (the three-lobed trait), in units of their mean radius (1.15 m, as in lesson 11), and let a scanner return 32 points on the outline in sweep order (increasing azimuth) with 2.3 cm of radial noise. Give the 64 coordinates to the plainest network there is, a multilayer perceptron with hidden layers of 32 and 16, trained for 300 steps of Adam on 16 freshly drawn clouds per step, and test it on 100 clouds it has not seen.

the same 100 test clouds	plain MLP
points listed in sweep order, as trained	91% right
the same points, shuffled	56% right (guessing: 50%)
how far its answer P(trefoil) moves when a cloud is reshuffled (mean over the 100 clouds and 24 shuffles of each)	0.46

The network did what it was shown. A set of 32 points can be listed in 32! = 2.6×10³⁵ orders, training saw 4,800 clouds, each in one of them, and nothing told the network that the orders are one cloud. The baton named two more difficulties: a list has a fixed length, so a sweep with 31 returns is not an input, and a voxel grid, which would fix both order and length, is almost all empty, which §4 prices. First the order: what form can a function of a set have?

2 · The form a set function must take

Ask three things of f(X) for a cloud X = {x₁, …, x_n}: the same answer for every ordering, any n, and a gradient to train it. One construction gives all three. Apply the same map φ to every point, combine the results with an operation that ignores order (a sum, a mean, a max), and let a second map ρ read the pooled vector:

f(X) = ρ( pool_i φ(x_i) )

Reordering the terms of a sum or a max changes nothing, so the first two properties hold by construction, and φ and ρ can be small networks. Does the form lose anything? Lesson 11 holds a case where it loses nothing. With prior mean μ, prior covariance Λ and reading noise σ, its posterior mean is m = (Λ⁻¹ + P)⁻¹(Λ⁻¹μ + b) with P = Σ_j h_jh_j^T/σ² and b = Σ_j h_jr_j/σ², where h_j = (cos ω_j, sin ω_j, …, cos 5ω_j, sin 5ω_j), ω_j is the direction of reading j (lesson 11's φ) and r_j is the reading minus 1. A point (x, z) has polar coordinates (ω, r), so every term depends on one point alone: φ(x_j) = (h_jh_j^T/σ², h_jr_j/σ²), which is 55 + 10 = 65 numbers, and m = ρ(Σ_j φ(x_j)) with ρ the matrix formula. Built this way from 3, 9 or 40 points in any order it equals lesson 11's closed form to within 10⁻¹⁴. "The closed form does not notice order or count" was this fact.

Conversely, Deep Sets (Zaheer et al., 2017) shows that for sets from a countable universe (points that take countably many values, such as the cells of a grid) every permutation-invariant function has the form ρ(Σ φ(x)); for sets of real numbers it proves this only for a fixed size. PointNet (Qi et al., 2017) pools with a max and proves that any set function that is continuous in the Hausdorff distance (moving the points a little changes the set a little) can be approximated by it. Both have a catch about the width of the pooled vector. For the sum, continuous φ and ρ can represent every set function only if the vector is at least as wide as the largest set has points (Wagstaff et al., 2019); PointNet's max pool is the analogous case. Example: with φ(x) = (x, x²) the sets {1, 5, 6} and {2, 3, 7} both pool to (12, 62), and only a third power (342 against 378) tells them apart. Lesson 11's cloud needed 65 numbers whatever n because its likelihood is Gaussian; a general function may need more.

The network here is the smallest of the family: φ is 2 → 16 → 16 with ReLU, the pool is a max, ρ is 16 → 16 → 2, trained for the same 300 steps on clouds of 12 to 48 points in random order. On the same 100 test clouds it is right 98% of the time, in sweep order or shuffled, and reshuffling moves its answer by exactly 0: the max of a list is the same in every order, to the last bit.

3 · What the max keeps, and what it cannot see

Channel c of the pooled vector is max_i φ_c(x_i), attained at one point. The output therefore depends on the cloud only through the points that win at least one of the 16 channels, its critical set. Add or delete a point whose features lie below the current maxima in every channel and nothing changes. In the widget's first cloud 7 of 32 points are critical (over the 100 test clouds 6 to 11, on average 8.3), and keeping only those leaves the output identical. Deleting a critical point moves the pooled vector, but the runner-up takes over and on a densely sampled outline has nearly the same features, so accuracy falls little: with half the points deleted, critical ones first, the PointNet is still right on 92% of the clouds, against 93% when the same number go at random and 98% with none deleted. The widget measures both.

What the pool cannot see is anything that depends on how points sit relative to each other, because φ looks at one point at a time: a dent between two critical points, the flatness of a wall, how many points there are. PointNet++ (Qi et al., 2017) restores neighbourhoods by repeating PointNet on them: farthest-point sampling picks centres, a ball query gathers the points within a radius, a small PointNet summarises each group in the group's own frame, and the levels stack. On the ModelNet40 classification benchmark it reaches 90.7% from coordinates alone, against 89.2% for PointNet.

4 · Space is mostly empty

A convolution shares one small kernel across all positions and costs (cells) × k² multiply-adds per pair of channels, which suits an image because every pixel carries something. Put a LiDAR sweep in a grid and nearly every cell is empty. The widget's room scan (720 beams from one point), binned into cells of 10 cm, fills 478 of 12,144 cells, 3.9%. In three dimensions a surface fills a share of order 1/N of the cells of an N³ grid: a sphere of radius 60 cells in a 128³ grid touches 67,664 of 2,097,152 cells, 3.2%, and the pillar grids of PointPillars (Lang et al., 2019) are about 97% empty.

Count one 3×3 layer under two rules. Dense: every cell is an output, cells × 9 multiply-adds. Sparse: only occupied cells emit, each into the 9 cells of its window, |A| × 9 for |A| occupied cells. The ratio is cells/|A|, the reciprocal of the occupancy whatever the kernel, so the finer the grid, the bigger the saving:

cell	occupied	dense	sparse	dense / sparse
40 cm	96	6,831	864	7.9
20 cm	300	27,324	2,700	10.1
10 cm	478	109,296	4,302	25.4
5 cm	652	437,184	5,868	74.5

The saving has a catch. A sparse layer writes into every cell its window reaches, so the active set grows by the window each layer: 478 sites at the input, then 1,404, 2,245, 3,127 and 4,054 after four layers (8.5 times as many), and four layers cost 65,286 multiply-adds, 6.7 times fewer than dense instead of 25. The remedy is a rule we can define here: a submanifold layer emits only at sites that are already active, and counts a multiply-add where the input site is active too. The set stays at 478, a layer costs 2,088, four layers 8,352: 52 times fewer than dense. The price is that two active sites farther apart than the window never exchange information in a layer, so pooling or strided layers must restore the reach. SECOND (Yan et al., 2018) built an improved sparse convolution into a LiDAR detector and reports a large gain in training and inference speed; MinkowskiNet (Choy et al., 2019) defines a generalised sparse convolution, in an open-source library, and applies it to four-dimensional (space and time) data.

A cloud, a scan, and a front

Three views. A set: an outline of 32 points (ringed: its critical points), the same points in 24 random orders through the plain MLP (red) and the PointNet (blue), and the PointNet's accuracy as points are deleted. A scan: the room's 720 returns on a grid, and what one 3×3 layer costs under the three rules. The hidden back belongs to §6.

points deleted 0 % deleted first grid cell 10 cm view

Show the core JS

  var F = net.F, g = new Float64Array(F), arg = new Int32Array(F), i, f;
  if (net.pool === 'max') {
    for (f = 0; f < F; f++) { var best = -Infinity, bi = 0; for (i = 0; i < n; i++) if (h[i * F + f] > best) { best = h[i * F + f]; bi = i; } g[f] = n ? best : 0; arg[f] = bi; }
...
PN.critical = function (net, X, n) {
  var f = PN.forward(net, X, n), c = f.c, F = net.F, seen = {}, out = [], h = c.H[c.H.length - 1];
  for (var k = 0; k < F; k++) if (n && h[c.arg[k] * F + k] > 1e-12 && !seen[c.arg[k]]) { seen[c.arg[k]] = 1; out.push(c.arg[k]); }
  return out.sort(function (a, b) { return a - b; });
};
...
  for (j = 0; j < gz; j++) for (i = 0; i < gx; i++) {
    if (!G.occ[j * gx + i]) continue;
    if (mode === 'submanifold') { out[j * gx + i] = 1; n++; }
    for (dj = -r; dj <= r; dj++) for (di = -r; di <= r; di++) {
      var a = i + di, b = j + dj;
      if (a < 0 || a >= gx || b < 0 || b >= gz) continue;
      if (mode === 'sparse') { macs++; if (!out[b * gx + a]) { out[b * gx + a] = 1; n++; } }
      else if (G.occ[b * gx + a]) macs++;
    }
  }

What to try. The first view opens on cloud 1, an oval. Its 24 reorderings move the plain MLP's answer by 0.40 (the red dots) and the PointNet's by 0 (one blue dot); over the 100 test clouds the MLP is right 91% in sweep order and 56% shuffled, the PointNet 98%. Slide points deleted to 70% with non-critical points going first: 10 points remain, the pooled feature has moved by 0 and the accuracy is still 98%. Delete at random instead and it is 88%; critical first, 90%, no worse, because neighbours take over (at 50%, critical-first moves the feature by 0.14 and costs a point: 92% against 93% at random). At 90% the policies part: 70% non-critical first, 52% at random, 50% critical first. Switch the view to a scan, cells of 10 cm: a dense layer costs 109,296 multiply-adds, a sparse one 4,302 (25.4 times fewer), a submanifold one 2,088; after four layers the sparse rule has 4,054 active sites and the submanifold rule still 478.

Road not taken · repair the order instead of respecting it

Three ways to keep the plain network. Sort the points. Azimuth around the centre was the sweep order, and it works for an outline that is star-shaped; in general no key keeps near points near. Sort by x, perturb every coordinate by 0.01 and re-sort: the list moves, on average over the 100 test clouds, by 0.90 in its largest entry, ninety times the perturbation, because two points of nearly equal x and opposite z swap places (sorted by azimuth: 0.04). PointNet's authors drop sorting for this reason: no stable order exists in high dimensions. Shuffle while training, or read the list with a recurrent network in random order, and the network learns an approximate invariance. Given the same 300 steps the MLP stays at 50%; a wider one (128 and 64 hidden units) with 13 times the steps reaches 66% on shuffled clouds, and its answer still moves by 0.12 on reshuffling: no guarantee, and 32! orders to cover. Voxelise everything and use dense 3D convolutions: the cost of §4.

5 · Gravity picks an axis

A driving scene is not isotropic: things stand on the ground and little of importance is stacked above a car. So spend the vertical axis once, inside each cell, and convolve only over the ground. PointPillars (Lang et al., 2019) cuts the ground into 0.16 m columns with no height bins, keeps at most N = 100 points in each of at most P = 12,000 non-empty columns (a 64-beam sweep fills 6,000 to 9,000), turns each point into 9 numbers, runs a small PointNet in every pillar (shared layers, max over its points), scatters the result to the pillar's cell of a 2D pseudo-image and applies an ordinary 2D network: a PointNet inside the cell (§2), an ordinary convolution across cells (§4). The stacked input is 9 × 12,000 × 100 = 10.8 million numbers, and the whole detector runs in 16.2 ms (62 Hz) on a desktop with a GTX 1080 Ti, against the 225 ms (4.4 Hz) that the same paper reports for VoxelNet, which follows its voxel encoder with 3D convolutions: 13.9 times faster, the encoder alone 1.3 ms against 190 ms (146 times). Cameras need a lift first. Lift-Splat-Shoot (Philion and Fidler, 2020) has each pixel predict a distribution over depths and a context vector, forms their outer product along the ray and sum-pools the resulting points into pillars; BEVFormer (Li et al., 2022) lets a grid of learned bird's-eye-view queries attend to the images, 56.9% NDS (the nuScenes detection score) on the nuScenes test set from cameras alone. Flatland has no gravity, so §5 is arithmetic, not a widget view.

6 · One answer per input

What can such a network answer? A vector per cloud: a class, a box (CenterPoint, Yin et al., 2021, finds object centres as heatmap peaks and regresses size, orientation and velocity there), the two scores of an object. Training moves the vector to minimise squared error over the examples, and for one input the minimiser is the mean of the answers the examples attach to it: if two answers a and b fit equally well, d/dŷ · ½[(ŷ − a)² + (ŷ − b)²] = 0 gives ŷ = (a + b)/2. When the data pin the answer down, as a sweep's points pin down where a car is, the mean of a narrow bump is a good answer. When two answers fit, it is their midpoint.

Make it concrete with the two kinds. A camera sees only the arc of an object within 25° of its viewing direction, with 4.6 cm of noise per reading. For a quarter of the objects the world makes (24.8%, 372 of 1,500) the front fits an oval and a trefoil about equally well: the posterior probability of each kind, by Bayes' rule, is between 35% and 65%, and lesson 11's closed form, with each kind's own mean and covariance as the prior, finds an oval and a trefoil that fit the front's sixteen points to 4.1 cm and 4.1 cm rms, within the 4.6 cm of noise.

Train the same kind of network, by squared error for 800 steps, to return two scores for the whole object: its amounts of lesson 11's elongated and three-lobed traits, called elongation and triangularity (the outline is the unit circle plus those amounts of the two traits). On those fronts its answer is 10.6 cm from the oval that fits and 11.3 cm from the trefoil that fits, which are 21.3 cm apart (rms radius difference over the directions the camera did not face, for a mean radius of 1.15 m). It returned about the midpoint, 3.0 cm from the best possible squared-error answer, which the closed form gives. Squared error asks for it: the network's answer errs against the true outline by 13.0 cm (12.5 for the best possible answer), committing to the likelier explanation by 15.1 cm.

And the average is not an object. The midpoint of the two explanations fits the front too, to 4.1 cm rms (a residual is linear in the outline, so a midpoint is never worse than the mean of the two residuals): the data cannot object. Switch the widget to the hidden back: for front 1 the answer has elongation 0.90 and triangularity 0.88, half an oval and half a trefoil, 12.9 cm from the one that fits and 12.5 cm from the other (they are 25.2 cm apart). The world makes ovals, with elongation near 1.6 and triangularity near 0, and trefoils, the reverse; of 4,000 objects drawn from it only 6 have both scores above 0.8. Only the world can object to the average.

What this lesson did not do

It trained tiny networks on outlines in a plane, at one orientation: objects turned at random need invariance to rotation as well, which PointNet gets from a learned alignment and which is not covered here. It read no real LiDAR sweep, trained no detector or segmenter, built no network on sparse convolution (it counted the cost) and gave no timings of its own: the speeds of §5 are published measurements. And it showed the failure of regression without curing it: the network cannot say how unsure it is or draw one of the two objects. That is lesson 13, which also writes out the posterior probabilities of the two kinds that §6 uses to pick its fronts (Bayes' rule on the readings, computed here but not derived). Lesson 14 sets the scene moving.

Common mistakes / failure modes

"shuffle the training data and the network learns to ignore order"

A wider MLP with 13 times the steps reached 66% on shuffled clouds and its answer still moved by 0.12; the symmetric form was exact at once (§2, road).

"max pooling throws information away, so the network must be sloppy"

The output depends only on the critical set, exactly: keep those 7 of 32 points and nothing changes (§3).

"PointNet sees local structure"

φ sees one point at a time; neighbourhoods need PointNet++ (§3).

"sparse convolution just skips the zeros, so depth is free"

A plain sparse layer grows the active set from 478 to 4,054 sites in four layers, and the saving falls from 25.4 to 6.7 times; holding the set fixed keeps it at 52 (§4).

"the network's answer is the most likely scene"

It is the mean of what fits: for a front that two objects explain it returned their midpoint, scores (0.90, 0.88), both above 0.8, as in only 6 of 4,000 objects (§6).

Checkpoint exercise

Try it

A sweep fills 600 cells of a 200 × 100 grid. How many multiply-adds does a 3×3 layer cost dense and sparse, and in what ratio? Then do the same for a 3×3×3 layer on the sphere of §4 (67,664 of 128³ cells). Why does the kernel size not matter to the ratio? Answer: dense 200 × 100 × 9 = 180,000, sparse 600 × 9 = 5,400, ratio 33.3, the reciprocal of the 3% occupancy. In 3D the window has 27 offsets: dense 128³ × 27 = 56.6 million, sparse 67,664 × 27 = 1.83 million, ratio 31.0. The window size multiplies both counts, so it cancels.

Where this points next

A network can now read a cloud in any order and any length, spend its arithmetic where there are points (25.4 times fewer multiply-adds on the scan at 10 cm, 31 times for a sphere in 128³) and collapse the vertical axis for driving. What it returns is one vector per input. For a front that an oval and a trefoil explain equally well it returned the midpoint, 12.9 cm from the one and 12.5 cm from the other, a hybrid with both scores above 0.8, as in only 6 of 4,000 objects of the world, and it did so because squared error asks for it: the average is a better bet (13.0 cm) than committing to the likelier explanation (15.1 cm). That is harmless for "where is the car" and wrong for "what is behind the mug". How do we produce a scene that agrees with the data and is also a valid sample of the kinds of scenes there are?

Takeaway

A point cloud has no order, and a function ρ(pool_i φ(x_i)) is invariant to reordering and accepts any length by construction: the plain MLP was right on 91% of clouds in sweep order and 56% shuffled, the PointNet on 98% either way with an answer that moves by exactly 0. The form is complete for countable sets, may need a wide pool, and lesson 11's closed form already has it. A max pool depends only on the critical set (7 of 32 points) and cannot see local structure, which PointNet++ restores. A volume is mostly empty, so a convolution should cost occupied sites, not cells: 25.4 times fewer multiply-adds on the scan, falling to 6.7 after four layers unless the active set is held fixed (52). Driving scenes collapse the vertical axis into pillars, a PointNet inside each column and a 2D network across columns. Trained by squared error, such a network answers with the mean of what fits, and for a front that fits two objects that is an object the world almost never makes.

Interview prompts

Why can a plain network not read a point cloud, and what exactly goes wrong? (§1 — it reads a list, so the 32! orderings of one cloud are 32! different inputs; shuffled, it is right on 56% of clouds against 91% in the order it was trained on.)
What form must a function of a set have, and is anything lost? (§2 — ρ(pool φ(x_i)); Deep Sets proves it is complete for countable universes, but the pooled vector may need as many entries as the set has points.)
What does a max-pooled network actually depend on? (§3 — only the critical set, the points that win a channel: keep them and the output is identical.)
Why does sparse convolution save exactly the reciprocal of the occupancy, and why does the saving shrink with depth? (§4 — dense costs cells × k², sparse |A| × k²; a plain sparse layer dilates the active set, a submanifold layer holds it fixed.)
What do pillars do with the height, and why is that fast? (§5 — a PointNet inside each ground column, then 2D convolution across columns: 16.2 ms against 225 ms for VoxelNet.)
Why does a network trained by squared error return an object that cannot exist when two answers fit? (§6 — the squared-error minimiser is the mean of the answers; two equally good answers give their midpoint, here scores (0.90, 0.88), both above 0.8, as in only 6 of 4,000 objects.)

Companion reads: Computer Vision · 09 Object detection (the 2D detection heads that CenterPoint and PointPillars extend), Computer Vision · 02 Filtering and convolution (the dense convolution §4 makes sparse).