Una pizza de 12 pulgadas no es la mitad más de pizza que una de 8 pulgadas. Es 2.25 veces más. Esto se debe a que el área de la pizza sigue el cuadrado de su radio.

La gente generalmente tiene mala intuición para las áreas, o cualquier cosa que crezca más rápido que sus límites lineales. Por eso las pizzerías cobran por diámetro y los clientes compran confiablemente pizzas que no pueden terminar. El mismo fallo de intuición estuvo dentro del pipeline de coincidencia de escaneos 3D de un cliente durante casi un año.

Les costó el doble de memoria en cada worker de la flota. En algún lugar del código de puntuación había una tabla con una fila y una columna por elemento. Todos los que leyeron ese código vieron una lista cuando deberían haber visto un cuadrado.

El pipeline alinea dos escaneos de superficie, resta uno del otro e inspecciona lo que queda. Si los dos escaneos son del mismo objeto, lo que sobra es nada. Una clase de escáner tiene un modo de fallo conocido: donde el objeto tiene una cara plana, el escáner a veces registra una pirámide poco profunda en su lugar.

Si se dejan en los datos, esas pirámides parecen diferencias geométricas reales y hacen que una coincidencia verdadera sea rechazada. Así que antes de marcar dos elementos como coincidentes, verificamos si la cáscara sobrante tiene forma de pirámide. Si es así, las piezas de la pirámide se eliminan de los objetos, en lugar de considerarse como evidencia de una coincidencia.

Detectar una pirámide significa encontrar su base plana, y el evaluador encuentra la base mirando la orientación de la superficie. Cada triángulo de la malla tiene una normal (una unidad de dirección perpendicular al plano del triángulo) y los triángulos de una base plana todos miran aproximadamente en la misma dirección. El evaluador agrupa las normales en clústeres.

Luego mide qué tan disperso está cada clúster. El clúster más ajustado es el candidato a base, y si su dispersión está por debajo de un umbral, la base se acepta. La dispersión es donde vivía el cuadrado.

Se definió como la varianza de los cosenos entre cada par de normales en el clúster. Esta es una medida perfectamente razonable de dispersión, y los cosenos se usan regularmente para comparar vectores ya que son rápidos, fáciles de calcular e invariantes a escala. Sin embargo, para cada clúster, la llamada construía una tabla de N * N cosenos.

Si los clústeres son grandes, como en superficies planas superpuestas, esto resulta en una tabla densa que potencialmente compara cada normal correspondiente. En el peor de los casos, la tabla se convierte en una matriz cuadrada. Esto es un problema porque requiere mucha memoria, y en el peor de los casos la memoria requerida es N^2 veces la memoria requerida para una sola comparación de coseno.

Lo que esto significó En la mayoría de las comparaciones N era pequeño y nadie lo notó. La cáscara sobrante entre dos escaneos del mismo objeto es delgada. Se fragmenta en muchas piezas pequeñas, y cada pieza tiene unos cientos de normales.

Unos cientos al cuadrado no es nada. La excepción fue el caso que el pipeline más quería acertar: dos escaneos del mismo objeto tomados por diferentes escáneres. La resta deja una cáscara delgada continua en lugar de muchas.

Para empeorar las cosas, las superficies de la cáscara eran casi paralelas. Esto resultó en un clúster y una tabla de dispersión densa de alta similitud. A ocho bytes por entrada, una tabla sobre un clúster en las altas decenas de miles son varios gigabytes por sí sola.

Dos de ellas, más las copias de trabajo que la biblioteca toma en el camino, alcanzaron aproximadamente quince gigabytes en la peor comparación que perfilamos. Esa comparación estableció el piso de memoria para cada worker en la flota. Cada trabajo de alineación se aprovisionó con un slot lo suficientemente grande para sobrevivirlo, aproximadamente el doble de lo que el trabajo típico necesitaba.