Minimum oriented bounding box. Implementation in Grasshopper + Python script node

My ancient rvb finds a minimum box along an edge of your object. I’ll have to improve my python version… MinBB_jm.3dm (102.4 KB)

Ah, OK, one edge… but that’s a fairly ambiguous to test for anyway, as you can have an infinite number of planes through that edge…

Your BB is a little bit better than my Python current one after the rough stage, you have a volume of around 3111 cm3, mine ends up at 3125, 3119 if I push the number of samples… But I haven’t hooked up the refinement stage yet, still too many other projects…

My old RVB also does better than my current Python at 3115 with “standard” sampling, and even a tiny, tiny, bit better than yours at the “fine” sampling setting with 3110.7… :stuck_out_tongue_winking_eye: It’s parallel to a different edge…

MinBB_jm_msh.3dm (152.5 KB)

–Mitch

I think it is the same edge, but you’ve changed the orientation of the object. The locale minimum I’m finding with a simple solver which works pretty accurate and fast. The real problem is the “pre-sampling” and not missing any locale minimum. A convex hull seems to be the solution but it is a bit too complex for my use of the minimum bounding box. Maybe I’ll find another way…

Well, in between end-of-semester bouts of laser cutting, milling and 3D printing, I was able to work on my bounding box script for sometimes a few minutes, sometimes a half hour or so… I finally put a bit of UI on it and I’m going to throw it out here now…

It’s a combined 2D and 3D bounding box tool, it first checks to see if the input objects are planar/coplanar, if yes, it calculates a minimum bounding rectangle, if not, it calculates a 3D box. In both cases it makes an initial rough pass to find the orientation of the smallest starting area (2D) or volume (3D), then refines in successive passes with smaller increments. Each pass is an order of magnitude (10x) smaller than the previous. When the next pass cannot find a better answer than the previous within tolerance, it stops and spits out the result.

It will accept any combination of points, pointclouds, curves, surfaces, polysurfaces and meshes. No blocks, sorry.

I didn’t want to throw in a huge number of options, but there are 3…

  • Standard or fine sampling - applies only to the 3D routine. Standard is 10 samples (9 degree intervals) in all three axes which makes 1000 samples; each refinement is also 1000 samples. Fine sampling is 18 samples (5 degree intervals), so 5832 samples each pass, which will be quite a bit slower. With Standard it zeroes in on a solution reasonably fast, and I’m not sure how many cases will actually benefit from the Fine setting, but I put it in there just in case.

  • StopVal - also for 3D only - you can decide if you want the script to stop after the difference from the preceding pass is within a percentage tolerance (default) or an absolute value. Both are hard coded, the relative is set at 0.01% (one hundredth of one percent) difference from the previous; the absolute uses the file tolerance (which is likely pretty small considering it’s applied to a volume measurement). In general the absolute setting will provoke more passes.

  • ReportIntermediateResults will simply print the intermediate area or volume calculations to the command line, set it to no to turn it off. In any case the final result will be printed.

I’ve tested it in V5 and V6 on a few things here and it seems to work OK without erroring out - haven’t tried on Mac, but I think it should work. Let me know if you find any major (or minor!) problems…

MinimumBoundingBox.py (16.3 KB)

–Mitch

15 Likes

Dear Mitch,
Thank you for your effort and detailed description of the script. I am very impressed! Your script works very well with upper limb 3D scans.


I’ll mark my question as solved now.
This forum (and especially members) are very helpful!

Sincerely,
Ilja

Hello,
@Helvetosaur, I’m new to grsshopper and scripting, is it possible to include your python script into grasshopper?
Philippe

It’s not really set up for that, although I suppose it could be adapted somehow. As it’s iterative, it needs some time to work, plus it does various command line reporting in the process. The reporting would need to be eliminated and a trigger installed to launch/refresh the operation.

There are probably already some minimum bounding box Grasshopper definitions floating around out there…

Thank you for your answer

Hey, this is a great script! Do you know a way to change this to work for multiple geometries, so that it creates independent bounding boxes on all input geometries?

I suppose that option can be added. It won’t go any faster, as it would have to repeat the calculation for each object, it would just make selection easier if you have numerous objects. It isn’t totally simple to add, but I’ll have a look when I have time.

Hi,

I’ve edited the script by @Helvetosaur so it creates a box for each selected geometry individually.
MinimumBoundingBoxMulti.py (16.7 KB)

-Willem

4 Likes

Great! Thank you for your quick replies, i will give this a try next week.

The script works great! I want to tune it so that instead of minimazing the volume of bounding boxes it would minimize the shortest side of the bounding box. Then boxes would be as slim as possible. I’m not yet sure how to do this, so i would really appreciate if someone has time for this.

I want also to tune it so that output bounding boxes have the same names as input geometry. This should not be tricky.

name = rs.ObjectName(obj)
rs.ObjectName(bbox, name)

I edited the script so that each bounding box has same name as input object.

MinimumBoundingBoxMultiNaming.py (17.0 KB)

2 Likes

Thanks Mitch @Helvetosaur and other contributors for this script

Well i had a quick go to remove the commandline input and geometry creation.
This works in Grasshopper, but it does need some improvement.

Hope someone else can add to it. I provided an input for the number of iterations, rather than the fine toggle in the commandline. My edits are a bit hacky, but it works for my purposes (faster would always be nicer!)

Gh file includes some test geometry, both planar and 3d. All OOTB except the Human line preview at the end to show the wireframes in rendered view. entirely unnecessary and shouldn’t stop this working for anyone.


minbb.gh (26.1 KB)

4 Likes

Nice one!
I had a chance to compare both versions: mine and yours. For some reason my script works a bit quicker against yours (set with 10 iterations). Here is a comparison test file: minbb-py-comparison-Ilja.gh (610.4 KB)
Both outputs (volume values, orientations of BB) are quite similar.



For my purposes, computational time is very critical so I even think to rewrite mine Python version with C# component to make it even more faster. But I just started to learn C# language…

2 Likes

If you use a fixed size array for the “new_vol_x” (and the other two), namely the size of the range count, then you can run ALL those rotations in a simple parallel.For-loop and assign the result into the array index of your current index, like so: “new_vol_x[i] = int(volume(new_bb))

That should probably be significantly faster. In C# that would look something like

    var new_vol_x = new int[180];
    System.Threading.Tasks.Parallel.For(0, 180, i => 
    {
        ...
        ...
        new_vol_x[i] = int(volume(new_bb));
    });
    // Aso.

By only assigning indexed slots ([i]) in the array, each thread in the parallel loop will handle each case (i) without conflating it with any other index (i) in another thread, and so it will not cause any data races or other spooky things.

// Rolf

2 Likes

Hi @ilmar_ik,

I tried to understand the code I have baisc c# understanding but dont know python.
You rotate it degrewise 180 degrees, rot_x is the degree with the smallest bBox?
I dont understand what in line 30 happens:

rot_x = new_vol_x.index(min(new_vol_x))+1 #degrees

Thanks