I’m playing around with a python bounding box generator and one of the things I would like it to do is find and create the smallest possible boundingbox. It doesn’t have to be mathematically perfect but close enough to not waste space.
I tried doing it by duplicating the object, querying the current bounding box and calculate the volume of the box. Then I’d rotate it 20 degrees and do the query again and so on… It works and I get a decent approximation of the smallest bounding box.
However, to do this with even 20 degree precison, it takes over 1400 loops and that just won’t work when you have a lot of objects in the scene to run the script on. Has anyone got nice easy solution for this?
Get a convex hull using something like qhull.
Get all of the vert-vert vectors in the hull and find the longest one.
Rotate the object so the long vector is aligned along a cardinal axis
get the vectors again in the plain perpendicular to the long axis. Pick the longest one there and rotate around the first axis so it is a second cardinal
Now get your ws bounding box.
If the objects are not too heavy you can do the same thing without the Qhull step
There’s an algorithm that finds the minimum volume bounding box of a convex hull without approximation.
This website has an excellent selection of well documented computational geometry algorithms, including a C++ implementation of this algorithm: http://www.geometrictools.com/LibMathematics/Containment/Containment.html
Actually I wouldn’t be surprised if there’s already a python library out there for that.
On the other hand it’s a fun exercise, if you have some time.
A while ago I implemented an approach similar to your suggestion in maxscript - it starts with large angles and then gradually refines the search. It repeats this along all axes, until it cannot reduce the volume anymore.
It’s an approximation, but gets precise very quickly and I didn’t have to bother implementing a convex hull algorithm in maxscript. (Although nowadays, I’d probably generate one with MassFX)
Yeah, the whole thing is an excercise. I’m trying to learn python. A couple of guys at work found it useful already so I want to keep improving it but it’s starting to sound seriously advanced so I may have to hand the reins over to a tech artist…
I’ll check your suggestions out and see if I understand them first though!
