From 1d651e82459c0480cb3e803a9d9452092ac9d502 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B8rn=20Erik=20Nilsen?= Date: Thu, 2 Jul 2009 18:01:33 +0200 Subject: More re-factoring of QGraphicsSceneIndex. New method: QGraphicsSceneIndex::estimateTopLevelItems. QGraphicsSceneIndex::estimateItems returns *all* items within the rect, but we are only interested in the top-levels (those that are within the rect themselves or have descendants within the rect) when doing recursive drawing/item-lookup. All auto-tests pass. Demos/examples/manualtests run fine. --- src/gui/graphicsview/qgraphicsscene.cpp | 46 +++++--------- src/gui/graphicsview/qgraphicsscene_bsp.cpp | 8 ++- src/gui/graphicsview/qgraphicsscene_bsp_p.h | 4 +- src/gui/graphicsview/qgraphicsscene_p.h | 17 +---- .../graphicsview/qgraphicsscenebsptreeindex.cpp | 72 ++++++++++++++-------- .../graphicsview/qgraphicsscenebsptreeindex_p.h | 8 ++- src/gui/graphicsview/qgraphicssceneindex.cpp | 21 +++++-- src/gui/graphicsview/qgraphicssceneindex_p.h | 10 +-- src/gui/graphicsview/qgraphicsscenelinearindex.cpp | 5 +- src/gui/graphicsview/qgraphicsscenelinearindex_p.h | 3 +- 10 files changed, 98 insertions(+), 96 deletions(-) diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp index 3b1c8ad..85d05e9 100644 --- a/src/gui/graphicsview/qgraphicsscene.cpp +++ b/src/gui/graphicsview/qgraphicsscene.cpp @@ -1085,36 +1085,6 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item) return 0; } -QList QGraphicsScenePrivate::topLevelItemsInStackingOrder(const QTransform *const viewTransform, - const QRectF &sceneRect) -{ - if (indexMethod == QGraphicsScene::NoIndex || sceneRect.isNull()) { - ensureSortedTopLevelItems(); - return topLevelItems; - } - - const QList tmp = index->estimateItems(sceneRect, Qt::SortOrder(-1), - viewTransform ? *viewTransform : QTransform()); - // estimateItems returns a list of *all* items, but we are only interested - // in the top-levels (those that are within the rect themselves and those that - // have descendants within the rect). - // ### Look into how we can add this feature to the BSP. - QList tli; - for (int i = 0; i < tmp.size(); ++i) { - QGraphicsItem *topLevelItem = tmp.at(i)->topLevelItem(); - if (!topLevelItem->d_ptr->itemDiscovered) { - tli << topLevelItem; - topLevelItem->d_ptr->itemDiscovered = 1; - } - } - // Reset discovered bit. - for (int i = 0; i < tli.size(); ++i) - tli.at(i)->d_ptr->itemDiscovered = 0; - - qSort(tli.begin(), tli.end(), qt_notclosestLeaf); - return tli; -} - /*! \internal @@ -1759,7 +1729,7 @@ QList QGraphicsScene::collidingItems(const QGraphicsItem *item, // Does not support ItemIgnoresTransformations. QList tmp; - foreach (QGraphicsItem *itemInVicinity, d->index->estimateItems(item->sceneBoundingRect(), Qt::AscendingOrder, QTransform())) { + foreach (QGraphicsItem *itemInVicinity, d->index->estimateItems(item->sceneBoundingRect(), Qt::AscendingOrder)) { if (item != itemInVicinity && item->collidesWithItem(itemInVicinity, mode)) tmp << itemInVicinity; } @@ -4209,6 +4179,20 @@ void QGraphicsScenePrivate::drawItemHelper(QGraphicsItem *item, QPainter *painte } } +void QGraphicsScenePrivate::drawItems(QPainter *painter, const QTransform *const viewTransform, + QRegion *exposedRegion, QWidget *widget) +{ + QRectF exposedSceneRect; + if (exposedRegion && indexMethod != QGraphicsScene::NoIndex) { + exposedSceneRect = exposedRegion->boundingRect().adjusted(-1, -1, 1, 1); + if (viewTransform) + exposedSceneRect = viewTransform->inverted().mapRect(exposedSceneRect); + } + const QList tli = index->estimateTopLevelItems(exposedSceneRect, Qt::DescendingOrder); + for (int i = 0; i < tli.size(); ++i) + drawSubtreeRecursive(tli.at(i), painter, viewTransform, exposedRegion, widget); +} + void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter, const QTransform *const viewTransform, QRegion *exposedRegion, QWidget *widget, diff --git a/src/gui/graphicsview/qgraphicsscene_bsp.cpp b/src/gui/graphicsview/qgraphicsscene_bsp.cpp index 7d30749..fb4b9a4 100644 --- a/src/gui/graphicsview/qgraphicsscene_bsp.cpp +++ b/src/gui/graphicsview/qgraphicsscene_bsp.cpp @@ -70,12 +70,15 @@ class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor { public: QList *foundItems; + bool onlyTopLevelItems; void visit(QList *items) { for (int i = 0; i < items->size(); ++i) { QGraphicsItem *item = items->at(i); - if (!item->d_func()->itemDiscovered && item->isVisible()) { + if (onlyTopLevelItems && item->d_ptr->parent) + item = item->topLevelItem(); + if (!item->d_func()->itemDiscovered && item->d_ptr->visible) { item->d_func()->itemDiscovered = 1; foundItems->prepend(item); } @@ -143,10 +146,11 @@ void QGraphicsSceneBspTree::removeItems(const QSet &items) } } -QList QGraphicsSceneBspTree::items(const QRectF &rect) const +QList QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const { QList tmp; findVisitor->foundItems = &tmp; + findVisitor->onlyTopLevelItems = onlyTopLevelItems; climbTree(findVisitor, rect); // Reset discovery bits. for (int i = 0; i < tmp.size(); ++i) diff --git a/src/gui/graphicsview/qgraphicsscene_bsp_p.h b/src/gui/graphicsview/qgraphicsscene_bsp_p.h index 24b926c..4cac64a 100644 --- a/src/gui/graphicsview/qgraphicsscene_bsp_p.h +++ b/src/gui/graphicsview/qgraphicsscene_bsp_p.h @@ -92,7 +92,7 @@ public: void removeItem(QGraphicsItem *item, const QRectF &rect); void removeItems(const QSet &items); - QList items(const QRectF &rect) const; + QList items(const QRectF &rect, bool onlyTopLevelItems = false) const; int leafCount() const; inline int firstChildIndex(int index) const @@ -106,8 +106,6 @@ public: private: void initialize(const QRectF &rect, int depth, int index); void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index = 0) const; - - void findItems(QList *foundItems, const QRectF &rect, int index); QRectF rectForIndex(int index) const; QVector nodes; diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h index 23b0dd5..245380f 100644 --- a/src/gui/graphicsview/qgraphicsscene_p.h +++ b/src/gui/graphicsview/qgraphicsscene_p.h @@ -191,26 +191,13 @@ public: QGraphicsWidget *windowForItem(const QGraphicsItem *item) const; bool sortCacheEnabled; // for compatibility - QList topLevelItemsInStackingOrder(const QTransform *const, const QRectF&); void drawItemHelper(QGraphicsItem *item, QPainter *painter, const QStyleOptionGraphicsItem *option, QWidget *widget, bool painterStateProtection); - inline void drawItems(QPainter *painter, const QTransform *const viewTransform, - QRegion *exposedRegion, QWidget *widget) - { - QRectF exposedSceneRect; - if (exposedRegion && indexMethod != QGraphicsScene::NoIndex) { - exposedSceneRect = exposedRegion->boundingRect().adjusted(-1, -1, 1, 1); - if (viewTransform) - exposedSceneRect = viewTransform->inverted().mapRect(exposedSceneRect); - } - const QList tli = topLevelItemsInStackingOrder(viewTransform, exposedSceneRect); - for (int i = 0; i < tli.size(); ++i) - drawSubtreeRecursive(tli.at(i), painter, viewTransform, exposedRegion, widget); - return; - } + void drawItems(QPainter *painter, const QTransform *const viewTransform, + QRegion *exposedRegion, QWidget *widget); void drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter, const QTransform *const, QRegion *exposedRegion, QWidget *widget, qreal parentOpacity = qreal(1.0)); diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp index 0688cb1..a7b4828 100644 --- a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp @@ -372,6 +372,32 @@ void QGraphicsSceneBspTreeIndexPrivate::removeItem(QGraphicsItem *item, bool rec } } +QList QGraphicsSceneBspTreeIndexPrivate::estimateItems(const QRectF &rect, Qt::SortOrder order, + bool onlyTopLevelItems) +{ + Q_Q(QGraphicsSceneBspTreeIndex); + if (onlyTopLevelItems && rect.isNull()) + return q->QGraphicsSceneIndex::estimateTopLevelItems(rect, order); + + purgeRemovedItems(); + _q_updateSortCache(); + Q_ASSERT(unindexedItems.isEmpty()); + + QList rectItems = bsp.items(rect, onlyTopLevelItems); + if (onlyTopLevelItems) { + for (int i = 0; i < untransformableItems.size(); ++i) { + QGraphicsItem *item = untransformableItems.at(i); + if (!item->d_ptr->parent) + rectItems << item; + } + } else { + rectItems += untransformableItems; + } + + sortItems(&rectItems, order, sortCacheEnabled, onlyTopLevelItems); + return rectItems; +} + /*! Returns true if \a item1 is on top of \a item2. @@ -442,8 +468,19 @@ bool QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withoutCache(const QGrap \internal */ void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList *itemList, Qt::SortOrder order, - bool sortCacheEnabled) + bool sortCacheEnabled, bool onlyTopLevelItems) { + if (order == Qt::SortOrder(-1)) + return; + + if (onlyTopLevelItems) { + if (order == Qt::AscendingOrder) + qSort(itemList->begin(), itemList->end(), qt_closestLeaf); + else if (order == Qt::DescendingOrder) + qSort(itemList->begin(), itemList->end(), qt_notclosestLeaf); + return; + } + if (sortCacheEnabled) { if (order == Qt::AscendingOrder) { qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache); @@ -548,36 +585,17 @@ void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem * \a deviceTransform is the transformation apply to the view. */ -QList QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, - const QTransform &deviceTransform) const +QList QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order) const { Q_D(const QGraphicsSceneBspTreeIndex); - const_cast(d)->purgeRemovedItems(); - const_cast(d)->_q_updateSortCache(); - - // ### Handle items that ignore transformations - Q_UNUSED(deviceTransform); - - QList rectItems = d->bsp.items(rect); - - // Fill in with any unindexed items - for (int i = 0; i < d->unindexedItems.size(); ++i) { - if (QGraphicsItem *item = d->unindexedItems.at(i)) { - if (item->d_ptr->visible - && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { - QRectF boundingRect = item->sceneBoundingRect(); - if (QRectF_intersects(boundingRect, rect)) - rectItems << item; - } - } - } - - rectItems += d->untransformableItems; - d->sortItems(&rectItems, order, d->sortCacheEnabled); - - return rectItems; + return const_cast(d)->estimateItems(rect, order); } +QList QGraphicsSceneBspTreeIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const +{ + Q_D(const QGraphicsSceneBspTreeIndex); + return const_cast(d)->estimateItems(rect, order, /*onlyTopLevels=*/true); +} /*! \fn QList QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order = Qt::AscendingOrder) const; diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h index 437b17d..3ac922b 100644 --- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h @@ -82,8 +82,8 @@ public: QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0); ~QGraphicsSceneBspTreeIndex(); - QList estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const; - + QList estimateItems(const QRectF &rect, Qt::SortOrder order) const; + QList estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const; QList items(Qt::SortOrder order = Qt::AscendingOrder) const; int bspTreeDepth(); @@ -145,6 +145,7 @@ public: void invalidateSortCache(); void addItem(QGraphicsItem *item, bool recursive = false); void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false); + QList estimateItems(const QRectF &, Qt::SortOrder, bool b = false); static void climbTree(QGraphicsItem *item, int *stackingOrder); static bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2); @@ -159,7 +160,8 @@ public: return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder; } - static void sortItems(QList *itemList, Qt::SortOrder order, bool cached); + static void sortItems(QList *itemList, Qt::SortOrder order, + bool cached, bool onlyTopLevelItems = false); }; diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp index d6281e2..5626051 100644 --- a/src/gui/graphicsview/qgraphicssceneindex.cpp +++ b/src/gui/graphicsview/qgraphicssceneindex.cpp @@ -482,12 +482,25 @@ QList QGraphicsSceneIndex::items(const QPainterPath &path, Qt:: /*! This virtual function return an estimation of items at position \a point. This method return a list sorted using \a order. - \a deviceTransform is the transformation apply to the view. */ -QList QGraphicsSceneIndex::estimateItems(const QPointF &point, Qt::SortOrder order, - const QTransform &deviceTransform) const +QList QGraphicsSceneIndex::estimateItems(const QPointF &point, Qt::SortOrder order) const +{ + return estimateItems(QRectF(point, QSize(1, 1)), order); +} + +QList QGraphicsSceneIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const { - return estimateItems(QRectF(point, QSize(1,1)), order, deviceTransform); + Q_D(const QGraphicsSceneIndex); + Q_UNUSED(rect); + QGraphicsScenePrivate *scened = d->scene->d_func(); + scened->ensureSortedTopLevelItems(); + if (order == Qt::AscendingOrder) { + QList sorted; + for (int i = scened->topLevelItems.size() - 1; i >= 0; --i) + sorted << scened->topLevelItems.at(i); + return sorted; + } + return scened->topLevelItems; } /*! diff --git a/src/gui/graphicsview/qgraphicssceneindex_p.h b/src/gui/graphicsview/qgraphicssceneindex_p.h index aabfa79..6521765 100644 --- a/src/gui/graphicsview/qgraphicssceneindex_p.h +++ b/src/gui/graphicsview/qgraphicssceneindex_p.h @@ -97,10 +97,9 @@ public: Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; virtual QList items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; - virtual QList estimateItems(const QPointF &point, - Qt::SortOrder order, const QTransform &deviceTransform) const; - virtual QList estimateItems(const QRectF &rect, - Qt::SortOrder order, const QTransform &deviceTransform) const = 0; + virtual QList estimateItems(const QPointF &point, Qt::SortOrder order) const; + virtual QList estimateItems(const QRectF &rect, Qt::SortOrder order) const = 0; + virtual QList estimateTopLevelItems(const QRectF &, Qt::SortOrder order) const; protected Q_SLOTS: virtual void updateSceneRect(const QRectF &rect); @@ -154,7 +153,8 @@ inline void QGraphicsSceneIndexPrivate::items_helper(const QRectF &rect, QGraphi QList *items, const QTransform &viewTransform, Qt::ItemSelectionMode mode, Qt::SortOrder order) const { - const QList tli = scene->d_func()->topLevelItemsInStackingOrder(&viewTransform, rect); + Q_Q(const QGraphicsSceneIndex); + const QList tli = q->estimateTopLevelItems(rect, Qt::DescendingOrder); const QTransform identity; for (int i = 0; i < tli.size(); ++i) recursive_items_helper(tli.at(i), rect, intersector, items, identity, viewTransform, mode, order); diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex.cpp b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp index bc401f2..5e6ac30 100644 --- a/src/gui/graphicsview/qgraphicsscenelinearindex.cpp +++ b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp @@ -30,13 +30,10 @@ /*! - \fn virtual QList QGraphicsSceneLinearIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const; + \fn virtual QList QGraphicsSceneLinearIndex::estimateItems(const QRectF &rect, Qt::SortOrder order) const; Returns an estimation visible items that are either inside or intersect with the specified \a rect and return a list sorted using \a order. - - \a deviceTransform is the transformation apply to the view. - */ /*! diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h index 9463487..56dde3a 100644 --- a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h +++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h @@ -79,11 +79,10 @@ public: QList items(Qt::SortOrder order = Qt::AscendingOrder) const { Q_UNUSED(order); return m_items; } - virtual QList estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const + virtual QList estimateItems(const QRectF &rect, Qt::SortOrder order) const { Q_UNUSED(rect); Q_UNUSED(order); - Q_UNUSED(deviceTransform); return m_items; } -- cgit v0.12