Problem: Given a 3d mesh with no leaks, convert that mesh into a solid Lego brick sculpture. Extra Credit: Find the minimal set of bricks that will approximate the mesh's volume (possibly with some set maximal error) Masochist: Only return configurations of bricks that could actually be built (assuming infinite joint strength). i.e. every brick is connected so that the thing does not fall apart due to gravity. This seems like a very hard to solve CSP. I was wondering if there was a better way to approach this type of problem? I am dubious since IIRC the optimal sphere-fill problem for arbitrary volumes is very hard. I'm actually interested in solving a less difficult version of this problem - I want to convert a heightfield into a landscape made out of Legos using the minimal number of bricks possible (allowing bricks to be any dimension, rather than the traditional Lego ones). I'm thinking greedy optimization would work ok if you think of terrain as being made of layers, but by simplifying the problem like this it seems one could miss some good optimizations (for cliffs and places we large cubes would be best). Hopefully that made some sense?

Oh. If it wasn't clear I was asking for review of my mad scheme and possibly suggestions of a better way to think about the problem.

For some reason, that problems makes me think of Haar wavelets.

The problem would be a lot easier if you would settle for a reasonably small number of bricks, instead of the optimal number.

I don't see the connection to haar features myself.

I was thinking about it some more and have decided that the original problem is even harder than it sounds. In order to insure the optimal solution, it seems like it would be necessary to first find the optimal "reading window" - the alignment between the continuous mesh and the discrete brick coordinates. Since it is impossible to try all combinations, you would have to find all the boundaries were a shift in the reading window raises or lowers your brick count.

More complication: I did not originally specify the orientation of the blocks (direction the studs face), or even that they all had to have a common orientation. So in addition to finding a solution for a given reading window, it would be necesary to optimize it wrt these six dimensions. Or step in front of a train...

All this makes me think that I should be looking for a reasonable shortcut (like maybe making terrain out of "Lego voxels", then possibily aggregating them).

You didn't specify which blocks we can use either, or how tightly we need to squeeze them into this mesh... or the dimensions of these blocks

Lego had quite a few pretty strangely shaped blocks, and some pretty large ones too, some even being entire cliff sides.

If i recall correctly, anytime 'lego' was faced with the need of a component of odd shape, they just made a new oddly shaped block. Guess I can take that cheap way out too and just declare that I'll invent a block with the exact measurements of the mesh :D