Welcome, Unregistered.

If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.

Reply
Old 01-May-2012, 21:08   #1
STTrife
Registered
 
Join Date: Sep 2011
Posts: 7
Default Partitioning a grid of cubes efficiently

Hello, I got a question, I hope I can explain it well.

If have a grid of (possible) cubes, say the grid is 10 by 10 by 10 and on each place on the grid there is either a cube or there is not. Now I would like to group cubes together that are next to each other together, into bigger cubes/boxes, to more efficiently describe the grid (for a physics simulation).

I assume this is not a very novel problem and there there are algorithms to do this optimally (or 'quite good') and hopefully a little fast. If i'd implement my own naive algorithm it'll probably be really slow :P

thanks for any advice!

Oh and with optimally I mean using the least amount of boxes.
STTrife is offline   Reply With Quote
Old 01-May-2012, 22:54   #2
Davros
Regular
 
Join Date: Jun 2004
Posts: 11,088
Default

So you want to render a as b but with cubes not squares ?
__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™
Davros is offline   Reply With Quote
Old 01-May-2012, 23:29   #3
STTrife
Registered
 
Join Date: Sep 2011
Posts: 7
Default

Yes indeed, and for clarity here is another example:



I want to create B from A, but not C for example (Because it has 3 parts instead of 2).

And ofcourse this is all in 3 dimensions, not 2.

Any idea what kind of algorithms I could use for this?

Thanks!
STTrife is offline   Reply With Quote
Old 02-May-2012, 09:29   #4
Simon F
Tea maker
 
Join Date: Feb 2002
Location: In the Island of Sodor, where the steam trains lie
Posts: 4,448
Default

I should imagine there would be quite a bit of literature coming from octree related work, but it just struck me that maybe this is not unlike Boolean minimisation in logic design e.g. Karnaugh Maps or the Quine–McCluskey algorithm. <shrug>

At worst, it might be a bin-packing problem which is hard.
__________________
"Your work is both good and original. Unfortunately the part that is good is not original and the part that is original is not good." -(attributed to) Samuel Johnson

"I invented the term Object-Oriented, and I can tell you I did not have C++ in mind." Alan Kay
Simon F is offline   Reply With Quote
Old 02-May-2012, 12:55   #5
Davros
Regular
 
Join Date: Jun 2004
Posts: 11,088
Default

I have an idea keep in mind I am just a dude that plays games and you shouldnt really pay any attention to me
but heres how i would do it.

first off lets number the square in your grid left to right (first row 1,2,3 ect) (second row 11,12,13 ect)

the you need to create all valid optimised cubes so a 10x10 cube 9x9 cube down to a 2x2 cube
note the top face of each optimised cube must contain the same amount of vertecies as the cubes it replaces
(the vertecies must also be in the same postion)
lets take the 2x2 optomised cube as an example
if we view the top face of it it would have vertecies in the following positions (same positions as 2x2 single cubes)


Next step is to grab (maybe put in a 2d array) the x/y co-ordinates of all the vertecies of the single cubes on the grid (top face only)

then place your 2x2 optomised cube on square 1 (obviously it occupies squares 1,2,11,12)
then you scan through your 2d array if you get a match for all verts in optomised cube with verts in the array(single cubes) you replace. if not do nothing

then move optomised cube to next valid location on grid (square 2 if no match, square 3 if match) and repeat

that was the example for 2x2
you would start off doing 10x10 then 9x9 ect

note: you dont actually have to create all the cubes, put them on the grid compare then move ect, (you just need to know all valid postions for the optomised cubes x/y co-ords) but explaining it the way I have makes it easier to visualise what i am trying to say.

I f this is a supid idea maybe it's give you some inspiration.
__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™
Davros is offline   Reply With Quote
Old 02-May-2012, 13:32   #6
sebbbi
Senior Member
 
Join Date: Nov 2007
Posts: 1,390
Default

Somehow my gut feeling tells me that this problem translates to finding the maximum clique in a graph... which is a NP complete problem. So finding an optimal solution might be impossible (unless your problem size is relatively small).
sebbbi is offline   Reply With Quote
Old 02-May-2012, 14:38   #7
Davros
Regular
 
Join Date: Jun 2004
Posts: 11,088
Default

Quote:
Originally Posted by sebbbi View Post
finding the maximum clique in a graph... which is a NP complete problem
You know that has absolutely no meaning to me
__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™
Davros is offline   Reply With Quote
Old 02-May-2012, 15:51   #8
STTrife
Registered
 
Join Date: Sep 2011
Posts: 7
Default

Thanks for your ideas Simon, I will look into the algoriths you mention .
The idea you propose Davros, will probably be too slow, I'm trying to imagine this with an example of maybe 10x10x10 which is about a large version (but not the limit) of what I expect will be used in the program.
In your idea I would first check the 10x10x10 full cube, if that fits, it's gonne be just one cube and I'm done.
If it doesnt fot, then I remove one row from either the x, the y and the z and try to fit for example the 10x10x9. But note, I also have to the check the 10x9x10 and the 9x10x10. Then if that does not fit it becomes 10x9x9 or 9x10x9 or 9x9x10 or 8x10x10 or 10x8x10 or 8x10x10. And if that doesn't fit there will be much more possible combination of the biggest cube that is not yet checked. It seems exponential to me, and that might be too slow.

