I have lots of bitmaps, all of different dimensions, which I would like to combine into one single bitmap. I want the resulting bitmap to have as small an area as possible. Does anyone know of an algorithm that will take an array of rectangles and produce the smallest possible rectangle into which the array of rectangles will fit? For those wondering why I need to do this, I''m using POV-Ray to render some sprites for my first 2D game. The bitmaps produced by POV are all the same dimensions, but the sprite contained within the bitmap will often be a lot smaller than the bitmap itself. I could simply take the bitmaps from POV and combine them into one large bitmap, but this would result in lots of wasted background space in between each sprite. I''d like to cut such waste down to a minimum and so save on video memory. I don''t need any help with the bitmap manipulation code, it''s just the "best fit rectangle" thing that I''m stuck on. I''ve tried sorting and ordering the bitmaps in various ways, some of which have has pretty good results, but I''m sure there must be an algorithm out there to do this. Thanks for any help, Moot

Why make things complicated? Store them linear =)

I agree with that one. Plus, in case you didn''t know, you can change the size of the output bitmap to whatever size you want. Of course, the scaling will change so you will have to mess with the camera some to get the proper scaling.

Regards,
Jumpster

Ok, i''m being thick here, but when you say store them linearly, do you mean store them as a big row of sprites (ie if I had 8 80x60 sprites, store them in a 640x60 surface) or do you mean store them linearly at a byte level? If you mean the latter, how would I blit between surfaces? For example, if I had an 8x8 sprite stored in a surface in 64 consecutive pixels, is it possible to blit that 64x1 rect to an 8x8 rect? This is the way I''d do it if I was using my own blitting routines, but I didn''t think DDraw allowed it.

If you mean store the sprites in one big row, will I run into problems if the offscreen surface is wider than the primary surface? I''ve heard that some graphics cards drivers will not let you create a surface larger than the primary surface. Does that mean the width, the height or total area?

Jumpster, yeah I know you can change the output bitmap but I don''t want to do any run-time scaling. Thanks anyway.

Cheers,

Moot

Can anyone help?

I don''t know about optimized, but here is an idea. Pick a size you want like 640X480. Sort the sprites by descending size and start filling the bitmap. Tile them across and start the next row at the bottom of the first bitmap of the previous row. You will waste a little space on the right end as well as between rows when the size changes in the row, but that should be minor if you have enough sprites. If you don''t have enough sprites then I would have to ask why you are optimizing their storage.

Thanks, LilBudyWizer, that's almost exactly what I'm doing now. I try all sorts of combinations of sort order and use whichever one results in the smallest area. I was just hoping that someone could provide me with an algorithm to work it out optimally.

I'm still confused by the reply saying "store them linear". If I was using my own blitting routines and as blitting, for example, an 8x4 sprite, I would have the sprite data stored in 32 contiguous bytes of memory (assuming 8 bit colour). I'd then copy 8 bits to the destination buffer, move the destination pointer down to the next line, blit another 8 bits, etc..., effectively blitting a 32x1 source rectangle to an 8x4 destination rectangle. Can someone please confirm that it's not possible to do this in DirectX (without using multiple blts)?

Thanks,

Moot

Edited by - Moot on December 7, 2000 8:28:39 AM

Moot: I think these people mean that 10 80x60 bitmaps can be stored as a 800x60 bitmap, not a 48000x1 bitmap. But then again, all your bitmaps are not the same size.

Yeah, thanks Beer Hunter, I''ll just squeeze my sprites in as best I can and not worry about wasted space.

This may be way off topic, but what you are trying to do reminds me of the ''backpack problem'' - trying to pack as much as possible into a ''backpack''.

A link:
http://www.edm2.com/0601/backpack.html

this is not the best link i''ve found, just the one i''ve most recently seen.

Hope this helps, or is remotely interesting - either way

Wyzfen