@addison-cochran

Как можно воксельную модель разбить на очень малое количество параллелепипедов?

Имеется воксельная модель, которую нужно разбить на очень малое количество параллелепипедов.
К примеру, есть гриб Voxel_amanita.png
Его ножка состоит из как минимум 16 вокселей (видимая часть, можно еще самый первый уровень взять, тогда 20). И ножку можно объединить в один параллелепипед размеров 2x2x4.
В какую сторону копать? Динамическое программирование?
Есть идея взять какой-то определенный воксель, посмотреть на соседние воксели. Если можно образовать параллелпипед, то идем дальше, если нет, то прекратить. Можно ли проще?
  • Вопрос задан
  • 51 просмотр
Пригласить эксперта
Ответы на вопрос 1
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Похоже на задачу об упаковке: надо заполнить контейнер в форме гриба минимальным количеством «коробок» любого размера.

Такая задача в общем случае считается NP-полной и требует перебора всех вариантов.

Например, с этим грибом можно было бы начать с поиска самых длинных сплошных цепочек и обнаружить центральный «столб». Сделать его 1 куском.
Но тогда самый верх и самый низ потребуют ещё 4 деталей, каждая по 2. А можно было бы столб сделать не максимально высоким, лишив 1 шага сверху и снизу. И тогда на верх и низ деталей потребовалось бы не по 4, а по 3.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы