GraphicsView performance problems

[camel]

I just wanted to post my last version of the to-be-optimized app.

Little changes I made, were for example:
* making sure that it actually paints correctly (also when the view gets to big, and we start to receive negative coordinates ;-)
* setting QGraphicsScene::NoIndex, with no obvious negative effects
* noticing that it is actually faster (on X11) to draw the pixmap by hand a few times than to use a brush :-/
* setting clipping to the exposed rect while painting the nodes

The top timespenders in the app are basically all related to QRegion, i.e. collision detection and repainting. These can only be optimized...well indirectly...


Anyways, if anybody would like to try out that version, here it is

#include <QtGui>
#include <cmath>
 
 
namespace {
    static inline int gridFloor(const qreal& value)
    {
        if (value < 0) {
            return -1 * static_cast<int>(std::ceil(qAbs(value)));
        } else {
            return static_cast<int>(std::floor(value));
        }
    }
 
    static inline int gridCeil(const qreal &value)
    {
        if (value < 0) {
            return -1 * static_cast<int>(std::floor(qAbs(value)));
        } else {
            return static_cast<int>(std::ceil(value));
        }
    }
 
    static inline int nextSmallerGrid(const int &value, const int &gridSize)
    {
        if (value < 0) {
            const int absValue = qAbs(value);
            return -1 * (absValue + gridSize - (absValue % gridSize));
        } else {
            return value - (value % gridSize);
        }
    }
}
 
class GridScene : public QGraphicsScene
{
   public:
      GridScene(qreal x, qreal y, qreal w, qreal h)
         : QGraphicsScene(x, y, w, h)
    {
        setItemIndexMethod(QGraphicsScene::NoIndex);
    }
 
   protected:
      void drawBackground(QPainter *painter, const QRectF &rect)
      {
          const int gridSize = 25;
 
          if (backgroundCache.isNull()) {
              backgroundCache = QPixmap(gridSize, gridSize);
              const int middle = gridSize / 2;
              {
                  QPainter backgroundPainter(&backgroundCache);
                  backgroundPainter.setRenderHints(painter->renderHints());
                  backgroundPainter.fillRect(QRect(0, 0, gridSize, gridSize), QBrush(Qt::white));
                  backgroundPainter.setPen(QPen(Qt::darkGreen,0));
                  backgroundPainter.setBrush(Qt::NoBrush);
                  backgroundPainter.drawLine(0, middle, gridSize, middle);
                  backgroundPainter.drawLine(middle, 0, middle, gridSize);
              }
          }
 
          const int realLeft = gridFloor(rect.left());
          const int realRight = gridCeil(rect.right());
          const int realTop = gridFloor(rect.top());
          const int realBottom = gridCeil(rect.bottom());
 
 
          const int firstLeftGridLine = nextSmallerGrid(realLeft, gridSize);
          const int firstTopGridLine = nextSmallerGrid(realTop, gridSize);
 
          QRectF cacheRect(0, 0, gridSize, gridSize);
          for (int x = firstLeftGridLine; x < realRight; x += gridSize) {
              for (int y = firstTopGridLine; y < realBottom; y += gridSize) {
                  painter->drawPixmap(QRectF(x, y, gridSize, gridSize),
                                      backgroundCache,
                                      cacheRect);
              }
          }
      }
 
   private:
      QPixmap backgroundCache;
};
 
namespace {
    static inline QPainterPath constructNodeShape(const QRectF& elipseRect)
    {
        QPainterPath path;
        path.addEllipse(elipseRect);
        return path;
    }
}
 
class Node : public QGraphicsItem
{
   public:
      Node(QGraphicsItem *par = 0, QGraphicsScene *sc = 0)
          : QGraphicsItem(par,sc),
            elipseRect(-4.0, -4.0, 8.0, 8.0),
            elipsePath(constructNodeShape(QRectF(-3.0, -3.0, 2.0*3.0, 2.0*3.0))),
            elipseShape(constructNodeShape(elipseRect)),
            nodePen(Qt::darkRed),
            nodeBrush(Qt::NoBrush)
      {
         setFlags(0);
         setAcceptedMouseButtons(0);
      }
 
