Slashdot Log In
Computer-Aided Lego Art Project
Posted by
timothy
on Fri Oct 10, 2008 07:12 PM
from the how-they-made-naughty-pictures-at-vesuvius dept.
from the how-they-made-naughty-pictures-at-vesuvius dept.
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 ..."
Related Stories
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Similar (Score:5, Interesting)
Post [cgsociety.org]
Webpage [lunarpages.com]
I'm a much better programmer now, just for the record.
Re: (Score:2)
Re: (Score:2)
Yeah, and an actual starry night looks far better than The Starry Night [wikipedia.org]
Great Tags (Score:2, Funny)
In a frame on his wall? Really? (Score:5, Interesting)
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? (Score:5, Insightful)
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.
Parent
Re: (Score:3, Insightful)
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? (Score:5, Insightful)
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.
Parent
Re:In a frame on his wall? Really? (Score:5, Funny)
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.
Parent
Re: (Score:3, Insightful)
Re: (Score:2)
Making it structurally sound is trivial. Just offset each block by 1/2.
Re: (Score:2)
Re: (Score:2)
Don't the 'square' Lego blocks actually have a 2x2 'pinout'? Thus greg_barton's suggestion in the GP sounds correct to me. Please correct me if I'm wrong (I want to know), but I think greg_barton is right --- his algorithm does sound both correct and simple.
Re: (Score:3, Insightful)
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: (Score:2)
Perhaps this is a candidate for a new benchmark for The Computer Language Benchmarks Game [debian.org].
Re: (Score:3, Informative)
He's using simulated annealing [wikipedia.org]. The idea is, you start with some state you can get to easily, and then either a) make a random change to the state or b) make a change that tries to improve the state. You have some variable T that determines what percentage of the time you do a. It starts out at some high percent, and then slowly goes down to 0%. The more slowly you decrease T, the closer to optimal your answer is. You can even find optimal solutions to NP complete problems if you let T decrease infinitely s
Re: (Score:2)
After that, you don't want to simply combine horizontally adjacent blocks if you want your final LEGO creation to be "solid
Re: (Score:2)
Making good interconnectivity is trivial. Just use blocks of minimum width 2 and offset each row by 1. Instant perfect stability.
Re: (Score:2)
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: (Score:2)
So just add some constraints to your model.
Try using a tool like drools-solver [telenet.be]
Re: (Score:2)
Mmmmmm, not really. Just use a standard grid, then offset every other row by 1/2 square. Rigidity issue solved. Visually there will be little difference, and less the larger the image gets.
Re: (Score:3, Insightful)
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: (Score:3, Insightful)
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: (Score:2)
"Good enough" is often better than optimal when you're dealing with a real world solution to a problem. It's much better when "good enough" takes only O(N). :)
A time for optimal (Score:2)
Yeah, I can't believe he wasted ten whole hours of computer time to find the optimal solution when he could have found a lesser solution in less time! Except that each image took fifteen hours of assembly time. And a less sturdy layout might take even longer to assemble. And the simple solution posted below of doubling the thickness to add a support layer would merely double the cost. Other than that, this project is a complete waste of leisure time!
Re: (Score:2)
The dithering rules drive the brick color rules (this is the rasterizing pass), so there's no conflict there. The strength rules definitely are superseded by the color rules. There's no conflict at all.
The reason the strength rules aren't as important as the color rules is that the strength rules don't affect the structure's integrity all that much. The right way to build the image is at least two layers deep. There's the image layer and then there's a structure layer, tied together with double width br
Re: (Score:2)
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.
FTA: "So the Java program runs for about ten hours for each image..."
Ok, so impressive yes. Still, can't help but wonder if c++ could have helped here...
Re: (Score:3, Informative)
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.
Re: (Score:2)
Here you go:
map [google.com]
Using street view you can almost see it. You may need to rotate so the view is towards I-10.
Ah memories.... (Score:3, Funny)
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.
Re: (Score:2, Funny)
Eric Harshbarger (Score:5, Informative)
Finally, an application for simulated annealing (Score:2)
Somebody finally found a use for simulated annealing.
That's mostly one of those AI ideas from the 1980s that turned out not to be too useful. It's a very slow approach to hill-climbing.
It was cooler 20 years ago or so, when Playboy Magazine did a cover which had an image tiled from all the previous covers.
Re: (Score:2)
Playboy: Models with tits out composing a further model with tits out.
Google: Kids bricks composing a shitty flower.
Geeks will inherit the earth my ass.
Geeks will inherit the earth my ass. (Score:2)
Geeks will inherit the earth my ass.
Well, the geek who started Various, Inc., which runs "alt.com", "adultfriendfinder.com", and "friendfinder.com", recently bought Penthouse.
Lego Art Robot - In Lego (Score:3, Funny)
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: (Score:2)
algo (Score:2)
Algorithm,
Didn't look at it, but the article says it's optimized for
- Rigidity (and NO it's not just, offset every row by 1/2, that's perfect rigidity, you're looking for a tradeof here !)
- Resemblance (int this case the way to go is NOT to try to match a dithered image but rather to compare the distance of a blurring of your candidate image to a blurring of the original image, at different blur width.
It's easy but no trivial.
Re: (Score:2)
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: (Score:3, Funny)
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: (Score:3, Insightful)
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! (Score:5, Informative)
Parent
Re: (Score:2)
Re: (Score:3, Informative)
Working on getting this horse running again. Sorry for that guys.
Re: (Score:2)
Well I guess I got lucky, nice pictures and texture.
Re:Prior Art (Score:4, Interesting)
Parent
Re: (Score:2)
Why is this front page material? Lego mosaics are ancient, and the source code is probably trivially simple.
Because it is a Google lead engineer doing it! Therefore it must be magic!
Re: (Score:2)
Oh, and that was "sarcasm", by the way. Like the original poster I'm also a little uncertain why a fairly trivial algorithm that quite a few probably already made as a child in one form or another is suddenly worthy of the frontpage...
Re: (Score:2)
I doubt that. Only Microsoft innovates(TM). Other people just code stuff. When Microsoft codes stuff, they're actually exercising their freedom to innovate(R).
Re: (Score:2)
Actually, you can watch any video by an "indie" band as they are all laboratory-grown clones of each other - Goldfrapp, Peaches, whatever...