Re: [pygame] Dirty rect overlapping optimizations

On Mon, Mar 27, 2017 at 12:34 PM, René Dudfield <renesd@xxxxxxxxx> wrote:

On Mon, Mar 27, 2017 at 8:08 PM, Ian Mallett <ian@xxxxxxxxxxxxxx> wrote:
--IDK if pygame does this, but I expect blitting, with overdraw, to a fullscreen temporary surface, and then sending the whole surface every frame to the GPU would be faster than updating multiple smaller portions of the GPU memory with CPU data.

Double buffering works like that. Except with update you can tell it to update only parts of the back buffer. When you display.flip()/update() it sends the data. It's faster because less data is sent over the bus. But even on OpenGL slower implementations (or with higher resolutions) you can gain benefits by only updating part of the buffer(s). Not on monster dedicated cards at lower resolutions of course.

I suppose. Still, this should be asynchronous. Maybe making it work in Python isn't possible.

--IIRC the fastest algorithm for rect-rect collision detection is the max-of-mins/min-of-maxes method, which is widely known. It maps nicely to SSE too.

Sounds interesting. Maybe that's what we're using now for rect collision... I'm not sure of the algo name. It's only in C however.

Yeah I'm not sure it has its own name. And definitely you'd want it in C or equivalent.

Below is one of the cases that benefits the most. (actually after drawing this I'm not sure if this is actually true or I dreamed it up... but I drew the diagrams... so it feels a waste to delete them).

Currently the update method combines two rects like this:
_______
|     |
|   __|____
|___|_|       |
    |     |
    |     |
    |_____|

Into a big rect like this:
___________
|     ####|
|   ####|
| XX | # - updated, but no need.
|###    | X - over drawn.
|###    |
|###______|

Note in these crude diagrams the # area is drawn even though it doesn't need to be, and the XX is over draw. When there are some overlapping rects like this that are large, that can be quite a saving of pixels not needed to be drawn.

Right.

the thing to consider is what you do about it. You can't just "not draw" those pixels, because you still have to iterate over them, which defeats the point. Instead, you have to decompose the combination of rects into disjoint subrects that span the region that needs to be updated. For your example:

┌────┐

│ │

│ ┌─┼──┐

└──┼─┘ │

│ │

└────┘

. . . the decomposition could be something like:

┌────┐

│ │

│ ├──┐

└──┬─┤ │

│ │ │

└─┴──┘

The key point is that doing this decomposition needs to be faster than just drawing. Unfortunately, computing those rectangles is annoying, and also O(n^2) in the number of rectangles (whereas the number of overdrawn pixels you save can be linear-ish).

Ian