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.
01May2012, 21:08  #1 
Registered
Join Date: Sep 2011
Posts: 7

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. 
01May2012, 22:54  #2 
Regular
Join Date: Jun 2004
Posts: 11,084

__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™ 
01May2012, 23:29  #3 
Registered
Join Date: Sep 2011
Posts: 7

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! 
02May2012, 09:29  #4 
Tea maker
Join Date: Feb 2002
Location: In the Island of Sodor, where the steam trains lie
Posts: 4,448

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 binpacking 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 ObjectOriented, and I can tell you I did not have C++ in mind." Alan Kay 
02May2012, 12:55  #5 
Regular
Join Date: Jun 2004
Posts: 11,084

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 coordinates 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 coords) 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™ 
02May2012, 13:32  #6 
Senior Member
Join Date: Nov 2007
Posts: 1,388

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).

02May2012, 14:38  #7 
Regular
Join Date: Jun 2004
Posts: 11,084

You know that has absolutely no meaning to me
__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™ 
02May2012, 15:51  #8 
Registered
Join Date: Sep 2011
Posts: 7

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! 
02May2012, 16:00  #9 
Registered
Join Date: Sep 2011
Posts: 7

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

02May2012, 16:28  #10  
Tea maker
Join Date: Feb 2002
Location: In the Island of Sodor, where the steam trains lie
Posts: 4,448

Quote:
__________________
"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 ObjectOriented, and I can tell you I did not have C++ in mind." Alan Kay 

02May2012, 16:53  #11 
Senior Member
Join Date: Mar 2002
Posts: 3,897

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. 
02May2012, 18:14  #12  
Member
Join Date: Jan 2010
Posts: 455

Quote:
Code:
@@@ @ @@ @@@ 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. 

02May2012, 19:43  #13 
Registered
Join Date: Sep 2011
Posts: 7

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 
02May2012, 21:52  #14 
Member
Join Date: Jan 2010
Posts: 455

Then you should consider a hierarchy with/allowing void volume on the node's BVs, bullet allows you to build BV hierarchies from primitives.

02May2012, 22:56  #15 
Regular
Join Date: Jun 2004
Posts: 11,084

doesnt bullet have a feature for grouping objects together ?
__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™ 
03May2012, 00:21  #16 
Registered
Join Date: Sep 2011
Posts: 7

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? 
03May2012, 09:06  #17 
Regular
Join Date: Jun 2004
Posts: 11,084

thats what I meant
__________________
Guardian of the Bodacious Three Terabytes of Gaming Goodness™ 
Thread Tools  
Display Modes  

