Saturday, March 06, 2010

Ideas for Super Surfaces in pygame.

pygame already has a sub-surface, which is part of a larger surface. Sub-surfaces refer to the same pixels as the surface they come from, and share the same Interface as a Surface. It's good for doing sprite sheets, where you save one file with many smaller images - but then being able to manipulate them as if you loaded the images as smaller separate surfaces.

However, sometimes we would like to operate on a whole bunch of smaller surfaces stuck together. This is what I'd like to call a Super Surface - a collection of smaller surfaces which can act as one big surface. It's a complementary idea to the sub-surface, and intuitively it should be there... but it's not yet.

Unfortunately it's a lot harder to code a Super Surface compared to a sub-surface. Since a Super Surface would need to have all the surface affecting routines changed to work with it.

For example, everything in the draw modules would need to be redone. So would all of the surface methods. So when you draw a line on a super surface, it should affect all of the sub-surfaces.

How can Super Surfaces be implemented.

Still trying to think of a simple/clever way of implementing it efficiently, without having to recode all of the drawing/blitting routines. However, just like how sub-surfaces in pygame can simplify code immensely - so too will Super Surfaces.

One method, might be to do a rect translation, and then broadcast the translated method calls over the sub surfaces of the Super Surface. So we translate the rects into the sub-surface coordinate space from the Super Surfaces coordinate space.

I'm not so sure if we can get a function pointer to a method from within the function pointer itself with the python C API. This would simplify it, because the translate-and-broadcast functionality could be implemented in one place and reused within all of the various surface affecting routines automatically. Something to research...

Common methods for implementing tiling engines.

Super Surfaces share a lot of the same properties a tiling engine. So how are tiling engines implemented?

A common way for tiling engines to work is to have the images being placed in a grid, and for each of the sub-surfaces to be the same size. So the image at [0][0] in the array is at those coordinates. This simplifies the implementation, but is not very flexible. A slightly more complex way to implement it is to have each sub surface have its position stored relative to the super surface. This complicates the clipping a little, and for speedy use it really requires a spatial hash... like a quadtree.

So I'm thinking of doing the more free form implementation... probably just a naive implementation to start with... then perhaps a quatree version as an improvement. It would be better to use a spatial hash more efficient at moving elements - but that could be a third improvement.

Use cases for Super Surfaces

Use cases include viewing massive images. Much graphics hardware has texture size limits, so it is common to combine many smaller textures when drawing larger images.

Another common use case is for 'tile engines'. Where tile engines show a larger image made up of many smaller images.

To allow using different image formats for different parts of an image is another use case. For example, a piece of the image which is just black only needs a few bytes to represent the image... it does not need 32bits per pixel. Whereas the part of the image which includes a persons face with 50% transparency will require 32bits per pixel for sure. This will save memory, and increase speed. It increases speed, because it is possible less memory bandwidth means faster operations. Also, less complicated blending - or more optimized blitting can happen (eg, fast 8 bit Run Length Encoding blitters). This should be possible with no extra effort from the programmer too.

Finally, by using smaller sub-surfaces it in effect becomes a tiling engine automatically. Tiling in graphics is used to split operations up easily. This gives memory, and speed advantages. By processing a tile at a time - you only need to have those tiles in memory at that time. It also gives easy parallelism, since the separate tiles are a form of data parallelism (which is the easiest type). For some hardware, it is possible to use parallelism when the surfaces are kept separate.

I'm interested in any comments, especially if you've made a tiling engine like this before?


Stu said...

The super surface should be able to tell it's sub surfaces when they are going to become visible and also, when they are not needed any more. This way it can be used for resource management.

Axion said...

I stumbled upon a simple trick for this in the source of Gummworld2, a big inspiration for the rewrite of crawlr.


The author has since modified this approach but I have not yet studied it. You can check out the 3 consecutive revisions there if you're interested.