Blit Queue Optimization Algorithm
- by martona
I'm looking to implement a module that manages a blit queue. There's a single surface, and portions of this surface (bounded by rectangles) are copied to elsewhere within the surface:
add_blt(rect src, point dst);
There can be any number of operations posted, in order, to the queue. Eventually the user of the queue will stop posting blits, and ask for an optimal set of operations to actually perform on the surface. The task of the module is to ensure that no pixel is copied unnecessarily.
This gets tricky because of overlaps of course. A blit could re-blit a previously copied pixel. Ideally blit operations would be subdivided in the optimization phase in such a way that every block goes to its final place with a single operation.
It's tricky but not impossible to put this together. I'm just trying to not reinvent the wheel.
I looked around on the 'net, and the only thing I found was the SDL_BlitPool Library which assumes that the source surface differs from the destination. It also does a lot of grunt work, seemingly unnecessarily: regions and similar building blocks are a given. I'm looking for something higher-level. Of course, I'm not going to look a gift horse in the mouth, and I also don't mind doing actual work... If someone can come forward with a basic idea that makes this problem seem less complex than it does right now, that'd be awesome too.
EDIT:
Thinking about aaronasterling's answer... could this work?
Implement customized region handler code that can maintain metadata for every rectangle it contains. When the region handler splits up a rectangle, it will automatically associate the metadata of this rectangle with the resulting sub-rectangles.
When the optimization run starts, create an empty region handled by the above customized code, call this the master region
Iterate through the blt queue, and for every entry:
Let srcrect be the source rectangle for the blt beng examined
Get the intersection of srcrect and master region into temp region
Remove temp region from master region, so master region no longer covers temp region
Promote srcrect to a region (srcrgn) and subtract temp region from it
Offset temp region and srcrgn with the vector of the current blt: their union will cover the destination area of the current blt
Add to master region all rects in temp region, retaining the original source metadata (step one of adding the current blt to the master region)
Add to master region all rects in srcrgn, adding the source information for the current blt (step two of adding the current blt to the master region)
Optimize master region by checking if adjacent sub-rectangles that are merge candidates have the same metadata. Two sub-rectangles are merge candidates if (r1.x1 == r2.x1 && r1.x2 == r2.x2) | (r1.y1 == r2.y1 && r1.y2 == r2.y2). If yes, combine them.
Enumerate master region's sub-rectangles. Every rectangle returned is an optimized blt operation destination. The associated metadata is the blt operation`s source.
