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)
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?
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.
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
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:
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.
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:
Rotate an initial worldXY plane arount global X axis 180 times. Calculate volumes and append then into an empty list
Find a plane which generates a minimum volume (index of item +1) Assign defined plane as current
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 .
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.
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.
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.