[Qt-interest] Best way to update 10^5 items

[Oliver.Knoll at comit.ch]

Ole Streicher wrote on Tuesday, September 29, 2009 4:08 PM:

> Hi,
> 
> I have a huge graphics scene that contains about 100.000 individual
> items (Ellipses, squares) whose colors are regularly updated. 

Typically you don't need to update *all* objects; unless they are about 4x4 pixels in size and fill an entire 1680 x 1024 screen (roughly ;) without overlapping each other.

So your problem is the typical graphic scenario: "Which objects are actually visible on the screen?" Or in other words: "Which objects do I actually have to *really* re-paint?"

The solution off course depends on your data model/organisation (hierarchical trees, such as octrees in 3D scenarios etc.), but in the end it all boils down to "clipping":

  http://en.wikipedia.org/wiki/Clipping_%28computer_graphics%29

That is, making sure you only update/draw those objects which are actually visible.

Once you have decided which objects are actually visible you can gain even more performance by *simplifying* your objects. For exampe, an ellipse which would end up as being rendered as a 4 x 4 pixel small object, why not "approximate" it with a simple rectangle? And if it becomes even smalller, why not just draw a dot? Turn off anti-aliasing for small objects, don't draw contour lines etc. etc.

Actually the Qt "Chips" graphic demo makes use of exactly these techniques, study its code. :)

  http://doc.trolltech.com/4.5/demos-chip.html

(It "only" deals with 40'000 objects - but then again, those "chips" are probably more complex than your rectangles and ellipses. Anyway, the same techniques apply ;)

Good luck, Oliver

-- 
Oliver Knoll
Dipl. Informatik-Ing. ETH
COMIT AG - ++41 79 520 95 22