      void paint(QPainter* p,const QStyleOptionGraphicsItem *o, QWidget *)
      {
         p->setPen(nodePen);
         p->setBrush(nodeBrush);
         p->setOpacity(1.0);
 
         p->setClipRect(o->exposedRect);
         p->drawPath(elipsePath);
      }
 
      QPainterPath shape() const
      {
         return elipseShape;
      }
 
      QRectF boundingRect() const
      {
         return elipseRect;
      }
 
    protected:
      const QRectF elipseRect;
      const QPainterPath elipsePath;
      const QPainterPath elipseShape;
      const QPen nodePen;
      const QBrush nodeBrush;
};
 
 
namespace {
    static inline QPainterPath constructResistorPath()
    {
        QPainterPath resistorPath;
        resistorPath.addRect(QRectF(-18.0, -9.0, 36.0, 18.0));
        resistorPath.moveTo(-27, 0);
        resistorPath.lineTo(-18, 0);
        resistorPath.moveTo(18, 0);
        resistorPath.lineTo(27, 0);
        return resistorPath;
    }
}
 
class Resistor : public QGraphicsItem
{
   public:
      Resistor(QGraphicsItem *par = 0, QGraphicsScene *scene = 0)
          : QGraphicsItem(par,scene),
            resistorPath(constructResistorPath()),
            boundingBox(resistorPath.boundingRect().adjusted(-1, -1, 1, 1)),
            resistorSelectedPen(Qt::darkBlue),
            resistorOpenPen(Qt::darkGray,1),
            resistorBrush(Qt::NoBrush)
      {
         setFlags(ItemIsMovable | ItemIsSelectable | ItemIsFocusable);
         // comment the following  4 lines to see the performance difference
         QGraphicsTextItem *t = new QGraphicsTextItem("R1 = 100k",this,scene);
         t->setPos(0,-35);
         Node * node = new Node(this,scene);
         node->setPos(QPointF(-30,0));
         node = new Node(this,scene);
         node->setPos(QPointF(30,0));
      }
 
      void paint(QPainter *p, const QStyleOptionGraphicsItem *o, QWidget *)
      {
         if(!(o->state & QStyle::State_Open))
            p->setPen(resistorOpenPen);
         if(o->state & QStyle::State_Selected)
            p->setPen(resistorSelectedPen);
 
         p->setClipRect( o->exposedRect );
         p->setBrush(resistorBrush);
         p->drawPath(resistorPath);
      }
 
      QRectF boundingRect() const
      {
        return boundingBox;
      }
 
   private:
      const QPainterPath resistorPath;
      const QRectF boundingBox;
      const QPen resistorSelectedPen;
      const QPen resistorOpenPen;
      const QBrush resistorBrush;
};
 
int main(int argc,char *argv[])
{
   QApplication app(argc,argv);
   GridScene scene(0,0,1024,768);
   for(int j = 2; j < 4; ++j)
      for(int i = 1; i <11; ++i)
      {
         Resistor *r = new Resistor(0,&scene);
         r->setPos(j*100, i * 50);
      }
   QGraphicsView *view = new QGraphicsView(&scene);
   view->setRenderHints(QPainter::Antialiasing | QPainter::SmoothPixmapTransform);
   view->setDragMode(QGraphicsView::RubberBandDrag);
   view->show();
   return app.exec();
}

#include <QtGui>
#include <cmath>


namespace {
    static inline int gridFloor(const qreal& value)
    {
        if (value < 0) {
            return -1 * static_cast<int>(std::ceil(qAbs(value)));
        } else {
            return static_cast<int>(std::floor(value));
        }
    }

    static inline int gridCeil(const qreal &value)
    {
        if (value < 0) {
            return -1 * static_cast<int>(std::floor(qAbs(value)));
        } else {
            return static_cast<int>(std::ceil(value));
        }
    }

    static inline int nextSmallerGrid(const int &value, const int &gridSize)
    {
        if (value < 0) {
            const int absValue = qAbs(value);
            return -1 * (absValue + gridSize - (absValue % gridSize));
        } else {
            return value - (value % gridSize);
        }
    }
}

class GridScene : public QGraphicsScene
{
   public:
      GridScene(qreal x, qreal y, qreal w, qreal h)
         : QGraphicsScene(x, y, w, h)
    {
        setItemIndexMethod(QGraphicsScene::NoIndex);
    }

