Cache QGrahicsItem's scene transform.

Invalidating the scene transform is just a matter of setting a bit on
the item. Then, when we ask for the item's scene transform, we
traverse its ancestors recursively and find the top-most dirty item.
The algorithm then backtracks to that item and start calculating the scene
transform for the item itself and all its children in the call stack.
If the item itself and all its ancestors are "clean", nothing is
calculated, only traversed.

We use this approach when processing dirty items / drawing items
as well. That way we ensure the scene transform is only calculated
once when absolutely needed.

G'night :)

5 files changed, 109 insertions, 39 deletions

diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index b913d89..57ca2ef 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -952,6 +952,7 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent, bool de
 
     // Resolve depth.
     resolveDepth(parent ? parent->d_ptr->depth : -1);
+    dirtySceneTransform = 1;
 
     // Deliver post-change notification
     q->itemChange(QGraphicsItem::ItemParentHasChanged, newParentVariant);
@@ -2540,6 +2541,7 @@ void QGraphicsItemPrivate::setPosHelper(const QPointF &pos)
     if (scene)
         q->prepareGeometryChange();
     this->pos = newPos;
+    dirtySceneTransform = 1;
 
     // Send post-notification.
 #ifndef QGRAPHICSITEM_NO_ITEMCHANGE
@@ -2682,12 +2684,17 @@ QMatrix QGraphicsItem::sceneMatrix() const
 */
 QTransform QGraphicsItem::sceneTransform() const
 {
-    QTransform m;
-    const QGraphicsItem *p = this;
-    do {
-        p->d_ptr->combineTransformToParent(&m);
-    } while ((p = p->d_ptr->parent));
-    return m;
+    if (d_ptr->dirtySceneTransform) {
+        // This item and all its descendants have dirty scene transforms.
+        // We're about to validate this item's scene transform, so we have to
+        // invalidate all the children; otherwise there's no way for the descendants
+        // to detect that the ancestor has changed.
+        d_ptr->invalidateChildrenSceneTransform();
+    }
+
+    QGraphicsItem *that = const_cast<QGraphicsItem *>(this);
+    d_ptr->ensureSceneTransformRecursive(&that);
+    return d_ptr->sceneTransform;
 }
 
 /*!
@@ -2899,6 +2906,7 @@ void QGraphicsItem::setMatrix(const QMatrix &matrix, bool combine)
     // Update and set the new transformation.
     prepareGeometryChange();
     *d_ptr->transform = newTransform;
+    d_ptr->dirtySceneTransform = 1;
 
     // Send post-notification.
 #ifndef QGRAPHICSITEM_NO_ITEMCHANGE
@@ -2945,6 +2953,7 @@ void QGraphicsItem::setTransform(const QTransform &matrix, bool combine)
     // Update and set the new transformation.
     prepareGeometryChange();
     *d_ptr->transform = newTransform;
+    d_ptr->dirtySceneTransform = 1;
 
     // Send post-notification.
     itemChange(ItemTransformHasChanged, newTransformVariant);
@@ -3966,6 +3975,35 @@ void QGraphicsItemPrivate::updateCachedClipPathFromSetPosHelper(const QPointF &n
     }
 }
 
+// Traverses all the ancestors up to the top-level and updates the pointer to
+// always point to the top-most item that has a dirty scene transform.
+// It then backtracks to the top-most dirty item and start calculating the
+// scene transform by combining the item's transform (+pos) with the parent's
+// cached scene transform (which we at this point know for sure is valid).
+void QGraphicsItemPrivate::ensureSceneTransformRecursive(QGraphicsItem **topMostDirtyItem)
+{
+    Q_ASSERT(topMostDirtyItem);
+
+    if (dirtySceneTransform)
+        *topMostDirtyItem = q_ptr;
+
+    if (parent)
+        parent->d_ptr->ensureSceneTransformRecursive(topMostDirtyItem);
+
+    if (*topMostDirtyItem == q_ptr) {
+        if (!dirtySceneTransform)
+            return; // OK, neither my ancestors nor I have dirty scene transforms.
+        *topMostDirtyItem = 0;
+    } else if (*topMostDirtyItem) {
+        return; // Continue backtrack.
+    }
+
+    // COMBINE my transform with the parent's scene transform.
+    sceneTransform = parent ? parent->d_ptr->sceneTransform : QTransform();
+    combineTransformFromParent(&sceneTransform);
+    dirtySceneTransform = 0;
+}
+
 /*!
     \internal
 
diff --git a/src/gui/graphicsview/qgraphicsitem_p.h b/src/gui/graphicsview/qgraphicsitem_p.h
index 0e0a121..f9d63fb 100644
--- a/src/gui/graphicsview/qgraphicsitem_p.h
+++ b/src/gui/graphicsview/qgraphicsitem_p.h
@@ -146,7 +146,7 @@ public:
         flags(0),
         dirtyChildrenBoundingRect(1),
         paintedViewBoundingRectsNeedRepaint(0),
-        hasValidSceneTransform(0),
+        dirtySceneTransform(1),
         globalStackingOrder(-1),
         q_ptr(0)
     {
@@ -275,6 +275,13 @@ public:
 
     void invalidateCachedClipPathRecursively(bool childrenOnly = false, const QRectF &emptyIfOutsideThisRect = QRectF());
     void updateCachedClipPathFromSetPosHelper(const QPointF &newPos);
+    void ensureSceneTransformRecursive(QGraphicsItem **topMostDirtyItem);
+
+    inline void invalidateChildrenSceneTransform()
+    {
+        for (int i = 0; i < children.size(); ++i)
+            children.at(i)->d_ptr->dirtySceneTransform = 1;
+    }
 
     inline qreal calcEffectiveOpacity() const
     {
@@ -388,7 +395,7 @@ public:
     quint32 flags : 11;
     quint32 dirtyChildrenBoundingRect : 1;
     quint32 paintedViewBoundingRectsNeedRepaint : 1;
-    quint32 hasValidSceneTransform  : 1;
+    quint32 dirtySceneTransform  : 1;
     quint32 padding : 18; // feel free to use
 
     // Optional stacking order
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 34c7dc1..2773bdd 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -680,7 +680,7 @@ void QGraphicsScenePrivate::_q_processDirtyItems()
     if (updateAll)
         return;
 
-    processDirtyItemsRecursive(0, QTransform());
+    processDirtyItemsRecursive(0);
     for (int i = 0; i < views.size(); ++i)
         views.at(i)->d_func()->processPendingUpdates();
 }
@@ -5083,7 +5083,7 @@ void QGraphicsScenePrivate::drawItemHelper(QGraphicsItem *item, QPainter *painte
     }
 }
 
-void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter, const QTransform &parentTransform,
+void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter,
                                                  const QTransform &viewTransform,
                                                  QRegion *exposedRegion, QWidget *widget,
                                                  QGraphicsView::OptimizationFlags optimizationFlags,
@@ -5110,10 +5110,24 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     }
 
     // Calculate the full transform for this item.
-    QTransform transform = parentTransform;
+    QTransform transform;
     QRect viewBoundingRect;
+    bool wasDirtyParentSceneTransform = false;
     if (item) {
-        item->d_ptr->combineTransformFromParent(&transform, &viewTransform);
+        if (item->d_ptr->itemIsUntransformable()) {
+            transform = item->deviceTransform(viewTransform);
+        } else {
+            if (item->d_ptr->dirtySceneTransform) {
+                item->d_ptr->sceneTransform = item->d_ptr->parent ? item->d_ptr->parent->d_ptr->sceneTransform
+                                                                  : transform;
+                item->d_ptr->combineTransformFromParent(&item->d_ptr->sceneTransform);
+                item->d_ptr->dirtySceneTransform = 0;
+                wasDirtyParentSceneTransform = true;
+            }
+            transform = item->d_ptr->sceneTransform;
+            transform *= viewTransform;
+        }
+
         QRectF brect = item->boundingRect();
         if (!brect.size().isNull()) {
             // ### This does not take the clip into account.
@@ -5156,11 +5170,12 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     if (!dontDrawChildren) {
         for (i = 0; i < children.size(); ++i) {
             QGraphicsItem *child = children.at(i);
+            if (wasDirtyParentSceneTransform)
+                child->d_ptr->dirtySceneTransform = 1;
             if (!(child->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent))
                 break;
-            drawSubtreeRecursive(child, painter, transform, viewTransform,
-                                 exposedRegion, widget, optimizationFlags,
-                                 0, opacity);
+            drawSubtreeRecursive(child, painter, viewTransform, exposedRegion, widget,
+                                 optimizationFlags, 0, opacity);
         }
     }
 
@@ -5186,9 +5201,14 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     // Draw children in front
     if (!dontDrawChildren) {
         for (; i < children.size(); ++i) {
-            drawSubtreeRecursive(children.at(i), painter, transform, viewTransform,
-                                 exposedRegion, widget, optimizationFlags, 0, opacity);
+            QGraphicsItem *child = children.at(i);
+            if (wasDirtyParentSceneTransform)
+                child->d_ptr->dirtySceneTransform = 1;
+            drawSubtreeRecursive(child, painter, viewTransform, exposedRegion,
+                                 widget, optimizationFlags, 0, opacity);
         }
+    } else if (wasDirtyParentSceneTransform) {
+        item->d_ptr->invalidateChildrenSceneTransform();
     }
 
     // Restore child clip
@@ -5236,17 +5256,19 @@ void QGraphicsScenePrivate::markDirty(QGraphicsItem *item, const QRectF &rect, b
     }
 }
 
-void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, const QTransform &parentTransform)
+void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item)
 {
     Q_ASSERT(!item || item->d_ptr->dirty || item->d_ptr->dirtyChildren);
     Q_Q(QGraphicsScene);
 
     // Calculate the full scene transform for this item.
-    QTransform transform = parentTransform;
-    if (item && !item->d_ptr->itemIsUntransformable()) {
-        item->d_ptr->combineTransformFromParent(&transform);
-        item->d_ptr->sceneTransform = transform;
-        item->d_ptr->hasValidSceneTransform = 1;
+    bool wasDirtyParentSceneTransform = false;
+    if (item && item->d_ptr->dirtySceneTransform && !item->d_ptr->itemIsUntransformable()) {
+        item->d_ptr->sceneTransform = item->d_ptr->parent ? item->d_ptr->parent->d_ptr->sceneTransform
+                                                          : QTransform();
+        item->d_ptr->combineTransformFromParent(&item->d_ptr->sceneTransform);
+        item->d_ptr->dirtySceneTransform = 0;
+        wasDirtyParentSceneTransform = true;
     }
 
     // Process item.
@@ -5261,6 +5283,7 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, cons
         } else {
             QRectF dirtyRect;
             bool uninitializedDirtyRect = true;
+            const bool untransformableItem = item->d_ptr->itemIsUntransformable();
 
             for (int j = 0; j < views.size(); ++j) {
                 QGraphicsView *view = views.at(j);
@@ -5290,15 +5313,15 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, cons
                 if (item->d_ptr->paintedViewBoundingRectsNeedRepaint)
                     viewPrivate->updateRect(item->d_ptr->paintedViewBoundingRects.value(viewPrivate->viewport));
 
-                if (item->d_ptr->hasBoundingRegionGranularity) {
-                    const QRegion dirtyViewRegion = item->deviceTransform(view->viewportTransform())
-                                                    .map(QRegion(dirtyRect.toRect()));
-                    viewPrivate->updateRegion(dirtyViewRegion);
-                } else {
-                    const QRect dirtyViewRect = item->deviceTransform(view->viewportTransform())
-                                                .mapRect(dirtyRect).toRect();
-                    viewPrivate->updateRect(dirtyViewRect);
-                }
+                QTransform deviceTransform = item->d_ptr->sceneTransform;
+                if (!untransformableItem)
+                    deviceTransform *= view->viewportTransform();
+                else
+                    deviceTransform = item->deviceTransform(view->viewportTransform());
+                if (item->d_ptr->hasBoundingRegionGranularity)
+                    viewPrivate->updateRegion(deviceTransform.map(QRegion(dirtyRect.toRect())));
+                else
+                    viewPrivate->updateRect(deviceTransform.mapRect(dirtyRect).toRect());
             }
         }
     }
@@ -5309,14 +5332,18 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, cons
         const bool allChildrenDirty = item && item->d_ptr->allChildrenDirty;
         for (int i = 0; i < children->size(); ++i) {
             QGraphicsItem *child = children->at(i);
+            if (wasDirtyParentSceneTransform)
+                child->d_ptr->dirtySceneTransform = 1;
             if (allChildrenDirty) {
                 child->d_ptr->dirty = 1;
             } else if (!child->d_ptr->dirty && !child->d_ptr->dirtyChildren) {
                 resetDirtyItem(child);
                 continue;
             }
-            processDirtyItemsRecursive(child, transform);
+            processDirtyItemsRecursive(child);
         }
+    } else if (wasDirtyParentSceneTransform) {
+        item->d_ptr->invalidateChildrenSceneTransform();
     }
 
     if (item)
@@ -5373,8 +5400,7 @@ void QGraphicsScene::drawItems(QPainter *painter,
         if (!item->d_ptr->itemDiscovered) {
             topLevelItems << item;
             item->d_ptr->itemDiscovered = 1;
-            d->drawSubtreeRecursive(item, painter, viewTransform, viewTransform,
-                                    expose, widget, flags);
+            d->drawSubtreeRecursive(item, painter, viewTransform, expose, widget, flags);
         }
     }
 
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index 6b4476c..e0c48a6 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -258,13 +258,12 @@ public:
                         const QStyleOptionGraphicsItem *option, QWidget *widget,
                         bool painterStateProtection);
     
-    void drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter, const QTransform &parentTransform,
-                              const QTransform &viewTransform,
+    void drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter, const QTransform &viewTransform,
                               QRegion *exposedRegion, QWidget *widget, QGraphicsView::OptimizationFlags optimizationFlags,
                               QList<QGraphicsItem *> *topLevelItems = 0, qreal parentOpacity = qreal(1.0));
     void markDirty(QGraphicsItem *item, const QRectF &rect = QRectF(), bool invalidateChildren = false,
                    bool maybeDirtyClipPath = false, bool force = false, bool ignoreOpacity = false);
-    void processDirtyItemsRecursive(QGraphicsItem *item, const QTransform &);
+    void processDirtyItemsRecursive(QGraphicsItem *item);
 
     inline void resetDirtyItem(QGraphicsItem *item)
     {
diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp
index caa3ffc..e9a432e 100644
--- a/src/gui/graphicsview/qgraphicsview.cpp
+++ b/src/gui/graphicsview/qgraphicsview.cpp
@@ -3301,7 +3301,7 @@ void QGraphicsView::paintEvent(QPaintEvent *event)
 
     // Items
     if (!(d->optimizationFlags & IndirectPainting)) {
-        d->scene->d_func()->drawSubtreeRecursive(0, &painter, viewTransform, viewTransform, &d->exposedRegion,
+        d->scene->d_func()->drawSubtreeRecursive(0, &painter, viewTransform, &d->exposedRegion,
                                                  viewport(), d->optimizationFlags, 0);
     } else {
         // Find all exposed items