Hi all,
Does anyone know of a way to find the maximum volume inner box of a set of points forming a convex hull ?
An example of this would be a lot of points forming a sphere, and I would like to find the box that sits inside the sphere…
DP
For a sphere it is quite simple, but I dont know for more complexe shape.
Inbox for a sphere:
1 - find your mesh Outbox : xmin,xmax,ymin,ymax,zmin,zmax
2 - find the center of your Outbox cx,cy,cz : cx=(xmax+xmin)*0.5,cy==(ymax+ymin)0.5 etc…
3 - find your sphere radius : r=xmax-cx
4 - your inside box edge length is e=Math.sqrt((rr)/3)*2
finaly : your inside box is a box width edge length=e and with its center = cx,cy,cz
you can also find ovoid inbox with few modifications
Bruno
Thats not a reliable solution…
If you imagine a triangle with a kink in one of the sides, the sphere would be outside that kink, hence there is a possibility that the inner box of that sphere to be outside the shape…
DP
The inside sphere is equivelent I beleive by finding the width of your convex hull (perhaps a lie, but it would be a good aprox at least :-)). Finding the width is still a pretty tricky computation, on par with general collision detection of arbitary geomeotries. Doing it for a box makes it x10.
I don’t think you could actually do it in one step way. You would have do an optimizing routine and there would be local minima present (but they could be ignored if you only need an approx). Do you need a perfect solution? Do you need it in real time? I think the best tradoff of those things would be a hill climber.
I rememebr in the main OBB paper they approximated a tight fitting bounding box, which is a similar, by randomly generating points over the surface of the hull. With these points they built a covarience matrix and took the eigenvectors. This gives you the principle directions of the points. The largest axis being the longest axis of spread. A Box built using these (inherently orthoganal) vectors will be a pretty tight fit round the points. But not optimal. Note they had to generate random points so that localized detail in the convex hull will not bias the covariance. I would have thought the same procedure for creating an inside box would also be pretty good.
I think the second approach I have mentioned would probably give the best speed accuracy tradoffs, but is a numerical nightmare. I do not know how to calculate eigenvectors for one thing (outside of matlab). Good luck. Its a real b***** of a problem that one
It is not required to be in real-time as the solution can be stored and then used again. It doesn’t need to be the optimal solution, but it cannot over-estimate, meaning the inner box cannot pass through the convex hull in any situation. It can under-estimate, which is fine.
Sounds like a toughie
It should works at least for a sphere , no ?
Here is a good paper about silhouette and covering convex hull in a first steep : http://research.microsoft.com/~hoppe/silclip.pdf
Other good paper can be found there http://research.microsoft.com/~hoppe/
Bruno
Dunno how useful this is but a triangle with a kink in the side is not a convex hull.
Anyway the algorithm mentioned does not work becuase even in the case of a simple triangle bounded by an square. The circle inside the square certainly would not envolope the triangle. Especially obvious if two of the verteces from the trinagle touch the verteces of the bounding box.
If it is not in real time and can be computed upfront and you don’t want to mess around fiddling for ages with math, then perform a search. Your parameters for optimization are the width, height, length of the box, the center point (3 variables) and the orientation (4 variable if a quaternion). The fitness function is the volume of the box iff the box does not overlap. To test for intersection betweeen a box and the convex hull just do numerous edge-box tests. The math for that is ugly but not overly difficult. To perform the search choose a method. If you want a really dirty quick solution jsut try loads of random variables, otherwise maybe genetic search or becuase everything is floating point evolutionary stratergies would be quite appropriate. ES is fairly easy to implement from scratch and we are in the AI thread! Or a hill climber would be good (try it from a few starting conditions).
This is the route I would go I think, not becuase its the best (the eigenvectors of the covarience matrix is probably the best), but becuase its probably the simplest to program. The search algorithm will be the hardest to write (becuase they are hard to debug). I use ECJ alot for my evolutionary needs but it might take a while for you to get the hang of it. Still, its worth investing in some generic seach software. You can use it it loads of places quickly and dirty if you have got a decent setup.
I have found a way to calculate eigenvectors at last!
http://math.nist.gov/javanumerics/jama/#Background
(also cholsky decompositions … needed for JOODE)