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

Hello for everyone,
I am trying to understand the logic of minimum bounding box definition so I can implement it in python script node. The reason is very simple - I am planning to test my gh definitons on Shapediver, which does support python script + Grasshopper. I am trying to develop an automated upper limb 3D scan re-alignment tool and as far as I am aware there is no possibility to (re) execute Galapagos in Shapediver.

I have a well-working definition in Grasshopper + Galapagos (attached) and I do have a sense that it is checking all possible options (optimisation algorithm) and seeks out for the best combination which generates minimum volume.

I did try to convert VBS to Python syntax of the code kindly provided by Mitch Heynick (I have a feeling that [Helvetosaur] is the same person here) but I am getting errors there as well (also attached here). I don’t have strong programming skills, all I do is I use this/grasshopper forums and try to “read” and “rewrite = understand” others scripts.

As I understand this is an iterative process (for loop) to rotate initial WorldXY plane, which defines the orientation of 8 points which defines boundaries of a object. So I have to rotate WorldXY plane around X [1,0,0] AND Y[0,1,0] AND Z[0,0,1] axes 360 times each and for every combination create generate “boundaries” for every combinations and check if its volume is still smaller than initial volume? So this is 360360360 combinations? So should I write all values (volumes) generated in for loop into a list and find a minimum value of that list? I am loosing track here at some point. Don’t really understand how to move from this point.

I don’t need a very precise and accurate method to find a minimum oriented bounding box. I would be very thankful if anyone could advise me how to implement this or give some hints about the most effective way to do it. It can be any example, even not related with this topic. Maybe there is a literature which practically explores similar optimization issues? I appreciate for your time and help QuickminimumBB VBS to Python Script by Mitch.gh (5.3 KB)
min_oriented_bb_ilja.gh (39.8 KB)

Sincerely,
Ilja

I gave it a try as a RhinoPython script. It runs but I must have something wrong because it doesn’t work very well. Let me know if you can find where I went wrong.

MinBB_VB_to_Python.py (6.7 KB)

Just to let you know that I am working on a new python version (based on my old VB method) but I haven’t got it finished yet… May be a few days more, I’ve got a lot of irons in the fire currently…

2 Likes

My two cents:

Forget about iterative long processes. For this problem binary search is way better and faster :slight_smile:

Hi Angel,

I’m curious how you would go about using a binary search as a means to speedup the minimum bbox finding.
You would still have to create the values to do a search on.
Since we want a minimum there is not much of a target search.
Am I missing something?

-Willem

Print a graph of the volume of the bounding box been rotated in only one axis.

Hi, Here is simple example, you don’t really need to create “360” rotations of the bounding box, apparently the Minimum Bounding Box is going to lay on one face of the convex hull, so you only need to calculate the 3d convex hull and align the geometry N times(being N the number of faces in the convex hull), I haven’t tried in 3d but in 2d is the faster way I have found, one problem would be to determine what are the correct points to use in the 3d convex hull, in a polygon is a lot easier and types make this a lot more complex to.

https://gis.stackexchange.com/questions/22895/finding-minimum-area-rectangle-for-given-points

This is my attempt to get a solution that’s not recursive, and you can increase precision, it uses the 3D ConvexHull that is on MilkBox. please tell me if I’m missing something, for me this was kind of “easy” and by looking at Helvetosaur VB script it seems a lot more difficult so I’m not sure If this is the right solution. Thanks

MINIMAL BOUNDING BOX.gh (14.7 KB)

1 Like

If I have a graph, I already have all the date to find the minimum for right?
How would that involve a binary search?
Still I do not see how one axis as a start would be sufficient.
This shape for example will have a flat graph when rotatating the bbox around the top-view z-axis:

Yet my minimun bbox will need to be alighned with the slab faces

-Willem

1 Like

Hi Antonio,

I like the idea of assuming the bbox to be aligned to a flat face.
Ofcourse with meshes you will always have planar faces, whereas with nurbs it’s easy to have curvature surfaces only.

Unfortunately I cannot run you definition because of some components missing and unable to download them.

For my own current implementation I know for sure I indeed will end up with a face-aliged bbox so I’m planning to optimize it by doing a coarse iterative scan followed by an iteration over all planar faces that are closely aligned to the found coarse solver’s bbox.

I get a feeling this 3D minimum bbox problem would be a really nice quest/competition.
We create a standard test set of breps and start a quest for the most efficient solver to find the minimum bbox within a definable tolerance.

-Willem

1 Like

That’s one of the best things with this forum. This fosters great ideas which we have already seen several times. Very good idea.

// Rolf

Hi,sorry there, I have mistaked the plugin MeshEdit for Milkbox.
Yes, it would be interesting to have a component that solve for different types of geometries with different algorithm, using the faster for the respective type, Probably Surfaces are the most complex cases, and recursion(optimization) is always available for it. One could probably solve using multithreading for those cases, the same for large meshes. Thanks
http://www.food4rhino.com/app/meshedit

