Аппроксимация твердого тела объединением сфер

У меня есть трехмерное тело, представленное как объединение множества полиэдральных выпуклых оболочек. (Или одно выпуклое, если это упростит ситуацию.) Я бы хотел аппроксимировать это твердое тело как объединение множества сфер таким образом, чтобы минимизировать как количество сфер в множестве, так и ошибку в приближении. (Последняя цель преднамеренно расплывчата: любой разумный показатель ошибки будет делать. Аналогично, способ объединения целей вверх в воздухе: либо количество сфер, либо показатель ошибки могут быть ограничены, либо какая-то функция двух может быть сведено к минимуму. Я не хочу указывать себя в угол.)

Аппроксимация не должна полностью содержать или полностью содержаться в исходном множестве. Каждая сфера может иметь произвольный радиус.

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

Ответ 1

Проблема не проста, но была изучена ранее. Центральная концепция медиальная ось, которая может быть рассматривается как представление объекта бесконечным объединением шаров. Ключевой документ, посвященный вашему вопросу:

"Силовая кора, союзы шаров и медиальная ось преобразуются". Нина Амента, Сунхи Чой, Рави Кришна Коллури. Вычислительная геометрия. Том 19, Проблемы 2-3, июль 2001, стр. 127-153. (Ссылка журнала.)

(Источник изображений: От облаков точек до сильных корок.)

Вторая статья

Cazals, Frédéric, et al. "Жадные геометрические алгоритмы для сбора шаров с приложениями к геометрической аппроксимации и молекулярно-крупнозернистым". Компьютерная графика. Том 33. № 6. 2014. (Загрузка PDF.)

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

Ответ 2

Hm, моя лучшая идея до сих пор связана с носителями векторных машин. Превратите свой объект в целую кучу (возможно, равномерно расположенных) точек внутри и на поверхности объекта. Постройте модель SVDD с использованием линейного ядра (см. libsvm для реализации SVDD). Тогда функция решения модели представляет собой неявную поверхность, определяемую опорными векторами модели (и rho). Если вы снижаете стоимость, вы получите больше векторов поддержки, и вы получите меньше.

К сожалению, характер SVM таков, что область, покрытая соседними векторами поддержки, будет, например, "blob" вместе, примерно такая:

(извините, моя интуиция для SVM полностью геометрическая/визуальная.)

Теперь у вас нет хороших хрустящих шаров, но (массивная рука размахивает!), надеюсь, алгоритм выбрал полезное распределение центров для сфер.

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

Если вы захотите добавить к нему больше мощности процессора, вы можете запустить еще один уровень минимизации ошибок поверх этого, который повторяет весь вышеперечисленный процесс для разных расходов вектора поддержки, пытаясь минимизировать некоторую комбинацию ошибок и Стоимость. (Возможно error/cost.)

Ответ 3

Вот что я придумал. Этот подход представляет собой скорее итеративную трехмерную булевскую операцию, поэтому она может и не быть тем, что вы ищете. Поверхность кажется более сложной, поэтому я сосредоточился на этом.

Обзор

В основном добавить сферы внутри формы в положениях, которые максимизируют покрытие поверхности. Мы преобразуем сферу в трехмерный массив подписанных байтовых значений. Эти значения являются точками и будут поглощены сферами. Мы добавляем одну сферу за один раз внутри объекта, а затем вырастаем/сжимаем его в разных направлениях, чтобы "съесть" как можно больше точек. Цель состоит в том, чтобы собрать как можно больше очков за сферу. Очки заработаны путем суммирования очков в области сферы. С добавлением каждой сферы мы подсчитываем, затем подсчитываем эту область и используем значения массива в 0.

  (A)       (B) ZZZZZZ   (C) ZZZZZZ   (D) ZZZZZZ   (E) ZZZZZZ   (F) ZZZZZZ   
     /\         ZX33XZ       ZX33XZ       ZX33XZ       ZX33XZ       ZX33XZ   
    /  \       ZX3223XZ     ZX3223XZ     ZX##23XZ     ZX  ##XZ     ZX    XZ  
   /    \     ZX321123XZ   ZX321123XZ   ZX####23XZ   ZX  ####XZ   ZX      XZ 
  |      |   ZX32111123XZ ZX32111123XZ ZX######23XZ ZX  ######XZ ZX        XZ
  |      |   ZX32111133XZ ZX32111133XZ ZX######23XZ ZX  ######XZ ZX        XZ
  |      |   ZX32222223XZ ZX##222223XZ ZX3####223XZ ZX3  ####3XZ ZX3     ##XZ
  |------|   ZX33333333XZ ZX##333333XZ ZX33##3333XZ ZX33  ##33XZ ZX33    ##XZ
   X= -1     ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ ZXXXXXXXXXXZ
   Y= -2     ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ ZZZZZZZZZZZZ

