Um novo método computacional facilita a colocação densa de objetos dentro de um recipiente rígido.
Em 1611, Johannes Kepler – conhecido por suas leis do movimento planetário – ofereceu uma solução para a questão relativa à maneira mais densa possível de organizar esferas de tamanhos iguais. O famoso astrônomo assumiu esse problema quando questionado sobre como empilhar balas de canhão de modo a ocupar o mínimo de espaço. Kepler concluiu que a melhor configuração é a chamada rede cúbica de face centrada – uma abordagem comumente usada em mercearias para exibir laranjas: cada bala de canhão deve repousar na cavidade deixada pelas quatro balas de canhão (alinhadas em -dois quadrado) situado diretamente abaixo dele. Isso foi apenas uma conjectura, no entanto, que não foi provada até quase 400 anos depois por um matemático da Universidade de Michigan.
Embora isso tenha resolvido a questão do empacotamento uniforme de esferas, o problema mais geral, referente à maneira ideal de posicionar objetos 3D de tamanhos e formas variados, ainda não foi resolvido. Esse problema, na verdade, é classificado como NP-difícil, o que significa que não pode ser resolvido exatamente – ou mesmo aproximadamente, com alto grau de precisão – sem exigir tempos computacionais absurdamente longos que podem levar anos ou décadas, dependendo do número de peças que precisam ser encaixadas em um espaço confinado.
No entanto, houve algum progresso importante, não na forma de uma prova matemática, mas sim por meio de uma nova metodologia computacional que torna essa tarefa anteriormente difícil de manejar mais tratável. Uma equipe de pesquisadores do MIT e da Inkbit (uma empresa derivada do MIT com sede em Medford, Massachusetts), liderada por Wojciech Matusik, professor do MIT e cofundador da Inkbit, está apresentando essa técnica, que eles chamam de “denso, livre de intertravamento e escalável Spectral Packing”, ou SSP, em agosto no SIGGRAPH 2023 – a maior conferência mundial sobre computação gráfica e técnicas interativas. Um artigo de acesso aberto, escrito por Qiaodong Cui da Inkbit, Victor Rong SM ’23, estudante de pós-graduação do MIT, Desai Chen PhD ’17 (também da Inkbit) e Matusik – será publicado no próximo mês na revista ACM Transactions on Graphics.
Crédito: Imagem cortesia dos pesquisadores.
O primeiro passo no SSP é elaborar uma ordenação de objetos 3D sólidos para preencher um recipiente fixo. Uma abordagem possível, por exemplo, é começar com os objetos maiores e terminar com os menores. O próximo passo é colocar cada objeto no recipiente. Para facilitar esse processo, o contêiner é “voxelizado”, o que significa que é representado por uma grade 3D composta por pequenos cubos ou voxels, cada um dos quais pode ter apenas um milímetro cúbico de tamanho. A grade mostra quais partes do contêiner – ou quais voxels – já estão preenchidas e quais estão vazias.
O objeto a ser empacotado também é voxelizado, novamente representado por uma aglomeração de cubos de mesmo tamanho que os do contêiner. Para descobrir o espaço disponível para esse objeto, o algoritmo calcula uma quantidade chamada métrica de colisão em cada voxel. Ele funciona colocando o centro do objeto em cada voxel no recipiente e, em seguida, contando o número de voxels ocupados com os quais o objeto se sobrepõe ou “colide”. O objeto só pode ser colocado em locais onde a sobreposição é zero – em outras palavras, onde não há colisões.
O próximo passo é filtrar todas as colocações possíveis e determinar a melhor posição disponível para colocar o objeto. Para essa tarefa, os pesquisadores calculam outra métrica em cada voxel, projetada para maximizar localmente a densidade de empacotamento. Essa métrica mede as lacunas entre o objeto e a parede do contêiner – ou entre o objeto que está sendo movido e os objetos já situados dentro do contêiner. Se o objeto for colocado bem no centro, por exemplo, a métrica provavelmente atribuiria um valor alto. O objetivo, no entanto, é minimizar as lacunas entre os objetos, e isso pode ser alcançado colocando o objeto onde o valor da métrica é o mais baixo. “É como o jogo Tetris”, explica Matusik. “Você quer deixar o mínimo de espaço vazio possível.”
Crédito: Imagem cortesia dos pesquisadores.
Essa não é toda a história, no entanto, porque a discussão anterior diz respeito a um objeto que é movido ou “traduzido” para o contêiner enquanto mantém uma orientação fixa no espaço. O computador pode passar por todo esse processo com várias orientações diferentes para o mesmo objeto até encontrar a orientação que melhor se adapta ao espaço.
A última etapa do algoritmo SSP é garantir que, para um arranjo aparentemente desejável, cada objeto possa realmente entrar em seu local designado ou, de forma equivalente, que cada objeto possa ser separado dos outros objetos quando o contêiner estiver sendo desempacotado. O que significa dizer que a gaxeta deve ser “livre de travamento” – uma condição para evitar configurações como anéis travados.
Descobrir os melhores posicionamentos para cada objeto à medida que o contêiner enche obviamente requer muitos cálculos. Mas a equipe empregou uma técnica matemática, a transformada rápida de Fourier (FFT), que nunca havia sido aplicada ao problema de empacotamento antes. Usando FFT, os problemas de minimizar a sobreposição de voxels e minimizar as lacunas para todos os voxels no contêiner podem ser resolvidos por meio de um conjunto relativamente limitado de cálculos, como multiplicações simples, em oposição à alternativa impraticável de testar todos os locais possíveis para os objetos para ser posicionado dentro. E isso torna a embalagem mais rápida em várias ordens de grandeza.
Em uma demonstração, o novo algoritmo posicionou eficientemente 670 objetos em apenas 40 segundos, atingindo uma densidade de empacotamento de cerca de 36%. Demorou duas horas para organizar 6.596 objetos com uma densidade de empacotamento de 37,30%. “As densidades que estamos obtendo, perto de 40%, são significativamente melhores do que as obtidas por algoritmos tradicionais”, diz Matusik, “e também são mais rápidas”.
Este trabalho representa “uma solução inovadora para um problema antigo de organização eficaz de objetos 3D”, comenta Bedrich Benes, professor de ciência da computação na Purdue University. “A solução proposta maximiza a densidade de embalagem e tem potencial para encontrar aplicações em muitas áreas práticas, desde a robótica até a manufatura. Além disso, as soluções sem intertravamento são adequadas para ambientes controlados por computador.”
A abordagem pode, é claro, ser útil para armazéns e empresas de transporte onde vários objetos são rotineiramente embalados em caixas de tamanhos diferentes, de acordo com Matusik. No entanto, ele e seus colegas estão especialmente interessados em aplicações em impressão 3D, também chamada de manufatura aditiva. As peças são normalmente fabricadas em lotes e colocadas em bandejas. No entanto, as abordagens atuais, diz Matusik, “têm uma utilização muito limitada do volume [do contêiner]” – normalmente em torno de 20%. “Se pudermos aumentar a densidade da embalagem”, acrescenta ele, “podemos aumentar a eficiência geral do processo de impressão, reduzindo assim o custo geral das peças fabricadas”.
Embora o papel SIGGRAPH ofereça novos e aprimorados procedimentos para impressão 3D, bem como para embalar objetos rígidos, o problema de como melhor organizar objetos deformáveis ou articulados – este último composto por mais de uma parte rígida conectada por juntas – ainda está em aberto , e podem ser abordadas em trabalhos futuros. Enquanto isso, se as pessoas tiverem apenas duas horas para colocar mais de 6.000 objetos em uma caixa de armazenamento, não há necessidade de se desesperar. A ajuda pode estar a apenas um algoritmo de distância.
Publicado em 09/07/2023 18h37
Artigo original: