Partitioning a grid of cubes efficiently

Discussion in 'Rendering Technology and APIs' started by STTrife, May 1, 2012.

1. STTrife Newcomer

Joined:
Sep 17, 2011
Messages:
7
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

Oh and with optimally I mean using the least amount of boxes.

#1
2. Davros Legend

Joined:
Jun 7, 2004
Messages:
12,969
So you want to render a as b but with cubes not squares ?

#2
3. STTrife Newcomer

Joined:
Sep 17, 2011
Messages:
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!

#3
4. Simon F Tea maker ModeratorVeteranSubscriber

Joined:
Feb 8, 2002
Messages:
4,524
Location:
In the Island of Sodor, where the steam trains lie
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.

#4
5. Davros Legend

Joined:
Jun 7, 2004
Messages:
12,969
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.

#5
6. sebbbi Veteran

Joined:
Nov 14, 2007
Messages:
2,235
Location:
Helsinki, Finland
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).

#6
7. Davros Legend

Joined:
Jun 7, 2004
Messages:
12,969
You know that has absolutely no meaning to me

#7
8. STTrife Newcomer

Joined:
Sep 17, 2011
Messages:
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!

#8
9. STTrife Newcomer

Joined:
Sep 17, 2011
Messages:
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

#9
10. Simon F Tea maker ModeratorVeteranSubscriber

Joined:
Feb 8, 2002
Messages:
4,524
Location:
In the Island of Sodor, where the steam trains lie
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.

#10
11. Mintmaster Veteran

Joined:
Mar 31, 2002
Messages:
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.

#11
12. Ethatron RegularSubscriber

Joined:
Jan 24, 2010
Messages:
697
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.

#12
13. STTrife Newcomer

Joined:
Sep 17, 2011
Messages:
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

#13
14. Ethatron RegularSubscriber

Joined:
Jan 24, 2010
Messages:
697
Then you should consider a hierarchy with/allowing void volume on the node's BVs, bullet allows you to build BV hierarchies from primitives.

#14
15. Davros Legend

Joined:
Jun 7, 2004
Messages:
12,969
doesnt bullet have a feature for grouping objects together ?

#15
16. STTrife Newcomer

Joined:
Sep 17, 2011
Messages:
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?

#16
17. Davros Legend

Joined:
Jun 7, 2004
Messages:
12,969
thats what I meant

#17