Rendering rectangles speed issue

[macbeth]

Hello to everyone,

I'm (still) working on an application used for plotting graphs and I've come across one not very pleasant speed issue regarding drawing rectangles -- the larger rectangle, the slower drawing speed.
My application should be able to handle millions of values, but I've found out, that it takes very long to draw barplot or similar plot containing rectangles (drawing ellipse is faster)... When drawing small rectangles (4x4 pixels), it is quite fast (250 000 rects/6sec), but then I tried to draw 250 000 rects, each 200x200 pixels large, and it took almost 15(!) minutes to complete this task... (same code and image size, just increased rects sizes)
Do you know any workaround for that? Or do you have any suggestions how to make drawing faster?

Another question: I'm drawing on QImage, do you think that new (since Qt4.2) graphic canvas would be better for drawing these kind of plots?

Thanks for every answer.

[Boron]

Some years ago, during my studies, I took over a student project, written in C++/Qt-3.
It was a simple user interface, whose main part was a simplified soccer field (a bitmap of about 500x300 pixels). Players were also drawn pixel-wise. Well, not pixel by pixel but in bitmap style, somehow.
A robot soccer game was shown with 3 vs. 3 players.
And the whole picture was flickering and awful slow. CPU utilisation was about 95% on an 1.5Ghz machine. Just für six players (shown as coloured circles) and on white filled circle as ball.

I decided to rewrite some code.
QCanvas of Qt3 was the "chosen one" for presenting/drawing the game.
After I did this the CPU utilisation was ridiculous low. Everything went smooth. And it even looked better .

Long story short:
Use QGraphicsScene, which replaces the QCanvas from Qt3 in Qt4.

[macbeth]

Thanks for your answer!

I'm just thinking about rewriting some code to see how would it behave with QGraphicsScene, it looks like it has many good features and supports printing and rendering to QPaintDevice, which is crucial for me...

[macbeth]

Hm, another strange thing that showed up: when I add 250 000 small (5x5pix) rectangles on the GraphicsScene and then want to show it using GraphicsView, the cpu 'user' load rises to ~90%. Not just during plotting, but for all the time after the rectangles are drawn. That's looks quite strange to me... (If I draw ~50 000 rectangles, the cpu usage is about 50%)

Does anybody know, what is GraphicsView doing in the background? Still updating the view?
I'm quite disappointed, because they say in Qt docs:

Graphics View uses a BSP (Binary Space Partitioning) tree to provide very fast item discovery, and as a result of this, it can visualize large scenes in real-time, even with millions of items.

But how can one use it, if the cpu load is 90% :/

Well, maybe I've made a mistake somewhere, but I just tried to edit one of the examples (portedcanvas in examples/graphicsview) and instead of adding one rectangle I added many of them, so I don't know what's wrong...

Any advice appreciated, thanks...

[jacek]

When drawing small rectangles (4x4 pixels), it is quite fast (250 000 rects/6sec), but then I tried to draw 250 000 rects, each 200x200 pixels large, and it took almost 15(!) minutes to complete this task... (same code and image size, just increased rects sizes)

250 000 of 4x4 rects gives 4 000 000 pixels to draw.
250 000 of 200x200 rects gives 10 000 000 000 pixels.

It has to take a lot of time to draw it, unless you reduce the number of rectangles (for example by throwing away the occluded ones).

Try this on your computer:

int main()
{
   for( long long i = 0; i < 10000000000; ++i );
   return 0;
}

int main()
{
   for( long long i = 0; i < 10000000000; ++i );
   return 0;
}

To copy to clipboard, switch view to plain text mode 

$ time ./a.out

real 0m30.870s
user 0m30.698s
sys 0m0.140s

