QGraphicsScene, Item Coordinates Affect Performance?

Question

With the below code snippet I create a scene with 100.000 rectangles.
The performance is fine; the view responds with no delays.

QGraphicsScene * scene = new QGraphicsScene;
for (int y = -50000; y < 50000; y++) {
   scene->addRect(0, y * 25, 40, 20);
}
...
view->setScene(scene);

And now the 2nd snippet sucks

for (int y = 0; y < 100000; y++) {
   scene->addRect(0, y * 25, 40, 20);
}

For the 1st half of scene elements the view delays to respond on mouse and key events, and for the other half it seems to be ok ?!?

The former scene has sceneRect (x, y, w, h) = (0, -1250000, 40, 2499995).
The latter scene has sceneRect (x, y, w, h) = (0, 0, 40, 2499995).

I don't know why the sceneRect affects the performance, since the BSP index is based on relative item coordinates.

Am I missing something? I didn't find any information on the documentation, plus the Qt demo 40000 Chips also distributes the elements around (0, 0), without explaining the reason for that choice.

 // Populate scene
 int xx = 0;
 int nitems = 0;
 for (int i = -11000; i < 11000; i += 110) {
     ++xx;
     int yy = 0;
     for (int j = -7000; j < 7000; j += 70) {
         ++yy;
         qreal x = (i + 11000) / 22000.0;
         qreal y = (j + 7000) / 14000.0;
         ...

Mueller

My first guess is the recalculation of scene rect. What happens if you set the sceneRect before adding the items? – Decimate

@Stephen, the result is the same. The view delays to respond even though the scene is ready and static. – Mueller

Wow, very surprising. I ran a few tests, and it seems that the widget becomes laggy only when you're looking at the 1-50.000 boxes. After, meaning 50.001-100.000, everything is smooth. Even more worrying, if I range for (int y = -70000; y < 30000; y++)­, then scrolling is smooth for -70.000/-20.000, is laggy for -20.000/0, then smooth again for 0/30.000! – Unaccomplished

Answer 1

I have a solution for you, but promise to not ask me why is this working, because I really don't know :-)

QGraphicsScene * scene = new QGraphicsScene;
// Define a fake symetrical scene-rectangle
scene->setSceneRect(0, -(25*100000+20), 40, 2 * (25*100000+20) );

for (int y = 0; y < 100000; y++) {
    scene->addRect(0, y * 25, 40, 20);
}
view->setScene(scene);
// Tell the view to display only the actual scene-objects area
view->setSceneRect(0, 0, 40, 25*100000+20);

Towline

of course I really want to know the reason for that behavior. A bug in the Qt, or is it something else? – Mueller

the bounty is yours Fivo, but the case is still open :) – Mueller

Thanks Nick, although I don't feel I really offered a solution but just a workaround. If you file a bug on Qt site, keep us updated on any official solutions ;-) – Towline

Answer 2

For the common case, the default index method BspTreeIndex works fine. If your scene uses many animations and you are experiencing slowness, you can disable indexing by calling setItemIndexMethod(NoIndex). Qt-doc

You will need to call setItemIndexMethod(QGraphicsScene::NoIndex) before insertion:

scene->setItemIndexMethod(QGraphicsScene::NoIndex);

for (int y = 0; y < 100000; y++) {
   scene->addRect(0, y * 25, 40, 20);
}
//...

Purse

this is not what I'm looking for, Red Hue. Disabling the index isn't a good idea if the scene contains hundred of thousands of items, or millions. What I want is to track down the root of this weird behavior. Plus I already knew a workaround to speed up the code, and Fivos Vilanakis posted another one. – Mueller

@Nick Dandoulakis Have you made a bug report? – Purse

but is it a bug? It could be by design. Anyway, making a report is a good idea. – Mueller

You can always enable BSP indexing again after inserting the items. Not sure if that still exploits the bug or not. – Flimsy

Answer 3

It could be due to loss of precision with float. A 32 bit float has a 23 bit mantissa (or significand), 1 bit sign and 8 bit exponent. This is like scientific notation. You have 23 "significant digits" (really 24 due to an implicit leading 1) and an exponent of 2^exp where the exponent can range from -126 to 127 (others are used to give you things like NaN and Inf). So you can represent really large numbers like 2^24*2^127 but the next closest floating point number to such a float is (2^24-1)*2^127 or 170 billion billion billion billion away. If you try to add a smaller amount (like 1000) to such a number it doesn't change. It has no way to represent that.

This becomes significant in computer graphics because you need some of your significant digits left over to make a fractional part. When your scene ranges up to 1250000.0 you can add 0.1 to that and get 1250000.1. If you take 2500000.0 + 0.1 you get 2500000.0. The problem is magnified by any scaling or rotation that occurs. This can lead to obvious visual problems if you actually fly out to those coordinates and look at your scene.

Why does centering around 0 help? Because there's a separate sign bit in the floating point representation. In floating point there are "more numbers" between (-x,+x) than there are from (0,2x). If I'm right it would also work if you simply scaled your entire scene down by 1/2. This moves the most significant bit down leaving it free for precision on the other end.

Why would this lead to poor performance? I can only speculate without reading the Qt source, but consider a data structure for storing objects by location. What might you have to do differently if two objects touch (or overlap) due to loss of precision that you didn't have to do when they did not overlap?

Nedranedrah

Hi Ben. I just tried your assumption by reducing the scale from 2.500.000 to 1.000.000 and even to 500.000 but there is no improvement. I assume the problem (or the bug?) is not precision-related but has to do mainly with how the Qt QGraphicsView uses the BSP index of QGraphicsScene to clip the Scene Objects when the QGraphicsView viewport is refreshed/updated. – Towline

hi @Ben and @Fivo. I checked out the implementation of the BSP, and float precision doesn't seem to be the case. Qt's BSP just segments the scene/area into N*N buckets without taking account of item positions! Perhaps it is indeed a bug in QGraphicsView. – Mueller