Over the long weekend, Kerm and I were discussing the possibility of downloading models off of Google Earth and reconstructing portions of cities (e.g., NYC) in Minecraft, or in Lego form (via LDraw models, which you can load into MLCad, BrickSmith, or eventually FreeBuild).

Minecraft models would be relatively straightforward to produce - voxelization of a mesh is a relatively simple algorithm.

However generating a well-formed Lego model is slightly more challenging, particularly if you want to ensure that your finished model is

• structurally sound (bricks aren't floating in space, and interlock horizontally from level to level as much as possible),
  
• preserves shape as much as possible using existing Lego arches and slopes, and
  
• makes good use of sub-models to represent tiled/repeating portions of the source model
  

As a first step, I've written a script with python + numpy that takes a source image and pixelizes it to a specified grid resolution, and palettizes it to standard Lego colors using a simple minimization of a Euclidean distance metric.

Additionally, I've add some (relatively naive) Fourier analysis to try and identify tiling within the image. The general idea is to identify a harmonic series, with as high as possible a base frequency, that appears in the Fourier transform of the image and use that to extrapolate information about the tiling.

I'm getting relatively good results first-order results, but haven't finalized a heuristic to make decisions based on the numerical output.

If anyone is familiar with image processing and has recommendations for algorithms to identify a tiled image, please let me know!


Code:




Also, we've set up a GitHub project if anyone wants to peak at the sourcecode.

Double post, but it's useful, and I don't want to insert this into the introductory post.

Apparently the appropriate keywords for literature searches on the image analysis stuff are "repetition detection".

I'm going to need some of that for what I'm working on, so that I can find windows and replace them with glass. With much work over the past twoish days, I am able to voxelize Collada models from Google 3D Warehouse:



(Reference model is this one)

That's super cool. Are you pulling individual models from source sites for now with the hopes of pulling a larger model (say, a city from Google Maps) and importing that?

Pretty much. The Google Earth license is very restrictive, and not all the models are available in the Warehouse, so we shall see. For now I'm learning about texture mapping so I can get some colors and materials on that.

Edit: Fledgling attempt to read texture data and apply colors:

Very cool! Why does it have a hole in the middle?

I'm not clear on that (another question is why the spire at the top of the building is missing). I suspect the answer is that very thin features are getting discarded incorrectly, which I need to debug. I also tried converting the Guggenheim Museum this evening, and discovered that some models and encoded in inches, others in centimeters. I haven't yet found the metadata that differentiates.

Good luck with further debugging/reverse engineering (even as I think that would look better with studs on it )

Nothing stopping us from giving Minecraft a texture pack with LEGO studs on the tops of the blocks. Although at this scale, I think Duplo blocks might be more appropriate.

*bump* The model is now properly scaled (cm != inches) and texture-mapping appears to be working perfectly. The "thin triangle" issue remains.

out of curiosity, what does the minecraft file-format look like?

schematic or anvil formats? Schematics are used to insert small buildings and such, seen here. Anvil holds the chunks for a map and is found here.

Which is KermM using for his building?

I would assume a schematic and placing it with WorldEdit.

Nope. I'm using PyMcLevel and NumPy to directly manipulate Anvil worlds, with an eye forward at eventually automating the process.

I ask because it seems like it would be a reasonable test case for my rendering system with a much simpler file format than is used for LDraw models, with many of the same desirable features/design constraints.

I suspect your empire state building would make just as good a test model as the Corellian Corvette/Star Destroyer LDraw models I was using before.

Why is there a part of it hovering?

elfprince: New York Life Building, but potato potato. I suppose all skyscrapers look the same to non-NYers.
Merthsoft: Some of the triangles being converted are making my barycentric coordinate conversion routine throw divide-by-zero errors while generating determinants. Those triangles are subsequently discarded, and I believe those triangles are to blame for the empty spaces. The original model does not have them.

Are you already using double precision? Because it seems like very poor model design indeed if you need astronomical-scale values to represent it.

[edit]
Wait, wtf? Why are you doing division to calculate a determinant? That seems wrong.

I'm using doubles, but there's no precision issue.

I didn't speak precisely. I use the determinant as an intermediate step towards computing barycentric coordinates on a triangle, and if the determinant is zero, that subsequent computation will divide by zero. I'm trying to understand what causes this case.