Re: [pygame] FastRenderGroup revised (update4)

["Brian Fisher" <brian@xxxxxxxxxxxxxxxxxxx>]

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.