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

Question

[addison-cochran]

Имеется воксельная модель, которую нужно разбить на очень малое количество параллелепипедов.
К примеру, есть гриб
Его ножка состоит из как минимум 16 вокселей (видимая часть, можно еще самый первый уровень взять, тогда 20). И ножку можно объединить в один параллелепипед размеров 2x2x4.
В какую сторону копать? Динамическое программирование?
Есть идея взять какой-то определенный воксель, посмотреть на соседние воксели. Если можно образовать параллелпипед, то идем дальше, если нет, то прекратить. Можно ли проще?

Answer 1

[Сергей Соколов]

Похоже на задачу об упаковке: надо заполнить контейнер в форме гриба минимальным количеством «коробок» любого размера.

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

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