(just don't cheat by turning on the optimization).
It takes 30 seconds on my computer just to count from 0 to 999 999 999 --- without any function calls or data manipulation.

Does anybody know, what is GraphicsView doing in the background? Still updating the view?
I'm quite disappointed, because they say in Qt docs:[...]

BSP won't speed up the drawing, it only speeds up the selection of items that have to be drawn. If you have milions of items and only 1% of them is visible, GraphicsView will do its job, if you want to show all of them at once --- it won't help you.

With such large amount of items, you should rather paint on a pixmap and store that pximap in the memory instead of particular items. You can also use a second thread that will do the drawing (in such case you will need a QImage) and the GUI thread would only display the updated pixmaps.

[macbeth]

Thanks for your answer, Jacek.

Well, I counted myself that 200x200 rectangles cover approx 2500-times larger area than 4x4 rects. (Thank God it doesn't take 2500-times longer than drawing 250 000 4x4 rects, it would take more than 4 hours...)

And to count up to 1x10^10 takes around 1 minute on my machine, but that's not really the point. I was surprised, that although the rectangles were already drawn and visible on the widget, the cpu load remained high (which, of course, does not happen if I draw on a pixmap or image). I was wondering what is graphicsview doing all the time...

Well, the reason I wanted to draw on GraphicsScene/GraphicsView was, that it has vector representation of the scene and you can easily zoom, print to ps/pdf etc.
But the true (and point) is, that I have to rasterize the image somewhere along the process, so drawing on a pixmap is probably a better choice, after all.

I was just impressed by the R-project and it's fast plotting and wondering how to plot with comparable speed, but it is probably using some smart optimizations... (I know, I know, mr nobody saw something somewhere and wants the same magic in his lousy app)

Once again, thanks for your advice and explanation, Jacek...

[jacek]

Well, I counted myself that 200x200 rectangles cover approx 2500-times larger area than 4x4 rects. (Thank God it doesn't take 2500-times longer than drawing 250 000 4x4 rects, it would take more than 4 hours...)

Suppose that you want to draw those 200x200 rectangles on a 1280x1024 screen. Statistically every pixel would be coloured around 7600 times. Imagine how big speed up you would get just by removing the occluded rectangles.

I was surprised, that although the rectangles were already drawn and visible on the widget, the cpu load remained high (which, of course, does not happen if I draw on a pixmap or image). I was wondering what is graphicsview doing all the time...

Maybe it was redrawing the scene after adding every single rectangle?

I was just impressed by the R-project and it's fast plotting and wondering how to plot with comparable speed, but it is probably using some smart optimizations...

I don't have R at hand currently. Have you tried to make it draw those 250 000 rectangles?

[macbeth]

Suppose that you want to draw those 200x200 rectangles on a 1280x1024 screen. Statistically every pixel would be coloured around 7600 times. Imagine how big speed up you would get just by removing the occluded rectangles.

Well, that's true. Maybe counting the area that is covered by those rects and then drawing it using some drawing primitives would be faster, but that was not exactly what I was looking for, that example with 200x200 rects was just a try.
As I mentioned somewhere in first post, I wanted to draw barplot with, many rectangles, which overlap, but they are, of course, so thin, that they probably overlap each other only in 1 pixel area (and that means, that every pixel is redrawn 10 000's times probably). I'll try to draw it as lines or one looong path instead to see if it won't take less time. (Let me explain, that I want so much speed because I need my plot to resize with the widget, so the user experience (and my professor experience ) would not be very pleasant, if he had to wait 30secs on every resize)

Maybe it was redrawing the scene after adding every single rectangle?

Don't have any idea. The rects were added in less than 0.1 seconds to the scene, their rasterization took about 30secs, but I have no idea what is going on afterwards. Maybe the graphicsView is checking which rectangle is under mouse cursor and donig some pre-selecting (searchnig that BSP tree?) But that probsbly does not make sense, because the cpu load is that high even though the window is covered by other windows, so it has no reason to repaint itself...

I don't have R at hand currently. Have you tried to make it draw those 250 000 rectangles?

c<-seq(1:250000);
 
system.time(barplot(c));
[1] 0.772 0.120 1.928 0.000 0.000

c<-seq(1:250000);

system.time(barplot(c));
[1] 0.772 0.120 1.928 0.000 0.000

To copy to clipboard, switch view to plain text mode 

Which means user CPU, system CPU, elapsed time, and 2x time consumed by child processes... (I know it's not the same as 250 000 time 200x200, but still it is tremendously fast...)

[jacek]

Don't have any idea. The rects were added in less than 0.1 seconds to the scene, their rasterization took about 30secs, but I have no idea what is going on afterwards.

Could you prepare a minimal compilable example, so I can test it too?

[macbeth]

Of course, just slightly modified portedcanvas example -- try to add rectangle using Edit menu (or Alt + R), it should draw +-100 000 rects (some of them maybe cut out) quite fast, but afterwards the cpu load remains high (according to top or KDE task manager), on my machie around 90%...

here is an archive
just try to run qmake && make/gmake on it, it should be compiled & able to run...

and let me know how it works on your machine...

And thank you for the fruitful discussion

[jacek]

On my machine it uses around 30% when idle, but when I drag items over the rectangles CPU utilization jumps to 70%--80% (according to top). I've commented out three lines in main() and now it uses less than 1% when I don't touch the items. Finding which lines should be commented out I leave to you

[macbeth]

Well, I don't know what to say. I was searching for a timer in all other cpp files and did not find anything, supposing that main is just usual app.exec()... but as sherlock holmes said, if you foreclose all other possibilities, it must be the last one, even if it's almost improbable.

Sorry, sometimes I don't see what's in front of me...

And thanks, once more...