How can a voxel model be divided into a very small number of boxes?

Question

3D

There is a voxel model that needs to be split into a very small number of boxes.
For example, there is a mushroom.
Its leg consists of at least 16 voxels (the visible part, you can take the very first level, then 20). And the leg can be combined into one 2x2x4 box.
In which direction to dig? Dynamic programming?
There is an idea to take some specific voxel, look at neighboring voxels. If it is possible to form a parallelpiped, then we go further, if not, then stop. Can it be easier?

Answer 1

Similar to the packing problem : fill a mushroom-shaped container with a minimum number of "boxes" of any size.
Such a problem is generally considered NP-complete and requires enumeration of all options.
For example, with this mushroom, one could start by looking for the longest continuous chains and find the central "pillar". Make it 1 piece.
But then the very top and the very bottom will require 4 more parts, each 2. And it would be possible to make the pillar not as high as possible, depriving 1 step from above and below. And then on the top and bottom of the parts it would take not 4, but 3 each.