Sign in to follow this  
razorjack

How to organize subareas on a bitmap?

Recommended Posts

Hello, I've got a question of an interesting puzzle problem for lightmap organization. The Problem is that I've different rectangle shaped areas I want to place on textures. New textures should be allocated if there are some rectangles which can't fit anywhere. How to organize this process if you want to have less memory wasting? Of course it would be also important to have a fast algorithm. Best results can be reached by bruteforce, but it becomes unpractical for a high amount of rectangles. Does anybody have an idea? ------ Sorry. My English isn't perfect. I'm from Germany. xD But I'll try my best to answer every question.

Share this post


Link to post
Share on other sites
I'd say, start with the largest patches. When you eventually reach the limit of a texture, start looking for smaller and smaller patches untill you've filled up the texture tightly, preferring patches that exactly match the dimensions of the leftover space.

What we did a while ago was dividing the leftover area into boxes, and trying to fill these as effectively as possible, recursively untill the leftover boxes were simply too small. We used some sort of bruteforcing, in that we tried the whole possibility tree and picked the best solution. The boxes we tried got filled for roughly 95%, quite a decent result methinks. Back then, we couldn't find much on this kind of problem though, this was all we could think up in the few weeks we were given. So perhaps you can think of a way to optimize this method... :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this