Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (576)
games submitted by our members
Games in WIP (497)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Maximum inner box of a convex hull  (Read 3263 times)
0 Members and 1 Guest are viewing this topic.
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Posted 2005-12-15 15: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
Offline DzzD
« Reply #1 - Posted 2005-12-15 16: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...
3 - find your sphere radius : r=xmax-cx
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

Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #2 - Posted 2005-12-15 17: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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #3 - Posted 2005-12-15 19: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.
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #4 - Posted 2005-12-15 22: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
Offline DzzD
« Reply #5 - Posted 2005-12-16 09: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

Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #6 - Posted 2005-12-16 15: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.
Offline t_larkworthy

Senior Member


Medals: 1
Projects: 1


Google App Engine Rocks!


« Reply #7 - Posted 2005-12-20 15: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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (12 views)
2014-04-15 18:08:23

BurntPizza (11 views)
2014-04-15 03:46:01

UprightPath (24 views)
2014-04-14 17:39:50

UprightPath (10 views)
2014-04-14 17:35:47

Porlus (27 views)
2014-04-14 15:48:38

tom_mai78101 (49 views)
2014-04-10 04:04:31

BurntPizza (108 views)
2014-04-08 23:06:04

tom_mai78101 (208 views)
2014-04-05 13:34:39

trollwarrior1 (176 views)
2014-04-04 12:06:45

CJLetsGame (182 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!