A 12-inch pizza is not half again as much pizza as an 8-inch one. It is 2.25x as much. This is because the pizza's area follows the square of its radius.

People generally have poor intuition for areas, or any thing that grows quicker than its linear boundaries. This is why pizzerias price by diameter and customers reliably buy pizzas they can't finish. The same failure of intuition sat inside a client's 3D scan-matching pipeline for the best part of a year.

It cost them double the memory on every worker in the fleet. Somewhere in the scoring code was a table with one row and one column per element. Everybody who read that code saw a list when they should have seen a square.

The pipeline aligns two surface scans, subtracts one from the other, and inspects what is left over. If the two scans are of the same object then the leftover is nothing. One class of scanner has a known failure mode: where the object has a flat face, the scanner sometimes records a shallow pyramid instead.

Left in the data, those pyramids look like real geometric differences and cause a true match to be rejected. So before we mark two items as matching, we check whether the leftover shell is pyramid-shaped. If it is the pyramid pieces are removed from the objects, rather than being considered as evidence of a match.

Detecting a pyramid means finding its flat base, and the scorer finds the base by looking at surface orientation. Every triangle on the mesh has a normal (a unit of direction perpendicular to the triangle's plane) and the triangles of a flat base all face roughly the same way. The scorer groups normals into clusters.

It then measures how spread out each cluster is. The tightest cluster is the base candidate, and if its spread is below a threshold the base is accepted. The spread is where the square lived.

It was defined as the variance of the cosines between every pair of normals in the cluster. This is a perfectly reasonable measure of spread, and cosines are regularly used to compare vectors as they are fast, easy to compute, and scale invariant. For each cluster however the call built an N * N table of cosines.

If the clusters are large, such as on flat overlapping surfaces, this results in a dense table that potentially compares each corresponding normal. In the worst case, the table becomes a square matrix. This is a problem because it requires a lot of memory, and in the worst case the memory required is N^2 times the memory required for a single cosine comparison.

What This Meant On most comparisons N was small and nobody noticed. The leftover shell between two scans of the same object is thin. It fragments into many small pieces, and each piece has a few hundred normals.

A few hundred squared is nothing. The exception was the case the pipeline most wanted to get right: two scans of the same object taken by different scanners. The subtraction leaves one continuous thin shell rather than many.

Making things worse, the shell surfaces were near-parallel. This resulted in one cluster and a dense dispersion table of high similarity. At eight bytes per entry, a table over a cluster in the high tens of thousands is several gigabytes on its own.

Two of them, plus the working copies the library takes along the way, reached roughly fifteen gigabytes on the worst comparison we profiled. That one comparison set the memory floor for every worker in the fleet. Every alignment job was provisioned at a slot large enough to survive it, roughly double what the typical job needed.