Ученые из MIT представляют новый алгоритм.

На вопрос о самой плотной возможной упаковке одинаковых сфер первоначально ответил в 1611 году Йоханнес Кеплер, известный своими законами о движении планет. Но более сложная задача о оптимальном расположении 3D-объектов различных размеров и форм до сих пор остается нерешенной.

Однако группа исследователей из MIT и компании Inkbit, возглавляемая Войцехом Матусиком, представила новую вычислительную методологию, которую они называют "плотная, без взаимного перекрытия и масштабируемая спектральная упаковка" (SSP). Эта техника будет представлена на конференции SIGGRAPH 2023, самой крупной конференции по компьютерной графике и интерактивным методам.

Подход SSP включает в себя процесс "вокселизации" контейнера, представляемого в виде 3D-сетки из маленьких кубиков или вокселей. Затем алгоритм вычисляет количество свободных вокселей для каждого объекта и определяет, в каких местах объект может быть размещен без пересечения с другими объектами. Исследователи используют еще одну метрику, которая предназначена для максимального увеличения плотности упаковки.

Последний шаг алгоритма SSP - обеспечить, чтобы при оптимальном расположении каждый объект мог попасть на свое назначенное место, а также мог быть отделен от других объектов при распаковке. С помощью быстрого преобразования Фурье (FFT) команда смогла ускорить упаковку на несколько порядков.

В одном демонстрационном примере новый алгоритм эффективно разместил 670 объектов всего за 40 секунд, достигнув плотности упаковки около 36%. Он за 2 часа разместил 6,596 объектов с плотностью упаковки 37.30%. "Плотности, которые мы получаем, близкие к 40%, значительно лучше тех, которые получаются с помощью традиционных алгоритмов," говорит Матусик, "и они также быстрее."

"Это прорывное решение к долгостоящей проблеме эффективной организации 3D-объектов", комментирует Бедрих Бенеш, профессор компьютерных наук в Университете Пердью.

Методика может быть полезна для компаний, занимающихся складированием и отправкой грузов, где различные объекты регулярно упаковываются в коробки разных размеров, согласно Матусику. Однако он и его коллеги особенно заинтересованы в применении в 3D-печати. "Если мы сможем увеличить плотность упаковки," добавляет он, "мы сможем увеличить общую эффективность процесса печати, тем самым снижая общую стоимость произведенных деталей."

Пока что остается открытой проблема оптимального расположения деформируемых объектов или суставных объектов, и она может быть решена в будущих работах.

Источник