Forgot your password?
typodupeerror
Toys Graphics Java Programming Software

Computer-Aided Lego Art Project 112

Posted by timothy
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 ..."
This discussion has been archived. No new comments can be posted.

Computer-Aided Lego Art Project

Comments Filter:
  • Similar (Score:5, Interesting)

    by Arngautr (745196) on Friday October 10, 2008 @08:26PM (#25334717)
    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. :)
    • That's really neat. Thanks for posting the link. Good excuse to fire up lightwave for the evening.
    • by Arngautr (745196)
      I guess not really very similar... graphics, vs real life. Real life is much cooler. Oh well.
    • Re: (Score:1, Offtopic)

      by jellomizer (103300)

      I'm a much better programmer now, just for the record. :)

      I am not sure why you had to qualify that. If you are a programmer and you do it longer you get better for at it.

      I was a good programmer even before I started college. After college I was a much better programmer. Starting working I was a really good programmer... Now I am even better at it...

      However over time we tend to specialize in different areas. Mine are in web application development, Business Intelligence and legacy maintenance. Others focus

  • "So the Java program runs for about ten hours for each image..."

    It would be interesting to know how powerful the computer was, because I'm sure it would take _a lot_ of processing time to do something this complex. It seems like he did it all at home, but I think it's also plausible that he could have borrowed computing power from his work.
    • by retchdog (1319261)

      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)

        by rsk (119464)

        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.

  • He should sell these.
  • "Slashdotted"? What's next... "story"? Oh wait...
  • by greg_barton (5551) * <greg_barton AT yahoo DOT com> on Friday October 10, 2008 @08:45PM (#25334879) Homepage Journal

    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]

    • by Sparr0 (451780) <sparr0@gmail.com> on Friday October 10, 2008 @09:15PM (#25335139) Homepage Journal

      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: (Score:3, Insightful)

        by greg_barton (5551) *

        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.

        • by greg_barton (5551) * <greg_barton AT yahoo DOT com> on Friday October 10, 2008 @09:50PM (#25335429) Homepage Journal

          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.

          • by gadzook33 (740455) on Saturday October 11, 2008 @12:54AM (#25336711)

            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: (Score:3, Insightful)

            by evanbd (210358)
            That method will result in structurally unsound pieces (not enough interlocking). His code apparently optimizes visual accuracy against structural soundness.
            • by greg_barton (5551) *

              Making it structurally sound is trivial. Just offset each block by 1/2.

              • by evanbd (210358)
                That's kinda hard with the 1x1 blocks the parent suggested.
                • by Z-MaxX (712880)

                  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.

            • Why does it even need to be structurally sound? the pictures are mounted inside a frame.
          • Re: (Score:3, Insightful)

            by TehZorroness (1104427)

            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

            • by Z-MaxX (712880)

              Perhaps this is a candidate for a new benchmark for The Computer Language Benchmarks Game [debian.org].

              1. Write the reference program, which implements the algorithm all other programs use (so that we are comparing language implementations, not the quality of a bunch of different algorithms).
              2. Everyone pitch in and port that program to other languages!
              3. Submit to Alioth for inclusion in the benchmarks
              4. Profit! (intellectually, of course)
            • Re: (Score:3, Informative)

              by IICV (652597)

              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

          • by adisakp (705706)
            There are some other complications. For example, you probably want to modify your dithering algorithm so that it's possible to heuristically swap adjacent "pixels" that changed by error diffusion to make longer contiguous horizontal blocks while still minimizing diffusion propagation (this may mean diffusing error in multiple directions or modifying diffusion propagation weightings).

            After that, you don't want to simply combine horizontally adjacent blocks if you want your final LEGO creation to be "solid
            • by greg_barton (5551) *

              good interconnectivity

              Making good interconnectivity is trivial. Just use blocks of minimum width 2 and offset each row by 1. Instant perfect stability.

        • by Sparr0 (451780)

          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).

          • by greg_barton (5551) *

            So just add some constraints to your model.

            Try using a tool like drools-solver [telenet.be]

          • by greg_barton (5551) *

            Then there is the rigidity issue

            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)

        by rossifer (581396)

        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)

          by Sparr0 (451780)

          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.

          • by greg_barton (5551) *

            Finding the combination of decisions that yields the optimal (for a given set of weights) arrangement is NP.

            "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). :)

            • 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!

          • by rossifer (581396)

            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

            • by gregorio (520049)

              This problem is linear complexity O(N). And if I know my future co-workers at Google at all, it will be an interview question before the week is out to demonstrate why it's O(N).

              If those are the questions asked during an interview, then I'm sorry for you. Not for having to endure this kind of process, but for wanting to work at such place.

              Real engineering isn't about impromptu "mad skillz" at solving puzzles or problems with a single solution (as in "the interviewer thinks he is really smart so any solu

              • The US is screwed, actually: while most people hate science, the small part of society that focus on science are actually failing really hard at it. They think they're doing great, as their life is about patting each other on the back, but they're actually failing.

                I work in an R&D group in a specialized field; some of the people who run the groups we interact with are amazing pieces of work, who really believe their way is the only way. Pointing up that someone's proposal violates an obvious natural law is supposed to be confined to weekend drinking with friends...Not a design review.

                As a nation, we have way too many religious sects which label knowledge as bad because it includes evolution and the scientific method; critical thinking isn't good for religious i

      • by gadzook33 (740455)

        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...

    • by lon3vman (1354401)
      Or the Rubik's cube art kicking around like Rubixel [rubixel.com] or the portraits the space invaders [space-invaders.com] guy did.
    • by leedsj (1346127)
      simply, wow! that beats Google's best by an order of magnitude
  • Can someone who got the page to load copy and paste the article here?
    • by rsk (119464)

      Yea sorry about that... I saw one post on the site "Did you know you got slashdotted?" I checked the server, the load level just said "Hahahah.0 0.24 0.13" and now I think it's in the process of melting.

      Sent a ticket to the hosting co asking them to stop throttling it temporarily.

      Sorry guys, I really didn't think slashdot would kill the site *that* freaking fast.

      Also shopping for dedicated solutions now =/

    • by dnwq (910646) on Friday October 10, 2008 @09:14PM (#25335123)
      Nyud.net [nyud.net] mirror. Slow, but works.
      • by dnwq (910646)
        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: (Score:3, Informative)

          by rsk (119464)

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

          • So you re-post your link on Slashdot? Try inserting this code into your load balancer.

            double is_computer_on_fire( void )

            • by rsk (119464)

              It's responding now, albeit a bit slowly. Server load is a nice healthy 31... that's a good thing right? :(

  • by coolgeek (140561) on Friday October 10, 2008 @09:20PM (#25335179) Homepage

    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.

  • You would figure LEGO would already have a system to do this

    • Re:Prior Art (Score:4, Interesting)

      by amyhughes (569088) on Friday October 10, 2008 @10:54PM (#25335885) Homepage
      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.
      • I'm not talking about specifically about mosaics, it's just the amount of human effort of figuring out every color in a 2000-piece set must reach the point of diminishing returns fairly quickly (more people might take more time), so I figured they may have some scanning software.

  • Eric Harshbarger (Score:5, Informative)

    by amyhughes (569088) on Friday October 10, 2008 @09:36PM (#25335319) Homepage
    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.
    • by dgriff (1263092)
      Yeah, but "Eric Harshbarger, a former Sun engineer..." doesn't have quite the same ring to it. Am I just being cynical or are these kinds of stories surreptitious advertising for Google, as in "look how smart our engineers are". I can't find the original source for this story. Or maybe people are just primed now to take more notice of something done by a Google employee?
    • by Keebler71 (520908)
      I wrote a program in MATLAB to do this as well about 3 years ago. Unfortunately I never actually built one although I generated plans to build about 30, mostly family portraits and famous paintings. The reason I never built one is it would have been very expensive. I want to say that for something like a 3'x4' size piece of art it would have cost me ~$800 or so in parts alone... and then a few months to put it together.

      I did this project after visiting legoland and being impressed with their lego mosic

  • When I first read this I wasn't impressed that he pixelated a few pictures into lego pieces. Its obviously not that hard because the story hasn't been up long and 2 or 3 people who have ever done any pixelating or lego stuff have posted their projects in the comments.

    Then I looked up how much lego pieces cost. 25,000 1x1 plates would cost around $1,750-$2,500. I'm curious how much his cost reduction the algorithm actually does. If it just searches and replaces rows of horizontal plates with 1x2, 1x3, et

  • 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.

    • by ozphx (1061292)

      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.

  • by Doc Ruby (173196) on Saturday October 11, 2008 @12:16AM (#25336467) Homepage Journal

    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.

    • by felipekk (1007591)

      and then fix the economy.

    • by Rigrig (922033)

      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 more copies of itself, and then take over the world, well that would be the coolest.

      There, fixed that for you.

  • Reminds me of this [youtube.com] music video by The White Stripes.
    • Actually, you can watch any video by an "indie" band as they are all laboratory-grown clones of each other - Goldfrapp, Peaches, whatever...

  • What struck me is that this guy apparently is making more or less 2D structures. With LEGO! I call that heresy.

    How cool would it be if the lighter parts of the image were protruding just slightly, to enhance the illusion of depth? I can't for the life of me believe this would be that hard, if the guy already came this far with his program.

  • 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.

If a camel is a horse designed by a committee, then a consensus forecast is a camel's behind. -- Edgar R. Fiedler

Working...