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

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!

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

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:**```
[thomas@Bombadil] LDRAW $ detile_image.py ldconfig.csv ~/Downloads/xelnagatiles5x3.jpg 194 150 2 2
```

Making palette

Optimizing palette (main)

Opening image

Resizing image

Palettizing image

Optimizing palette (palettize)

Color mapping

Depalettizing image

Done

Fourier Analysis

Min tiling resolution 2 x 2

Suggested tiling schemes

X: [ 1 5 2 10]

Y: [1 3 2 6]

Done

[thomas@Bombadil] LDRAW $ detile_image.py ldconfig.csv ~/Downloads/xelnagatiles.jpg 78 100 2 2

Making palette

Optimizing palette (main)

Opening image

Resizing image

Palettizing image

Optimizing palette (palettize)

Color mapping

Depalettizing image

Done

Fourier Analysis

Min tiling resolution 2 x 2

Suggested tiling schemes

X: [1 2 4 3]

Y: [1 2 4 3]

Done

[thomas@Bombadil] LDRAW $ detile_image.py ldconfig.csv ~/Downloads/xelnaga.jpg 39 50 2 2

Making palette

Optimizing palette (main)

Opening image

Resizing image

Palettizing image

Optimizing palette (palettize)

Color mapping

Depalettizing image

Done

Fourier Analysis

Min tiling resolution 2 x 2

Suggested tiling schemes

X: [2 1 4 8]

Y: [ 1 2 10 7]

Done

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