## RE: [Algorithms] Packing textures into a bigger texture

 RE: [Algorithms] Packing textures into a bigger texture From: - 2000-11-08 13:55:27 ```On Tue, 7 Nov 2000, Hugo Allaire wrote: > It's for an automatic lightmap generator, so since it's not at runtime, > minimal space, not efficiency, is the top priority (don't go telling that to > my artists :) ). I've experimented on paper with a quadtree implementation, > and didn't seem to get satisfactory results. I try to place the largest > textures first, and sorting the textures with the same width or height, to > create squares. Anyway, I'll implement it and check the results. Don't worry > about your "I don't know post", I'm interested in every input on this > subject. Thanks! A few years back I wrote an algorithm for quillotine cutting problem (customer had to cut rectangular pieces off of a plastic sheet). It's a bit different problem since the sheet was always cut into two pieces, but I'll mention a couple of things that the better of the algorithms I tried had, they might be useful. Note that I had lots of equal sized pieces and not too many sizes to use. If your textures have wildly differing sizes, then this probably will not work too well. There's a couple other suggestions, as well (this message is gaining length at an alarming rate). -First sort the textures (henceforth referred to as pieces) in descending order according to size (or longer side, if some are very long and narrow). -While there are pieces, pick a piece randomly in a way that larger pieces have greater possibility to be selected. -Pick a position for the piece and put as many pieces of same size (width & height) in a row or column. I always had a rectangular area so I always picked a corner, for you the selection is probably more difficult. (You don't have to cut the available area in two at every step, so you get a lot more corners.) Try all possibilities and pick the best according to some criterion (our's was remaining space at the end of row or column). -A successful variation was to check what kind of pieces were left and see if some of them would fit well (less wasted space) at the end of row. I used that to limit the number of pieces put in a row. I.e. don't put as many as you can, pick a number that allows possibly better fit at the next step. Looking one step forward might be a good thing anyway, even if you do it with a simple heuristic. -If we ran out of space, we took a new sheet :-) -Repeat until user halts the process. Keep the best solution. Nowadays for single sheet size (we did this for several) it's probably a couple of seconds this finds the best solution it can. Customer was happy, I don't remember wasted area percentages etc. An algorithm that we also looked at was apparently designed for lots of different-sized pieces. It was also for quillotine cutting-problem, so it has the restriction you don't have. The algorithm started by combining pieces in pairs such that the resulting rectangle had as little wasted space as possible. Then those combinations became new pieces and they built the solution that way, eventually getting all pieces combined into a single piece. This results in a tree. Then I think they optimized it by swapping sub-trees so that a piece in a pair was swapped with another piece of another pair if the space requirement decreased. I don't have the url for this, nor any further details. Another thought, how about doing it this way: You have a big texture where you drop small textures. Maybe you can rotate the textures, but I'm not taking that into account below. Textures are added to the bottom (which tells how high the bottom is or how much space above it is left). (Think of dropping rectangular pieces into a thin box where they stand upright.) Repeat until no textures left: -Seek the shortest horizontal range of values in the bottom where some texture fits that has the smallest maximum value of height. A wider range that has lower maximum wins. -Place the largest texture that fits (fills the most of the range) into that position such that it shares the longest edge with neighboring textures. Or place two textures if they fit better. Some smart test here might pay off well. -In the range, set the bottom to maximum of range plus the height of the texture. Any gaps covered this way don't matter because no texture fits in there anyway. (You would have placed it earlier, then.) I guess it's simple to turn that into a depth-first search or something similar. Keep the best solution and return it in the end. Simplest representation of the bottom is simply an integer array telling how much of the column is used or unused and two lists can hold not-yet placed and placed textures. Clever decision on what to place in the middle step might pay off well. E.g. you might try to keep the bottom as level as possible. Hopefully that is of use. Ismo Kärkkäinen -------------------| M.Sc., Assistant | You think that's air you're breathing? Dept. of CS | -- Morpheus Univ. of Joensuu | iak@... | Tel:(013)251 5329 | GSM: 040 774 3722 | ```