   protected:
      void drawBackground(QPainter *painter, const QRectF &rect)
      {
          const int gridSize = 25;

          if (backgroundCache.isNull()) {
              backgroundCache = QPixmap(gridSize, gridSize);
              const int middle = gridSize / 2;
              {
                  QPainter backgroundPainter(&backgroundCache);
                  backgroundPainter.setRenderHints(painter->renderHints());
                  backgroundPainter.fillRect(QRect(0, 0, gridSize, gridSize), QBrush(Qt::white));
                  backgroundPainter.setPen(QPen(Qt::darkGreen,0));
                  backgroundPainter.setBrush(Qt::NoBrush);
                  backgroundPainter.drawLine(0, middle, gridSize, middle);
                  backgroundPainter.drawLine(middle, 0, middle, gridSize);
              }
          }

          const int realLeft = gridFloor(rect.left());
          const int realRight = gridCeil(rect.right());
          const int realTop = gridFloor(rect.top());
          const int realBottom = gridCeil(rect.bottom());


          const int firstLeftGridLine = nextSmallerGrid(realLeft, gridSize);
          const int firstTopGridLine = nextSmallerGrid(realTop, gridSize);

          QRectF cacheRect(0, 0, gridSize, gridSize);
          for (int x = firstLeftGridLine; x < realRight; x += gridSize) {
              for (int y = firstTopGridLine; y < realBottom; y += gridSize) {
                  painter->drawPixmap(QRectF(x, y, gridSize, gridSize),
                                      backgroundCache,
                                      cacheRect);
              }
          }
      }

   private:
      QPixmap backgroundCache;
};

namespace {
    static inline QPainterPath constructNodeShape(const QRectF& elipseRect)
    {
        QPainterPath path;
        path.addEllipse(elipseRect);
        return path;
    }
}

class Node : public QGraphicsItem
{
   public:
      Node(QGraphicsItem *par = 0, QGraphicsScene *sc = 0)
          : QGraphicsItem(par,sc),
            elipseRect(-4.0, -4.0, 8.0, 8.0),
            elipsePath(constructNodeShape(QRectF(-3.0, -3.0, 2.0*3.0, 2.0*3.0))),
            elipseShape(constructNodeShape(elipseRect)),
            nodePen(Qt::darkRed),
            nodeBrush(Qt::NoBrush)
      {
         setFlags(0);
         setAcceptedMouseButtons(0);
      }

      void paint(QPainter* p,const QStyleOptionGraphicsItem *o, QWidget *)
      {
         p->setPen(nodePen);
         p->setBrush(nodeBrush);
         p->setOpacity(1.0);

         p->setClipRect(o->exposedRect);
         p->drawPath(elipsePath);
      }

      QPainterPath shape() const
      {
         return elipseShape;
      }

      QRectF boundingRect() const
      {
         return elipseRect;
      }

    protected:
      const QRectF elipseRect;
      const QPainterPath elipsePath;
      const QPainterPath elipseShape;
      const QPen nodePen;
      const QBrush nodeBrush;
};


namespace {
    static inline QPainterPath constructResistorPath()
    {
        QPainterPath resistorPath;
        resistorPath.addRect(QRectF(-18.0, -9.0, 36.0, 18.0));
        resistorPath.moveTo(-27, 0);
        resistorPath.lineTo(-18, 0);
        resistorPath.moveTo(18, 0);
        resistorPath.lineTo(27, 0);
        return resistorPath;
    }
}

class Resistor : public QGraphicsItem
{
   public:
      Resistor(QGraphicsItem *par = 0, QGraphicsScene *scene = 0)
          : QGraphicsItem(par,scene),
            resistorPath(constructResistorPath()),
            boundingBox(resistorPath.boundingRect().adjusted(-1, -1, 1, 1)),
            resistorSelectedPen(Qt::darkBlue),
            resistorOpenPen(Qt::darkGray,1),
            resistorBrush(Qt::NoBrush)
      {
         setFlags(ItemIsMovable | ItemIsSelectable | ItemIsFocusable);
         // comment the following  4 lines to see the performance difference
         QGraphicsTextItem *t = new QGraphicsTextItem("R1 = 100k",this,scene);
         t->setPos(0,-35);
         Node * node = new Node(this,scene);
         node->setPos(QPointF(-30,0));
         node = new Node(this,scene);
         node->setPos(QPointF(30,0));
      }