What I was thinking about is more of a growing algorithm. In that I would first find a cube which has the most neighborgs, which, if put together would form a valid box. (so the best is a cube with all 8 neighbours, so a 3x3x3 box, or the next best things would be 3x3x2). Then from that best box, try to grow in different directions, and see how I can, in each step , make the box the largest by expanding in any of the 8 possible directions. Then at a certain point if it can't grow any more I would keep that box and not change it anymore. Then remove the cubes that were in the box from the grid and restart the algorithm, until no cubes are left.
Now I know this would not per se find the best solution, but I try to imagine how 'good' it would be. I do believe it would be fast enough for my purposes, but not sure how well the solutions would be.

But first, I'll have a look at the algorithms Simon proposed, see if they fit my problem!
STTrife is offline   Reply With Quote
Old 02-May-2012, 16:00   #9
STTrife
Registered
 
Join Date: Sep 2011
Posts: 7
Default

An Octree would indeed be able to group some cubes togehter, and if we're very lucky it will be optimal. but for example if the full box doesn't fit, it immediately starts by dividing the grid into 8 parts, which might already lose the best solution, so that's not our guy I'll keep looking at the rest
STTrife is offline   Reply With Quote
Old 02-May-2012, 16:28   #10
Simon F
Tea maker
 
Join Date: Feb 2002
Location: In the Island of Sodor, where the steam trains lie
Posts: 4,448
Default

Quote:
Originally Posted by STTrife View Post
An Octree would indeed be able to group some cubes togehter, and if we're very lucky it will be optimal. but for example if the full box doesn't fit, it immediately starts by dividing the grid into 8 parts, which might already lose the best solution, so that's not our guy I'll keep looking at the rest
I was thinking more along the lines of a "bottom up" fusion of cubes. Of course, you don't need to restrict every level to be a cube, but just an aligned rectangular prism (i.e. just split at one plane at a time) and you don't necessarily want to constrain them to power of two boundaries.
__________________
"Your work is both good and original. Unfortunately the part that is good is not original and the part that is original is not good." -(attributed to) Samuel Johnson

"I invented the term Object-Oriented, and I can tell you I did not have C++ in mind." Alan Kay
Simon F is offline   Reply With Quote
Old 02-May-2012, 16:53   #11
Mintmaster
Senior Member
 
Join Date: Mar 2002
Posts: 3,897
Default

I imagine that a greedy cube growth algorithm could be quite effective:
1. Seed growth cubes at each corner (i.e. grid locations with at least three adjacent faces touching empty space) with a flag for each face
2. For each growth cube, and for each face not yet marked as ungrowable:
-check if it touches any empty space, and if so, mark it as ungrowable; otherwise, grow it one step
3. Repeat step 2 until nothing grows
4. Sort them by volume
5. Check for intersections:
-Starting with the biggest cube, check what other cubes it intersects with
-If you care about making sure no grid location has a two growth cubes covering it, find the way to split each intersecting pair that results in the fewest new cubes (I assume that cubes can't overlap, right?) and insert the new ones into the list.
-Otherwise, just check if a smaller cube is ever completely contained in a larger one, and eliminate it.

Lots of optimizations possible even for this base rudimentary algorithm.
Mintmaster is offline   Reply With Quote
Old 02-May-2012, 18:14   #12
Ethatron
Member
 
Join Date: Jan 2010
Posts: 455
Default

Quote:
Originally Posted by STTrife View Post
Yes indeed, and for clarity here is another example:



I want to create B from A, but not C for example (Because it has 3 parts instead of 2).

Thanks!
Why least number-of? What would you want for this?:

Code:
@@@
@ @@
@@@
4 is the minimum number and there are about 10 distinct combinations for it. Of course it is a pathologically "bad" case.

Finding the smallest number is NP complete and your growth algorithm will very likely not come near the global minimum, just lock up on a local minimum - with the [probably guaranteed] biggest single volume of all possible solutions.
Ethatron is offline   Reply With Quote
Old 02-May-2012, 19:43   #13
STTrife
Registered
 
Join Date: Sep 2011
Posts: 7
Default

Mintmaster, thanks for the idea, seems like a decent algorithm, it is probably not guaranteed to find the best solution possible in all cases, but I suppose your algorithm would work just fine for practical situations.

Ethatron, the reason is that I want to feed the grid as a single (compound) object to the physics engine. less boxes is better performance. Ofcourse it is also possible to create several convex meshes and use that as collision object, but as boxes are implemented as basic shape in Bullet, so I assumed that a few boxes in a compound object might give better peformance than (a few less) convex meshes. But then again I don't know this for sure
STTrife is offline   Reply With Quote
Old 02-May-2012, 21:52   #14
Ethatron
Member
 
Join Date: Jan 2010
Posts: 455
Default

Then you should consider a hierarchy with/allowing void volume on the node's BVs, bullet allows you to build BV hierarchies from primitives.
Ethatron is offline   Reply With Quote
Old 02-May-2012, 22:56   #15
Davros
Regular
 
Join Date: Jun 2004
Posts: 11,088
Default

doesnt bullet have a feature for grouping objects together ?
__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™
Davros is offline   Reply With Quote
Old 03-May-2012, 00:21   #16
STTrife
Registered
 
Join Date: Sep 2011
Posts: 7
Default

I'll look into those BV hierarchies, I didn't notice them in the manual of bullet, but the manual does seem a little short for such a big library, so maybe I'll just have to look at the class referenc or something.

Davros: the compound shape is a way to group several shapes if that's what you mean, but it still needs to calculate for each subshape the collisions etc., that's why I wanted to reduce the number of boxes, but keep the same shape.
Or did you mean something else?
STTrife is offline   Reply With Quote
Old 03-May-2012, 09:06   #17
Davros
Regular
 
Join Date: Jun 2004
Posts: 11,088
Default

thats what I meant
__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™
Davros is offline   Reply With Quote

Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 09:13.


Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.