Algorithm to fit fewest rectangles to irregular shape

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 triangl开发者_C百科es.

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.

---

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.