Sign in to follow this  
mameman

Splitting Rectangle Into Squares

Recommended Posts

mameman    100
Hi All, Here is my particular problem. I want to take a rectangle of size xr, yr and split it into squares of size xs, ys. The values xs, ys will have the following constraints: xs = ys (i.e. square), both xs and ys must be a power of 2, and the number squares contained in xr, yr must be minimal. Why would I want to do this?. What I am trying to do is to take an image of any size and split it into a minimal number of square textures. My API of choice is OpenGL with a mixture of C/C++. Any help or points to the applicable resources would be appreciated. Cheers, MAMEman.

Share this post


Link to post
Share on other sites
Colin Jeanne    1114
This problem sounds like it is almost certainly NP-complete. I believe it is reducible to Knapsack if you consider larger squares to have a larger value.

You might want to try approximating the solution using a greedy algorithm that first tries to cut out the largest square that it can and then apply the algorithm recursively.

Share this post


Link to post
Share on other sites
frob    44972
Question 1: Why square textures? You can use any shape as long as the lengths are power-of-two. Newer cards can even ignore that constraint.

Question 2: Why force it to be smaller? Programs can use larger textures as long as that size is supported on the hardware. 2048x2048 is a common maximum texture size if you support anything made in the last eight years.

Question 3: Why are you requiring minimization of space? If it is bigger than one texture, it is trivial to just extend it to four, then nine textures (that would be 6144 x 6144 for many cards, which is somewhat huge)

Unless your image is greater than 2048x2048, why are you bothering with this?

Share this post


Link to post
Share on other sites
mameman    100
Hi,

I'm looking at this problem from an efficiency and compatibility perspective. Storing the textures (x, y) as pow2 will (I assume at least) make it as efficient as possible for moving the texture data about the system, and it will work on as many systems as possible, even those that have a low maxtexture size. Sure modern hardware systems support rectangular texturing, and it would be trivial to simply load in the image and apply it to a rectangular polygon but is this more efficient/faster than using pow2 textures?.

MAMEman

Share this post


Link to post
Share on other sites
Drigovas    509
To answer the question that was originally asked, you have a major advantage if you restrict the square size to be powers of 2 as it's edges [in that any square of a given size cannot be broken down into it's next smallest sizes and have those sizes be able to reduce the number of total squares. It's a pretty easy math proof to show this to be the case.]. This breaks the problem down into a problem that isn't like the knapsack problem, because of this additional constraint of each next-largest object being no more than half the weight of the current object [in this case, the weight would be a single edge length. This is exactly why the problem of giving change back to a person using conventional american coinage, while reducable to the knapsack problem, can be solve drasticly faster with a strickly greedy approach]

You have a few options.

A: Start with a square that is too big, and reduce it by half length and half width each iteration, cookie-cutting parts of the image away. Works great so long as each square has two of it's edges completely along the edge of the remaining image.

B: Start with an image covered in 1x1 squares [thats 2^0, so still counts], and merge squares together any time you have a block of four squares of the same size that have at least two of the edges of the final-product block not being adjacent to any smaller blocks. Have your block-merge method consider just blocks of size 1x1, then just 2x2, then just 4x4 and so on.

Both methods will leave you with minimal numbers.

Either way, it's a problem that is ideally assaulted from a greedy approach, and doesn't require the careful handling of a knapsack-like problem. It's also not NP, or NP-Complete. It also DOES NOT YEILD UNIQUE ANSWERS [as more than one arrangement of squares will meet this request in most cases.] It IS reducable to the knapsack problem, and a knapsack solver will successfully solve it, but a straight-forward greedy approach would be faster.

Anyway, not too bad to hack it together. Seriously consider revising your texture formation though, as changing textures THIS much will kick your performance in the teeth.

Share this post


Link to post
Share on other sites
mameman    100
Hi,

Many thanks for all of the responses :). I think that I may have to think about using smaller rectangles for the partitioning of the larger rectangle xr, yr as opposed to using squares. Because using my approaches to this problem have yeilded a HUGE number of separate squares, and I've not completely covered the original rect. In this context Drigovas, the switching of textures to use with the polygons would indeed kill my performance stone dead. Using the rectangular approach (width being pow2) does make the problem of developing an algorithm for the partitioning of the larger rectangle trivial (just split the rect up into 4 separate rectangles and texture those), however will I be sure that the implementation of this will work on as many graphics platforms as possible?. What about those that don't have hardware support for rectangular non-pow2 textures?.

