On 6/29/07, DR0ID <[EMAIL PROTECTED]> 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.