      void paint(QPainter *p, const QStyleOptionGraphicsItem *o, QWidget *)
      {
         if(!(o->state & QStyle::State_Open))
            p->setPen(resistorOpenPen);
         if(o->state & QStyle::State_Selected)
            p->setPen(resistorSelectedPen);

         p->setClipRect( o->exposedRect );
         p->setBrush(resistorBrush);
         p->drawPath(resistorPath);
      }

      QRectF boundingRect() const
      {
        return boundingBox;
      }

   private:
      const QPainterPath resistorPath;
      const QRectF boundingBox;
      const QPen resistorSelectedPen;
      const QPen resistorOpenPen;
      const QBrush resistorBrush;
};

int main(int argc,char *argv[])
{
   QApplication app(argc,argv);
   GridScene scene(0,0,1024,768);
   for(int j = 2; j < 4; ++j)
      for(int i = 1; i <11; ++i)
      {
         Resistor *r = new Resistor(0,&scene);
         r->setPos(j*100, i * 50);
      }
   QGraphicsView *view = new QGraphicsView(&scene);
   view->setRenderHints(QPainter::Antialiasing | QPainter::SmoothPixmapTransform);
   view->setDragMode(QGraphicsView::RubberBandDrag);
   view->show();
   return app.exec();
}

To copy to clipboard, switch view to plain text mode 

Uiiii....that was fun... ;-)

[Gopala Krishna]

I just wanted to post my last version of the to-be-optimized app.

Little changes I made, were for example:
* making sure that it actually paints correctly (also when the view gets to big, and we start to receive negative coordinates ;-)
* setting QGraphicsScene::NoIndex, with no obvious negative effects
* noticing that it is actually faster (on X11) to draw the pixmap by hand a few times than to use a brush :-/
* setting clipping to the exposed rect while painting the nodes

The top timespenders in the app are basically all related to QRegion, i.e. collision detection and repainting. These can only be optimized...well indirectly...


Anyways, if anybody would like to try out that version, here it is

#include <QtGui>
#include <cmath>
 
....

#include <QtGui>
#include <cmath>

....

To copy to clipboard, switch view to plain text mode 

Uiiii....that was fun... ;-)

Thanks for the cleaner optimized version.

[Gopala Krishna]

Just to fine tune my understanding. Is the indexing helpful only if we use QGraphicsScene::items() in our code? Doesn't the framework use this internally (while detecting event receiving item)thereby reducing speed?

[wysota]

This won't be possible since I need node to be independent of component.

As far as I remember you had an additional item for displaying some text which you can easily get rid of. But I may be wrong, maybe it was someone else with such an architecture.

I'll post the proper one after recompilation today.

I meant that the compilation was not correct, not the method.

Could the last post in this thread mean an improvement of performance in Qt4.3 with indexing enabled.

Yes. Andreas describes the exact solution you should use.

Just to fine tune my understanding. Is the indexing helpful only if we use QGraphicsScene::items() in our code? Doesn't the framework use this internally (while detecting event receiving item)thereby reducing speed?

It is helpfull for answering a question "What parts of the canvas does a particular item occupy?" which is strongly related to "What items collide with point X?". So it is for example used to swiftly determine which item was clicked.

[Gopala Krishna]

I meant that the compilation was not correct, not the method.

Ah how fortunate I am. I didn't recompile Qt because of power failure. BTW, I tried to analyze more from kcachegrind itself. Unfortunately I can't post the generated file(even after bzip2 --best) due to size limit of attachments. The following are first few functions of QGraphicsView:: paintEvent()

[HTML] Ir Count Calee
--------------------------------------------------------------------------
14.97 2578 QPainter::setClipRect()
14.12 1289 QGraphicsScene::items(QRectF const&)
9.29 21 QGraphicsView::drawItems()
2.3 2578 QPainter::restore()
2.06 78,272 QRectF:: operator|
0.99 1289 QGraphicsView::drawBackground()[/HTML]


