From 226baa99f53eeeff2489148c9187c19f5bc86f0e Mon Sep 17 00:00:00 2001 From: Alexis Menard Date: Tue, 7 Apr 2009 20:42:53 +0200 Subject: Remove the indexing (BSP) logic from the scene We basically add a new index that implement the old BSP logic but in a separate class instead of living into the QGraphicsScene. It will be much more easier to add a new index method or for people to use their own Conflicts: src/gui/graphicsview/qgraphicsitem.cpp src/gui/graphicsview/qgraphicssceneindex.h --- src/gui/graphicsview/graphicsview.pri | 4 +- src/gui/graphicsview/qgraphicsitem.cpp | 10 +- src/gui/graphicsview/qgraphicsitem.h | 1 + src/gui/graphicsview/qgraphicsscene.cpp | 390 ++---------------- src/gui/graphicsview/qgraphicsscene.h | 2 +- src/gui/graphicsview/qgraphicsscene_bsp.cpp | 40 +- src/gui/graphicsview/qgraphicsscene_bsp_p.h | 27 +- src/gui/graphicsview/qgraphicsscene_linear_p.h | 124 ------ src/gui/graphicsview/qgraphicsscene_p.h | 20 +- .../graphicsview/qgraphicsscenebsptreeindex_p.cpp | 437 +++++++++++++++++++++ .../graphicsview/qgraphicsscenebsptreeindex_p.h | 118 ++++++ src/gui/graphicsview/qgraphicssceneindex.cpp | 14 +- src/gui/graphicsview/qgraphicssceneindex.h | 15 +- src/gui/graphicsview/qgraphicsscenelinearindex_p.h | 126 ++++++ .../tst_qgraphicssceneindex.cpp | 15 +- 15 files changed, 769 insertions(+), 574 deletions(-) delete mode 100644 src/gui/graphicsview/qgraphicsscene_linear_p.h create mode 100644 src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp create mode 100644 src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h create mode 100644 src/gui/graphicsview/qgraphicsscenelinearindex_p.h diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri index bc4d9dd..9097497 100644 --- a/src/gui/graphicsview/graphicsview.pri +++ b/src/gui/graphicsview/graphicsview.pri @@ -6,8 +6,9 @@ HEADERS += \ graphicsview/qgraphicsitemanimation.h \ graphicsview/qgraphicsscene.h \ graphicsview/qgraphicsscene_p.h \ + graphicsview/qgraphicsscenebsptreeindex_p.h \ graphicsview/qgraphicsscene_bsp_p.h \ - graphicsview/qgraphicsscene_linear_p.h \ + graphicsview/qgraphicsscenelinearindex_p.h \ graphicsview/qgraphicssceneindex.h \ graphicsview/qgraphicssceneevent.h \ graphicsview/qgraphicsview_p.h \ @@ -18,6 +19,7 @@ SOURCES += \ graphicsview/qgraphicsitemanimation.cpp \ graphicsview/qgraphicsscene.cpp \ graphicsview/qgraphicsscene_bsp.cpp \ + graphicsview/qgraphicsscenebsptreeindex_p.cpp \ graphicsview/qgraphicssceneindex.cpp \ graphicsview/qgraphicssceneevent.cpp \ graphicsview/qgraphicsview.cpp diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp index b8ff5b4..4574334 100644 --- a/src/gui/graphicsview/qgraphicsitem.cpp +++ b/src/gui/graphicsview/qgraphicsitem.cpp @@ -5789,7 +5789,7 @@ void QGraphicsItem::addToIndex() return; } if (d_ptr->scene) - d_ptr->scene->d_func()->addToIndex(this); + d_ptr->scene->d_func()->index->insertItem(this); d_ptr->updateHelper(); } @@ -5802,13 +5802,9 @@ void QGraphicsItem::addToIndex() */ void QGraphicsItem::removeFromIndex() { - if (d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) { - // ### remove from child index only if applicable - return; - } d_ptr->updateHelper(); if (d_ptr->scene) - d_ptr->scene->d_func()->removeFromIndex(this); + d_ptr->scene->d_func()->index->removeItem(this,false); } /*! @@ -5831,7 +5827,7 @@ void QGraphicsItem::prepareGeometryChange() d_ptr->updateHelper(QRectF(), false, /*maybeDirtyClipPath=*/!d_ptr->inSetPosHelper); QGraphicsScenePrivate *scenePrivate = d_ptr->scene->d_func(); - scenePrivate->removeFromIndex(this); + scenePrivate->index->updateItem(this); if (d_ptr->inSetPosHelper) return; diff --git a/src/gui/graphicsview/qgraphicsitem.h b/src/gui/graphicsview/qgraphicsitem.h index b98882d..1b41232 100644 --- a/src/gui/graphicsview/qgraphicsitem.h +++ b/src/gui/graphicsview/qgraphicsitem.h @@ -398,6 +398,7 @@ private: friend class QGraphicsWidget; friend class QGraphicsWidgetPrivate; friend class QGraphicsProxyWidgetPrivate; + friend class QGraphicsSceneBspTreeIndex; friend class ::tst_QGraphicsItem; friend bool qt_closestLeaf(const QGraphicsItem *, const QGraphicsItem *); friend bool qt_closestItemFirst(const QGraphicsItem *, const QGraphicsItem *); diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp index b559835..8140f79 100644 --- a/src/gui/graphicsview/qgraphicsscene.cpp +++ b/src/gui/graphicsview/qgraphicsscene.cpp @@ -39,8 +39,6 @@ ** ****************************************************************************/ -static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; - /*! \class QGraphicsScene \brief The QGraphicsScene class provides a surface for managing a large @@ -329,18 +327,14 @@ static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraph QGraphicsScenePrivate::QGraphicsScenePrivate() : changedSignalMask(0), indexMethod(QGraphicsScene::BspTreeIndex), + bspTreeDepth(0), lastItemCount(0), - index(new QGraphicsSceneBspTree()), - linearIndex(new QGraphicsSceneLinearIndex()), + index(0), hasSceneRect(false), updateAll(false), calledEmitUpdated(false), selectionChanging(0), dirtyItemResetPending(false), - regenerateIndex(true), - purgePending(false), - indexTimerId(0), - restartIndexTimer(false), stickyFocus(false), hasFocus(false), focusItem(0), @@ -369,8 +363,7 @@ void QGraphicsScenePrivate::init() { Q_Q(QGraphicsScene); - index->setParent(q); - linearIndex->setParent(q); + index = new QGraphicsSceneBspTreeIndex(q); // Keep this index so we can check for connected slots later on. changedSignalMask = (1 << q->metaObject()->indexOfSignal("changed(QList)")); @@ -383,220 +376,14 @@ void QGraphicsScenePrivate::init() */ QList QGraphicsScenePrivate::estimateItemsInRect(const QRectF &rect) const { - const_cast(this)->purgeRemovedItems(); const_cast(this)->_q_updateSortCache(); - if (indexMethod != QGraphicsScene::NoIndex) { - // ### Only do this once in a while. - QGraphicsScenePrivate *that = const_cast(this); - - QList items; - // Get items from index - items = that->index->items(rect); - - //### Why there are items indexed and not at some point? - - // Fill in with any unindexed items - foreach (QGraphicsItem *item, linearIndex->items(rect)) { - if (!item->d_ptr->itemDiscovered && item->d_ptr->visible && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { - item->d_ptr->itemDiscovered = 1; - items << item; - } - } - - // Reset the discovered state of all discovered items - for (int i = 0; i < items.size(); ++i) - items.at(i)->d_func()->itemDiscovered = 0; - return items; - } - - QList itemsInRect; - foreach (QGraphicsItem *item, linearIndex->items(rect)) { - if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) - continue; - if (item->d_ptr->visible && item->effectiveOpacity() > qreal(0.0)) - itemsInRect << item; - } + // ### Only do this once in a while. + QGraphicsScenePrivate *that = const_cast(this); - //### Why there are items indexed and not at some point? - - for (int i = 0; i < indexedItems.size(); ++i) { - if (QGraphicsItem *item = indexedItems.at(i)) { - if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) - continue; - if (item->d_ptr->visible && item->effectiveOpacity() > qreal(0.0)) - itemsInRect << item; - } - } + // Get items from index + return that->index->items(rect); - return itemsInRect; -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::addToIndex(QGraphicsItem *item) -{ - if (indexMethod == QGraphicsScene::BspTreeIndex) { - if (item->d_func()->index != -1) { - index->insertItem(item); - foreach (QGraphicsItem *child, item->children()) - child->addToIndex(); - } else { - // The BSP tree is regenerated if the number of items grows to a - // certain threshold, or if the bounding rect of the graph doubles in - // size. - startIndexTimer(); - } - } else if (indexMethod == QGraphicsScene::CustomIndex) { - if (item->d_func()->index != -1) { - index->insertItem(item); - foreach (QGraphicsItem *child, item->children()) - child->addToIndex(); - } - } -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::removeFromIndex(QGraphicsItem *item) -{ - if (indexMethod != QGraphicsScene::NoIndex) { - int index = item->d_func()->index; - if (index != -1) { - this->index->removeItem(item); - freeItemIndexes << index; - indexedItems[index] = 0; - item->d_func()->index = -1; - linearIndex->insertItem(item); - - foreach (QGraphicsItem *child, item->children()) - child->removeFromIndex(); - } - startIndexTimer(); - } -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::resetIndex() -{ - purgeRemovedItems(); - if (indexMethod != QGraphicsScene::NoIndex) { - for (int i = 0; i < indexedItems.size(); ++i) { - if (QGraphicsItem *item = indexedItems.at(i)) { - item->d_ptr->index = -1; - linearIndex->insertItem(item); - } - } - indexedItems.clear(); - freeItemIndexes.clear(); - regenerateIndex = true; - startIndexTimer(); - } -} - -static inline int intmaxlog(int n) -{ - return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0); -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::_q_updateIndex() -{ - if (!indexTimerId) - return; - - Q_Q(QGraphicsScene); - q->killTimer(indexTimerId); - indexTimerId = 0; - - purgeRemovedItems(); - - // Add unindexedItems to indexedItems - QRectF unindexedItemsBoundingRect; - foreach (QGraphicsItem *item, linearIndex->indexedItems()) { - unindexedItemsBoundingRect |= item->sceneBoundingRect(); - if (!freeItemIndexes.isEmpty()) { - int freeIndex = freeItemIndexes.takeFirst(); - item->d_func()->index = freeIndex; - indexedItems[freeIndex] = item; - } else { - item->d_func()->index = indexedItems.size(); - indexedItems << item; - } - } - - // Update growing scene rect. - QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect; - growingItemsBoundingRect |= unindexedItemsBoundingRect; - - // Determine whether we should regenerate the BSP tree. - if (indexMethod == QGraphicsScene::BspTreeIndex) { - QGraphicsSceneBspTree *bspTree = qobject_cast(index); - Q_ASSERT(bspTree); - int depth = bspTree->depth; - if (depth == 0) { - int oldDepth = intmaxlog(lastItemCount); - depth = intmaxlog(indexedItems.size()); - static const int slack = 100; - //### do something better - QGraphicsSceneBspTree *bsp = static_cast(index); - if (bsp->leafCount() == 0 || (oldDepth != depth && qAbs(lastItemCount - indexedItems.size()) > slack)) { - // ### Crude algorithm. - regenerateIndex = true; - } - } - - // Regenerate the tree. - if (regenerateIndex) { - regenerateIndex = false; - //### do something better - QGraphicsSceneBspTree *bsp = static_cast(index); - bsp->initialize(q->sceneRect(), depth); - foreach (QGraphicsItem *item, indexedItems) - linearIndex->insertItem(item); - lastItemCount = indexedItems.size(); - q->update(); - - // Take this opportunity to reset our largest-item counter for - // untransformable items. When the items are inserted into the BSP - // tree, we'll get an accurate calculation. - largestUntransformableItem = QRectF(); - } - } - - // Insert all unindexed items into the tree. - foreach (QGraphicsItem *item, linearIndex->indexedItems()) { - QRectF rect = item->sceneBoundingRect(); - if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) - continue; - - if (indexMethod != QGraphicsScene::NoIndex) - index->insertItem(item); - - // If the item ignores view transformations, update our - // largest-item-counter to ensure that the view can accurately - // discover untransformable items when drawing. - if (item->d_ptr->itemIsUntransformable()) { - QGraphicsItem *topmostUntransformable = item; - while (topmostUntransformable && (topmostUntransformable->d_ptr->ancestorFlags - & QGraphicsItemPrivate::AncestorIgnoresTransformations)) { - topmostUntransformable = topmostUntransformable->parentItem(); - } - // ### Verify that this is the correct largest untransformable rectangle. - largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect(); - } - } - linearIndex->clear(); - - // Notify scene rect changes. - if (!hasSceneRect && growingItemsBoundingRect != oldGrowingItemsBoundingRect) - emit q->sceneRectChanged(growingItemsBoundingRect); } /*! @@ -740,22 +527,8 @@ void QGraphicsScenePrivate::_q_removeItemLater(QGraphicsItem *item) // chain. item->clearFocus(); - int index = item->d_func()->index; - if (index != -1) { - // Important: The index is useless until purgeRemovedItems() is - // called. - indexedItems[index] = (QGraphicsItem *)0; - if (!purgePending) { - purgePending = true; - q->update(); - } - removedItems << item; - } else { - // Recently added items are purged immediately. unindexedItems() never - // contains stale items. - linearIndex->removeItem(item); - q->update(); - } + //We ask for a removing in the index + this->index->removeItem(item, true); // Reset the mouse grabber and focus item data. if (item == focusItem) @@ -806,51 +579,6 @@ void QGraphicsScenePrivate::_q_removeItemLater(QGraphicsItem *item) /*! \internal - - Removes stale pointers from all data structures. -*/ -void QGraphicsScenePrivate::purgeRemovedItems() -{ - Q_Q(QGraphicsScene); - - if (!purgePending && removedItems.isEmpty()) - return; - - // Remove stale items from the BSP tree. - if (indexMethod != QGraphicsScene::NoIndex) { - index->removeItems(removedItems); - } - - // Purge this list. - removedItems.clear(); - freeItemIndexes.clear(); - for (int i = 0; i < indexedItems.size(); ++i) { - if (!indexedItems.at(i)) - freeItemIndexes << i; - } - purgePending = false; - - // No locality info for the items; update the whole scene. - q->update(); -} - -/*! - \internal - - Starts or restarts the timer used for reindexing unindexed items. -*/ -void QGraphicsScenePrivate::startIndexTimer() -{ - Q_Q(QGraphicsScene); - if (indexTimerId) { - restartIndexTimer = true; - } else { - indexTimerId = q->startTimer(QGRAPHICSSCENE_INDEXTIMER_TIMEOUT); - } -} - -/*! - \internal */ void QGraphicsScenePrivate::addPopup(QGraphicsWidget *widget) { @@ -1964,7 +1692,7 @@ void QGraphicsScenePrivate::climbTree(QGraphicsItem *item, int *stackingOrder) void QGraphicsScenePrivate::_q_updateSortCache() { - _q_updateIndex(); + index->updateIndex(); if (!sortCacheEnabled || !updatingSortCache) return; @@ -1974,15 +1702,11 @@ void QGraphicsScenePrivate::_q_updateSortCache() QList topLevels; - for (int i = 0; i < indexedItems.size(); ++i) { - QGraphicsItem *item = indexedItems.at(i); + for (int i = 0; i < index->indexedItems().count(); ++i) { + QGraphicsItem *item = index->indexedItems().at(i); if (item && item->parentItem() == 0) topLevels << item; } - foreach (QGraphicsItem *item, linearIndex->indexedItems()) { - if (item->parentItem() == 0) - topLevels << item; - } qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf); for (int i = 0; i < topLevels.size(); ++i) @@ -2139,8 +1863,8 @@ QGraphicsScene::QGraphicsScene(QObject *parent) QGraphicsScene::QGraphicsScene(const QRectF &sceneRect, QObject *parent) : QObject(*new QGraphicsScenePrivate, parent) { - setSceneRect(sceneRect); d_func()->init(); + setSceneRect(sceneRect); } /*! @@ -2154,8 +1878,8 @@ QGraphicsScene::QGraphicsScene(const QRectF &sceneRect, QObject *parent) QGraphicsScene::QGraphicsScene(qreal x, qreal y, qreal width, qreal height, QObject *parent) : QObject(*new QGraphicsScenePrivate, parent) { - setSceneRect(x, y, width, height); d_func()->init(); + setSceneRect(x, y, width, height); } /*! @@ -2192,8 +1916,8 @@ QGraphicsScene::~QGraphicsScene() QRectF QGraphicsScene::sceneRect() const { Q_D(const QGraphicsScene); - const_cast(d)->_q_updateIndex(); - return d->hasSceneRect ? d->sceneRect : d->growingItemsBoundingRect; + d->index->updateIndex(); + return d->hasSceneRect ? d->index->rect() : d->growingItemsBoundingRect; } void QGraphicsScene::setSceneRect(const QRectF &rect) { @@ -2201,7 +1925,7 @@ void QGraphicsScene::setSceneRect(const QRectF &rect) if (rect != d->sceneRect) { d->hasSceneRect = !rect.isNull(); d->sceneRect = rect; - d->resetIndex(); + d->index->setRect(rect); emit sceneRectChanged(rect); } } @@ -2390,24 +2114,23 @@ void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method) if (d->indexMethod == method) { return; } - d->resetIndex(); if (d->indexMethod == NoIndex && method == BspTreeIndex) { - QGraphicsSceneBspTree *tree = qobject_cast(d->index); + QGraphicsSceneBspTreeIndex *tree = qobject_cast(d->index); if (!tree) { delete d->index; - d->index = new QGraphicsSceneBspTree(this); + d->index = new QGraphicsSceneBspTreeIndex(this); } } if (d->indexMethod == CustomIndex && method == BspTreeIndex) { QGraphicsSceneIndex *oldIndex = d->index; - d->index = new QGraphicsSceneBspTree(this); + d->index = new QGraphicsSceneBspTreeIndex(this); d->index->insertItems(oldIndex->items(oldIndex->rect())); } if (d->indexMethod == CustomIndex && method == NoIndex) { - d->index = new QGraphicsSceneBspTree(this); + d->index = new QGraphicsSceneLinearIndex(this); } d->indexMethod = method; @@ -2424,7 +2147,6 @@ void QGraphicsScene::setSceneIndex(QGraphicsSceneIndex *index) } d->indexMethod = CustomIndex; d->index = index; - index->mscene = this; } } @@ -2469,8 +2191,8 @@ QGraphicsSceneIndex* QGraphicsScene::sceneIndex() const int QGraphicsScene::bspTreeDepth() const { Q_D(const QGraphicsScene); - QGraphicsSceneBspTree *bspTree = qobject_cast(d->index); - return bspTree ? bspTree->depth : 0; + QGraphicsSceneBspTreeIndex *bspTree = qobject_cast(d->index); + return bspTree ? bspTree->bspDepth() : 0; } void QGraphicsScene::setBspTreeDepth(int depth) { @@ -2483,14 +2205,13 @@ void QGraphicsScene::setBspTreeDepth(int depth) return; } - QGraphicsSceneBspTree *bspTree = qobject_cast(d->index); + QGraphicsSceneBspTreeIndex *bspTree = qobject_cast(d->index); if (!bspTree) { qWarning("QGraphicsScene::setBspTreeDepth: can not apply if indexing method is not BSP"); return; } - bspTree->depth = depth; - d->resetIndex(); + bspTree->setBspDepth(depth); } /*! @@ -2543,24 +2264,7 @@ QRectF QGraphicsScene::itemsBoundingRect() const QList QGraphicsScene::items() const { Q_D(const QGraphicsScene); - const_cast(d)->purgeRemovedItems(); - - // If freeItemIndexes is empty, we know there are no holes in indexedItems and - // unindexedItems. - if (d->freeItemIndexes.isEmpty()) { - if (d->linearIndex->indexedItems().isEmpty()) - return d->indexedItems; - return d->indexedItems + d->linearIndex->indexedItems(); - } - - // Rebuild the list of items to avoid holes. ### We could also just - // compress the item lists at this point. - QList itemList; - foreach (QGraphicsItem *item, d->indexedItems + d->linearIndex->indexedItems()) { - if (item) - itemList << item; - } - return itemList; + return d->index->indexedItems(); } /*! @@ -2830,21 +2534,12 @@ void QGraphicsScene::clear() { Q_D(QGraphicsScene); // Recursive descent delete - for (int i = 0; i < d->indexedItems.size(); ++i) { - if (QGraphicsItem *item = d->indexedItems.at(i)) { + for (int i = 0; i < d->index->indexedItems().size(); ++i) { + if (QGraphicsItem *item = d->index->indexedItems().at(i)) { if (!item->parentItem()) delete item; } } - QList unindexedParents; - foreach (QGraphicsItem *item, d->linearIndex->indexedItems()) { - if (!item->parentItem()) - unindexedParents << item; - } - d->linearIndex->clear(); - qDeleteAll(unindexedParents); - d->indexedItems.clear(); - d->freeItemIndexes.clear(); d->lastItemCount = 0; d->index->clear(); d->largestUntransformableItem = QRectF(); @@ -2968,10 +2663,6 @@ void QGraphicsScene::addItem(QGraphicsItem *item) return; } - // Prevent reusing a recently deleted pointer: purge all removed items - // from our lists. - d->purgeRemovedItems(); - // Invalidate any sort caching; arrival of a new item means we need to // resort. d->invalidateSortCache(); @@ -2989,9 +2680,7 @@ void QGraphicsScene::addItem(QGraphicsItem *item) // Indexing requires sceneBoundingRect(), but because \a item might // not be completely constructed at this point, we need to store it in // a temporary list and schedule an indexing for later. - d->linearIndex->insertItem(item); - item->d_func()->index = -1; - d->startIndexTimer(); + d->index->insertItem(item); // Add to list of toplevels if this item is a toplevel. if (!item->d_ptr->parent) @@ -3351,7 +3040,7 @@ void QGraphicsScene::removeItem(QGraphicsItem *item) // Note: This will access item's sceneBoundingRect(), which (as this is // C++) is why we cannot call removeItem() from QGraphicsItem's // destructor. - d->removeFromIndex(item); + d->index->removeItem(item, false); if (item == d->tabFocusFirst) { QGraphicsWidget *widget = static_cast(item); @@ -3371,15 +3060,6 @@ void QGraphicsScene::removeItem(QGraphicsItem *item) d->unregisterTopLevelItem(item); } - // Remove from our item lists. - int index = item->d_func()->index; - if (index != -1) { - d->freeItemIndexes << index; - d->indexedItems[index] = 0; - } else { - d->linearIndex->removeItem(item); - } - // Remove from scene transform cache int transformIndex = item->d_func()->sceneTransformIndex; if (transformIndex != -1) { @@ -3998,16 +3678,6 @@ bool QGraphicsScene::event(QEvent *event) // geometries that do not have an explicit style set. update(); break; - case QEvent::Timer: - if (d->indexTimerId && static_cast(event)->timerId() == d->indexTimerId) { - if (d->restartIndexTimer) { - d->restartIndexTimer = false; - } else { - // this call will kill the timer - d->_q_updateIndex(); - } - } - // Fallthrough intended - support timers in subclasses. default: return QObject::event(event); } diff --git a/src/gui/graphicsview/qgraphicsscene.h b/src/gui/graphicsview/qgraphicsscene.h index bb3cea7..6476b8c 100644 --- a/src/gui/graphicsview/qgraphicsscene.h +++ b/src/gui/graphicsview/qgraphicsscene.h @@ -279,7 +279,6 @@ private: Q_DECLARE_PRIVATE(QGraphicsScene) Q_DISABLE_COPY(QGraphicsScene) - Q_PRIVATE_SLOT(d_func(), void _q_updateIndex()) Q_PRIVATE_SLOT(d_func(), void _q_emitUpdated()) Q_PRIVATE_SLOT(d_func(), void _q_removeItemLater(QGraphicsItem *item)) Q_PRIVATE_SLOT(d_func(), void _q_updateLater()) @@ -292,6 +291,7 @@ private: friend class QGraphicsViewPrivate; friend class QGraphicsWidget; friend class QGraphicsWidgetPrivate; + friend class QGraphicsSceneBspTreeIndex; }; Q_DECLARE_OPERATORS_FOR_FLAGS(QGraphicsScene::SceneLayers) diff --git a/src/gui/graphicsview/qgraphicsscene_bsp.cpp b/src/gui/graphicsview/qgraphicsscene_bsp.cpp index a81b14d..f8fa450 100644 --- a/src/gui/graphicsview/qgraphicsscene_bsp.cpp +++ b/src/gui/graphicsview/qgraphicsscene_bsp.cpp @@ -83,8 +83,8 @@ public: } }; -QGraphicsSceneBspTree::QGraphicsSceneBspTree(QObject *parent) - : QGraphicsSceneIndex(parent), depth(0), leafCnt(0) +QGraphicsSceneBspTree::QGraphicsSceneBspTree() + : leafCnt(0) { insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor; removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor; @@ -100,7 +100,7 @@ QGraphicsSceneBspTree::~QGraphicsSceneBspTree() void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth) { - sceneRect = rect; + this->rect = rect; leafCnt = 0; nodes.resize((1 << (depth + 1)) - 1); nodes.fill(Node()); @@ -117,29 +117,19 @@ void QGraphicsSceneBspTree::clear() leaves.clear(); } -QRectF QGraphicsSceneBspTree::rect() const -{ - return sceneRect; -} - -void QGraphicsSceneBspTree::setRect(const QRectF &rect) -{ - sceneRect = rect; -} - -void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item) +void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect) { insertVisitor->item = item; - climbTree(insertVisitor, item->sceneBoundingRect()); + climbTree(insertVisitor, rect); } -void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item) +void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect) { removeVisitor->item = item; - climbTree(removeVisitor, item->sceneBoundingRect()); + climbTree(removeVisitor, rect); } -void QGraphicsSceneBspTree::removeItems(const QList &items) +void QGraphicsSceneBspTree::removeItems(const QSet &items) { for (int i = 0; i < leaves.size(); ++i) { QList newItemList; @@ -247,10 +237,8 @@ void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index) void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index) { - if (nodes.isEmpty()) { - // should never happen for bsp tree internal to QGraphicsScene - initialize(sceneRect, 0); - } + if (nodes.isEmpty()) + return; const Node &node = nodes.at(index); int childIndex = firstChildIndex(index); @@ -279,10 +267,8 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) { - if (nodes.isEmpty()) { - // should never happen for bsp tree internal to QGraphicsScene - initialize(sceneRect, 0); - } + if (nodes.isEmpty()) + return; const Node &node = nodes.at(index); int childIndex = firstChildIndex(index); @@ -316,7 +302,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con QRectF QGraphicsSceneBspTree::rectForIndex(int index) const { if (index <= 0) - return sceneRect; + return rect; int parentIdx = parentIndex(index); QRectF rect = rectForIndex(parentIdx); diff --git a/src/gui/graphicsview/qgraphicsscene_bsp_p.h b/src/gui/graphicsview/qgraphicsscene_bsp_p.h index 69d9eee..e6ceb78 100644 --- a/src/gui/graphicsview/qgraphicsscene_bsp_p.h +++ b/src/gui/graphicsview/qgraphicsscene_bsp_p.h @@ -60,7 +60,6 @@ #include #include #include -#include QT_BEGIN_NAMESPACE @@ -70,10 +69,8 @@ class QGraphicsSceneInsertItemBspTreeVisitor; class QGraphicsSceneRemoveItemBspTreeVisitor; class QGraphicsSceneFindItemBspTreeVisitor; -class Q_AUTOTEST_EXPORT QGraphicsSceneBspTree : public QGraphicsSceneIndex +class QGraphicsSceneBspTree { - Q_OBJECT - public: struct Node { @@ -85,27 +82,20 @@ public: Type type; }; - QGraphicsSceneBspTree(QObject *parent = 0); + QGraphicsSceneBspTree(); ~QGraphicsSceneBspTree(); void initialize(const QRectF &rect, int depth); void clear(); - QRectF rect() const; - void setRect(const QRectF &rect); - void insertItem(QGraphicsItem *item); - void removeItem(QGraphicsItem *item); - void removeItems(const QList &items); + void insertItem(QGraphicsItem *item, const QRectF &rect); + void removeItem(QGraphicsItem *item, const QRectF &rect); + void removeItems(const QSet &items); - QList items(const QPointF &point); QList items(const QRectF &rect); - + QList items(const QPointF &pos); int leafCount() const; - int depth; - -private: - inline int firstChildIndex(int index) const { return index * 2 + 1; } @@ -114,6 +104,7 @@ private: QString debug(int index) const; +private: void initialize(const QRectF &rect, int depth, int index); void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index = 0); void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index = 0); @@ -125,7 +116,7 @@ private: QVector nodes; QVector > leaves; int leafCnt; - QRectF sceneRect; + QRectF rect; QGraphicsSceneInsertItemBspTreeVisitor *insertVisitor; QGraphicsSceneRemoveItemBspTreeVisitor *removeVisitor; @@ -139,8 +130,6 @@ public: virtual void visit(QList *items) = 0; }; -Q_DECLARE_TYPEINFO(QGraphicsSceneBspTree::Node, Q_PRIMITIVE_TYPE); - QT_END_NAMESPACE #endif // QT_NO_GRAPHICSVIEW diff --git a/src/gui/graphicsview/qgraphicsscene_linear_p.h b/src/gui/graphicsview/qgraphicsscene_linear_p.h deleted file mode 100644 index 41e03e4..0000000 --- a/src/gui/graphicsview/qgraphicsscene_linear_p.h +++ /dev/null @@ -1,124 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). -** Contact: Qt Software Information (qt-info@nokia.com) -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** No Commercial Usage -** This file contains pre-release code and may not be distributed. -** You may use this file in accordance with the terms and conditions -** contained in the either Technology Preview License Agreement or the -** Beta Release License Agreement. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 2.1 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 2.1 requirements -** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -** -** In addition, as a special exception, Nokia gives you certain -** additional rights. These rights are described in the Nokia Qt LGPL -** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this -** package. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 3.0 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU General Public License version 3.0 requirements will be -** met: http://www.gnu.org/copyleft/gpl.html. -** -** If you are unsure which license is appropriate for your use, please -** contact the sales department at qt-sales@nokia.com. -** $QT_END_LICENSE$ -** -****************************************************************************/ - -#ifndef QGRAPHICSSCENELINEARINDEX_P_H -#define QGRAPHICSSCENELINEARINDEX_P_H - -// -// W A R N I N G -// ------------- -// -// This file is not part of the Qt API. It exists for the convenience -// of other Qt classes. This header file may change from version to -// version without notice, or even be removed. -// -// We mean it. -// - -#include - -#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW - -#include -#include -#include -#include - -QT_BEGIN_NAMESPACE - -class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex -{ - Q_OBJECT - -private: - QRectF m_sceneRect; - QList m_items; - -public: - QGraphicsSceneLinearIndex(QObject *parent = 0): QGraphicsSceneIndex(parent) { - } - - virtual void setRect(const QRectF &rect) { - m_sceneRect = rect; - } - - virtual QRectF rect() const { - return m_sceneRect; - } - - virtual void clear() { - m_items.clear(); - } - - virtual void insertItem(QGraphicsItem *item) { - m_items << item; - } - - virtual void removeItem(QGraphicsItem *item) { - m_items.removeAll(item); - } - - virtual QList items(const QPointF &point) { - QList result; - foreach (QGraphicsItem *item, m_items) - if (item->sceneBoundingRect().contains(point)) - result << item; - return result; - } - - virtual QList items(const QRectF &rect) { - QList result; - foreach (QGraphicsItem *item, m_items) - if (item->sceneBoundingRect().intersects(rect)) - result << item; - return result; - } - - QList indexedItems() { - return m_items; - } -}; - -QT_END_NAMESPACE - -#endif // QT_NO_GRAPHICSVIEW - -#endif // QGRAPHICSSCENELINEARINDEX_P_H diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h index 65c1a69..2c0d464 100644 --- a/src/gui/graphicsview/qgraphicsscene_p.h +++ b/src/gui/graphicsview/qgraphicsscene_p.h @@ -57,8 +57,8 @@ #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW -#include "qgraphicsscene_bsp_p.h" -#include "qgraphicsscene_linear_p.h" +#include "qgraphicsscenebsptreeindex_p.h" +#include "qgraphicsscenelinearindex_p.h" #include "qgraphicssceneindex.h" #include "qgraphicsitem_p.h" @@ -89,15 +89,10 @@ public: int bspTreeDepth; QList estimateItemsInRect(const QRectF &rect) const; - void addToIndex(QGraphicsItem *item); - void removeFromIndex(QGraphicsItem *item); - void resetIndex(); - void _q_updateIndex(); int lastItemCount; QGraphicsSceneIndex *index; - QGraphicsSceneLinearIndex *linearIndex; QRectF sceneRect; bool hasSceneRect; @@ -112,7 +107,6 @@ public: QPainterPath selectionArea; int selectionChanging; QSet selectedItems; - QList indexedItems; QList dirtyItems; QList pendingUpdateItems; QList unpolishedItems; @@ -127,21 +121,11 @@ public: void resetDirtyItemsLater(); bool dirtyItemResetPending; - QList freeItemIndexes; - bool regenerateIndex; - - bool purgePending; void _q_removeItemLater(QGraphicsItem *item); - QList removedItems; - void purgeRemovedItems(); QBrush backgroundBrush; QBrush foregroundBrush; - int indexTimerId; - bool restartIndexTimer; - void startIndexTimer(); - bool stickyFocus; bool hasFocus; QGraphicsItem *focusItem; diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp new file mode 100644 index 0000000..ebc167a --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp @@ -0,0 +1,437 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; + +#include "qgraphicsscenebsptreeindex_p.h" +#include "qgraphicsitem_p.h" +#include "qgraphicsscene_p.h" + +#include + +#include + +QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene) + : QGraphicsSceneIndex(scene), + bspTreeDepth(0), + indexTimerId(0), + restartIndexTimer(false), + regenerateIndex(true), + lastItemCount(0), + purgePending(false) +{ + +} + +void QGraphicsSceneBspTreeIndex::setRect(const QRectF &rect) +{ + m_sceneRect = rect; + resetIndex(); +} + +QRectF QGraphicsSceneBspTreeIndex::rect() const +{ + const_cast(this)->updateIndex(); + return m_sceneRect; +} + +void QGraphicsSceneBspTreeIndex::clear() +{ + bsp.clear(); + lastItemCount = 0; + freeItemIndexes.clear(); + m_indexedItems.clear(); + unindexedItems.clear(); +} + +void QGraphicsSceneBspTreeIndex::insertItem(QGraphicsItem *item) +{ + // Prevent reusing a recently deleted pointer: purge all removed items + // from our lists. + purgeRemovedItems(); + + // Indexing requires sceneBoundingRect(), but because \a item might + // not be completely constructed at this point, we need to store it in + // a temporary list and schedule an indexing for later. + unindexedItems << item; + item->d_func()->index = -1; + startIndexTimer(); +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndex::addToIndex(QGraphicsItem *item) +{ + if (item->d_func()->index != -1) { + bsp.insertItem(item, item->sceneBoundingRect()); + foreach (QGraphicsItem *child, item->children()) + child->addToIndex(); + } else { + // The BSP tree is regenerated if the number of items grows to a + // certain threshold, or if the bounding rect of the graph doubles in + // size. + startIndexTimer(); + } +} + +void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item, bool itemIsAboutToDie) +{ + if (!itemIsAboutToDie) { + // Note: This will access item's sceneBoundingRect(), which (as this is + // C++) is why we cannot call removeItem() from QGraphicsItem's + // destructor. + removeFromIndex(item); + + // Remove from our item lists. + int index = item->d_func()->index; + if (index != -1) { + freeItemIndexes << index; + m_indexedItems[index] = 0; + } else { + unindexedItems.removeAll(item); + } + + } else { + int index = item->d_func()->index; + if (index != -1) { + // Important: The index is useless until purgeRemovedItems() is + // called. + m_indexedItems[index] = (QGraphicsItem *)0; + if (!purgePending) { + purgePending = true; + scene()->update(); + } + removedItems << item; + } else { + // Recently added items are purged immediately. unindexedItems() never + // contains stale items. + unindexedItems.removeAll(item); + scene()->update(); + } + } +} +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndex::removeFromIndex(QGraphicsItem *item) +{ + if (item->d_func()->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) { + // ### remove from child index only if applicable + return; + } + int index = item->d_func()->index; + if (index != -1) { + bsp.removeItem(item, item->sceneBoundingRect()); + freeItemIndexes << index; + m_indexedItems[index] = 0; + item->d_func()->index = -1; + unindexedItems << item; + + //prepareGeometryChange will call updateItem + foreach (QGraphicsItem *child, item->children()) + child->prepareGeometryChange(); + } + startIndexTimer(); +} + +void QGraphicsSceneBspTreeIndex::updateItem(QGraphicsItem *item) +{ + // Note: This will access item's sceneBoundingRect(), which (as this is + // C++) is why we cannot call removeItem() from QGraphicsItem's + // destructor. + removeFromIndex(item); +} + +QList QGraphicsSceneBspTreeIndex::items(const QPointF &point) +{ + purgeRemovedItems(); + QList rectItems = bsp.items(QRectF(point, QSizeF(1, 1))); + // Fill in with any unindexed items + for (int i = 0; i < unindexedItems.size(); ++i) { + if (QGraphicsItem *item = unindexedItems.at(i)) { + if (!item->d_ptr->itemDiscovered && item->d_ptr->visible && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { + QRectF boundingRect = item->sceneBoundingRect(); + if (boundingRect.intersects(QRectF(point, QSizeF(1, 1)))) { + item->d_ptr->itemDiscovered = 1; + rectItems << item; + } + } + } + } + + // Reset the discovered state of all discovered items + for (int i = 0; i < rectItems.size(); ++i) + rectItems.at(i)->d_func()->itemDiscovered = 0; + + return rectItems; +} + +QList QGraphicsSceneBspTreeIndex::items(const QRectF &rect) +{ + purgeRemovedItems(); + QList rectItems = bsp.items(rect); + // Fill in with any unindexed items + for (int i = 0; i < unindexedItems.size(); ++i) { + if (QGraphicsItem *item = unindexedItems.at(i)) { + if (!item->d_ptr->itemDiscovered && item->d_ptr->visible && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { + QRectF boundingRect = item->sceneBoundingRect(); + if (boundingRect.intersects(rect)) { + item->d_ptr->itemDiscovered = 1; + rectItems << item; + } + } + } + } + + // Reset the discovered state of all discovered items + for (int i = 0; i < rectItems.size(); ++i) + rectItems.at(i)->d_func()->itemDiscovered = 0; + + return rectItems; +} + +QList QGraphicsSceneBspTreeIndex::indexedItems() +{ + purgeRemovedItems(); + // If freeItemIndexes is empty, we know there are no holes in indexedItems and + // unindexedItems. + if (freeItemIndexes.isEmpty()) { + if (unindexedItems.isEmpty()) + return m_indexedItems; + return m_indexedItems + unindexedItems; + } + + // Rebuild the list of items to avoid holes. ### We could also just + // compress the item lists at this point. + QList itemList; + foreach (QGraphicsItem *item, m_indexedItems + unindexedItems) { + if (item) + itemList << item; + } + return itemList; +} + +void QGraphicsSceneBspTreeIndex::updateIndex() +{ + _q_updateIndex(); +} + +int QGraphicsSceneBspTreeIndex::bspDepth() +{ + return bspTreeDepth; +} + +void QGraphicsSceneBspTreeIndex::setBspDepth(int depth) +{ + bspTreeDepth = depth; + resetIndex(); +} + +bool QGraphicsSceneBspTreeIndex::event(QEvent *event) +{ + switch (event->type()) { + case QEvent::Timer: + if (indexTimerId && static_cast(event)->timerId() == indexTimerId) { + if (restartIndexTimer) { + restartIndexTimer = false; + } else { + // this call will kill the timer + _q_updateIndex(); + } + } + // Fallthrough intended - support timers in subclasses. + default: + return QObject::event(event); + } + return true; +} + +static inline int intmaxlog(int n) +{ + return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0); +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndex::_q_updateIndex() +{ + if (!indexTimerId) + return; + + killTimer(indexTimerId); + indexTimerId = 0; + + purgeRemovedItems(); + + // Add unindexedItems to indexedItems + QRectF unindexedItemsBoundingRect; + for (int i = 0; i < unindexedItems.size(); ++i) { + if (QGraphicsItem *item = unindexedItems.at(i)) { + unindexedItemsBoundingRect |= item->sceneBoundingRect(); + if (!freeItemIndexes.isEmpty()) { + int freeIndex = freeItemIndexes.takeFirst(); + item->d_func()->index = freeIndex; + m_indexedItems[freeIndex] = item; + } else { + item->d_func()->index = m_indexedItems.size(); + m_indexedItems << item; + } + } + } + + // Update growing scene rect. + QRectF oldGrowingItemsBoundingRect = scene()->d_func()->growingItemsBoundingRect; + scene()->d_func()->growingItemsBoundingRect |= unindexedItemsBoundingRect; + + // Determine whether we should regenerate the BSP tree. + if (bspTreeDepth == 0) { + int oldDepth = intmaxlog(lastItemCount); + bspTreeDepth = intmaxlog(m_indexedItems.size()); + static const int slack = 100; + if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - m_indexedItems.size()) > slack)) { + // ### Crude algorithm. + regenerateIndex = true; + } + } + + // Regenerate the tree. + if (regenerateIndex) { + regenerateIndex = false; + bsp.initialize(scene()->sceneRect(), bspTreeDepth); + unindexedItems = m_indexedItems; + lastItemCount = m_indexedItems.size(); + scene()->update(); + + // Take this opportunity to reset our largest-item counter for + // untransformable items. When the items are inserted into the BSP + // tree, we'll get an accurate calculation. + scene()->d_func()->largestUntransformableItem = QRectF(); + } + + // Insert all unindexed items into the tree. + for (int i = 0; i < unindexedItems.size(); ++i) { + if (QGraphicsItem *item = unindexedItems.at(i)) { + QRectF rect = item->sceneBoundingRect(); + if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) + continue; + + bsp.insertItem(item,rect); + + // If the item ignores view transformations, update our + // largest-item-counter to ensure that the view can accurately + // discover untransformable items when drawing. + if (item->d_ptr->itemIsUntransformable()) { + QGraphicsItem *topmostUntransformable = item; + while (topmostUntransformable && (topmostUntransformable->d_ptr->ancestorFlags + & QGraphicsItemPrivate::AncestorIgnoresTransformations)) { + topmostUntransformable = topmostUntransformable->parentItem(); + } + // ### Verify that this is the correct largest untransformable rectangle. + scene()->d_func()->largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect(); + } + } + } + unindexedItems.clear(); + + // Notify scene rect changes. + if (!scene()->d_func()->hasSceneRect && scene()->d_func()->growingItemsBoundingRect != oldGrowingItemsBoundingRect) + emit scene()->sceneRectChanged(scene()->d_func()->growingItemsBoundingRect); +} + + +/*! + \internal + + Removes stale pointers from all data structures. +*/ +void QGraphicsSceneBspTreeIndex::purgeRemovedItems() +{ + if (!purgePending && removedItems.isEmpty()) + return; + + // Remove stale items from the BSP tree. + bsp.removeItems(removedItems.toSet()); + // Purge this list. + removedItems.clear(); + freeItemIndexes.clear(); + for (int i = 0; i < m_indexedItems.size(); ++i) { + if (!m_indexedItems.at(i)) + freeItemIndexes << i; + } + purgePending = false; + + // No locality info for the items; update the whole scene. + scene()->update(); +} + +/*! + \internal + + Starts or restarts the timer used for reindexing unindexed items. +*/ +void QGraphicsSceneBspTreeIndex::startIndexTimer() +{ + if (indexTimerId) { + restartIndexTimer = true; + } else { + indexTimerId = startTimer(QGRAPHICSSCENE_INDEXTIMER_TIMEOUT); + } +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndex::resetIndex() +{ + purgeRemovedItems(); + for (int i = 0; i < m_indexedItems.size(); ++i) { + if (QGraphicsItem *item = m_indexedItems.at(i)) { + item->d_ptr->index = -1; + unindexedItems << item; + } + } + m_indexedItems.clear(); + freeItemIndexes.clear(); + regenerateIndex = true; + startIndexTimer(); +} diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h new file mode 100644 index 0000000..74af910 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h @@ -0,0 +1,118 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include + +#ifndef QGRAPHICSBSPTREEINDEX_H +#define QGRAPHICSBSPTREEINDEX_H + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +QT_BEGIN_NAMESPACE + +#include +#include +#include +#include +#include + +#include "qgraphicsscene_bsp_p.h" + +class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex +{ + Q_OBJECT +public: + QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0); + + void setRect(const QRectF &rect); + virtual QRectF rect() const; + + void clear(); + + void insertItem(QGraphicsItem *item); + void removeItem(QGraphicsItem *item, bool itemIsAboutToDie); + void updateItem(QGraphicsItem *item); + + QList items(const QPointF &point); + QList items(const QRectF &rect); + + QList indexedItems(); + + void updateIndex(); + + int bspDepth(); + void setBspDepth(int depth); + +protected: + bool event(QEvent *event); + +public slots : + void _q_updateIndex(); + +private : + QGraphicsSceneBspTree bsp; + QRectF m_sceneRect; + int bspTreeDepth; + int indexTimerId; + bool restartIndexTimer; + bool regenerateIndex; + int lastItemCount; + + QList m_indexedItems; + QList unindexedItems; + QList freeItemIndexes; + + bool purgePending; + QList removedItems; + void purgeRemovedItems(); + + void startIndexTimer(); + void resetIndex(); + + void addToIndex(QGraphicsItem *item); + void removeFromIndex(QGraphicsItem *item); +}; + +QT_END_NAMESPACE + +#endif // QT_NO_GRAPHICSVIEW + +#endif // QGRAPHICSBSPTREEINDEX_H diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp index 904e0af..7360bed 100644 --- a/src/gui/graphicsview/qgraphicssceneindex.cpp +++ b/src/gui/graphicsview/qgraphicssceneindex.cpp @@ -49,7 +49,7 @@ QT_BEGIN_NAMESPACE /*! Constructs an abstract scene index. */ -QGraphicsSceneIndex::QGraphicsSceneIndex(QObject *parent): QObject(parent) +QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene): QObject(scene), m_scene(scene) { } @@ -108,7 +108,7 @@ QGraphicsSceneIndex::~QGraphicsSceneIndex() */ QGraphicsScene* QGraphicsSceneIndex::scene() { - return mscene; + return m_scene; } /*! @@ -121,7 +121,7 @@ QGraphicsScene* QGraphicsSceneIndex::scene() */ void QGraphicsSceneIndex::updateItem(QGraphicsItem *item) { - removeItem(item); + removeItem(item,false); insertItem(item); } @@ -145,10 +145,10 @@ void QGraphicsSceneIndex::insertItems(const QList &items) \sa removeItem(), removeItems(), updateItems() */ -void QGraphicsSceneIndex::removeItems(const QList &items) +void QGraphicsSceneIndex::removeItems(const QList &items, bool itemsAreAboutToDie) { foreach (QGraphicsItem *item, items) - removeItem(item); + removeItem(item,itemsAreAboutToDie); } /*! @@ -164,6 +164,10 @@ void QGraphicsSceneIndex::updateItems(const QList &items) updateItem(item); } +void QGraphicsSceneIndex::updateIndex() +{ +} + QT_END_NAMESPACE #include "moc_qgraphicssceneindex.cpp" diff --git a/src/gui/graphicsview/qgraphicssceneindex.h b/src/gui/graphicsview/qgraphicssceneindex.h index d3b6c9f..3b034d4 100644 --- a/src/gui/graphicsview/qgraphicssceneindex.h +++ b/src/gui/graphicsview/qgraphicssceneindex.h @@ -64,27 +64,32 @@ class Q_GUI_EXPORT QGraphicsSceneIndex: public QObject Q_OBJECT public: - QGraphicsSceneIndex(QObject *parent = 0); + QGraphicsSceneIndex(QGraphicsScene *scene = 0); virtual ~QGraphicsSceneIndex(); + QGraphicsScene* scene(); + virtual void setRect(const QRectF &rect) = 0; virtual QRectF rect() const = 0; virtual void clear() = 0; virtual void insertItem(QGraphicsItem *item) = 0; - virtual void removeItem(QGraphicsItem *item) = 0; + virtual void removeItem(QGraphicsItem *items, bool itemIsAboutToDie) = 0; virtual void updateItem(QGraphicsItem *item); virtual void insertItems(const QList &items); - virtual void removeItems(const QList &items); + virtual void removeItems(const QList &items, bool itemsAreAboutToDie); virtual void updateItems(const QList &items); virtual QList items(const QPointF &point) = 0; virtual QList items(const QRectF &rect) = 0; - QGraphicsScene* scene(); + virtual QList indexedItems() = 0; + + virtual void updateIndex(); - QGraphicsScene* mscene; +private: + QGraphicsScene *m_scene; }; #endif // QT_NO_GRAPHICSVIEW diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h new file mode 100644 index 0000000..30948d9 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h @@ -0,0 +1,126 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QGRAPHICSSCENELINEARINDEX_P_H +#define QGRAPHICSSCENELINEARINDEX_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include +#include +#include +#include + +QT_BEGIN_NAMESPACE + +class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex +{ + Q_OBJECT + +private: + QRectF m_sceneRect; + QList m_items; + +public: + QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0): QGraphicsSceneIndex(scene) + { + } + + virtual void setRect(const QRectF &rect) { + m_sceneRect = rect; + } + + virtual QRectF rect() const { + return m_sceneRect; + } + + virtual void clear() { + m_items.clear(); + } + + virtual void insertItem(QGraphicsItem *item) { + m_items << item; + } + + virtual void removeItem(QGraphicsItem *item, bool itemIsAboutToDie) { + Q_UNUSED(itemIsAboutToDie); + m_items.removeAll(item); + } + + virtual QList items(const QPointF &point) { + QList result; + foreach (QGraphicsItem *item, m_items) + if (item->sceneBoundingRect().contains(point)) + result << item; + return result; + } + + virtual QList items(const QRectF &rect) { + QList result; + foreach (QGraphicsItem *item, m_items) + if (item->sceneBoundingRect().intersects(rect)) + result << item; + return result; + } + + QList indexedItems() { + return m_items; + } +}; + +QT_END_NAMESPACE + +#endif // QT_NO_GRAPHICSVIEW + +#endif // QGRAPHICSSCENELINEARINDEX_P_H diff --git a/tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp b/tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp index 955f2d3..3dca152 100644 --- a/tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp +++ b/tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp @@ -43,8 +43,8 @@ #include #include #include -#include -#include +#include +#include //TESTED_CLASS= @@ -88,12 +88,12 @@ void tst_QGraphicsSceneIndex::common_data() QGraphicsSceneIndex *tst_QGraphicsSceneIndex::createIndex(const QString &indexMethod) { QGraphicsSceneIndex *index = 0; - + QGraphicsScene *scene = new QGraphicsScene(); if (indexMethod == "bsp") - index = new QGraphicsSceneBspTree; + index = new QGraphicsSceneBspTreeIndex(scene); if (indexMethod == "linear") - index = new QGraphicsSceneLinearIndex; + index = new QGraphicsSceneLinearIndex(scene); return index; } @@ -104,8 +104,9 @@ void tst_QGraphicsSceneIndex::sceneRect_data() } void tst_QGraphicsSceneIndex::sceneRect() -{ - QGraphicsSceneIndex *index = new QGraphicsSceneBspTree; +{ + QGraphicsScene *scene = new QGraphicsScene(); + QGraphicsSceneIndex *index = new QGraphicsSceneBspTreeIndex(scene); index->setRect(QRectF(0, 0, 2000, 2000)); QCOMPARE(index->rect(), QRectF(0, 0, 2000, 2000)); } -- cgit v0.12