Blit Queue Optimization Algorithm

Question

I am looking to implement a module that manages a blute queue. There is one surface, and parts of this surface (limited by rectangles) are copied to another place on the surface:

add_blt(rect src, point dst); 

A queue can have any number of operations sent to the queue. In the end, the queue user will cease to place glare and ask for the optimal set of operations for actual execution on the surface. The task of the module is to ensure that the pixel will not be copied unnecessarily.

It gets complicated due to coincidences, of course. Blit can rekindle a previously copied pixel. Ideally related operations are subdivided into the optimization phase in such a way that each block goes to its final location with one operation.

It is difficult, but not impossible to combine it. I'm just trying not to reinvent the wheel.

I looked around the net, and the only thing I found was the SDL_BlitPool Library , which assumes the source surface is different from the destination. It also makes a lot of grunts, seemingly unnecessary: ​​regions and similar building blocks are preset. I am looking for something of a higher level. Of course, I’m not going to look like a gift horse in my mouth, and I don’t mind doing the real job either ... If someone can offer a basic idea that makes this problem less complicated than the right one now it would be great too.

EDIT:

Thinking about the answer aaronasterling ... can this work?

• Introduce an individual area handler code that can support metadata for each rectangle it contains. When a region handler splits a rectangle, it automatically associates the metadata of that rectangle with the resulting sub-rectangles.

• When the optimization starts, create an empty area processed by the above code, name it master region

• Iterate through the blt and for each entry:

  • Let srcrect be the source rectangle for blt beng reviewed

  • Get the intersection of srcrect and master region in temp region

  • Remove temp region from master region , so master region no longer covers temp region

  • srcrect to the area ( srcrgn ) and subtract temp region from it

  • The offset of temp region and srcrgn with the vector of the current blt : their union will cover the destination area of ​​the current blt

  • Add to the master region all the rectangles in the temp region , preserving the original metadata of the source code (step 1 of adding the current blt to the master region )

  • Add to the master region all the rectangles in srcrgn , adding the source information for the current blt (the second step is to add the current blt to the master region )

• Optimize the master region by checking if adjacent sub-rectangles that are merge candidates have the same metadata. Two sub-rectangles are candidates for merging if (r1.x1 == r2.x1 && r1.x2 == r2.x2) | (r1.y1 == r2.y1 && r1.y2 == r2.y2) (r1.x1 == r2.x1 && r1.x2 == r2.x2) | (r1.y1 == r2.y1 && r1.y2 == r2.y2) . If yes, connect them.

• List the sub-rectangles of the master region . Each rectangle returned is an optimized blt operation destination. Associated metadata is the source of the blt operation.

Answer 1

One idea that comes to mind is to store the defining points of the rectangles that are added in the quad tree (or in some other structure that will allow for efficient collision detection). So, now when you add a new rectangle, you can check it for conflicts. The idea is that when a new rectangle collides with an old rectangle, you resolve collisions by breaking the old rectangle into 4, 3 or 2 new rectangles that do not include the part that intersects the newly added rectangle. We know that the old rectangle did not intersect with any other old rectangles, and therefore, since it has just been created, we know that they do not intersect with any of them, so you do not need to perform collision detection.

For example, starting with:

and adding one rectangle:

will be allowed:

Here, one of the old rectangles is divided into two new rectangles, and the other is divided into three.

This ensures that after adding a new rectangle, the queue is always in the non-intersecting state, which means that copying these rectangles will not copy the pixel twice.

Answer 2

SDL_BlitPool .. oh, what is my early work.

BlitPool Path -

 for_each(down to up) { if (overlapped) { 1 split back-surface 1-1 calculate overlap code 1-2 add sub-rectangle (use overlap code) 1-3 delete divided-surface } } 

basically that is all.

"overlap code" is 0-15 integers.

you know, the overlap pattern is only 16 patterns.

http://bitbucket.org/sharow/sdl_blitpool/src/ea6c02fef26f/resource/SDL_BlitPool_02.png

The overlap code is a 4-bit (0-15) value.

The first 2 bits is the Y axis, and the 2bit tail is the X axis (in SDL_BlitPool).

Each 1 bit value is an MSB value.

This is visualized as ...

http://bitbucket.org/sharow/sdl_blitpool/src/ea6c02fef26f/resource/SDL_BlitPool_01.png

In this image: MSB == arrow.

I thought there was a better library for another. hmm, I want to rewrite it ...

sorry for my english level.