Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (592) Games in Android Showcase (168) games submitted by our members Games in WIP (645) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Maximum inner box of a convex hull  (Read 3888 times) 0 Members and 1 Guest are viewing this topic.
darkprophet

Senior Devvie

 « Posted 2005-12-15 14:32:26 »

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

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
DzzD
 « Reply #1 - Posted 2005-12-15 15:56:12 »

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...
4 - your inside box edge length is e=Math.sqrt((r*r)/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

darkprophet

Senior Devvie

 « Reply #2 - Posted 2005-12-15 16:19:16 »

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

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
t_larkworthy

Senior Devvie

Medals: 1
Projects: 1

 « Reply #3 - Posted 2005-12-15 18:26:59 »

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

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
darkprophet

Senior Devvie

 « Reply #4 - Posted 2005-12-15 21:30:18 »

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

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
DzzD
 « Reply #5 - Posted 2005-12-16 08:36:59 »

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

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

t_larkworthy

Senior Devvie

Medals: 1
Projects: 1

 « Reply #6 - Posted 2005-12-16 14:28:12 »

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.

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
t_larkworthy

Senior Devvie

Medals: 1
Projects: 1

 « Reply #7 - Posted 2005-12-20 14:09:05 »

I have found a way to calculate eigenvectors at last!

http://math.nist.gov/javanumerics/jama/#Background

(also cholsky decompositions ... needed for JOODE)

Runesketch: an Online CCG built on Google App Engine where players draw their cards and trade. Fight, draw or trade yourself to success.
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 deepthought (17 views) 2015-06-30 15:39:44 deepthought (20 views) 2015-06-30 15:39:09 deepthought (24 views) 2015-06-30 15:36:52 Za\'Anzabar (20 views) 2015-06-29 05:44:54 TritonDreyja (36 views) 2015-06-24 17:10:40 CopyableCougar4 (33 views) 2015-06-23 00:34:45 BurntPizza (36 views) 2015-06-21 20:36:46 cookiecompiler (80 views) 2015-06-11 15:42:53 cookiecompiler (44 views) 2015-06-11 15:41:14 NegativeZero (71 views) 2015-06-11 09:49:18
 princec 37x theagentd 19x BurntPizza 18x wessles 18x opiop65 18x CopyableCougar4 18x Riven 17x nsigma 16x EgonOlsen 15x KaiHH 14x SauronWatchesYou 12x KevinWorkman 11x sunburn 11x DavidBVal 10x NegativeZero 10x SHC 9x
 How Do I Expand My Game?by bashfrog2015-06-14 11:34:43List of Learning Resources2015-05-31 05:37:30Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org