Hi Jason
Thanks for your code, it inspired me to try to make a faster version.
At first I tried other ways but at the end I implemented almost the same
as you did, but just using the pygame methods for speed up (in exchange
it is tied to pygame now, yours works just for python). For next time at
least there will be some tests that can be re-used.
IIRC the algorithm tries to make as big rectangles if possible, so it
does some sort of union them (without extra pixels). One can see how the
algorithm splits the rects using the sript 'gumm_needs_to_see.py' (needs
pygame) in my repo [1]. Use arrow keys to move forward, space to change
between the two algorithms (so you see differences between them in the
result). It will go through all rect configurations (and some more) from
the article [2].
My code has been tried to be written for performance that is why it
might not be that readable (and also because there are many cases). Also
I'm not sure anymore why it is around 2x faster only with -OO flags
(looking at the code there aren't any asserts or such).
~DR0ID
[1]
https://bitbucket.org/dr0id/pyweek-games/src/1a9943ebadc6e2102db0457d17ca3e6025f6ca60/pyweek19-2014-10/practice/dirtyrects/?at=default
<https://bitbucket.org/dr0id/pyweek-games/src/1a9943ebadc6e2102db0457d17ca3e6025f6ca60/pyweek19-2014-10/practice/dirtyrects/?at=default>
[2] http://gandraxa.com/detect_overlapping_subrectangles.xml
<http://gandraxa.com/detect_overlapping_subrectangles.xml>
On 28.03.2017 14:19, Jason Marshall wrote:
I tested the effect of my optimize_dirty_rects script that René
mentioned, and I found that the time spent in my optimization
algorithm exceeded the time saved by blitting fewer pixels. :-( I've
thought about reimplementing it in Cython to see if that would make
the algorithm run fast enough that its overall effect is to save time,
but I haven't gotten around to doing that.
Jason
On Mar 26, 2017 2:50 PM, "René Dudfield" <ren...@gmail.com
<mailto:ren...@gmail.com>> wrote:
Because rectangles can overlap, it's possible to reduce the amount
drawing done when using them for dirty rect updating. If there's
two rectangles overlapping, then we don't need to over draw the
overlapping area twice. Normally the dirty rect update algorithm
used just makes a bigger rectangle which contains two of the
smaller rectangles. But that's not optimal.
But, as with all over draw algorithms, can it be done fast enough
to be worth it?
Here's an article on the topic:
http://gandraxa.com/detect_overlapping_subrectangles.xml
<http://gandraxa.com/detect_overlapping_subrectangles.xml>
jmm0 made some code here:
https://bitbucket.org/jmm0/optimize_dirty_rects/src/c2affd5450b57fc142c919de10e530e367306222/optimize_dirty_rects.py?at=default&fileviewer=file-view-default
<https://bitbucket.org/jmm0/optimize_dirty_rects/src/c2affd5450b57fc142c919de10e530e367306222/optimize_dirty_rects.py?at=default&fileviewer=file-view-default>
DR0ID, also did some with tests and faster code...
https://bitbucket.org/dr0id/pyweek-games/src/1a9943ebadc6e2102db0457d17ca3e6025f6ca60/pyweek19-2014-10/practice/dirtyrects/?at=default
<https://bitbucket.org/dr0id/pyweek-games/src/1a9943ebadc6e2102db0457d17ca3e6025f6ca60/pyweek19-2014-10/practice/dirtyrects/?at=default>
So far DR0ID says it's not really fast enough to be worth it.
However, there are opportunities to improve it. Perhaps a more
optimal algorithm, or one which uses C or Cython.
"worst case szenario with 2000 rects it takes ~0.31299996376 seconds"
If it's 20x faster in C, then that gets down to 0.016666. Still
too slow perhaps.
It's not an embarrassingly parallel problem... I think. But I
haven't thought on it much at all. Maybe there is a use for multi
core here.
Anyone done any other work like this? Or know of some good algos
for this?
cheers,