Hallosince my last email (with attachment) did not get through to the mailing list, this time I only will provide a link :-)
http://www.mypage.bluewin.ch/DR0ID/pygame_projects.html#fast_dirty1 or direct donwload: http://www.mypage.bluewin.ch/DR0ID/pygame/FastRenderGroup_v1.1.83.zipI have been trying different tiling methods and timing methods. All tiling methods I tried were about 3 times slower as current implementation in the average case. Because of that result it still uses the original implementation which is an O(n**2) algorithm in worst case (I think average case is something between O(n) and O(n**2) ). Perhaps I have done something wrong so if you implement a fast tiling algorithm let me know please. If you are interested in what i have done then look into the subfolders tiling and timing and search for "####try" in the source code of TilingFastRenderGroup.py or in the other case TimingFastRenderGroup.py.
I have changed the timing code to the very simplest approach: it checks the time needed to render the frame at each frame and decides using a threshold value what mode to use. The problem now lies in finding the correct threshold (which at the moment has to be set by the programmer). This approach works even smother than the old one.
I have modified testsprite.py to use FRG, please test following configurations:
testsprite.py testsprite.py -update_rects testsprite.py -FastRenderGroup testsprite.py -static testsprite.py -static -update_rects testsprite.py -static -FastRenderGroup What do you think? For that tests I have added a new image, as you can see.I have written a demo to demonstrate that all sprites have to be in the same FRG to be drawn correctly:
multi_FRG_demo.pyuse the same arguments as for testsprite.py and you will see what happens when using the FRG.
~DR0ID Brian Fisher schrieb:
On 6/29/07, DR0ID <dr0id@xxxxxxxxxx> wrote:I think this is only a O(n^2) in worst case otherwise it is less (but I cant tell you what it is). The drawback of that method is, that in the worst case it ends up with a big rect covering the entire screen. Perhaps using Gustavos rect splitting thing would be better (? faster?).At work we use tiled rects for our dirty rect system for software rendering. It's a C++ engine, but the 2 really big wins for a tiling system is that you never need to merge rects (merging is in general O(n^2) unless you maintain some kind of partitioning system, then it can by n log n) and you don't need to manage a pool for allocating/deleting (a fixed size linked list pool can be constant allocation and deletion time, but naive object allocation and deletion from a variable sized heap/pool can be very very slow) We tested a lot of different approaches and tiling was by far the fastest we tried (in C++ anyways). In particular the fastest implementation for us was where each tile has it's own rect, and it does min/max ops on the cells rect to grow it to cover the overlap being the dirty rect and the cell area. So in cases with a fairly small number of objects, you oftenget a perfectly tight fit even though the cells are like 16x8, but it's still all O(n) where n is the number of objects.