Minimum bounding box problem

[bildsoe]

Hi,

I'm working at a small company currently trying to create a casting mould for double curved surfaces. I'm in charge of programming, and I'm creating a plugin for Rhino which is supposed to take a double curved panel and reorient it to the xy-plane from where it is read and sent to our machine.

In order for this to work, I need to calculate a minimum bounding box and use this to check if it is within the allowed domain for the machine.

In Rhino / Grasshopper I can use an evolutionary solver and use the volume of the bouding box as fitness and rotation of the baseplane in x,y,z axi as genomes. However in the solution I'm currently doing I cannot use the elolutionary solver.

Do you have any ideas of how to solve this?

My current solution is to read a lot of points on the surface. Find the best fit plane through the points using a SVD factorization(I'm a math newbie, so I found the SVD solution on a math forum and implemented it), and then I incrementially rotate a bounding box in this plane, and accept the minimal volume as my solution. It is especially this last part I don't like.

Best
Thomas

 

[Stephen Tashi]

a double curved panel

I don't understand what "double curved" signifies. Is this panel specified by one or two equations for a surface (in some coordinate system)? Or is it a more complicated shape, say one that would be specified by a large number of different areas, each with its own equation?

Does the terminology "panel" mean that it can be modeled as a single curved surface or does "double curved" mean that it is a 3D object bounded by two curved surfaces and more or less straight "walls" on the edges - i.e. is it more like a car door or a car hood?

 

[bildsoe]

Sorry. Panel is just a term we use at the practice where I work. By panel I mean a three dimensional surface. By double curved I mean that in any point on the surface it has two perpendicular intersection planes which yields two non-straight curves.

The surface is continuous in all of its domain, so it can be described by one equation. The minimum curvature radius is 400mm.

 

[Stephen Tashi]

It wouldn't surprise me if there are papers written about problems like yours, but I haven't searched for them yet.

In practical geometry optimization problems, I have used very general technique that you might find useful - if not for this particular problem then perhaps for others. I haven't seen this method described anywhere or given a name, so I don't know what to call it.

There are often problems where you need to search a space of parameters that describe the size and "pose" of an object and try to find optimize something about the situation that depends on geometry. For example, find a box of a given size that contains the most points in a set, or find the biggest box that contains no points in the set etc. The vexing property of such a search is that you cannot simply search a grid of points in the space of parameters since you can't be sure what happens to the geometry at the values "between" the grid points. For example, in your problem, the a box might be described by the one corner (x,y,z) and 3 vectors that define the edges. Taking that approach, the parameter space has 12 dimensions. It might be that a cluster of points exactly on points of the grid don't define bounding boxes, but some non-grid point in the their vicinity does.

The method I have used tries to test the feasibility of all the points in a "cell" of the grid, by which I mean all the points in a hypercube whose vertices are points on the grid.

Let the cell in question be C. Imagine (but don't necessarily write) a program that draws all the figures defined by the parameters in C, not just the figures defined by the parameters that are on the vertices of C. It draws the figures defined by the interior points also. In your case you would imagine a program that "drew" in 3D space all the bounded boxes defined by the parameters in C. (It would vary the corner (x,y,z) the vectors defining the sides etc. Each parameter would be varied by plus or minus some amount. about some fixed value.)

The figure that is formed by the union of all these figures is some kind of complicated 3D solid. Let's call this figure F_union. It may be possible to construct a simpler figure F_big that contains F_union (F_big could be a box or even a different shape) and has the property that it is simple to perform the algorithm that tests whether F_big satisfies the required geometry. In this case, you would test whether F_big bounded the panel. The utility of testing F_big is that it can detect infeasible cells. If the F_big for a cell C doesn't contain the panel, then no box defined by a point in C could contain it, since the box defined by one point would be even smaller than F_big.

The figure that is formed by the intersection of all the 3D figures will also be a complicated shape. If you allow the parameters to vary too much (by making C too big) then it will be the null set. Let's assume you make the scale of the grid small enough so that this doesn't happen and call the figure F_intersection. It may be possible to define a smaller figure, F_small (it can be any shape that you want) that is a subset of F_intersection and has the property that we can write an algorithm to determine whether F_small satisfies the geometry. In your case, this would mean to test whether F_small contained all the points on the panel. The utility of testing F_small is that it detects cells that contain only feasible solutions. Since F_small is a proper subset of any box defined by parameter values in the cell, if F_small contains all the points on the panel then all parameter values in the cell define feasible boxes.

The general search procedure is:

1) Establish some rough bounds on parameter space.
2) Define a grid size such that the F_small for a cell is not the empty set.
Search the cells of the grid as follows.
For each cell C, find the F_big for the cell.
If F_big fails to satisfy the geometry, forget about searching C and search the next cell.


If F_big satisfies the geometry. Compute F_small for the cell.

If F_small fails to satisfiy the geometry then we have the posibility that C may contain both feasible and non-feasible values of the parameters. So subdivide C into a smaller grid and repeat the search procedure on that grid.

If F_small satisfies the geometry then each value in C is feasible. You can search for an optimal value within C by using an algorithm that assumes all the values "in between" feasible values are also feasible. Or you could simply subdivide C into a smaller grid and repeat the search procedure on this smaller subdivision of C - to save writing special code.

There should naturally be a limit on the smallest grid size that is used in the above calculations and the search should terminate when that grid size is reached. This condition might cause the search to miss a mathematically ideal answer, but since the controls and measurements of practical geometry have some limits on their precision, the answers found by the search are practical to use.

 

[bildsoe]

