Once you limit to a limited set of colors, try to build picture with bigger than 1x1 pieces
gwachob opened this issue · 12 comments
And also generate a parts list.
Added here for discussion :D I realize this could be a lot of work. But the payoff! Oh, the payoff!
I guess you'll want a packing algorithm to work out which pieces to use in the spaces.
Yah, thats a big part of it. I've already forked to see how hard that would be. Simplifying assumptions: square/rectangular lego pieces only. A limited palette (on the order of several dozen colors only).
The other slightly nontrivial aspect is determining the shapes of similar color that are to be filled with lego pieces of a single color (this is analogous to doing a "paint fill" in a paint app, I think... so should not be too hard).
Nice idea.
I would not use a packing algorithm. Most humans do not use one, as well ;-). Create a set of 4, 8, 6 ( more rare) pieces and use them a bit randomly.
Yah, I was thinking of using something more random. Since the actual space to be packed is not that large (30x30), I have a random algorithm in mind that should be fairly simple to implement... when i get a chance ... :)
That would definitely be a great idea and as @gwachob says (by the way any update on your algorithm ?) it should not be that hard with a random algorithm but it comes tricky when you have a look at the existing pieces, some like 2x1 are existing in almost any colour but some like this cross seem to be more limited in term of colours. Don't know if there is a solution to deal with existing colours/shapes for >1x1 bricks (but having a look at the price it would cost me to actually buy the bricks to build the picture I want, finding an easy way to find which 8x8 or 2x8 I should buy would be a relief, a 2x8 is defintely cheaper than 16 bricks of 1x1).
Thought of a small algorithm.
- go through shrunken image's pixels
- for each pixel, check if surrounding pixels are the same color, favor squares over rectangles, take a random choice if you can have a horizontal or vertical rectangles but not square.
- do stuff
@JuanPotato that seems a good start. Following my comment I have been searching for algorithms aiming at solving this issue and there seems to be a lot of options. What seems to be the most advanced software (regarding algorithms available) is PicToBrick and the source code is available. It contains a ElementSizeOptimisation.java file which seems to do this kind of thing. I have just had a quick look but it might be worth having a look (the guy doing the software seem to have spent a lot of time of theoretical aspect, I am pretty sure the solution they have used is one of the best in term of complexity/efficiency)
Hey Everyone, I created www.BrickIt.co using just jQuery and HTML5's Canvas element to do this and actually got a great algorithm for parting things out I came up with when I was 20 (3 years ago), it's wicked fast (like 1024 pegs x 1024 pegs image in less than 10 seconds) and as optimal as any complex optimization problem attempt. Everyone wayy over complicates it. I think the parting out results speaks for themselves.
It's simple. Given a set of brick dimensions (2x4, 2x3, 1x6, 2x2, 1x4, 1x3, 1x2, 1x1). Start out with the highest priority piece (2x4) in the top left corner and work your way from left to right, top to bottom, checking:
Does this piece fit here (doesn't exceed the boundary)
Has any piece already been placed here before (If I were to place this piece here, would it overlap
Are all colors the same for the pegs that that piece would take up if it were to be placed there
If so, place it, if not, move to the left 1 (or start a new row) etc.
Go through the entire image trying to place the top priority piece, then repeat starting in the top left corner for the second highest priority piece, etc.
Once you realize you can place a piece, draw it with the borders, otherwise it'd be really hard to figure out where are the borders are supposed to go once you are done.
Theoretically, you could save maybe 1% of pieces or costs if you started your optimizations in other places other than the top left corner, but you would also spend millions of times longer processing every possible starting location and sprawl pattern for a 1% improvement gain.
How I have this implemented is ridiculously easy as well, just have two matrices, one to indicate the color index of a particular peg, one to keep track if that peg has a piece placed on it or not, and then I guess you have to have the matrix representing your actual image as well.
I'll try and add my BrickIt project to github soon, none of the source code is obfuscated though so feel free to look through it (literally just vanilla javascript, jQuery and HTML5 canvas) - I was going to try and turn it into a business or sell it but it's been years now.
@shaun3141 that sounds great! Can't wait to see it. 😄
@JuanPotato I was willing to give a try to @shaun3141 suggestion but trying to build 1x2.png and so on from your original 1x1.png file, I notice that just copying/pasting the file and trying to remove the central vertical line does not work as the background gray is not the same on the left and on the right of the image ( see the result and the tiny difference in the middle of the image). Any suggestion based on the process you used on the best way to produce the 1x2, 1x3, 1x6 and others ?
Thanks
@symac I took the photos of the art works that were made into lego like this one and took one block from it. So you may want to try to find good pictures of blocks and just edit them so that the color and size is correct.
Thanks @JuanPotato I rather have been trying to build something from the 256px version of the 1x1 you had provided in another issue. My fork of the project now contains a --optimize parameter that can be used with cli.py to limit the number of bricks used. That seems to work pretty well according to my tests but the low quality of the bricks I have created doesn't give a good result. That is a good start but I hope someone will be able to create better png for the "big" bricks.