First of all, let me thank you for your attention and help! I am very curious to test your scripts! I’ll do it straight away! After I posted this question on the forum, I moved on and tried to develop mine own way! And surprisingly - it worked out!!! It is not accurate enough, but it generates the output relatively quickly and can operate on multiple objects. The Idea is very simple:

  1. Rotate an initial worldXY plane arount global X axis 180 times. Calculate volumes and append then into an empty list
  2. Find a plane which generates a minimum volume (index of item +1) Assign defined plane as current
  3. Repeat the same procedure, but rotate around Y
  4. Repeat the same, but rotate around Z,
  5. From resultant bb extract local axes with vector
  6. Repeat 3 rotations around local axes.
    At least I understand what is happening :wink: I think that some sort of refining can be added to increase achieved accuracy. You are very welcome to test mine rought_bounding_box_ilja_working.gh (9.3 KB)
    rought_bounding_box_ilja_working.3dm (37.9 KB)
    Thank you again

I don’t have the time to look closely into this right now, but just to point out a few things - finding minimum oriented bounding box in general is a difficult problem to do efficiently. Over all possible orientations, the box volume or “fitness” does not change in well behaved (convex) manner , so you can’t simply do a binary divide-and-search algorithm or treat each axis “one at a time” ( if I understood the above post correctly) .

Most of the time you’ll see people simply plugging the rotation controls into Galapagos or some other nonlinear solver because that’s often the simplest way to get things done. Also worth noting that because of box symmetry, you only have to consider a range of 0 to 90 degrees in all axes instead of the full 360, that cuts down the search space by factor of 64 .

@Antonio_Cersosimo The property of convex hull faces only applies for 2d bounding rectangle, in 3D it’s not necessary for the minimum bounding box to be oriented to a mesh face. The wikipedia article (https://en.wikipedia.org/wiki/Minimum_bounding_box_algorithms) explains the exact conditions for 3D but they are not as easy to take advantage of as in 2D.

image

(To really go deep into the issue there are published papers with all sorts of complicated maths involved, some implementations can be found here https://github.com/gaschler/bounding-mesh)

4 Likes

Here, I’m uploading an implementation of MAR(Minimal Area Rectangle) in python for anyone interested, it is an analytical solution, I’m pretty sure this one works fine, but if anyone notice any bugs or inefficiencies please comment on it.
Hi, qythium, Thanks, I knew I was oversimplifying the problem. The O’Rourke’s algorithm seems very interesting.http://cs.smith.edu/~jorourke/Papers/MinVolBox.pdf

This are other possible condition for “alignment”:

– There must exist two neighboring faces of the smallest-volume enclosing box which both contain an edge of the convex hull of the point set. This criterion is satisfied by a single convex hull edge collinear with an edge of the box, or by two distinct hull edges lying in adjacent box faces.
– The other four faces need only contain a point of the convex hull. Again, the points which they contain need not be distinct: a single hull point lying in the corner of the box already satisfies three of these four criteria.

Minimal Bounding Rectangle Python.gh (5.6 KB)

1 Like

This is similar to what I do… Rough calculation, get best result, refine with a smaller locus around that, repeat the refinement stage as many times as you want…

There is always a chance that the rough calculation will miss a different, smaller bounding box on a different vector if the object is really irregular. In that case one could say, pick the best 3 or 5 results and refine them all, and see if one jumps out… But that’s a lot of work.

Yep. That part’s done.

Just haven’t had time to get all the refinement stage and UI hooked up… too many other things to do currently.

–Mitch

1 Like

Based on the Convex Hull idea mentioned above, it could be a significant speedup to first check

  • A. if there are any curved edges (on the ConvexHull), and if not

    • Ab. test if there’s only planar surfaces and,
      • Abc. if so, test only with these planar surfaces oriented to WorldXY for the BoundingBox test.
        In many (most?) cases that would get very quickly to a minimal bb(?).
  • B. If not Abc, then do the more extensive tests

// Rolf

Is that really guaranteed to be true…? How about this quick example… Doesn’t seem that the minimum bb is parallel to any face or edge… All faces are planar and edges linear.

MinPlanarTest.3dm (80.7 KB)

I guess it might be parallel to one of the faces of a convex polyhedron made from the vertices… Wouldn’t know how to get that though.

Hm, right, that’s not the case. Funny how geometry can fool you (me). :slight_smile:

But then the next question: is the final minimum bb perhaps touching any of the edges of that parallel face which in its oriented position gives the smallest bb among those parallel oriented faces?

If so trying to tilt over the edges of that face, at least the Convex Hull would give a better starting point?

// Rolf

Hey!,

Yes, you are totally right, the binary-search or divide and conquer approach only works straight away on 2D shapes (knowing the plain in which they are contained). I have that implemented for nesting purposes and works well (even for round shapes or splines).

For 3D shapes is more complicated than just that as you guys pointed out; I didn’t jump into it yet and supposed that it could be solved with a similar approach. I’m thinking in a solution using a solution space clustering approach (to try to reuse partially the binary-search trick). Let’s see if it pushes me to any interesting solution.

Cheers!

1 Like

This paper talks a bit about on how to implement the MBB using the edges of the convex hull as reference.
http://clb.demon.fi/minobb/minobb.html

1 Like