Thank you for the very elaborate answer. I have a couple of questions. In this method you propose, I'm supposed to have found the fit plane first right? or else won't the boxes allways be based on the chosen plane for the grid? and the chosen plane for the grid, might not necessarily be the one in which the minimum bounding box is defined. Actually does it take rotation into account?

 

[Stephen Tashi]

The admittedly sketching description I gave didn't mention a plane, although when if you try to implement it, you might deal with planes when you try to determine if a particular box bounds the panel. The parameters (x,y,z, ax,ay,az,bx,by,bz,cx,cy,cz) describe an oriented rectangular figure in 3D space. The vectors that give the 3 sides implicitly define the angles of the boxes sides with the coordinate axes, so I suppose you can call this rotation. ( When I think of "rotation" I think of rotation with respect to something. )

Of course you can parameterize bounding boxes differently. You could parameterize them by (x,y,z, l,w,h,theta, alpha phi) where (x,y) is the center. (l,w,h) are the length, width and height of the rectangle and (theta,alpha,phi) are the roll, pitch, yaw description of the orientation of the rectangle.

I'm interpreting "bounding box" to literally be a box in in the sense of a rectangular solid in 3D space. Perhaps you mean something different by "bounding box". My point of view is that we leave the panel in some default position and try all sorts of boxes, which have various sizes and orientations. When you find the best bounding box, you can define a coordinate system where that box is your machine and compute how to express the location and orientation of the panel inside it in those coordinates.

One thing to consider about your problem is whether you only need a feasible solution (one where the panel fits in the machine) instead of an optimal solution (the smallest bounding box that can be fit around the panel).

 

[bildsoe]

Ah ok, I had trouble abstracting from the fact that the vectors could point in other directions than a x,y,z based grid.

Do you have any figures or other visualization of this method? I have trouble visualizing the result and my understanding is very visually based.

I found a method called O'Rourkes where you find the centroid of the surface and more or less by brute force rotate a bounding box around this point finding all configurations of the bounding box, selecting the minimum one. However this is pretty slow. Computational speed also plays a role.

Is it correctly understood that your method is somewhat faster since it tries configurations that are related to the actual surface?

We actually only need to know a feasible solution. However our machine is most precise towards the center of it, so in the long run an optimal solution would be better but a feasible would suffice for now.

 

[Stephen Tashi]

I don't have any material on the method readily at hand since I'm now a happily retired guy.

Making this method work does require a good ability to visualize geometry. In the cases that I have applied it, it didn't require calculus or advanced linear algebra.

Let me sketch a simpler case of it. Suppose the problem is to find the largest rectangle that fits inside a given irregular shaped figure in 2D.

Parameterize the rectangle by its center (x,y), the length and width of its sides (L,W) and an orientation angle theta. So a point in the parameter space is (x,y,L,W,theta).

A grid cell in parameter space has lower "left" corner (x - dx, y - dy, L - dL, W - dW, theta - dtheta) and upper "right" corner (x + dx, y + dy, L + dl, W + dw, theta + dtheta) where dx,dy,...dtheta are finite values, not "infinitesimals".

Consider the particular grid cell around (x,y,L,W,theta) = (0,0,5,10,0)

Once upon a time, I actually wrote a program that rendered the rectangles corresponding to many points in that grid cell (my approximation for "all" of them). It superimposed all these rectangles on each other. The points that were in all of the rectangles were colored red and the points that were in at least one, but not all of the the rectangles were colored blue. So if I picked (dx,dy,dL,dW,dtheta) small enough I ended up with blue shape with a red shape inside it. These figures are F_union and F_intersection.

From the pictures and some elementary geometry, I figured out a formula for a simple shape that contained F_union, the blue points. As I recall it was a figure that amounted to rectangle with two triangles stuck on its opposite ends. This figure is F_big.

I also figured out the formula for a simple shape that fit inside F_intersection, the red points. As I recall it was a diamond shape. This is F_small.

(I think I could have used a box shape for both F_big and F_small, but I sensed that the code would work faster if I exerted myself to make the figures "close" approximations for the colored figures.)

[ I edited the following since I had things exactly backwards on my first draft of this post!]

The code followed the procedure I outlined. The important point to grasp is that if you test whether F_big is within the required boundary and find that it IS, then you have veriifed that ALL of the parameter values in the entire cell produce rectangles that are within the boundary. If you test whether F_small is within the required boundary and find that it NOT, then NONE of the parameter values in the entire cell produce rectangles that are within the boundary.

The two tests above don't exhaust the possibilities. When you find that F_big is NOT within the boundary but F_small IS, then you must begin searching the cell using a finer grid.

If you finally get to a cell where F_bis is within the boundary then parameter value at the center of that cell is a good practical solution since it produces a rectangle within the boundary and the parameter values around it do also. You have some room for error if you are trying to set the parameter values in a real life situation.

The method could miss an "unstable" solution, one where one vector of parameter values gives rectangle within the boundary but any small change in one of its values produces a rectangle that doesn't work.

Although I used the example of defining your bounding box with vectors, reflecting on the above example, I think your instinct to use orientation angles is better.

In the above example the equations for the edges of F_big and F_small could be worked out assuming x = 0, y = 0, theta = 0 and doing the math only as a function of L,W, dx,dy, dtheta. To compute the edges of F_big and F_small for different x,y,theta values, all I had to do was a transformation of coordinates to reorient the shape.

Whether this method works for your problem will depend on whether you can find a way to write the equations for an F_big and an F_small. You have to visualize the figures "swept out" as the parameter values vary through all the points in a cell.

------------------

In your current code, when you have a particular bounding box, what method do you use to determine if the panel is completely inside it?