En 1611, Johannes Kepler, conocido por sus leyes del movimiento planetario, ofreció una solución a la pregunta sobre la forma más densa posible de disponer esferas del mismo tamaño. El famoso astrónomo abordó este problema cuando se le preguntó cómo apilar balas de cañón para que ocupen la menor cantidad de espacio. Kepler llegó a la conclusión de que la mejor configuración es la llamada red cúbica centrada en las caras, un enfoque que se usa comúnmente en las tiendas de comestibles para exhibir naranjas: cada bala de cañón debe descansar en la cavidad dejada por las cuatro balas de cañón (alineadas en un espacio apretado de dos por -dos cuadrados) que se encuentran directamente debajo de él. Sin embargo, esto era simplemente una conjetura que no fue probada hasta casi 400 años después por un matemático de la Universidad de Michigan.

Si bien eso resolvió el problema del empaque uniforme de las esferas, el problema más general, relacionado con la forma óptima de colocar objetos 3D de varios tamaños y formas, sigue sin resolverse. Este problema, de hecho, se clasifica como NP-difícil, lo que significa que no se puede resolver exactamente, ni siquiera aproximadamente, con un alto grado de precisión, sin requerir tiempos de cálculo absurdamente largos que podrían llevar años o décadas, dependiendo de la cantidad de problemas. piezas que deben encajar en un espacio confinado.

Sin embargo, ha habido un gran progreso, no en la forma de una prueba matemática, sino más bien a través de una nueva metodología computacional que hace que esta tarea que antes era difícil de manejar sea más manejable. Un equipo de investigadores del MIT e Inkbit (una empresa spin-out del MIT con sede en Medford, Massachusetts), encabezado por Wojciech Matusik, profesor del MIT y cofundador de Inkbit, presenta esta técnica, a la que denominan “tecnología densa, sin entrelazamientos y escalable ” . Spectral Packing”, o SSP, este agosto en SIGGRAPH 2023, la conferencia más grande del mundo sobre gráficos por computadora y técnicas interactivas. Un documento de acceso abierto adjunto, escrito por Qiaodong Cui de Inkbit, el estudiante graduado del MIT Victor Rong SM ´23, Desai Chen PhD ´17 (también de Inkbit) y Matusik, se publicará el próximo mes en la revista.Transacciones de ACM en gráficos.

El primer paso en SSP es elaborar un pedido de objetos 3D sólidos para llenar un contenedor fijo. Un enfoque posible, por ejemplo, es comenzar con los objetos más grandes y terminar con los más pequeños. El siguiente paso es colocar cada objeto en el contenedor. Para facilitar este proceso, el contenedor está "voxelizado", lo que significa que está representado por una cuadrícula 3D compuesta de pequeños cubos o vóxeles, cada uno de los cuales puede tener solo un milímetro cúbico de tamaño. La cuadrícula muestra qué partes del contenedor, o qué vóxeles, ya están llenos y cuáles están vacíos.

El objeto a envasar también se voxeliza, nuevamente representado por una aglomeración de cubos que tienen el mismo tamaño que los del contenedor. Para calcular el espacio disponible para este objeto, el algoritmo calcula una cantidad llamada métrica de colisión en cada vóxel. Funciona colocando el centro del objeto en cada vóxel del contenedor y luego contando el número de vóxeles ocupados con los que el objeto se superpone o "choca". El objeto solo se puede colocar en ubicaciones donde la superposición sea cero; en otras palabras, donde no haya colisiones.

El siguiente paso es analizar todas las ubicaciones posibles y determinar la mejor posición disponible para colocar el objeto. Para esta tarea, los investigadores calculan otra métrica en cada vóxel, que está diseñada para maximizar localmente la densidad de empaquetamiento. Esta métrica mide los espacios entre el objeto y la pared del contenedor, o entre el objeto que se está moviendo y los objetos que ya se encuentran dentro del contenedor. Si el objeto se coloca en el centro, por ejemplo, la métrica probablemente asignaría un valor alto. Sin embargo, el objetivo es minimizar los espacios entre los objetos, y eso se puede lograr colocando el objeto donde el valor métrico es el más bajo. “Es como el juego Tetris”, explica Matusik. “Quieres dejar el menor espacio vacío posible”.

