5 мин. чтения
7/7/2023 2:02:33 PM

Новый вычислительный метод облегчает плотное размещение объектов внутри жесткого контейнера

Featured Image 1 Команда под руководством Массачусетского технологического института разработала новый алгоритм упаковки для поиска мест размещения в данном объекте. Предоставлено: Массачусетский технологический институт

В 1611 году Иоганн Кеплер, известный своими законами движения планет, предложил решение вопроса о наиболее плотном способе расположения сфер одинакового размера. Знаменитый астроном взялся за эту проблему, когда его спросили, как складывать пушечные ядра так, чтобы они занимали наименьшее количество места. Кеплер пришел к выводу, что лучшей конфигурацией является так называемая гранецентрированная кубическая решетка — подход, обычно используемый в продуктовых магазинах для демонстрации апельсинов: каждое пушечное ядро должно лежать в полости, оставленной четырьмя пушечными ядрами (выстроенными в плотный квадрат два на два), лежащими прямо под ним. Однако это была всего лишь гипотеза, которая была доказана почти 400 лет спустя математиком из Мичиганского университета.

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

Тем не менее, был достигнут значительный прогресс, но не в форме математического доказательства, а скорее благодаря новой вычислительной методологии, которая делает эту ранее громоздкую задачу более разрешимой. Команда исследователей из Массачусетского технологического института и Inkbit (дочерняя компания Массачусетского технологического института, базирующаяся в Медфорде, штат Массачусетс), во главе с Войцехом Матусиком, доктором философии ‘03, профессором Массачусетского технологического института и соучредителем Inkbit, представит эту технику, которую они называют «плотной, свободной от блокировки и масштабируемой спектральной упаковки», или SSP, в августе этого года на SIGGRAPH 2023 — крупнейшей в мире конференции по компьютерной графике и интерактивные методы.

Первым шагом в SSP является разработка твердых 3D-объектов для заполнения фиксированного контейнера. Один из возможных подходов, например, заключается в том, чтобы начать с самых больших объектов и закончить самыми маленькими. Следующим шагом является помещение каждого объекта в контейнер. Чтобы облегчить этот процесс, контейнер «вокселизируется», что означает, что он представлен 3D-сеткой, состоящей из крошечных кубиков или вокселей, каждый из которых может быть размером всего в кубический миллиметр. Сетка показывает, какие части контейнера или какие воксели уже заполнены, а какие свободны.

Объект, подлежащий упаковке, также вокселизирован, опять же представлен агломерацией кубов, имеющих тот же размер, что и в контейнере. Чтобы выяснить доступное пространство для этого объекта, алгоритм затем вычисляет величину, называемую метрикой столкновения, на каждом вокселе. Он работает, помещая центр объекта на каждый воксель в контейнере, а затем подсчитывая количество занятых вокселей, с которыми объект перекрывается или «сталкивается». Объект может быть размещен только в тех местах, где перекрытие равно нулю, другими словами, где нет столкновений.

Следующим шагом является просеивание всех возможных мест размещения и определение наилучшего доступного положения для размещения объекта. Для этой задачи исследователи вычисляют еще одну метрику на каждом вокселе, которая предназначена для локального максимизации плотности упаковки. Эта метрика измеряет зазоры между объектом и стенкой контейнера или между перемещаемым объектом и объектами, уже расположенными в контейнере. Например, если объект размещен в самом центре, метрика, скорее всего, присвоит высокое значение.

Цель, однако, состоит в том, чтобы свести к минимуму промежутки между объектами, и этого можно достичь, поместив объект туда, где значение метрики является наименьшим. «Это похоже на игру «Тетрис», — объясняет Матусик. «Вы хотите оставить как можно меньше пустого места».

Однако это еще не все, потому что вышеприведенное обсуждение касается объекта, который перемещается или «переводится» в контейнер, сохраняя при этом фиксированную ориентацию в пространстве. Компьютер может пройти через весь этот процесс с множеством различных ориентаций для одного и того же объекта, пока не найдет ориентацию, которая лучше всего подходит для пространства.

Последний шаг алгоритма SSP состоит в том, чтобы гарантировать, что для, казалось бы, желаемого расположения каждый объект действительно может попасть в назначенный ему кусочек, или, что эквивалентно, что каждый объект может быть отделен от других объектов при распаковке контейнера. Это означает, что упаковка должна быть «свободной от блокировки» — условие для избежания таких конфигураций, как сблокированные кольца.

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

В одной из демонстраций новый алгоритм эффективно разместил 670 объектов всего за 40 секунд, достигнув плотности упаковки около 36%. За два часа было организовано 6 596 объектов с плотностью упаковки 37,30%. «Плотности, которые мы получаем, близкие к 40%, значительно лучше, чем те, которые получены традиционными алгоритмами, — говорит Матусик, — и они также быстрее».

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

Подробнее: “Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects” inkbit3d.com/wp-content/upload … acking_optimized.pdf 🔗

Получи бесплатную еженедельную рассылку со ссылками на репозитории и лонгриды самых интересных историй о стартапах 🚀, AI технологиях 👩‍💻 и программировании 💻!
Присоединяйся к тысячам читателей для получения одного еженедельного письма

Подписывайся на нас:

Нашли ошибку в тексте? Напишите нам.

Добавляй ЛРНЧ в свою ленту Google Новостей.
Читайте далее 📖

Новая модель искусственного интеллекта может изменять видимый возраст изображений лица, сохраняя при этом отличительные черты.

8/29/2023 · 5 мин. чтения

Новая модель искусственного интеллекта может изменять видимый возраст изображений лица, сохраняя при этом отличительные черты.

Hack Hack раскрывает риск безопасности звонков на смартфонах

8/23/2023 · 5 мин. чтения

Hack Hack раскрывает риск безопасности звонков на смартфонах