Computer-Aided Lego Art Project

rsk writes "Justin Voskuhl, a Google engineer, in a 2-fold bid to fight boredom and figure out something to cover a large barren wall in his living room, one weekend developed a Java program using an annealing algorithm to figure out the best layout and colors of Lego blocks to reproduce a source image exclusively in Lego blocks inside a frame. He plans to release the source code soon. I probably would have just painted the wall ..."

Similar

OK, I have to show off - I did something similar four years ago.
Post [cgsociety.org]
Webpage [lunarpages.com]
I'm a much better programmer now, just for the record. :)

Re:

That's really neat. Thanks for posting the link. Good excuse to fire up lightwave for the evening.

Great Tags

"Slashdotted"? What's next... "story"? Oh wait...

In a frame on his wall? Really?

How about glass tiles on a 100'x30' wall, [hzgstudio.org] or a 30'x75' [geocaching.com] wall?

I wrote the code [java.net], my brother in law did the hard parts. [flickr.com]

Re:In a frame on his wall? Really?

The major algorithmic difference is that lego blocks are not [always] square, and figuring out which combination of sizes to use to cover an arbitrarily shaped block of color is NP-Hard. What he has done here is seriously impressive.

Re:

Yes, but they're always rectangles, with predictable proportions, (1 by X, with a maximum X) you always stack them horizontally, and there's a very limited color palette.

If you think it's difficult to calculate you're probably modeling it wrong.

Re:In a frame on his wall? Really?

Actually, it's easier than that. :) Model with 1x1 blocks on the first pass, using standard interpolation limiting to your available palette colors, then combine horizontally adjacent blocks with the same color as 1xN blocks according to availability.

Re:In a frame on his wall? Really?

Actually, it's easier than that. :) Model with 1x1 blocks on the first pass, using standard interpolation limiting to your available palette colors, then combine horizontally adjacent blocks with the same color as 1xN blocks according to availability.

And then write it in C++ instead of Java.

Re:

That method will result in structurally unsound pieces (not enough interlocking). His code apparently optimizes visual accuracy against structural soundness.

Re:

You are forgetting that legos must be interlocking. That somehow is a part of the algorithom unless the guy cheated (the frame/glue holds it together). Assuming the picture is two "nubs" thick, The algorithm must combine 1x2, 2x2, and 4x2 blocks in a way where they hold on to eachother - in addition to dithering and making the photo look more realistic.

I'm willing to bet that the code isn't optomised (hey - it's java!). I bet these calculations can be done in a couple of minutes at most, not 10 hours (as

Re:

If you use a less strict definition of "lego brick" that includes plates then there are also 1/3 by X proportions. Then there is the rigidity issue (the classic brick-laying arrangement of offset rows is good, while straight row/column arrangement of constant-width bricks is very bad). And finally the problem of parts cost (the easiest solution is a whole lot of 1x1 bricks, but 1x1 are rare and expensive, while 1x4 are cheap and super common).

Re:

Finding any one fit of lego blocks to produce a given image is linear complexity (O(N)). It's the same algorithm used in your video card to rasterize a 3-d polygon model or in photoshop to rescale an image. Definitely not NP-hard.

Growing adjacent spaces of matching color to use larger bricks isn't tough either. Use a simple run-length encoding algorithm (second pass, also O(N)) and then when you're breaking up long stretches into brick-sized stretches in the third pass, add a constraint that within a "sa

Re:

How do you resolve conflicts when the rigidity rules say one thing, while the brick value rules say another, and the color dithering rules say yet another? There should be a weighting function, and the impact of that decision will cascade down the mosaic, affecting other decisions. Finding the combination of decisions that yields the optimal (for a given set of weights) arrangement is NP.

Re:

The Anita Barrio neighborhood. It's along I-10, on the opposite side from the freeway, facing a park. I don't know the exact address off the top of my head.

Ah memories....

Reminds me of the time my buddy and I were playing some 301 at the dart board. Both of us were pretty wasted. I discovered he couldn't subtract, and that was giving him an advantage, so I started keeping score. Then we discovered I also was too wasted to subtract.

We decided I would sit down and code a score keeping program with a text-based GUI (similar to ye olde Vitamin C Screen Utilities). Each player just entered their darts 10, 13, etc. or D20 for a double 20 T13 for triple 13, and B/DB for bullseye and double bull, then the code would do the math. Apparently writing a parser and an event loop with some event handlers taps a part of my brain unhindered by all the alcohol, etc.

Eric Harshbarger

This guy [ericharshbarger.org] has been doing LEGO mosaics for years, and if you google a bit you'll find others and the code for creating them.

Lego Art Robot - In Lego

What would be really cool would be a robot arm that assembles any source image in a Lego target at a specified scale, after the software calculates exactly which and how many bricks are required in the "palette" bin.

And if that robot arm were made from Lego Mindstorms, that would be even cooler.

If a program could run a Mindstorms arm that is totally rudimentary, put together in under 15 minutes by a human, then upgrade itself into the arm required to assemble these images into Lego sculptures, and then assemble the sculpture, well that would be the coolest.

Re:

Ugh... I also think google should have hosted the website... Slashdot is borrowing a lot of bandwidth power from someone without much to spare.

Re:

That was my bad, Justin sent me some pictures and I popped them up cause I thought it was awesome... and then I realized what "Slashdotted" meant like 35 seconds later.

Re:

It would be more interesting to know why it takes such long time. Doing this in photoshop takes about two minutes, including the editing.

Re:slashdotted already!

Nyud.net [nyud.net] mirror. Slow, but works.

Re:

Scratch that, the page has a huge amount of absolute URIs.

What happens when you are really smart like Google-lead-engineer smart, you move into a new place that has a big blank living room wall and you end up being bored one weekend? Well, Ill tell you what I would do I would order pizza, probably watch a movie, stare at the wall for a good 45mins until I decided it wasnt going to change on its own, then play some video games.

But thats not what Justin Voskuhl did.

What you see above isnt a horribly pixelated

Re:

Working on getting this horse running again. Sorry for that guys.

Re:

Well I guess I got lucky, nice pictures and texture.

Re:Prior Art

For a time LEGO sold a few grey-scale mosaics, but even better you could upload an image and they'd send you pieces in black, white and three shades of grey, and instructions to create your image. If you just wanted the pieces (they were 1x1 plates) you could upload an image that had shades in the proportions you needed. And since they sent you bags (of IIRC 270) and not exact counts, you could create an image that maximized the number of pieces you'd receive. If your image required 271 dark grey pieces, for example, you'd get two bags of 270.