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

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

Второй документ

Казальс, Фредерик и др. «Жадные геометрические алгоритмы для сбора шаров с приложениями к геометрической аппроксимации и молекулярной грубой зернистости». Форум компьютерной графики. Том. 33. № 6. 2014 г. (скачать в формате PDF. )

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

Хм, моя лучшая идея на данный момент связана с машинами опорных векторов. Превратите ваш объект в целую кучу (возможно, равномерно расположенных) точек внутри и на поверхности объекта. Обучите модель SVDD с помощью линейного ядра (см. libsvm для SVDD). реализация). Затем решающая функция модели представляет собой неявную поверхность, определяемую опорными векторами модели (и ро). Снижение стоимости даст вам больше векторов поддержки, увеличение — меньше.

К сожалению, природа SVM такова, что область, охватываемая близлежащими опорными векторами, будет, э-э, «капли» вместе, примерно так:

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

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

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

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

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

Обзор

В основном добавляйте сферы внутри фигуры в положениях, максимально закрывающих поверхность. Мы преобразуем сферу в трехмерный массив байтовых значений со знаком. Эти значения являются точками и будут поглощены сферами. Мы добавляем по одной сфере внутри объекта, а затем увеличиваем/уменьшаем ее в разные стороны, чтобы «съесть» как можно больше точек. Цель состоит в том, чтобы набрать как можно больше очков за каждую сферу. Очки зарабатываются путем суммирования очков в области сферы. С добавлением каждой сферы мы подсчитываем, затем считаем эту область использованной и устанавливаем значения массива равными 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

(C) Добавьте небольшую сферу. (будем выращивать)

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

(E) Добавьте следующую сферу и увеличьте ее.

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

Процесс

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

85) Готово

Заметки

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

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

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

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

3) Аппроксимируйте вычитаемый объем многогранником.

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

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

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