Jump to content
  • Advertisement
Sign in to follow this  
mameman

Splitting Rectangle Into Squares

This topic is 4126 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!