Sin embargo, esa no es toda la historia, porque la discusión anterior se refiere a un objeto que se mueve, o “traduce”, al contenedor mientras mantiene una orientación fija en el espacio. La computadora puede pasar por todo este proceso con muchas orientaciones diferentes para el mismo objeto hasta que encuentra la orientación que mejor se adapta al espacio.

El último paso del algoritmo SSP es garantizar que, para un arreglo aparentemente deseable, cada objeto pueda realmente ingresar a su sitio asignado o, de manera equivalente, que cada objeto pueda separarse de los demás objetos cuando se desempaqueta el contenedor. Lo que quiere decir que el empaque debe estar "libre de enclavamientos", una condición para evitar configuraciones tales como anillos entrelazados.

Descubrir las mejores ubicaciones para todos y cada uno de los objetos a medida que el contenedor se llena obviamente requiere muchos cálculos. Pero el equipo empleó una técnica matemática, la transformada rápida de Fourier (FFT), que nunca antes se había aplicado al problema del empaquetamiento. Al usar FFT, los problemas de minimizar la superposición de vóxeles y minimizar los espacios para todos los vóxeles en el contenedor se pueden resolver a través de un conjunto relativamente limitado de cálculos, como multiplicaciones simples, en lugar de la alternativa poco práctica de probar todas las ubicaciones posibles para los objetos. para colocar en el interior. Y eso hace que empacar sea más rápido en varios órdenes de magnitud.

En una demostración, el nuevo algoritmo colocó eficientemente 670 objetos en solo 40 segundos, logrando una densidad de empaquetamiento de alrededor del 36 por ciento. Se necesitaron dos horas para organizar 6596 objetos con una densidad de empaque del 37,30 por ciento. “Las densidades que estamos obteniendo, cercanas al 40 por ciento, son significativamente mejores que las obtenidas por los algoritmos tradicionales”, dice Matusik, “y también son más rápidas”.

Este trabajo representa "una solución innovadora a un problema de larga data de organizar objetos 3D de manera efectiva", comenta Bedrich Benes, profesor de informática en la Universidad de Purdue. “La solución propuesta maximiza la densidad de empaque y tiene el potencial de encontrar aplicaciones en muchas áreas prácticas, que van desde la robótica hasta la fabricación. Además, las soluciones sin enclavamiento son adecuadas para entornos controlados por computadora”.

El enfoque puede, por supuesto, ser útil para las empresas de almacenamiento y envío donde varios objetos se empaquetan rutinariamente en cajas de diferentes tamaños, según Matusik. Sin embargo, él y sus colegas están especialmente interesados ​​en aplicaciones de impresión 3D, también llamada fabricación aditiva. Las piezas normalmente se fabrican en lotes y se colocan en bandejas. Sin embargo, los enfoques actuales, dice Matusik, "tienen una utilización muy limitada del volumen [del contenedor]", generalmente alrededor del 20 por ciento. “Si podemos aumentar la densidad del empaque”, agrega, “podemos aumentar la eficiencia general del proceso de impresión, reduciendo así el costo total de las piezas fabricadas”.

Si bien el papel SIGGRAPH ofrece procedimientos nuevos y mejorados para la impresión en 3D, así como para empaquetar objetos rígidos, el problema de cómo organizar mejor los objetos deformables o los objetos articulados, que consisten en más de una parte rígida conectada por juntas, aún está abierto, y puede ser abordado en trabajos futuros. Mientras tanto, si las personas alguna vez se encuentran con solo dos horas para colocar más de 6,000 objetos en un contenedor de almacenamiento, no hay necesidad de desesperarse. La ayuda puede estar a solo un algoritmo de distancia.

Autor