(A) Форма, которую мы хотим заполнить. (2D, используемый здесь, но 3D будет аналогичным)

(B) Преобразуйте фигуру в трехмерную сетку точек. Поверхность получает наибольшее число, и по мере того, как вы работаете с центром, числа оседают на низких положительных числах (например, 1); Вне формы получаются отрицательные числа; глубокий интерьер получает 1

(D) Разверните сферу, пока мы не сожжем максимальное число точек

(E) Добавьте сферу Next и произведите ее.

(F) Добавьте еще одну сферу. Этот маленький.

Процесс

5) сначала разбивайте фигуру на 3D-разрешение.

10) Затем дайте самые "точки" блокам вокруг поверхности. Высокие точки с блоком, который на самом деле касается поверхности и нижних точек при движении внутрь или наружу. По мере того, как вы выходите наружу, точки должны быстро становиться отрицательными, поскольку это предотвратит появление выступающих сфер. Когда вы двигаетесь внутрь с поверхности, точки должны опускаться на 1 так, чтобы центральная область была бы все. Эти точки могут быть настроены по-разному для получения разных результатов.

15) Найдите местоположение на внутреннем крае формы, находящейся вне сферы. Не приближаясь к краю, он не минимизирует область поиска. Если местоположение не может быть найдено goto 80. Если местоположение не может быть найдено, находящееся рядом с

20) Нарисуйте сферу с нулевым радиусом внутри формы, которая не покрыта

25) Переместите сферу вверх/вниз, пока точки не будут максимизированы (имитированный отжиг)

26) Переместите сферу в/из до максимальной точки

27) Переместите сферу влево/вправо, пока точки не будут максимальными

28) Переместите верхнюю часть сферы вверх/вниз, пока точки не будут максимизированы (имитированный отжиг/подъем высоты)

29) Переместите снизу сферу вверх/вниз, пока точки не будут максимальными

30) Переместите левую сторону сферы в/из до максимальной точки

31) Переместите правую сторону сферы в/из до максимальной точки

32) Переместите фронт сферы в/из, пока точки не будут максимальными

50) Если какие-либо изменения в 25-32 затем повторите (goto 25)

70) Вычтите точки из последней добавленной сферы. Установите для всех значений значение "0" для внутренних значений (положительные числа) и не настраивайте внешние значения (отрицательные числа). Получите 15.

80) (необязательно) Заполните внутренние промежутки. В основном посетите каждый элемент, чтобы убедиться, что он меньше или равен 0. Если положительный, то goto 20 с этим элементом. Иначе, если не найдено, то goto 85. Примечание: все внешние значения должны быть отрицательными, а все внутренние значения, которые находятся в сфере, должны быть равны 0.

85) Закончено

Примечания

Так как будет сетка значений, рабочее пространство 1000x1000x1000 будет потреблять 1 ГБ.
Не точное решение
Может потребоваться много вычислений для более высоких разрешений.
Для эффективности меньшие сферы могут иметь предварительно записанные диапазоны пикселей, чтобы сфера не требовалась для каждой итерации.
Сначала может быть выполнена версия с более низким разрешением (то есть 500x500x500), а затем местоположение и размер сфер могут быть применены к более крупному 1000x1000x1000. Также для очень больших форм можно было бы разрезать разделы.

Ответ 4

Хорошим началом было бы разработать алгоритм для:

1) Найдите наибольший радиус вписанной сферы.

2) Затем рассмотрим объем вычитания

3) Приблизить объем вычитания полиэдральным.

4) Разделите это многогранное на более мелкие (более мелкие) многогранники.

5) Повторить шаг 1.

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