Le problème de l’empaquetage 3D résolu grâce à la méthode SSP

Imaginez que vous ayez à résoudre un problème qui a résisté à certains des plus grands esprits de l’humanité depuis près de quatre siècles. Un défi que même Johannes Kepler, connu pour ses lois sur le mouvement planétaire, n’a pas pu résoudre complètement.

Un défi qui a une importance pratique pour tout, du remplissage d’un conteneur d’expédition à la configuration d’une imprimante 3D. Aujourd’hui, une équipe de chercheurs du MIT et d’Inkbit, une entreprise issue du MIT, a réalisé des progrès significatifs dans la résolution de ce problème.

Le fond du problème

En 1611, Johannes Kepler a été chargé de trouver la meilleure manière d’empiler des boulets de canon pour qu’ils occupent le moins d’espace possible. Il en a conclu que la configuration optimale était une sorte de réseau cubique à faces centrées, un principe couramment utilisé dans les épiceries pour exposer les oranges : chaque boulet de canon devrait reposer dans la cavité laissée par les quatre boulets de canon situés juste en dessous. Cette hypothèse, toutefois, n’a été prouvée que près de 400 ans plus tard par un mathématicien de l’Université du Michigan.

Cependant, le problème plus général concernant la manière optimale de positionner des objets 3D de tailles et de formes variées est encore sans solution. Ce problème est classifié comme NP-difficile, ce qui signifie qu’il ne peut pas être résolu exactement – ou même approximativement, avec une grande précision – sans nécessiter des temps de calcul absurdement longs qui pourraient prendre des années ou des décennies, selon le nombre d’éléments à ajuster dans un espace confiné.

Une nouvelle méthodologie computationnelle

Malgré cela, une équipe de chercheurs du MIT et d’Inkbit, dirigée par le professeur du MIT et co-fondateur d’Inkbit, Wojciech Matusik, a fait un grand progrès. Il ne s’agit pas d’une preuve mathématique, mais plutôt d’une nouvelle méthodologie computationnelle qui rend cette tâche auparavant ingérable plus gérable. Cette technique, qu’ils appellent « dense, interlocking-free and Scalable Spectral Packing » ou SSP, sera présentée en août à SIGGRAPH 2023 – la plus grande conférence mondiale sur les graphiques informatiques et les techniques interactives.

L’essentiel de cette méthode SSP consiste à déterminer l’ordre de remplissage d’un conteneur fixe avec des objets 3D solides. Par exemple, on pourrait commencer par les objets les plus grands et finir par les plus petits. Le conteneur et les objets sont ensuite « voxélisés« , c’est-à-dire représentés par une grille 3D composée de minuscules cubes ou voxels. Cette grille indique quelles parties du conteneur sont déjà remplies et lesquelles sont vides.

Le procédé SSP en action

Le processus SSP place l’objet à emballer à chaque voxel dans le conteneur et compte le nombre de voxels occupés avec lesquels l’objet chevauche, ou « entre en collision ». L’objet ne peut être placé qu’à des endroits où le chevauchement est nul, c’est-à-dire où il n’y a pas de collisions.

Le pas suivant consiste à passer en revue tous les placements possibles et à déterminer le meilleur emplacement pour placer l’objet. Pour ce faire, les chercheurs calculent une autre métrique à chaque voxel, conçue pour maximiser localement la densité de l’emballage. Cette métrique mesure les écarts entre l’objet et la paroi du conteneur – ou entre l’objet qui est déplacé et ceux qui sont déjà placés dans le conteneur. L’objectif est de minimiser les espaces vides entre les objets, ce qui peut être accompli en plaçant l’objet là où la valeur de la métrique est la plus faible.

Résultats de l’application de la méthode SSP

En utilisant cette méthode, les chercheurs ont pu placer efficacement 670 objets en seulement 40 secondes, atteignant une densité de remplissage d’environ 36%. Il a fallu deux heures pour organiser 6 596 objets avec une densité de remplissage de 37,30%. Ces densités, proches de 40%, sont significativement meilleures que celles obtenues par les algorithmes traditionnels, et elles sont également plus rapides.

Ce travail représente « une solution remarquable à un problème de longue date de l’organisation efficace des objets 3D« , commente Bedrich Benes, professeur d’informatique à l’Université Purdue. « La solution proposée maximise la densité de l’emballage et a le potentiel de trouver des applications dans de nombreux domaines pratiques, allant de la robotique à la fabrication.« 

Potentiels domaines d’application

L’approche peut être utile pour les entreprises d’entreposage et d’expédition où divers objets sont régulièrement emballés dans des boîtes de différentes tailles. Cependant, Matusik et ses collègues s’intéressent particulièrement aux applications en impression 3D, également appelée fabrication additive.

Les pièces sont normalement fabriquées par lots et placées sur des plateaux. Toutefois, les approches actuelles, dit Matusik, « ont une utilisation très limitée du volume [du conteneur] » – généralement environ 20%. « Si nous pouvons augmenter la densité de l’emballage, » ajoute-t-il, « nous pouvons augmenter l’efficacité globale du processus d’impression, réduisant ainsi le coût global des pièces fabriquées.«