NOTE: indexing is disabled for this profile and grids drawn as camel did in his last code.
Also HTML instead of QUOTE tag is for clarity.

This means QRectF:: operator | is proving costly in this case!!

[Kuzemko]

I have idea. What changed when I createItemGroup with selected object then move this group by mouse, then destroyItemGroup (when finish moving). Can I increase performance?

[aamer4yu]

phew !!
what a thread ... nice to know so many things about improving performance...

Gopal, u made a small mistake, and i wonder why it wasnt caught...u were drawing out of the boundingrect !!
Problem was not with drawing backgound... ur items as slow as without drawing the background

just replace ur first code ... change ur boundingRect to

QRectF boundingRect() const
 
      {
 
         qreal pw = 0.5;
 
        QRectF rectf = QRectF(-36,-9,70,18);     // use this rectangle
        //QRectF rectf =  QRectF(-27,-9,54,18);
         return rectf.adjusted(-pw,-pw,pw,pw);
 
      }

QRectF boundingRect() const

      {

         qreal pw = 0.5;

        QRectF rectf = QRectF(-36,-9,70,18);     // use this rectangle
        //QRectF rectf =  QRectF(-27,-9,54,18);
         return rectf.adjusted(-pw,-pw,pw,pw);

      }

To copy to clipboard, switch view to plain text mode 

see the performance difference urself... !!!
have to go thru other posts... will see them when have time... and if I can improve more,,, will surely let u know

[camel]

Gopal, u made a small mistake, and i wonder why it wasnt caught...u were drawing out of the boundingrect !!

No actually he was not. The bounding rect you created was much too large. You only have to specify the bounding rect of the current item. You seem to want to include additionally the bounding rects of the child items.

see the performance difference urself... !!!

The reson for the perfomance advantage in this case can be seen in my analysis a few posts up.

[Gopala Krishna]

Has anyone tried the above codes with the snapshots(Qt4.3) ? If so did anybody notice performance difference ? This will surely improve my confidence since my project will mostly be released during that the release of Qt4.3

[Gopala Krishna]

Do you think its better to fake bounding rect for now (larger bounding rect for all components) to address performance issue ?

[wysota]

Do you think its better to fake bounding rect for now (larger bounding rect for all components) to address performance issue ?

Increasing the boundingRect will cause a performance drop when the number of items increases as more and more items will have to be redrawn when you do anything because of overlapping boundingRects.

[camel]

Depends on where your bottleneck is. (And that means profiling)

If it is drawing, as small a boundingrect as possible.
If it is the calculation of what has to be redrawn, bigger roundingrect is better.

But as a general rule: as small boundingrect as possible. This way you do not get in the way when optimization deeper in the framework make all your little workarounds obsolete ;-)


As 4.3, it "felt" faster to me (in valgrind). But I did not compare 1:1, and it might be that I even compared an optimized build to an debug built. Best test yourself ;-)

[wysota]

I have idea. What changed when I createItemGroup with selected object then move this group by mouse, then destroyItemGroup (when finish moving). Can I increase performance?

No, those will still be distinct items which might occupy different nodes in the BSP tree.

[camel]

Just to fine tune my understanding. Is the indexing helpful only if we use QGraphicsScene::items() in our code? Doesn't the framework use this internally (while detecting event receiving item)thereby reducing speed?

Yes the framework uses it internally, but it is a tradeoff (as so much in life ;-)

When you use the Index, the collision-detection may be sped up, but every position/size change of every item will cost you.
If you do not use the index, finding an item at a certain location will probably be linear to the number of items in the scene, but you can move/change very cheaply.

If you have many moving things but not so many overall, turning of the index may be a good idea.
If you have many mostly stationary items, the index is very nice indeed.

In the end it depends on experimentation (or very carefull analysis ;-) to find the optimal solution for you.


Since you were keen on moving many items at the same time, it is disabled here. ;-)

I think one could think about it like this (for n: all items, x:moving items)
Looking up items in the index costs log(n)but returns a filtered selection of items z with n >= z >= x
When you have a repaint, you need to find the repainted items, check if they are really included in the repainted area and then repaint them (which we ignore since it does not change with the use of the index ;-), which will cost about O(log(n) + z). Since you are moving you also need to update the index which cost O(log(n)) which means updating for all items costs O(log(n) * x). If we say that painting and updating is done in lockstep, each this step will cost O(x*log(n) + z). (let us hope that the index is sufficiently well thought out so that z is always very near to x and just say the cost is O(x*log(n)))

