В 1611 году Иоганн Кеплер, известный своими законами движения планет, предложил решение вопроса о максимально плотном расположении сфер одинакового размера. Знаменитый астроном взялся за эту проблему, когда его спросили, как сложить ядра так, чтобы они занимали как можно меньше места. Кеплер пришел к выводу, что наилучшей конфигурацией является так называемая гранецентрированная кубическая решетка — подход, обычно используемый в продуктовых магазинах для выкладки апельсинов: каждое пушечное ядро должно лежать в полости, оставленной четырьмя пушечными ядрами (выстроенными в плотный ряд по два). -два квадрата), лежащих непосредственно под ним. Однако это была всего лишь гипотеза, которая была доказана почти 400 лет спустя математиком из Мичиганского университета.
Хотя это решило проблему равномерной упаковки сфер, более общая проблема, касающаяся оптимального способа позиционирования трехмерных объектов различных размеров и форм, все еще не решена. Эта задача, по сути, классифицируется как NP-сложная, что означает, что ее нельзя решить точно — или даже приблизительно, с высокой степенью точности — без абсурдно долгих вычислений, которые могут занять годы или десятилетия, в зависимости от количества вычислений. предметы, которые необходимо разместить в ограниченном пространстве.
Тем не менее, был достигнут значительный прогресс, но не в форме математического доказательства, а скорее благодаря новой вычислительной методологии, которая делает эту ранее громоздкую задачу более решаемой. Группа исследователей из Массачусетского технологического института и Inkbit (дочерняя компания MIT, базирующаяся в Медфорде, штат Массачусетс) под руководством Войцеха Матусика, профессора Массачусетского технологического института и соучредителя Inkbit, представляет эту технику, которую они называют «плотной, свободной от блокировок и масштабируемой». Spectral Packing», или SSP, в августе этого года на SIGGRAPH 2023 — крупнейшей в мире конференции по компьютерной графике и интерактивным технологиям. Сопутствующая статья в открытом доступе, написанная Цяодун Цуй из Inkbit, аспирантом Массачусетского технологического института Виктором Ронгом SM ’23, Десаи Ченом, доктором философии ’17 (также из Inkbit), и Матусиком, будет опубликована в следующем месяце в журнале. Транзакции ACM на графике.
Первым шагом в SSP является разработка порядка твердых 3D-объектов для заполнения фиксированного контейнера. Например, один из возможных подходов — начать с самых больших объектов и закончить самыми маленькими. Следующий шаг — поместить каждый объект в контейнер. Чтобы облегчить этот процесс, контейнер «вокселизирован», что означает, что он представлен трехмерной сеткой, состоящей из крошечных кубов или вокселей, каждый из которых может иметь размер всего лишь кубический миллиметр. Сетка показывает, какие части контейнера — или воксели — уже заполнены, а какие свободны.
Упаковываемый объект также вокселизирован, снова представлен скоплением кубов того же размера, что и в контейнере. Чтобы определить доступное пространство для этого объекта, алгоритм затем вычисляет величину, называемую метрикой столкновений в каждом вокселе. Он работает, помещая центр объекта в каждый воксель в контейнере, а затем подсчитывая количество занятых вокселей, с которыми объект перекрывается или «сталкивается». Объект можно разместить только в местах, где перекрытие равно нулю, другими словами, там, где нет столкновений.
Следующим шагом является просмотр всех возможных мест размещения и определение наилучшей доступной позиции для размещения объекта. Для этой задачи исследователи вычисляют еще одну метрику для каждого вокселя, которая предназначена для локального максимизации плотности упаковки. Эта метрика измеряет зазоры между объектом и стенкой контейнера или между перемещаемым объектом и теми объектами, которые уже находятся внутри контейнера. Например, если объект расположен в самом центре, метрика, скорее всего, присвоит высокое значение. Однако цель состоит в том, чтобы свести к минимуму промежутки между объектами, и этого можно достичь, поместив объект в место с наименьшим значением метрики. «Это похоже на игру «Тетрис», — объясняет Матусик. «Вы хотите оставить как можно меньше пустого пространства».
Однако это еще не все, потому что предыдущее обсуждение касается объекта, который перемещается или «переводится» в контейнер, сохраняя при этом фиксированную ориентацию в пространстве. Компьютер может пройти через весь этот процесс с разными ориентациями одного и того же объекта, пока не найдет ориентацию, которая лучше всего соответствует пространству.
Последним шагом алгоритма SSP является обеспечение того, чтобы при желаемом расположении каждый объект мог действительно попасть на назначенное ему место или, что то же самое, чтобы каждый объект можно было отделить от других объектов при распаковке контейнера. Это означает, что набивка должна быть «свободной от блокировок» — условие, позволяющее избежать таких конфигураций, как блокированные кольца.
Выяснение наилучших мест размещения для каждого объекта по мере заполнения контейнера, очевидно, требует большого количества вычислений. Но команда использовала математический метод, быстрое преобразование Фурье (БПФ), которое никогда раньше не применялось к задаче упаковки. Используя БПФ, проблемы минимизации перекрытия вокселей и минимизации промежутков для всех вокселей в контейнере могут быть решены с помощью относительно ограниченного набора вычислений, таких как простые умножения, в отличие от непрактичной альтернативы проверки всех возможных местоположений для объектов. располагаться внутри. И это ускоряет упаковку на несколько порядков.
В одной из демонстраций новый алгоритм эффективно разместил 670 объектов всего за 40 секунд, достигнув плотности упаковки около 36 процентов. На размещение 6596 объектов с плотностью упаковки 37,30% ушло два часа. «Плотности, которые мы получаем, около 40 процентов, значительно лучше, чем у традиционных алгоритмов, — говорит Матусик, — и они также быстрее».
Эта работа представляет собой «прорывное решение давней проблемы эффективной организации 3D-объектов», — комментирует Бедрих Бенеш, профессор компьютерных наук в Университете Пердью. «Предлагаемое решение максимально увеличивает плотность упаковки и может найти применение во многих практических областях, от робототехники до производства. Кроме того, решения без блокировки подходят для сред с компьютерным управлением».
По словам Матусика, такой подход, безусловно, может быть полезен для складских и транспортных компаний, где различные предметы регулярно упаковываются в коробки разного размера. Однако его и его коллег особенно интересуют применения в 3D-печати, также называемой аддитивным производством. Детали обычно изготавливаются партиями и размещаются на лотках. Однако современные подходы, по словам Матусика, «имеют очень ограниченное использование [container] объем» — обычно около 20 процентов. «Если мы сможем увеличить плотность упаковки, — добавляет он, — мы сможем повысить общую эффективность процесса печати, тем самым снизив общую стоимость производимых деталей».
В то время как документ SIGGRAPH предлагает новые и улучшенные процедуры для 3D-печати, а также для упаковки жестких объектов, проблема того, как лучше всего расположить деформируемые объекты или сочлененные объекты — последние состоящие из более чем одной жесткой части, соединенной соединениями — все еще остается открытой. , и может быть рассмотрено в будущей работе. Между тем, если у людей когда-нибудь будет всего два часа, чтобы поместить более 6000 объектов в корзину для хранения, не нужно отчаиваться. Помощь может быть всего в одном алгоритме.