MAMEman.

Share this post


Link to post
Share on other sites
Agony    3452
I'd say just go with a larger single texture and be done with it.

If you have a 31x31 image, and you try to represent that with square power-of-2 textures, then you'll end up with 109 total textures, if my count isn't off. This is an absurd number of textures, and only for a 31x31 image. The texture state swapping performance would probably be attrocious compared to if you simply used a 32x32 image and wasted 63 pixels. Not to mention, all the memory needed to manage 109 textures is probably larger than the space wasted by 63 pixels. (Yes I know, this is a worst-case scenario, but you'll probably wind up with a lot of scenarios that are approaching it in terms of severity.)

Image: (excuse the fact that characters aren't actually square)
|<-------------31------------>|
|<-----16----->||<-08->||04||||

/--------------\/------\/--\/\o
|oooooooooooooo||oooooo||oo|\/o
|oooooooooooooo||oooooo||oo|/\o
|oooooooooooooo||oooooo|\--/\/o
|oooooooooooooo||oooooo|/--\/\o
|oooooooooooooo||oooooo||oo|\/o
|oooooooooooooo||oooooo||oo|/\o
|oooooooooooooo|\------/\--/\/o
|oooooooooooooo|/------\/--\/\o
|oooooooooooooo||oooooo||oo|\/o
|oooooooooooooo||oooooo||oo|/\o
|oooooooooooooo||oooooo|\--/\/o
|oooooooooooooo||oooooo|/--\/\o
|oooooooooooooo||oooooo||oo|\/o
|oooooooooooooo||oooooo||oo|/\o
\--------------/\------/\--/\/o
/------\/------\/------\/--\/\o
|oooooo||oooooo||oooooo||oo|\/o
|oooooo||oooooo||oooooo||oo|/\o
|oooooo||oooooo||oooooo|\--/\/o
|oooooo||oooooo||oooooo|/--\/\o
|oooooo||oooooo||oooooo||oo|\/o
|oooooo||oooooo||oooooo||oo|/\o
\------/\------/\------/\--/\/o
/--\/--\/--\/--\/--\/--\/--\/\o
|oo||oo||oo||oo||oo||oo||oo|\/o
|oo||oo||oo||oo||oo||oo||oo|/\o
\--/\--/\--/\--/\--/\--/\--/\/o
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\o
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/o
ooooooooooooooooooooooooooooooo

You could give up on the square texture compatibility, and simply go with power-of-2 rectangles while still trying to conserve space. You'd end up with a total of 25 textures that way. Still a lot of textures, far more than should be used in my opinion.
|<-------------31------------>|
|<-----16----->||<-08->||04||||

/--------------\/------\/--\/\o
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
\--------------/\------/\--/\/o
/--------------\/------\/--\/\o
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
\--------------/\------/\--/\/o
/--------------\/------\/--\/\o
|oooooooooooooo||oooooo||oo||||
|oooooooooooooo||oooooo||oo||||
\--------------/\------/\--/\/o
/--------------\/------\/--\/\o
\--------------/\------/\--/\/o
o--------------oo------oo--oooo

Not to mention that dividing your image this way will mess up attempts to do any texture filtering, since all the edges will probably show up as sharper, while the filtered inner regions of each sub-texture will be appropriately filtered (generally providing that somewhat blurry look, of course).

It just seems like it would be a mess, compared to using the smallest legal texture that is of equal or greater size than the image and using texture coordinates to cut off the unused portions.

Share this post


Link to post
Share on other sites
mameman    100
Hi,

Hmm.. Interesting thoughts Agony (you came up with the same figure I did for a 31x31 image) ;). However having looked at your diagrams I've just thought of maybe an acceptible solution to the problem. As an example consider a rectangular image of size say 20x19. Now if I consider this in terms of my contraints the polygon and texture to be used will be 32x32. If I create a texture that is 32x32 and then just copy the pixels (starting at the top left corner of the destination texture) then of course the texture co-ordinates will be (0, 1), (20 / 32, 1), (20 / 32, 19 / 32), (0, 19 / 32), if you start the the top left and work counter-clockwise. Using this approach does seem like the best way to go for number of reasons.

(1) I'm only using 1 texture context so I don't have to keep changing contexts for the same image. (can't get any lower than that) :)
(2) It doesn't invalidate any of the initial contraints.
(3) It should (in theory at least) work on most hardware platforms.

The downsides to this approach (that I can see) are:

(1) Lots and lots of texture space being wasted on systems that only support square textures.
(2) Could be performance issues on low-spec systems because of (1).
(3) Having to do alpha testing on square textures so as to make sure that the wasted space isn't visible.
(4) Textures will take up even more space because of (3) i.e. 32-bit textures.

Any thoughts and or comments on this would be appreciated.

Share this post


Link to post
Share on other sites
Agony    3452
Quote:
(1) Lots and lots of texture space being wasted on systems that only support square textures.

Instead of thinking in terms of breaking an image into multiple square textures, you might consider a somewhat opposite idea: Packing multiple images into one larger square texture.

If you had a bunch of 129x129 images, for example (I love worst-case scenarios), you could create a 1024x1024 texture, and pack 49 of those 129x129 images in there. If you didn't do that, you'd be allocating 256x256 pixels per image (65536 pixels total), but using only 129x129 per image (16641), which means you waste 74.6% of the space allocated. But if you did use the big texture (and did happen to have 49 of these images), then you'd allocate 1048576 pixels, use 16641 * 49 = 815409 pixels, and only waste 22.2% of the space you allocated.

You could later come back and improve your packing algorithm, by trying to intelligently pack all your images of various sizes into as few textures as possible. Depending on the max texture size allowed by the card, and depending on the nature of the images you're trying to pack, I bet you could get a pretty low percentage of waste with a good algorithm.

An additional side benefit is that it could potentially reduce texture switches even more, and thus might even be useful on devices that support non-square non-power-of-2 textures.

Share this post


Link to post
Share on other sites
mameman    100
Many thanks Agony. You've given me some great ideas there. Storing the images in separate files and then packing them into one big texture.. Cool. This would be good because I could use 1 big texture for example to draw game sprites or models etc. and not have to worry about loading in lots of images for the same sprite / model or indeed different models or sprites and do loads of texture context switching. I also save space too!. I'm not to keen on looking at non-pow2 rectangular textures just yet because not many people (I assume) have got the hardware to support it, so I'll just keep looking at pow2 square textures for the immediate future. Once again cheers dude.

Share this post


Link to post
Share on other sites
frob    44972
Quote:
Original post by mameman
I'm not to keen on looking at non-pow2 rectangular textures just yet because not many people (I assume) have got the hardware to support it, so I'll just keep looking at pow2 square textures for the immediate future. Once again cheers dude.

These have nothing to do with your question, but ...

Even the oldest consumer 3D hardware supports pow2 rectangular textures.

Any competent artist or experienced 3D programmer could have told you to stick multiple pieces of art on a single texture. That wasn't your original question, though, and I assumed you knew about that.

Font texture sheets are a classic example of both of these. You can stick raster glyphs on a texture, maybe have some mipmaps of them, and save on the (very slow) texture changes

If your purpose is actual runtime speed, you should know that changing textures is an extremely slow state change. About a decade ago it was one of the longest state changes, although newer more advanced features take longer in newer cards. This, along with data caching, is a good reason to render all the instances of a model at the same time.

Share this post


Link to post
Share on other sites
mameman    100
Frob,

I don't want to start an argument here, but I have a very old Hercules Prophet graphics card (GeForce2 chipset) and this cannot create rectangular pow2 textures. The OpenGL(1.3) extensions string does not have the EXT_texture_rectangle present. Which means (I assume) that the system doesn't support rectangular textures. I do know that newer OpenGL implementations do (2.0 or above I think) because I have a much newer system < 3 months and I have non-pow2 and rectangular texture support (according to the OpenGL extensions string). As a thought, how many old books/websites (say > 2 years old) on OpenGL do you know of with examples of creating rectangular pow2 textures?. If you'd point me in the right direction I'd be most interested to see them.

The advice given by Agony made me think about my particular problem in a different way, which lead me to a different solution to my original question. In that it will not matter what images I'm using (xr, yr) the textures created will always be (xs, ys) with (xs = ys) and pow2. In addition there will be fewer texture context changes because the image(s) can be packed into a few textures.

BTW, I'm a Windoze applications programmer (with SQL) (therefore the people I know, know as much about 3D game programming as they would about quantum theory) ;) by day, and newbie game programmer by night.

But anyway, thanks for your thoughts and comments.

[Edited by - mameman on March 8, 2007 7:19:12 AM]

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