Une pizza de 12 pouces n'est pas une fois et demie plus de pizza qu'une de 8 pouces. C'est 2,25 fois plus. C'est parce que la surface de la pizza suit le carré de son rayon.

Les gens ont généralement une mauvaise intuition des surfaces, ou de toute chose qui croît plus vite que ses limites linéaires. C'est pourquoi les pizzerias fixent leurs prix selon le diamètre et les clients achètent de façon fiable des pizzas qu'ils ne peuvent pas finir. La même faille d'intuition se trouvait dans le pipeline de correspondance de scans 3D d'un client pendant la majeure partie d'un an.

Cela leur a coûté le double de mémoire sur chaque worker de la flotte. Quelque part dans le code de scoring se trouvait un tableau avec une ligne et une colonne par élément. Tous ceux qui lisaient ce code voyaient une liste alors qu'ils auraient dû voir un carré.

Le pipeline aligne deux scans de surface, soustrait l'un de l'autre, et inspecte ce qui reste. Si les deux scans sont du même objet, ce qui reste n'est rien. Une classe de scanner a un mode de défaillance connu: là où l'objet a une face plane, le scanner enregistre parfois une pyramide peu profonde à la place.

Laissées dans les données, ces pyramides ressemblent à des différences géométriques réelles et font qu'une correspondance vraie est rejetée. Donc avant de marquer deux éléments comme correspondants, nous vérifions si la coquille restante a la forme d'une pyramide. Si c'est le cas, les morceaux de pyramide sont retirés des objets, plutôt que d'être considérés comme preuve d'une correspondance.

Détecter une pyramide signifie trouver sa base plane, et le scoreur trouve la base en regardant l'orientation de la surface. Chaque triangle du maillage a une normale (une unité de direction perpendiculaire au plan du triangle) et les triangles d'une base plane font tous face à peu près dans la même direction. Le scoreur regroupe les normales en clusters.

Il mesure ensuite la dispersion de chaque cluster. Le cluster le plus serré est le candidat pour la base, et si sa dispersion est inférieure à un seuil, la base est acceptée. La dispersion est l'endroit où résidait le carré.

Elle était définie comme la variance des cosinus entre chaque paire de normales dans le cluster. C'est une mesure parfaitement raisonnable de dispersion, et les cosinus sont régulièrement utilisés pour comparer des vecteurs car ils sont rapides, faciles à calculer et invariants à l'échelle. Pour chaque cluster cependant, l'appel construisait un tableau de cosinus N * N.

Si les clusters sont grands, comme sur des surfaces planes chevauchantes, cela résulte en un tableau dense qui compare potentiellement chaque normale correspondante. Dans le pire des cas, le tableau devient une matrice carrée. C'est un problème car cela nécessite beaucoup de mémoire, et dans le pire des cas la mémoire requise est N^2 fois la mémoire requise pour une seule comparaison de cosinus.

Ce que cela signifiait Dans la plupart des comparaisons N était petit et personne ne l'a remarqué. La coquille restante entre deux scans du même objet est fine. Elle se fragmente en de nombreux petits morceaux, et chaque morceau a quelques centaines de normales.

Quelques centaines au carré n'est rien. L'exception était le cas que le pipeline voulait le plus réussir: deux scans du même objet pris par différents scanners. La soustraction laisse une coquille fine continue plutôt que plusieurs.

Pour aggraver les choses, les surfaces de la coquille étaient quasi-parallèles. Cela a donné un cluster et un tableau de dispersion dense de forte similarité. À huit octets par entrée, un tableau sur un cluster dans les hautes dizaines de milliers représente plusieurs gigaoctets à lui seul. Deux d'entre eux, plus les copies de travail que la bibliothèque prend en cours de route, ont atteint environ quinze gigaoctets dans la pire comparaison que nous avons profilée.

Cette seule comparaison a fixé le plancher de mémoire pour chaque worker de la flotte. Chaque tâche d'alignement a été provisionnée avec un emplacement assez grand pour y survivre, environ le double de ce dont la tâche typique avait besoin.