summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/gui/graphicsview/graphicsview.pri1
-rw-r--r--src/gui/graphicsview/qgraphicsitem.cpp22
-rw-r--r--src/gui/graphicsview/qgraphicsitem.h1
-rw-r--r--src/gui/graphicsview/qgraphicsscene.cpp200
-rw-r--r--src/gui/graphicsview/qgraphicsscene.h2
-rw-r--r--src/gui/graphicsview/qgraphicsscene_p.h19
-rw-r--r--src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp614
-rw-r--r--src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h51
-rw-r--r--src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h140
-rw-r--r--src/gui/graphicsview/qgraphicssceneindex.cpp28
-rw-r--r--src/gui/graphicsview/qgraphicssceneindex.h9
-rw-r--r--src/gui/graphicsview/qgraphicssceneindex_p.h3
-rw-r--r--src/gui/graphicsview/qgraphicsscenelinearindex_p.h2
-rw-r--r--src/gui/graphicsview/qgraphicsview.cpp11
-rw-r--r--tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp5
-rw-r--r--tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp5
-rw-r--r--tests/auto/qgraphicsview/tst_qgraphicsview.cpp8
17 files changed, 642 insertions, 479 deletions
diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri
index cc57892..a4a79e8 100644
--- a/src/gui/graphicsview/graphicsview.pri
+++ b/src/gui/graphicsview/graphicsview.pri
@@ -7,6 +7,7 @@ HEADERS += \
graphicsview/qgraphicsscene.h \
graphicsview/qgraphicsscene_p.h \
graphicsview/qgraphicsscenebsptreeindex_p.h \
+ graphicsview/qgraphicsscenebsptreeindex_p_p.h \
graphicsview/qgraphicsscene_bsp_p.h \
graphicsview/qgraphicsscenelinearindex_p.h \
graphicsview/qgraphicssceneindex.h \
diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index fc5895c..ee32724 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -537,6 +537,7 @@
#include "qgraphicsview.h"
#include "qgraphicswidget.h"
#include "qgraphicsproxywidget.h"
+#include "qgraphicsscenebsptreeindex_p_p.h"
#include <QtCore/qbitarray.h>
#include <QtCore/qdebug.h>
#include <QtCore/qpoint.h>
@@ -888,12 +889,6 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent, bool de
}
}
- if (scene) {
- // Invalidate any sort caching; arrival of a new item means we need to
- // resort.
- scene->d_func()->invalidateSortCache();
- }
-
// Resolve opacity.
updateEffectiveOpacity();
@@ -905,6 +900,11 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent, bool de
// Deliver post-change notification
q->itemChange(QGraphicsItem::ItemParentHasChanged, newParentVariant);
+
+ if (scene) {
+ // Deliver the change to the index
+ scene->d_func()->index->itemChanged(q, QGraphicsItem::ItemParentHasChanged, newParentVariant);
+ }
}
/*!
@@ -3528,11 +3528,9 @@ void QGraphicsItem::setZValue(qreal z)
d_ptr->z = newZ;
d_ptr->fullUpdateHelper();
- if (d_ptr->scene) {
- // Invalidate any sort caching; arrival of a new item means we need to
- // resort.
- d_ptr->scene->d_func()->invalidateSortCache();
- }
+ //Z Value has changed, we have to notify the index.
+ if (d_ptr->scene)
+ d_ptr->scene->d_func()->index->itemChanged(this, ItemZValueChange, z);
itemChange(ItemZValueHasChanged, newZVariant);
}
@@ -3991,7 +3989,7 @@ bool QGraphicsItem::isObscuredBy(const QGraphicsItem *item) const
{
if (!item)
return false;
- return QGraphicsScenePrivate::closestItemFirst_withoutCache(item, this)
+ return QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(item, this)
&& qt_QGraphicsItem_isObscured(this, item, boundingRect());
}
diff --git a/src/gui/graphicsview/qgraphicsitem.h b/src/gui/graphicsview/qgraphicsitem.h
index e244c13..7874033 100644
--- a/src/gui/graphicsview/qgraphicsitem.h
+++ b/src/gui/graphicsview/qgraphicsitem.h
@@ -435,6 +435,7 @@ private:
friend class QGraphicsSceneIndex;
friend class QGraphicsSceneIndexPrivate;
friend class QGraphicsSceneBspTreeIndex;
+ friend class QGraphicsSceneBspTreeIndexPrivate;
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 0172a23..4734e74 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -218,6 +218,7 @@
#include "qgraphicswidget.h"
#include "qgraphicswidget_p.h"
#include "qgraphicssceneindex.h"
+#include "qgraphicsscenebsptreeindex_p_p.h"
#include <QtCore/qdebug.h>
#include <QtCore/qlist.h>
@@ -291,8 +292,6 @@ QGraphicsScenePrivate::QGraphicsScenePrivate()
allItemsIgnoreHoverEvents(true),
allItemsUseDefaultCursor(true),
painterStateProtection(true),
- sortCacheEnabled(false),
- updatingSortCache(false),
style(0)
{
}
@@ -1073,175 +1072,6 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item)
return 0;
}
-void QGraphicsScenePrivate::invalidateSortCache()
-{
- Q_Q(QGraphicsScene);
- if (!sortCacheEnabled || updatingSortCache)
- return;
-
- updatingSortCache = true;
- QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);
-}
-
-/*!
- \internal
-
- Should not be exported, but we can't change that now.
- ### Qt 5: Remove symbol / make static
-*/
-inline bool qt_closestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
- // Return true if sibling item1 is on top of item2.
- const QGraphicsItemPrivate *d1 = item1->d_ptr;
- const QGraphicsItemPrivate *d2 = item2->d_ptr;
- bool f1 = d1->flags & QGraphicsItem::ItemStacksBehindParent;
- bool f2 = d2->flags & QGraphicsItem::ItemStacksBehindParent;
- if (f1 != f2) return f2;
- qreal z1 = d1->z;
- qreal z2 = d2->z;
- return z1 != z2 ? z1 > z2 : d1->siblingIndex > d2->siblingIndex;
-}
-
-/*!
- \internal
-
- Should not be exported, but we can't change that now.
-*/
-inline bool qt_closestItemFirst(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
- return QGraphicsScenePrivate::closestItemFirst_withoutCache(item1, item2);
-}
-
-/*!
- Returns true if \a item1 is on top of \a item2.
-
- \internal
-*/
-bool QGraphicsScenePrivate::closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
- // Siblings? Just check their z-values.
- const QGraphicsItemPrivate *d1 = item1->d_ptr;
- const QGraphicsItemPrivate *d2 = item2->d_ptr;
- if (d1->parent == d2->parent)
- return qt_closestLeaf(item1, item2);
-
- // Find common ancestor, and each item's ancestor closest to the common
- // ancestor.
- int item1Depth = d1->depth;
- int item2Depth = d2->depth;
- const QGraphicsItem *p = item1;
- const QGraphicsItem *t1 = item1;
- while (item1Depth > item2Depth && (p = p->d_ptr->parent)) {
- if (p == item2) {
- // item2 is one of item1's ancestors; item1 is on top
- return !(t1->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
- }
- t1 = p;
- --item1Depth;
- }
- p = item2;
- const QGraphicsItem *t2 = item2;
- while (item2Depth > item1Depth && (p = p->d_ptr->parent)) {
- if (p == item1) {
- // item1 is one of item2's ancestors; item1 is not on top
- return (t2->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
- }
- t2 = p;
- --item2Depth;
- }
-
- // item1Ancestor is now at the same level as item2Ancestor, but not the same.
- const QGraphicsItem *a1 = t1;
- const QGraphicsItem *a2 = t2;
- while (a1) {
- const QGraphicsItem *p1 = a1;
- const QGraphicsItem *p2 = a2;
- a1 = a1->parentItem();
- a2 = a2->parentItem();
- if (a1 && a1 == a2)
- return qt_closestLeaf(p1, p2);
- }
-
- // No common ancestor? Then just compare the items' toplevels directly.
- return qt_closestLeaf(t1->topLevelItem(), t2->topLevelItem());
-}
-
-/*!
- Returns true if \a item2 is on top of \a item1.
-
- \internal
-*/
-bool QGraphicsScenePrivate::closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
- return closestItemFirst_withoutCache(item2, item1);
-}
-
-void QGraphicsScenePrivate::climbTree(QGraphicsItem *item, int *stackingOrder)
-{
- if (!item->d_ptr->children.isEmpty()) {
- QList<QGraphicsItem *> childList = item->d_ptr->children;
- qSort(childList.begin(), childList.end(), qt_closestLeaf);
- for (int i = 0; i < childList.size(); ++i) {
- QGraphicsItem *item = childList.at(i);
- if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))
- climbTree(childList.at(i), stackingOrder);
- }
- item->d_ptr->globalStackingOrder = (*stackingOrder)++;
- for (int i = 0; i < childList.size(); ++i) {
- QGraphicsItem *item = childList.at(i);
- if (item->flags() & QGraphicsItem::ItemStacksBehindParent)
- climbTree(childList.at(i), stackingOrder);
- }
- } else {
- item->d_ptr->globalStackingOrder = (*stackingOrder)++;
- }
-}
-
-void QGraphicsScenePrivate::_q_updateSortCache()
-{
- //### FIXME
- QGraphicsSceneBspTreeIndex *tree = qobject_cast<QGraphicsSceneBspTreeIndex*>(index);
- if (tree) {
- tree->_q_updateIndex();
- }
-
- if (!sortCacheEnabled || !updatingSortCache)
- return;
-
- updatingSortCache = false;
- int stackingOrder = 0;
-
- QList<QGraphicsItem *> topLevels;
-
- for (int i = 0; i < index->items().count(); ++i) {
- QGraphicsItem *item = index->items().at(i);
- if (item && item->parentItem() == 0)
- topLevels << item;
- }
-
- qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
- for (int i = 0; i < topLevels.size(); ++i)
- climbTree(topLevels.at(i), &stackingOrder);
-}
-
-void QGraphicsScenePrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
- bool sortCacheEnabled)
-{
- if (sortCacheEnabled) {
- if (order == Qt::AscendingOrder) {
- qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
- } else if (order == Qt::DescendingOrder) {
- qSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
- }
- } else {
- if (order == Qt::AscendingOrder) {
- qSort(itemList->begin(), itemList->end(), closestItemFirst_withoutCache);
- } else if (order == Qt::DescendingOrder) {
- qSort(itemList->begin(), itemList->end(), closestItemLast_withoutCache);
- }
- }
-}
-
/*!
\internal
@@ -1707,15 +1537,25 @@ void QGraphicsScene::setBspTreeDepth(int depth)
bool QGraphicsScene::isSortCacheEnabled() const
{
Q_D(const QGraphicsScene);
- return d->sortCacheEnabled;
+ QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index);
+ if (!bspTree) {
+ qWarning("QGraphicsScene::isSortCacheEnabled: can not apply if indexing method is not BSP");
+ return false;
+ }
+ return bspTree->d_func()->sortCacheEnabled;
}
void QGraphicsScene::setSortCacheEnabled(bool enabled)
{
Q_D(QGraphicsScene);
- if (enabled == d->sortCacheEnabled)
+ QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index);
+ if (!bspTree) {
+ qWarning("QGraphicsScene::isSortCacheEnabled: can not apply if indexing method is not BSP");
return;
- if ((d->sortCacheEnabled = enabled))
- d->invalidateSortCache();
+ }
+ if (enabled == bspTree->d_func()->sortCacheEnabled)
+ return;
+ if ((bspTree->d_func()->sortCacheEnabled = enabled))
+ bspTree->d_func()->invalidateSortCache();
}
/*!
@@ -1910,8 +1750,6 @@ QList<QGraphicsItem *> QGraphicsScene::collidingItems(const QGraphicsItem *item,
if (item != itemInVicinity && item->collidesWithItem(itemInVicinity, mode))
tmp << itemInVicinity;
}
- //### remove me
- d->sortItems(&tmp, Qt::AscendingOrder, d->sortCacheEnabled);
return tmp;
}
@@ -2211,10 +2049,6 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
return;
}
- // Invalidate any sort caching; arrival of a new item means we need to
- // resort.
- d->invalidateSortCache();
-
// Detach this item from its parent if the parent's scene is different
// from this scene.
if (QGraphicsItem *itemParent = item->parentItem()) {
@@ -2232,10 +2066,6 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
if (!item->d_ptr->parent)
d->registerTopLevelItem(item);
- // Update the scene's sort cache settings.
- item->d_ptr->globalStackingOrder = -1;
- d->invalidateSortCache();
-
// Add to list of items that require an update. We cannot assume that the
// item is fully constructed, so calling item->update() can lead to a pure
// virtual function call to boundingRect().
diff --git a/src/gui/graphicsview/qgraphicsscene.h b/src/gui/graphicsview/qgraphicsscene.h
index 5d70087..702813c 100644
--- a/src/gui/graphicsview/qgraphicsscene.h
+++ b/src/gui/graphicsview/qgraphicsscene.h
@@ -290,7 +290,6 @@ private:
Q_PRIVATE_SLOT(d_func(), void _q_removeItemLater(QGraphicsItem *item))
Q_PRIVATE_SLOT(d_func(), void _q_updateLater())
Q_PRIVATE_SLOT(d_func(), void _q_polishItems())
- Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
Q_PRIVATE_SLOT(d_func(), void _q_resetDirtyItems())
friend class QGraphicsItem;
friend class QGraphicsItemPrivate;
@@ -301,6 +300,7 @@ private:
friend class QGraphicsSceneIndex;
friend class QGraphicsSceneIndexPrivate;
friend class QGraphicsSceneBspTreeIndex;
+ friend class QGraphicsSceneBspTreeIndexPrivate;
};
Q_DECLARE_OPERATORS_FOR_FLAGS(QGraphicsScene::SceneLayers)
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index a035159..d2a5cdb 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -187,25 +187,6 @@ public:
void sendMouseEvent(QGraphicsSceneMouseEvent *mouseEvent);
void mousePressEventHandler(QGraphicsSceneMouseEvent *mouseEvent);
QGraphicsWidget *windowForItem(const QGraphicsItem *item) const;
- bool sortCacheEnabled;
- bool updatingSortCache;
- void invalidateSortCache();
- static void climbTree(QGraphicsItem *item, int *stackingOrder);
- void _q_updateSortCache();
-
- static bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
- static bool closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
-
- static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
- {
- return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
- }
- static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
- {
- return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
- }
-
- static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order, bool cached);
void drawItemHelper(QGraphicsItem *item, QPainter *painter,
const QStyleOptionGraphicsItem *option, QWidget *widget,
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
index f8f1f56..19aa9d5 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
@@ -39,9 +39,15 @@
**
****************************************************************************/
+
static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
#include "qgraphicsscenebsptreeindex_p.h"
+
+#ifndef QT_NO_GRAPHICSVIEW
+
+#include "qgraphicsscenebsptreeindex_p_p.h"
+#include "qgraphicssceneindex_p.h"
#include "qgraphicsitem_p.h"
#include "qgraphicsscene_p.h"
@@ -49,51 +55,365 @@ static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
#include <QtCore/qdebug.h>
-QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)
- : QGraphicsSceneIndex(scene),
+QT_BEGIN_NAMESPACE
+
+static inline int intmaxlog(int n)
+{
+ return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);
+}
+
+/*!
+ Constructs a private scene index.
+*/
+QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene)
+ : scene(scene),
bspTreeDepth(0),
indexTimerId(0),
restartIndexTimer(false),
regenerateIndex(true),
lastItemCount(0),
- purgePending(false)
+ purgePending(false),
+ sortCacheEnabled(false),
+ updatingSortCache(false)
+{
+}
+
+
+/*!
+ \internal
+*/
+void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex()
{
+ Q_Q(QGraphicsSceneBspTreeIndex);
+ if (!indexTimerId)
+ return;
+ QGraphicsScenePrivate * scenePrivate = q->scene()->d_func();
+ q->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;
+ indexedItems[freeIndex] = item;
+ } else {
+ item->d_func()->index = indexedItems.size();
+ indexedItems << item;
+ }
+ }
+ }
+
+ // Update growing scene rect.
+ QRectF oldGrowingItemsBoundingRect = scenePrivate->growingItemsBoundingRect;
+ scenePrivate->growingItemsBoundingRect |= unindexedItemsBoundingRect;
+
+ // Determine whether we should regenerate the BSP tree.
+ if (bspTreeDepth == 0) {
+ int oldDepth = intmaxlog(lastItemCount);
+ bspTreeDepth = intmaxlog(indexedItems.size());
+ static const int slack = 100;
+ if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - indexedItems.size()) > slack)) {
+ // ### Crude algorithm.
+ regenerateIndex = true;
+ }
+ }
+
+ // Regenerate the tree.
+ if (regenerateIndex) {
+ regenerateIndex = false;
+ bsp.initialize(q->scene()->sceneRect(), bspTreeDepth);
+ unindexedItems = indexedItems;
+ lastItemCount = indexedItems.size();
+ q->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.
+ scenePrivate->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.
+ scenePrivate->largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect();
+ }
+ }
+ }
+ unindexedItems.clear();
+
+ // Notify scene rect changes.
+ if (!scenePrivate->hasSceneRect && scenePrivate->growingItemsBoundingRect != oldGrowingItemsBoundingRect)
+ emit q->scene()->sceneRectChanged(scenePrivate->growingItemsBoundingRect);
}
-QRectF QGraphicsSceneBspTreeIndex::indexedRect()
+
+/*!
+ \internal
+
+ Removes stale pointers from all data structures.
+*/
+void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems()
+{
+ Q_Q(QGraphicsSceneBspTreeIndex);
+ 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 < indexedItems.size(); ++i) {
+ if (!indexedItems.at(i))
+ freeItemIndexes << i;
+ }
+ purgePending = false;
+
+ // No locality info for the items; update the whole scene.
+ q->scene()->update();
+}
+
+/*!
+ \internal
+
+ Starts or restarts the timer used for reindexing unindexed items.
+*/
+void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer()
+{
+ Q_Q(QGraphicsSceneBspTreeIndex);
+ if (indexTimerId) {
+ restartIndexTimer = true;
+ } else {
+ indexTimerId = q->startTimer(QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
+ }
+}
+
+/*!
+ \internal
+*/
+void QGraphicsSceneBspTreeIndexPrivate::resetIndex()
+{
+ purgeRemovedItems();
+ for (int i = 0; i < indexedItems.size(); ++i) {
+ if (QGraphicsItem *item = indexedItems.at(i)) {
+ item->d_ptr->index = -1;
+ unindexedItems << item;
+ }
+ }
+ indexedItems.clear();
+ freeItemIndexes.clear();
+ regenerateIndex = true;
+ startIndexTimer();
+}
+
+void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder)
{
+ if (!item->d_ptr->children.isEmpty()) {
+ QList<QGraphicsItem *> childList = item->d_ptr->children;
+ qSort(childList.begin(), childList.end(), qt_closestLeaf);
+ for (int i = 0; i < childList.size(); ++i) {
+ QGraphicsItem *item = childList.at(i);
+ if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))
+ climbTree(childList.at(i), stackingOrder);
+ }
+ item->d_ptr->globalStackingOrder = (*stackingOrder)++;
+ for (int i = 0; i < childList.size(); ++i) {
+ QGraphicsItem *item = childList.at(i);
+ if (item->flags() & QGraphicsItem::ItemStacksBehindParent)
+ climbTree(childList.at(i), stackingOrder);
+ }
+ } else {
+ item->d_ptr->globalStackingOrder = (*stackingOrder)++;
+ }
+}
+
+void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache()
+{
+ Q_Q(QGraphicsSceneBspTreeIndex);
_q_updateIndex();
+
+ if (!sortCacheEnabled || !updatingSortCache)
+ return;
+
+ updatingSortCache = false;
+ int stackingOrder = 0;
+
+ QList<QGraphicsItem *> topLevels;
+
+ for (int i = 0; i < q->items().count(); ++i) {
+ QGraphicsItem *item = q->items().at(i);
+ if (item && item->parentItem() == 0)
+ topLevels << item;
+ }
+
+ qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
+ for (int i = 0; i < topLevels.size(); ++i)
+ climbTree(topLevels.at(i), &stackingOrder);
+}
+
+void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache()
+{
+ Q_Q(QGraphicsSceneBspTreeIndex);
+ if (!sortCacheEnabled || updatingSortCache)
+ return;
+
+ updatingSortCache = true;
+ QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);
+}
+
+/*!
+ Returns true if \a item1 is on top of \a item2.
+
+ \internal
+*/
+bool QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
+{
+ // Siblings? Just check their z-values.
+ const QGraphicsItemPrivate *d1 = item1->d_ptr;
+ const QGraphicsItemPrivate *d2 = item2->d_ptr;
+ if (d1->parent == d2->parent)
+ return qt_closestLeaf(item1, item2);
+
+ // Find common ancestor, and each item's ancestor closest to the common
+ // ancestor.
+ int item1Depth = d1->depth;
+ int item2Depth = d2->depth;
+ const QGraphicsItem *p = item1;
+ const QGraphicsItem *t1 = item1;
+ while (item1Depth > item2Depth && (p = p->d_ptr->parent)) {
+ if (p == item2) {
+ // item2 is one of item1's ancestors; item1 is on top
+ return !(t1->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
+ }
+ t1 = p;
+ --item1Depth;
+ }
+ p = item2;
+ const QGraphicsItem *t2 = item2;
+ while (item2Depth > item1Depth && (p = p->d_ptr->parent)) {
+ if (p == item1) {
+ // item1 is one of item2's ancestors; item1 is not on top
+ return (t2->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
+ }
+ t2 = p;
+ --item2Depth;
+ }
+
+ // item1Ancestor is now at the same level as item2Ancestor, but not the same.
+ const QGraphicsItem *a1 = t1;
+ const QGraphicsItem *a2 = t2;
+ while (a1) {
+ const QGraphicsItem *p1 = a1;
+ const QGraphicsItem *p2 = a2;
+ a1 = a1->parentItem();
+ a2 = a2->parentItem();
+ if (a1 && a1 == a2)
+ return qt_closestLeaf(p1, p2);
+ }
+
+ // No common ancestor? Then just compare the items' toplevels directly.
+ return qt_closestLeaf(t1->topLevelItem(), t2->topLevelItem());
+}
+
+/*!
+ Returns true if \a item2 is on top of \a item1.
+
+ \internal
+*/
+bool QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
+{
+ return closestItemFirst_withoutCache(item2, item1);
+}
+
+void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
+ bool sortCacheEnabled)
+{
+ if (sortCacheEnabled) {
+ if (order == Qt::AscendingOrder) {
+ qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
+ } else if (order == Qt::DescendingOrder) {
+ qSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
+ }
+ } else {
+ if (order == Qt::AscendingOrder) {
+ qSort(itemList->begin(), itemList->end(), closestItemFirst_withoutCache);
+ } else if (order == Qt::DescendingOrder) {
+ qSort(itemList->begin(), itemList->end(), closestItemLast_withoutCache);
+ }
+ }
+}
+
+QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)
+ : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene)
+{
+
+}
+
+QRectF QGraphicsSceneBspTreeIndex::indexedRect() const
+{
+ Q_D(const QGraphicsSceneBspTreeIndex);
+ const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->_q_updateIndex();
return scene()->d_func()->hasSceneRect ? scene()->d_func()->sceneRect : scene()->d_func()->growingItemsBoundingRect;
}
void QGraphicsSceneBspTreeIndex::clear()
{
- bsp.clear();
- lastItemCount = 0;
- freeItemIndexes.clear();
- m_indexedItems.clear();
- unindexedItems.clear();
+ Q_D(QGraphicsSceneBspTreeIndex);
+ d->bsp.clear();
+ d->lastItemCount = 0;
+ d->freeItemIndexes.clear();
+ d->indexedItems.clear();
+ d->unindexedItems.clear();
}
void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item)
{
+ Q_D(QGraphicsSceneBspTreeIndex);
// Prevent reusing a recently deleted pointer: purge all removed items
// from our lists.
- purgeRemovedItems();
+ d->purgeRemovedItems();
+
+ // Invalidate any sort caching; arrival of a new item means we need to
+ // resort.
+ // Update the scene's sort cache settings.
+ item->d_ptr->globalStackingOrder = -1;
+ d->invalidateSortCache();
// 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;
+ d->unindexedItems << item;
item->d_func()->index = -1;
- startIndexTimer();
+ d->startIndexTimer();
}
/*!
\internal
*/
-void QGraphicsSceneBspTreeIndex::addToIndex(QGraphicsItem *item)
+void QGraphicsSceneBspTreeIndexPrivate::addToIndex(QGraphicsItem *item)
{
if (item->d_func()->index != -1) {
bsp.insertItem(item, item->sceneBoundingRect());
@@ -109,37 +429,47 @@ void QGraphicsSceneBspTreeIndex::addToIndex(QGraphicsItem *item)
void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item)
{
+ Q_D(QGraphicsSceneBspTreeIndex);
// Note: This will access item's sceneBoundingRect(), which (as this is
// C++) is why we cannot call removeItem() from QGraphicsItem's
// destructor.
- removeFromIndex(item);
+ d->removeFromIndex(item);
+
+ // Invalidate any sort caching; arrival of a new item means we need to
+ // resort.
+ d->invalidateSortCache();
// Remove from our item lists.
int index = item->d_func()->index;
if (index != -1) {
- freeItemIndexes << index;
- m_indexedItems[index] = 0;
+ d->freeItemIndexes << index;
+ d->indexedItems[index] = 0;
} else {
- unindexedItems.removeAll(item);
+ d->unindexedItems.removeAll(item);
}
}
void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item)
{
+ Q_D(QGraphicsSceneBspTreeIndex);
+ // Invalidate any sort caching; arrival of a new item means we need to
+ // resort.
+ d->invalidateSortCache();
+
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;
+ d->indexedItems[index] = (QGraphicsItem *)0;
+ if (!d->purgePending) {
+ d->purgePending = true;
scene()->update();
}
- removedItems << item;
+ d->removedItems << item;
} else {
// Recently added items are purged immediately. unindexedItems() never
// contains stale items.
- unindexedItems.removeAll(item);
+ d->unindexedItems.removeAll(item);
scene()->update();
}
}
@@ -147,7 +477,7 @@ void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item)
/*!
\internal
*/
-void QGraphicsSceneBspTreeIndex::removeFromIndex(QGraphicsItem *item)
+void QGraphicsSceneBspTreeIndexPrivate::removeFromIndex(QGraphicsItem *item)
{
if (item->d_func()->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) {
// ### remove from child index only if applicable
@@ -157,7 +487,7 @@ void QGraphicsSceneBspTreeIndex::removeFromIndex(QGraphicsItem *item)
if (index != -1) {
bsp.removeItem(item, item->sceneBoundingRect());
freeItemIndexes << index;
- m_indexedItems[index] = 0;
+ indexedItems[index] = 0;
item->d_func()->index = -1;
unindexedItems << item;
@@ -170,21 +500,23 @@ void QGraphicsSceneBspTreeIndex::removeFromIndex(QGraphicsItem *item)
void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item)
{
+ Q_D(QGraphicsSceneBspTreeIndex);
// Note: This will access item's sceneBoundingRect(), which (as this is
// C++) is why we cannot call removeItem() from QGraphicsItem's
// destructor.
- removeFromIndex(const_cast<QGraphicsItem *>(item));
+ d->removeFromIndex(const_cast<QGraphicsItem *>(item));
}
QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const
{
- const_cast<QGraphicsSceneBspTreeIndex*>(this)->purgeRemovedItems();
- scene()->d_func()->_q_updateSortCache();
+ Q_D(const QGraphicsSceneBspTreeIndex);
+ const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems();
+ const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->_q_updateSortCache();
- QList<QGraphicsItem *> rectItems = bsp.items(rect);
+ QList<QGraphicsItem *> rectItems = d->bsp.items(rect);
// Fill in with any unindexed items
- for (int i = 0; i < unindexedItems.size(); ++i) {
- if (QGraphicsItem *item = unindexedItems.at(i)) {
+ for (int i = 0; i < d->unindexedItems.size(); ++i) {
+ if (QGraphicsItem *item = d->unindexedItems.at(i)) {
if (!item->d_ptr->itemDiscovered && item->d_ptr->visible && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) {
QRectF boundingRect = item->sceneBoundingRect();
if (QRectF_intersects(boundingRect, rect)) {
@@ -199,57 +531,83 @@ QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &r
for (int i = 0; i < rectItems.size(); ++i)
rectItems.at(i)->d_func()->itemDiscovered = 0;
+ d->sortItems(&rectItems, order, d->sortCacheEnabled);
+
return rectItems;
}
-QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items() const
+QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) const
{
- const_cast<QGraphicsSceneBspTreeIndex*>(this)->purgeRemovedItems();
+ Q_D(const QGraphicsSceneBspTreeIndex);
+ const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems();
+ QList<QGraphicsItem *> itemList;
// 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<QGraphicsItem *> itemList;
- foreach (QGraphicsItem *item, m_indexedItems + unindexedItems) {
- if (item)
- itemList << item;
+ if (d->freeItemIndexes.isEmpty()) {
+ if (d->unindexedItems.isEmpty()) {
+ itemList = d->indexedItems;
+ } else {
+ itemList = d->indexedItems + d->unindexedItems;
+ }
+ } else {
+ // Rebuild the list of items to avoid holes. ### We could also just
+ // compress the item lists at this point.
+ foreach (QGraphicsItem *item, d->indexedItems + d->unindexedItems) {
+ if (item)
+ itemList << item;
+ }
}
+ //We sort descending order
+ d->sortItems(&itemList, order, d->sortCacheEnabled);
return itemList;
}
int QGraphicsSceneBspTreeIndex::bspDepth()
{
- return bspTreeDepth;
+ Q_D(const QGraphicsSceneBspTreeIndex);
+ return d->bspTreeDepth;
}
void QGraphicsSceneBspTreeIndex::setBspDepth(int depth)
{
- bspTreeDepth = depth;
- resetIndex();
+ Q_D(QGraphicsSceneBspTreeIndex);
+ d->bspTreeDepth = depth;
+ d->resetIndex();
}
void QGraphicsSceneBspTreeIndex::sceneRectChanged(const QRectF &rect)
{
- m_sceneRect = rect;
- resetIndex();
+ Q_D(QGraphicsSceneBspTreeIndex);
+ d->sceneRect = rect;
+ d->resetIndex();
+}
+
+void QGraphicsSceneBspTreeIndex::itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value)
+{
+ Q_D(QGraphicsSceneBspTreeIndex);
+ switch (change) {
+ case QGraphicsItem::ItemZValueChange:
+ case QGraphicsItem::ItemParentChange: {
+ d->invalidateSortCache();
+ break;
+ }
+ default:
+ break;
+ }
+ return QGraphicsSceneIndex::itemChanged(item, change, value);
}
bool QGraphicsSceneBspTreeIndex::event(QEvent *event)
{
+ Q_D(QGraphicsSceneBspTreeIndex);
switch (event->type()) {
case QEvent::Timer:
- if (indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == indexTimerId) {
- if (restartIndexTimer) {
- restartIndexTimer = false;
+ if (d->indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == d->indexTimerId) {
+ if (d->restartIndexTimer) {
+ d->restartIndexTimer = false;
} else {
// this call will kill the timer
- _q_updateIndex();
+ d->_q_updateIndex();
}
}
// Fallthrough intended - support timers in subclasses.
@@ -259,153 +617,9 @@ bool QGraphicsSceneBspTreeIndex::event(QEvent *event)
return true;
}
-static inline int intmaxlog(int n)
-{
- return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);
-}
+QT_END_NAMESPACE
-/*!
- \internal
-*/
-void QGraphicsSceneBspTreeIndex::_q_updateIndex()
-{
- if (!indexTimerId)
- return;
+#include "moc_qgraphicsscenebsptreeindex_p.cpp"
- killTimer(indexTimerId);
- indexTimerId = 0;
+#endif // QT_NO_GRAPHICSVIEW
- 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
index 7a6ea0b..b1ea977 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
@@ -56,56 +56,41 @@ QT_BEGIN_NAMESPACE
#include "qgraphicsscene_bsp_p.h"
+class QGraphicsSceneBspTreeIndexPrivate;
class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
{
Q_OBJECT
public:
QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0);
- QRectF indexedRect();
-
- void clear();
-
- void addItem(QGraphicsItem *item);
- void removeItem(QGraphicsItem *item);
- void deleteItem(QGraphicsItem *item);
- void prepareBoundingRectChange(const QGraphicsItem *item);
+ QRectF indexedRect() const;
QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const;
- QList<QGraphicsItem *> items() const;
+ QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const;
int bspDepth();
void setBspDepth(int depth);
protected:
bool event(QEvent *event);
- void sceneRectChanged(const QRectF &rect);
+ void clear();
+
+ void addItem(QGraphicsItem *item);
+ void removeItem(QGraphicsItem *item);
+ void deleteItem(QGraphicsItem *item);
+ void prepareBoundingRectChange(const QGraphicsItem *item);
-public slots :
- void _q_updateIndex();
+ void sceneRectChanged(const QRectF &rect);
+ void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value);
private :
- QGraphicsSceneBspTree bsp;
- QRectF m_sceneRect;
- int bspTreeDepth;
- int indexTimerId;
- bool restartIndexTimer;
- bool regenerateIndex;
- int lastItemCount;
-
- QList<QGraphicsItem *> m_indexedItems;
- QList<QGraphicsItem *> unindexedItems;
- QList<int> freeItemIndexes;
-
- bool purgePending;
- QList<QGraphicsItem *> removedItems;
- void purgeRemovedItems();
-
- void startIndexTimer();
- void resetIndex();
-
- void addToIndex(QGraphicsItem *item);
- void removeFromIndex(QGraphicsItem *item);
+ Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex)
+ Q_DISABLE_COPY(QGraphicsSceneBspTreeIndex)
+ Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
+ Q_PRIVATE_SLOT(d_func(), void _q_updateIndex())
+
+ friend class QGraphicsScene;
+ friend class QGraphicsScenePrivate;
};
QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h
new file mode 100644
index 0000000..2df5fbc
--- /dev/null
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h
@@ -0,0 +1,140 @@
+/****************************************************************************
+**
+** 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 QGRAPHICSSCENEBSPTREEINDEX_P_P_H
+#define QGRAPHICSSCENEBSPTREEINDEX_P_P_H
+
+//
+// W A R N I N G
+// -------------
+//
+// This file is not part of the Qt API. It exists for the convenience
+// of qapplication_*.cpp, qwidget*.cpp and qfiledialog.cpp. This header
+// file may change from version to version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include "qgraphicsscenebsptreeindex_p.h"
+
+#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
+
+#include <private/qobject_p.h>
+#include <private/qgraphicsitem_p.h>
+
+QT_BEGIN_NAMESPACE
+
+class QGraphicsScene;
+
+class QGraphicsSceneBspTreeIndexPrivate : public QObjectPrivate
+{
+ Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)
+public:
+ QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);
+
+ QGraphicsScene *scene;
+ QGraphicsSceneBspTree bsp;
+ QRectF sceneRect;
+ int bspTreeDepth;
+ int indexTimerId;
+ bool restartIndexTimer;
+ bool regenerateIndex;
+ int lastItemCount;
+
+ QList<QGraphicsItem *> indexedItems;
+ QList<QGraphicsItem *> unindexedItems;
+ QList<int> freeItemIndexes;
+
+ bool purgePending;
+ QList<QGraphicsItem *> removedItems;
+ void purgeRemovedItems();
+
+ void _q_updateIndex();
+ void startIndexTimer();
+ void resetIndex();
+
+ void addToIndex(QGraphicsItem *item);
+ void removeFromIndex(QGraphicsItem *item);
+
+ void _q_updateSortCache();
+ bool sortCacheEnabled;
+ bool updatingSortCache;
+ void invalidateSortCache();
+
+ static void climbTree(QGraphicsItem *item, int *stackingOrder);
+ static bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
+ static bool closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
+
+ static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
+ {
+ return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
+ }
+ static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
+ {
+ return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
+ }
+
+ static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order, bool cached);
+};
+
+
+/*!
+ \internal
+*/
+inline bool qt_closestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
+{
+ // Return true if sibling item1 is on top of item2.
+ const QGraphicsItemPrivate *d1 = item1->d_ptr;
+ const QGraphicsItemPrivate *d2 = item2->d_ptr;
+ bool f1 = d1->flags & QGraphicsItem::ItemStacksBehindParent;
+ bool f2 = d2->flags & QGraphicsItem::ItemStacksBehindParent;
+ if (f1 != f2) return f2;
+ qreal z1 = d1->z;
+ qreal z2 = d2->z;
+ return z1 != z2 ? z1 > z2 : d1->siblingIndex > d2->siblingIndex;
+}
+
+QT_END_NAMESPACE
+
+#endif // QGRAPHICSSCENEBSPTREEINDEX_P_P_H
+
+#endif
+
diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp
index d0d6081..eeee74e 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.cpp
+++ b/src/gui/graphicsview/qgraphicssceneindex.cpp
@@ -41,6 +41,7 @@
#include "qgraphicssceneindex.h"
#include "qgraphicssceneindex_p.h"
+#include "qgraphicsscenebsptreeindex_p_p.h"
#include "qgraphicsscene.h"
#include "qgraphicsitem_p.h"
#include "qgraphicsscene_p.h"
@@ -282,6 +283,14 @@ QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene)
}
/*!
+ \internal
+*/
+QGraphicsSceneIndex::QGraphicsSceneIndex(QObjectPrivate &dd, QGraphicsScene *scene)
+ : QObject(dd, scene)
+{
+}
+
+/*!
Destroys the scene index.
*/
QGraphicsSceneIndex::~QGraphicsSceneIndex()
@@ -301,7 +310,7 @@ QGraphicsScene* QGraphicsSceneIndex::scene() const
/*!
Returns the indexed area for the index
*/
-QRectF QGraphicsSceneIndex::indexedRect()
+QRectF QGraphicsSceneIndex::indexedRect() const
{
Q_D(const QGraphicsSceneIndex);
return d->scene->d_func()->sceneRect;
@@ -351,8 +360,9 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, Qt::ItemSe
d->childItems_helper(&items, item, xinv.map(pos));
}
}
-
- d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+ //### Needed but it should be handle differently
+ if (order != Qt::SortOrder(-1))
+ QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false);
return items;
}
@@ -415,9 +425,9 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, Qt::ItemSe
}
}
}
-
+ //### Needed but it should be handle differently
if (order != Qt::SortOrder(-1))
- d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+ QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false);
return items;
}
@@ -474,9 +484,9 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF &polygon, Qt::
d->childItems_helper(&items, item, xinv.map(polygon), mode);
}
}
-
+ //### Needed but it should be handle differently
if (order != Qt::SortOrder(-1))
- d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+ QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false);
return items;
}
QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
@@ -525,9 +535,9 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::
d->childItems_helper(&items, item, xinv.map(path), mode);
}
}
-
+ //### Needed but it should be handle differently
if (order != Qt::SortOrder(-1))
- d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+ QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false);
return items;
}
diff --git a/src/gui/graphicsview/qgraphicssceneindex.h b/src/gui/graphicsview/qgraphicssceneindex.h
index 11d9aae..084a623 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.h
+++ b/src/gui/graphicsview/qgraphicssceneindex.h
@@ -71,9 +71,9 @@ public:
QGraphicsScene *scene() const;
- virtual QRectF indexedRect();
+ virtual QRectF indexedRect() const;
- virtual QList<QGraphicsItem *> items() const = 0;
+ virtual QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const = 0;
virtual QList<QGraphicsItem *> items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
virtual QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
virtual QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
@@ -91,10 +91,15 @@ protected:
virtual void prepareBoundingRectChange(const QGraphicsItem *item);
virtual void sceneRectChanged(const QRectF &rect);
+ QGraphicsSceneIndex(QObjectPrivate &dd, QGraphicsScene *scene);
+
friend class QGraphicsScene;
friend class QGraphicsScenePrivate;
friend class QGraphicsItem;
+ friend class QGraphicsItemPrivate;
+ friend class QGraphicsSceneBspTreeIndex;
private:
+ Q_DISABLE_COPY(QGraphicsSceneIndex)
Q_DECLARE_PRIVATE(QGraphicsSceneIndex)
};
diff --git a/src/gui/graphicsview/qgraphicssceneindex_p.h b/src/gui/graphicsview/qgraphicssceneindex_p.h
index f2cdca3..2014693 100644
--- a/src/gui/graphicsview/qgraphicssceneindex_p.h
+++ b/src/gui/graphicsview/qgraphicssceneindex_p.h
@@ -58,6 +58,7 @@
#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
#include <private/qobject_p.h>
+#include <private/qgraphicsitem_p.h>
QT_BEGIN_NAMESPACE
@@ -86,7 +87,7 @@ public:
const QPainterPath &path,
Qt::ItemSelectionMode mode) const;
- QGraphicsScene *scene;
+ QGraphicsScene *scene;
};
QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
index dc45a17..3057b4a 100644
--- a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
@@ -105,7 +105,7 @@ public:
return result;
}
- QList<QGraphicsItem *> items() const {
+ QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const {
return m_items;
}
};
diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp
index 91f97a1..e8330a9 100644
--- a/src/gui/graphicsview/qgraphicsview.cpp
+++ b/src/gui/graphicsview/qgraphicsview.cpp
@@ -1056,7 +1056,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg
*allItems = true;
// All items are guaranteed within the exposed region, don't bother using the index.
- QList<QGraphicsItem *> itemList(scene->items());
+ QList<QGraphicsItem *> itemList(scene->d_func()->index->items(Qt::DescendingOrder));
int i = 0;
while (i < itemList.size()) {
const QGraphicsItem *item = itemList.at(i);
@@ -1069,9 +1069,6 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg
else
++i;
}
-
- // Sort the items.
- QGraphicsScenePrivate::sortItems(&itemList, Qt::DescendingOrder, scene->d_func()->sortCacheEnabled);
return itemList;
}
@@ -2134,7 +2131,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat
// Then find the minimal list of items that are inside \a path, and
// convert it to a set.
- QList<QGraphicsItem *> regularCandidates = scene->items(q->mapToScene(path), mode);
+ QList<QGraphicsItem *> regularCandidates = scene->items(q->mapToScene(path), mode, order, q->transform());
QSet<QGraphicsItem *> candSet = QSet<QGraphicsItem *>::fromList(regularCandidates);
QTransform viewMatrix = q->viewportTransform();
@@ -2161,10 +2158,6 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat
}
++it;
}
-
- // ### Insertion sort would be faster.
- if (order != Qt::SortOrder(-1))
- QGraphicsScenePrivate::sortItems(&result, order, scene->d_func()->sortCacheEnabled);
return result;
}
diff --git a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
index 8afdeb4..c83134f 100644
--- a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
+++ b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
@@ -4685,6 +4685,11 @@ void tst_QGraphicsItem::itemClipsChildrenToShape()
scene.render(&painter);
painter.end();
+ QGraphicsView view(&scene);
+ view.show();
+
+ QTest::qWait(5000);
+
QCOMPARE(image.pixel(16, 16), QColor(255, 0, 0).rgba());
QCOMPARE(image.pixel(32, 32), QColor(0, 0, 255).rgba());
QCOMPARE(image.pixel(50, 50), QColor(0, 255, 0).rgba());
diff --git a/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp b/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp
index eb117ab..dd997c7 100644
--- a/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp
+++ b/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp
@@ -379,8 +379,7 @@ void tst_QGraphicsScene::items()
for (int x = minX; x < maxX; x += 100)
items << scene.addRect(QRectF(0, 0, 10, 10));
}
-
- QCOMPARE(scene.items(), items);
+ QCOMPARE(scene.items().size(), items.size());
scene.itemAt(0, 0); // trigger indexing
scene.removeItem(items.at(5));
@@ -397,7 +396,7 @@ void tst_QGraphicsScene::items()
QVERIFY(!l2->sceneBoundingRect().intersects(l1->sceneBoundingRect()));
QList<QGraphicsItem *> items;
items<<l1<<l2;
- QCOMPARE(scene.items(), items);
+ QCOMPARE(scene.items().size(), items.size());
QVERIFY(scene.items(-1, -1, 2, 2).contains(l1));
QVERIFY(scene.items(-1, -1, 2, 2).contains(l2));
}
diff --git a/tests/auto/qgraphicsview/tst_qgraphicsview.cpp b/tests/auto/qgraphicsview/tst_qgraphicsview.cpp
index 8e490ad..447de34 100644
--- a/tests/auto/qgraphicsview/tst_qgraphicsview.cpp
+++ b/tests/auto/qgraphicsview/tst_qgraphicsview.cpp
@@ -2102,12 +2102,12 @@ void tst_QGraphicsView::resizeAnchor()
view.setResizeAnchor(QGraphicsView::AnchorViewCenter);
}
view.centerOn(0, 0);
- QTest::qWait(100);
+ QTest::qWait(250);
QPointF f = view.mapToScene(50, 50);
QPointF center = view.mapToScene(view.viewport()->rect().center());
- QTest::qWait(100);
+ QTest::qWait(250);
for (int size = 200; size <= 400; size += 25) {
view.resize(size, size);
@@ -2122,7 +2122,7 @@ void tst_QGraphicsView::resizeAnchor()
QVERIFY(qAbs(newCenter.x() - center.x()) < slack);
QVERIFY(qAbs(newCenter.y() - center.y()) < slack);
}
- QTest::qWait(100);
+ QTest::qWait(250);
}
}
}
@@ -2925,7 +2925,7 @@ void tst_QGraphicsView::task245469_itemsAtPointWithClip()
QTest::qWait(100);
QList<QGraphicsItem *> itemsAtCenter = view.items(view.viewport()->rect().center());
- QCOMPARE(itemsAtCenter, (QList<QGraphicsItem *>() << child << parent));
+ QCOMPARE(itemsAtCenter, (QList<QGraphicsItem *>() << parent << child));
QPolygonF p = view.mapToScene(QRect(view.viewport()->rect().center(), QSize(1, 1)));
QList<QGraphicsItem *> itemsAtCenter2 = scene.items(p);
generated by cgit v0.12 at 2025-01-05 00:18:12 (GMT)