Sunday scripting - minimum 3D bounding box

Scripting
1

Been hacking at this on and off for awhile now, I think it’s finally ready to let out into the wild for testing… The script below attempts to quickly find the minimum volume bounding box of a given object or set of objects. As you well know this is an iterative task which usually involves a lot of testing. My goal was to have a tool which would work quickly and yield a good approximation for most objects. There are a couple of others already out there, but I wanted to write my own.

The method is a typical tree-branch “test and refine” sort of thing, it takes an initial set of samples, finds the “best candidate” and then loops through successively smaller variations around the target to refine it. A reasonably precise solution can thus be arrived at with relatively few iterations. The method I used for determining the initial sample and the refinements may seem a bit quirky though…

Note that with certain complex geometries, this strategy can be “fooled”, there may be a better branch point located somewhere between the initial samples which will not be found, so the method is not completely foolproof - but I wanted a quick one-click tool for most objects, and was willing to sacrifice the small possibility of a wrong answer on certain oddball objects for speed. Otherwise, one can work with Galapagos in Grasshopper for this type of stuff, as it is evolutionary and constantly considers a “pool” of best candidates, not just one.

Instead of hanging a lot of arcane user controls on the script, I ended up hard coding just two easy to understand options: Standard (faster) // Fine (slower) sampling and a Standard / Custom “are we done yet?” tolerance. That tolerance is not a tolerance in the real sense, it’s used to compare successive refinement steps, when the last refinement does not result in something smaller than the previous (within tolerance) the refinement is stopped. The “standard” tolerance is the file tolerance. I also threw some caps on the number of refinement steps for Standard/Fine.

The standard initial sampling setting checks the object at about 9° intervals, resulting in 1680 bounding box calculations. The fine initial sampling lowers that to 3°, making about 9 times that many… Successive refinements have each around 1320 (std) or 2640 (fine) calculations. So the Fine setting will be a lot slower for most objects. The more complex the object is the longer it will take, as Rhino takes longer to calculate each bounding box. A simple object like a box oriented at random in space takes only a second or two.

One trick: To override the artificial cap I set on the number of refinement steps (4 for standard, 9 for fine), set the tolerance to custom, then just accept the tolerance offered on the command line (it will be the file tolerance), the script will run until that tolerance is reached or 25 refinement steps have been done (the absolute cap to keep from a possible endless loop).

Anyway, FWIW - hopefully it’s useful to someone… I will get around to “Pythonizing” it in awhile for my Mac people… Note, it’s NOT been set up for drag and drop…

–Mitch

Edit: fixed version 1 below

QuickMinimum3DBoundingBox.rvb (8.8 KB)

5 Likes
2

Hi Mitch, a really useful script, thanks for sharing it - it seems to be hanging at line 152 here, trying to add a 3d vector to a point.

3

Hi Brian,

Is this on every object? Doesn’t do that here on anything I tested, but I haven’t tested it that extensively… If just one, can you post the object(s) so I can debug? (adding vectors to points shouldn’t be a problem so it’s elsewhere…)

–Thanks, --Mitch

4

OK, I found something that errors out too… Will check why, may take awhile… hmm, sorry about that.

Edit: OK, dumb mistake, it will error out with objects that are aligned with one of the princple planes with the initial sample… One line fix (I hope…) Re-Download form the original post, I will edit it…

–Mitch

5

That seems to be the answer Mitch, transform the object out of world plane and the script works well. Don’t stay up too late… Monday mid-morning here. :smile:

Edit: hope you don’t mind Mitch, I added to your script to end up with a ghosted BBox

Dim FinalBox : FinalBox = Rhino.AddBox(arrBB)	
If Not IsNull(FinalBox) Then
Rhino.AddObjectDisplayMode FinalBox, "Ghosted"
End If
6

Good idea - I have that in some of my other scripts I’ll add that too, thanks!
Edit: but beware, hard coding “Ghosted” may cause it to fail when running in other than English, as display mode names, like views, are localized… So I have it check for presence of a “Ghosted” mode first…

–Mitch

7

Thanks for your script Mitch! Very helpful! Since your are optimizing for speed. Just write your own vector functions replacing “Rhino.VectorRotate” and “Rhino.VectorUnitize”. It will be much faster. Here is one for Unitize and rotation:

' Normalize 3D Vector Function VectorNormalize(v) Dim VLeng VectorNormalize = Null If Not IsArray(v) Then Exit Function VLeng = Abs(sqr((v(0) * v(0)) + (v(1) * v(1)) + (v(2) * v(2)))) If VLeng = 0 Then Exit Function VectorNormalize = Array(v(0) / VLeng, v(1) / VLeng, v(2) / VLeng)

End Function

’ rotates a 3D vector v1 around axis vector v2 (axis vector must be normalized!) by angle a in degrees
Function VectorRotate1(v1, v2, a)

a = a * (3.14159265359 / 180)
Dim x,y,z
Dim u,v,w
Dim ux,uy,uz,vx,vy,vz,wx,wy,wz,sa,ca

x = v1(0)
y = v1(1)
z = v1(2)

u = v2(0)
v = v2(1)
w = v2(2)
	
ux = u * x
uy = u * y
uz = u * z
vx = v * x
vy = v * y
vz = v * z
wx = w * x
wy = w * y
wz = w * z
sa = Sin(a)
ca = Cos(a)
x = u * (ux + vy + wz) + (x * (v * v + w * w) - u * (vy + wz)) * ca + (-wy + vz) * sa
y = v * (ux + vy + wz) + (y * (u * u + w * w) - v * (ux + wz)) * ca + (wx - uz) * sa
z = w * (ux + vy + wz) + (z * (u * u + v * v) - w * (ux + vy)) * ca + (-vx + uy) * sa

VectorRotate1 = Array(x, y, z)

End Function
1 Like
8

OK, thanks! Have you tested the difference? My impression is that the bounding box calculation is the overwhelming time consumer here… Maybe I’m wrong about that, but as soon as the objects get more complex, the script slows down, even with the same number of iterations…

–Mitch

9

No, I haven’t checked it. But you are right, if it is not in your inner loop then in doesn’t matter… Might be useful for someone else, though.

Thanks

10

Hi

is anyone willing to share a minimum bounding box script using python? Would be helpful and very much appreciated!

Best Manuel

3 Likes