Rectangle packing...

Java 2D
#1

Has anybody written or found an algorithm for performing this operation?

I’m totally amazed there are no resources on the web offering an open source solution to this problem, even poor implementations seem to not exist =/

While I understand the complexity of the problem, a generalized solution should be totally reusable - afterall, a rectangle is a rectangle!
The only problem specific aspects are specializations in the type of rectangles that are present in the input dataset.

I would expect every single game developer has at one time or another come across this problem, as it is fundamental to optimal texture-page arrangement.
My instance of this problem is in the domain of J2ME development, where memory is at a premium - so optimal use of textures is critical.
That said, scalability is also paramount, so automated packing of texture data is of critical importance also. (doing it by hand is simply not an option)

#2

SPGL has a tool that does it I believe. Cas is your man for this one,

Kev

#3

ahhh! cheers, having a look now.

#4

Check out a “bin packing”. There are variations, but 2D bin packing should get you on the right track I’d imagine. I haven’t played around with something like this for optimizing textures, but I wrote such a program for my 1st quarter CS class way back in the day… Sounds tough for a 1st quarter class, but it was an accelerated class combining the intro 101, 102, 103 series (3 courses into 1). Heh, the extra credit project that would get you an A in the class and not have to take the final was to create a chess program that could beat the professors. :stuck_out_tongue_winking_eye:

#5

sorry for offtopic :stuck_out_tongue:

[quote=“Catharsis”]Heh, the extra credit project that would get you an A in the class and not have to take the final was to create a chess program that could beat the professors. :stuck_out_tongue_winking_eye:
[/quote]
doable… with some research how best chess programs work and such stuff :slight_smile: … did anybody did it? :slight_smile:

#6

Ended up writing my own implementation, as the problem solved in the SPGL code is subtlely different to my requirements.
(Cas is packing a set number of images into a variable number of 256x256 textures,
I on the other hand need to pack a set number of images into the smallest possible area.)
There was also a minor complication that in my datasets, the input rectangles could be super-imposed. (several sprites sharing the same pixels)

Ended up with an acceptable solution that given a random dataset of rectangles with dimensions [1<=x<=26, 1<=y<=26] it on average attains a 91% fitness efficiency.
With a real-life dataset the variance is alot larger (typicaly between 80-100%) which is acceptable for the time constraints I had to write it in…1 day ::slight_smile:

Most importantly - it generates better texture pages than the artists usually manage (One step closer to making the artists redundant ;D)

The modularity of the problem does leave the algorithm open to future improvements too - so i’m happy.

#7

doable… with some research how best chess programs work and such stuff :slight_smile: … did anybody did it? :slight_smile:
[/quote]
Continued off topic… :stuck_out_tongue_winking_eye:

Certainly doable; max/min type stuff; This was a 1st quarter .freshman. class though, so it was a little on the hardcore side when everyone else that didn’t have a clue taking just 101 was lucky to be writing for loops by the end of their 1st quarter. The bin packing problem was just before the chess extra credit as well in assignments and to reasonably get the chess program done you’d have to skip that one and take a gamble… I played it safe, but a couple of folks did do it… About 5-6 people actually failed the course (12 units in major!) because they shared their work amongst each other which was forbidden by signed contract. You know college was going to be fun when you walk into your 1st class and the prof says this is the hardest class you will take; almost was… I went on to do the computer architecture classes and more freshman year and finished my senior project that summer… Then slacked like a mofo after one more year of hard effort… I was trying to get out in 3 years, but just didn’t care at some point. :stuck_out_tongue_winking_eye: