Decomposing mesh into boxes

[basick]

Hello, I'm trying to find a way to efficiently scatter boxes inside a static object in such a way that they can cover as much of its volume as they possibly can.

Conditions for boxes I'm trying to meet:
- they may overlap, but their size should be proportional to the volume to be covered (e.g. 1 larger box rather than 100 small boxes for a given volume ),
- should cover as much volume as possible without straying too far outside of a geometry (coverage can be approximate),
- cannot be skewed, in the end, they need to stay orthogonal.

I've tried scattering boxes inside the volume first and then expanding them until they hit the boundary, but this method is slow and inefficient. I also tried clustering voxelized object, but this method is inefficient as well with complex geometry meshes (e.g. long, thin parts placed at an angle require small voxel size to catch the shape).
The closest I could get to the result I wanted was to use the convex decomposition to decompose mesh into convex shapes and then replace them with boxes. This works decent as a starting point, but often creates excess shapes that I'm struggling to find a way to cluster.

If anyone knows a better logic for approaching this problem or has a different idea I should try, I would be grateful. 

 

pack_000.hiplc

[Aizatulin]

Hi,

using the eigenvectors/eigenvalues of the covariance matrices seems to give good orientations and should give a proportional approximation of the volume (but this will depend on point distribution). Here is a modification using the eigenvector method.

@edit: there are two options using the relative bounding box or the eigenvalues(square roots) with scale (3 or something)

and if you want, that the box has the same volume as the piece, you can use the volume ratio and rescale the box.

pack_000_mod.hipnc

pack_000_modA.hipnc

Edited January 28, 2023 by Aizatulin

[maiden666]

I understand that this is not what you want, but...

Edited January 28, 2023 by maiden666

[basick]

@Aizatulin
Thanks a lot, I was also playing around with the way bounding boxes are created (wasn't planning on sticking with Bound SOP) but I wasn't aware of this method (not saying that it would be easy to implement for me without digging deeper into linear algebra..). Using eigenvectors of the covariance matrices definitely gives a good orientation at the cost of making them slightly larger when compared to Bound SOP, but this can be easily adjusted and produces a cleaner result in the end.

@maiden666
Yes, I was experimenting with converting mesh to vdb. The issue is that I was losing a lot of detail with some of the meshes during the process, resulting in an overly rough approximation of the original mesh (unless giving it more resolution, which made things slow). In the end, those boxes will primarly be used for collision detection in external software, so the closer I can get to the original mesh and the more efficient with the overall amount of them, the better.

Thanks again to you both, it gave me few ideas to play with. You guys are awesome.