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

 01-May-2012, 21:08 #1 STTrife 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.
 01-May-2012, 22:54 #2 Davros Darlek ******   Join Date: Jun 2004 Posts: 10,800 So you want to render a as b but with cubes not squares ? __________________ Guardian of the Bodacious Three Terabytes of Gaming Goodness™
 01-May-2012, 23:29 #3 STTrife 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!
 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,425 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. 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
 02-May-2012, 12:55 #5 Davros Darlek ******   Join Date: Jun 2004 Posts: 10,800 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™
 02-May-2012, 13:32 #6 sebbbi Senior Member   Join Date: Nov 2007 Posts: 1,204 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).
02-May-2012, 14:38   #7
Davros
Darlek ******

Join Date: Jun 2004
Posts: 10,800

Quote:
 Originally Posted by sebbbi 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™

 02-May-2012, 15:51 #8 STTrife 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!
 02-May-2012, 16:00 #9 STTrife 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
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,425

Quote:
 Originally Posted by STTrife 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

 02-May-2012, 16:53 #11 Mintmaster Senior Member   Join Date: Mar 2002 Posts: 3,896 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.
02-May-2012, 18:14   #12
Ethatron
Member

Join Date: Jan 2010
Posts: 421

Quote:
 Originally Posted by STTrife 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.

 02-May-2012, 19:43 #13 STTrife 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
 02-May-2012, 21:52 #14 Ethatron Member   Join Date: Jan 2010 Posts: 421 Then you should consider a hierarchy with/allowing void volume on the node's BVs, bullet allows you to build BV hierarchies from primitives.
 02-May-2012, 22:56 #15 Davros Darlek ******   Join Date: Jun 2004 Posts: 10,800 doesnt bullet have a feature for grouping objects together ? __________________ Guardian of the Bodacious Three Terabytes of Gaming Goodness™
 03-May-2012, 00:21 #16 STTrife 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?
 03-May-2012, 09:06 #17 Davros Darlek ******   Join Date: Jun 2004 Posts: 10,800 thats what I meant __________________ Guardian of the Bodacious Three Terabytes of Gaming Goodness™

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home News Forums     Beyond3D News         Press Releases         Beyond3D Articles Core Forums     3D Architectures & Chips         3D Beginner's Questions     3D Technology & Algorithms         3D Programming & Tools     3D Hardware, Software & Output Devices         Video Technology, Displays, & HTPC     3D & Semiconductor Industry     GPGPU Technology & Programming Embedded 3D Forums     Console Forum         Console Technology         Console Games             PC Games     Handheld Gaming     Handheld Technology     CellPerformance@B3D PC Forums     Hardware & Software Talk         Politics & Ethics of Technology         Unix, Mac, & BSD (3D)     Processor & Chipset Technology     Purchase Decisions Help     PC Games         Console Games Site Forums     General Discussion     Folding For Beyond3D Team #32377     Industry Jobs     Site Feedback Beyond3D Hall of Fame     Pre-release GPU Speculation     General 3D Technology     Consoles     Other

All times are GMT +1. The time now is 01:38.

 -- vB3D -- vBulletin Default Style Contact Us - Beyond3D - Archive - Top