Re: [pygame] Dirty rect overlapping optimizations

[Ian Mallett <ian@xxxxxxxxxxxxxx>]

Hi,

On Mon, Mar 27, 2017 at 12:16 PM, DR0ID <dr0id@xxxxxxxxxx> wrote:

On 27.03.2017 20:08, Ian Mallett wrote:

max-of-mins/min-of-maxes method

Hi Ian

Could you share more about this method? Seems I can't find something related to dirty rects with that.


~DR0ID

It's a rect-rect collision detection algorithm, which could be applied to detect which rects overlap (and gives the overlapping rect also). It's the standard algorithm people use for this purpose, although people tend to think of it in terms of multiple tests, which is less intuitive (to me, anyway) and slower.

The test is basically (from memory):

collided = max(rect1.min,rect2.min) < min(rect1.max,rect2.max)

In 1D, you can think of "rect.min" as being "rect.left" and "rect.max" being "rect.right". In nD rect.min is a vector [left,bottom,back,...] and rect.max is a vector [right,top,front,...] and the "<" must apply along all axes. That's why it's great for SSE. You can also subtract the terms to get the dimensions of the overlapping area.

On Mon, Mar 27, 2017 at 12:23 PM, Radomir Dopieralski <pygame@xxxxxxxxxxxx> wrote:

On Mon, 27 Mar 2017 12:08:10 -0600
Ian Mallett <ian@xxxxxxxxxxxxxx> wrote:

> --There are two key cases to think about: (1) You have 1x1 pixel
> rects for each pixel on the screen. No overdraw, so the algorithm is
> complete waste.

I think it would make sense to merge dirty rectangles even if they don't
actually overlap, but simply touch. This would improve this use case
(and a common use case of a tiled map) greatly.

--
Radomir Dopieralski

 

​I agree; this is desirable.​

Ian​