3

I have a rendering application that renders lots and lots of cubes in a 3-dimensional grid. This is inherently inefficient as each cube represents 4 vertices, and often the cubes are adjacent, creating one surface that could be represented by a single rectangle.

To populate the area I use a 3-dimensional array, where a value of 0 denotes empty space and a non-0 value denotes a block.

e.g. (where X denotes where a cube would be placed)

OOOXXXOOOO
OOXXXXXXXO
OOXXXXXXXO
OOXXXXOOOO

would currently be represented as 21 cubes, or 252 triangles, whereas it could easily be represented as (where each letter denotes a part of a rectangle)

OOOAAAOOOO
OOBAAACCCO
OOBAAACCCO
OOBAAAOOOO

which is a mere 3 rectangles, or 26 triangles.

The typical size of these grids is 128x128x128, so it's clear I would benefit from a massive performance boost if I could efficiently reduce the shapes to the fewest rectangles possible in a reasonable amount of time, but I'm stuck for ideas for an algorithm.

Using Dynamic programming - Largest square block would be one option, but it wouldn't result in an optimal answer, although if the solution is too complex to perform efficiently then this would have to be the way to go.

Eventually I will have multiple types of cubes (e.g. green, brown, blue, referenced using different non-0 numbers in the array) so if possible a version that would work with multiple categories would be very helpful.

Community
  • 1
  • 1
Nick Udell
  • 2,420
  • 5
  • 44
  • 83
  • Is there a single "shape" in your grid? – Nicolas Repiquet Jan 10 '11 at 14:06
  • It is possible that isolated "islands" of Xs can be generated (I'm generating these maps using Ken Perlin's simplex noise) – Nick Udell Jan 10 '11 at 14:08
  • 1
    If you're rendering, shouldn't you go for the smallest number of vertices instead of fewest rectangles? You can probably throw out all the vertices inside your volume... (unless you have transparency) – ltjax Jan 10 '11 at 14:44
  • Good point, I'm not sure why I intended to draw it this way any more. – Nick Udell Jan 10 '11 at 14:55
  • See also: [1]: http://stackoverflow.com/questions/4304750/how-can-i-reduce-a-grid-of-equal-sized-squares-to-a-minimum-set-of-rectangles – Keith Jan 11 '11 at 03:34

1 Answers1

0

Maybe something "octree" like:

Build a 64x64x64 grid over your 128x128x128 grid so each cell of the first grid "contains" height cells of the second.

For each cell, of the 64x64x64 grid, proceed like that:

  • If the height contained cells have the same value, put that value in the 64x64x64 grid.
  • Else draw each cell individually and put -1 in the 64x64x64 grid.

Now build a 32x32x32 grid over the 64x64x64 one and repeat.

Then 16x16x16, 8x8x8, 4x4x4, 2x2x2, 1x1x1 and you're done :)

Of course, it would be best if the octree was computed once and for all, not for each rendering operation.

Nicolas Repiquet
  • 9,097
  • 2
  • 31
  • 53
  • Yeah I'm not computing the geometry every frame, but I have to recompute it every time it changes, as it is a dynamic system – Nick Udell Jan 10 '11 at 17:58