If you do not use the index, you have to check each item if it is included, then repaint , ie it will cost O(n). When we are moving we do not need to update anything, thus the total cost will be somewhere around O(n)

Now we have the choice O(n) or O(x*log(n)) which is better?
Depends on your purposes, if you have the need to move/change nearly as many items as there are in the scene, the non index version with O(n) is better than the index version with O(n*log(n)).
If the number of changing/moving items is much smaller than the total items, ie n >> x, the index version is clearly better O(log(n) * small number) vs. O(n)



So that concludes my lecture on the run time behavior of the graphics scene. Next week: Mating Rituals of the Norwegian Widget.

[By the way, since half of the time I do not know what I talk about take everything here with a grain of salt ;-) ]

EDIT:
Actually there is another factor in there: The checks for the repaints is done per "dirty" area d, which should (for moving items) be d < 2*x. Why ? The dirty areas may be combined if they are overlapping but you have always one for where the object was, and one for where the object is.

So in the end it would realy be:
O(log(n) * x * d) vs. O(n * d)
This explains for example why it was faster for you when you increased the bounding rect of the resistors. By increasing the bounding rect you created overlapping regions and thus less work had to be done.
Worst case: O(log(n) * n) when overlapping vs. O(log(n) * n^2) when not.

EDIT 2:
As Andreas explains in the post you mentioned, the index will be changed in 4.3 so this analysis is not valid for Qt > 4.2

[Gopala Krishna]

Yes the framework uses it internally, but it is a tradeoff (as so much in life ;-)

When you use the Index, the collision-detection may be sped up, but every position/size change of every item will cost you.
If you do not use the index, finding an item at a certain location will probably be linear to the number of items in the scene, but you can move/change very cheaply.
....
..

Thanks a lot camel! I am really grateful to you for explaining these details. They are really worth a lot for me
But one thing regarding my app, you cant say whether you will use many items, move them all together since that is all dependent on user. So I'd be happy if the performance is better for moving around 10-15 components at a time on medium end computers. Also I feel that maximum components generally used will be around 30.
But since I need to provide proper feedback while drawing wires, I optimized there to use QRubberBand's while the wires are being resized or drawn, which was rather huge performance improvement.

Just one more question here. Suppose I want to show feedback of possible connections while moving components (say the nodes of component overlap with the node of other component) by drawing those nodes with different color or some other way, I may need good and fast collision detection - which means I might need indexing. Rather than compromising for trade off of using this, if I decide to show feedback only if mouse rests for a few milliseconds by using timers, will I need indexing ?

[camel]

Thanks a lot camel! I am really grateful to you for explaining these details. They are really worth a lot for me

You are welcome. Actually it is a good and fun way for me to avoid that what I should be doing in the moment ;-)

Just one more question here. Suppose I want to show feedback of possible connections while moving components (say the nodes of component overlap with the node of other component) by drawing those nodes with different color or some other way, I may need good and fast collision detection - which means I might need indexing.

Best thing: Benchmark ;-)
Check if the lookup is reasonable fast on 4.2 without the index, and check if the moving is reasonable fast on 4.3 (try the snapshots)
then use

#if QT_VERSION <= 0x040300
     setItemIndexMethod(QGraphicsScene::NoIndex);
#endif

#if QT_VERSION <= 0x040300
     setItemIndexMethod(QGraphicsScene::NoIndex);
#endif

To copy to clipboard, switch view to plain text mode 

to only switch of the index for 4.2

Rather than compromising for trade off of using this, if I decide to show feedback only if mouse rests for a few milliseconds by using timers, will I need indexing ?

It is probably a smart thing to do. Restarting a timer and storing the last location to a variable is probably faster than to do a collision detection on every mouse move. If you keep the interval short enough people will probably not even notice ;-)
Even then indexing is helpfull as it would speed it up, but you will not take as much as an performance hit without it as you would if you just went ahead and did collision detection all the time.


Again, probably best advice: "See What Works"(tm)
And: Keep KCacheGrind handy ;-)