summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/gui/graphicsview/graphicsview.pri4
-rw-r--r--src/gui/graphicsview/qgraphicsitem.cpp10
-rw-r--r--src/gui/graphicsview/qgraphicsitem.h1
-rw-r--r--src/gui/graphicsview/qgraphicsscene.cpp390
-rw-r--r--src/gui/graphicsview/qgraphicsscene.h2
-rw-r--r--src/gui/graphicsview/qgraphicsscene_bsp.cpp40
-rw-r--r--src/gui/graphicsview/qgraphicsscene_bsp_p.h27
-rw-r--r--src/gui/graphicsview/qgraphicsscene_p.h20
-rw-r--r--src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp437
-rw-r--r--src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h118
-rw-r--r--src/gui/graphicsview/qgraphicssceneindex.cpp14
-rw-r--r--src/gui/graphicsview/qgraphicssceneindex.h15
-rw-r--r--src/gui/graphicsview/qgraphicsscenelinearindex_p.h (renamed from src/gui/graphicsview/qgraphicsscene_linear_p.h)6
-rw-r--r--tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp15
14 files changed, 647 insertions, 452 deletions
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<QRectF>)"));
@@ -383,220 +376,14 @@ void QGraphicsScenePrivate::init()
*/
QList<QGraphicsItem *> QGraphicsScenePrivate::estimateItemsInRect(const QRectF &rect) const
{
- const_cast<QGraphicsScenePrivate *>(this)->purgeRemovedItems();
const_cast<QGraphicsScenePrivate *>(this)->_q_updateSortCache();
- if (indexMethod != QGraphicsScene::NoIndex) {
- // ### Only do this once in a while.
- QGraphicsScenePrivate *that = const_cast<QGraphicsScenePrivate *>(this);
-
- QList<QGraphicsItem *> 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<QGraphicsItem *> 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<QGraphicsScenePrivate *>(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<QGraphicsSceneBspTree*>(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<QGraphicsSceneBspTree *>(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<QGraphicsSceneBspTree *>(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<QGraphicsItem *> 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<QGraphicsScenePrivate *>(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<QGraphicsSceneBspTree*>(d->index);
+ QGraphicsSceneBspTreeIndex *tree = qobject_cast<QGraphicsSceneBspTreeIndex*>(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<QGraphicsSceneBspTree*>(d->index);
- return bspTree ? bspTree->depth : 0;
+ QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(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<QGraphicsSceneBspTree*>(d->index);
+ QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(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<QGraphicsItem *> QGraphicsScene::items() const
{
Q_D(const QGraphicsScene);
- const_cast<QGraphicsScenePrivate *>(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<QGraphicsItem *> 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<QGraphicsItem *> 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<QGraphicsWidget *>(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<QTimerEvent *>(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<QGraphicsItem *> &items)
+void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items)
{
for (int i = 0; i < leaves.size(); ++i) {
QList<QGraphicsItem *> 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 <QtCore/qrect.h>
#include <QtCore/qset.h>
#include <QtCore/qvector.h>
-#include <QtGui/qgraphicssceneindex.h>
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<QGraphicsItem *> &items);
+ void insertItem(QGraphicsItem *item, const QRectF &rect);
+ void removeItem(QGraphicsItem *item, const QRectF &rect);
+ void removeItems(const QSet<QGraphicsItem *> &items);
- QList<QGraphicsItem *> items(const QPointF &point);
QList<QGraphicsItem *> items(const QRectF &rect);
-
+ QList<QGraphicsItem *> 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<Node> nodes;
QVector<QList<QGraphicsItem *> > leaves;
int leafCnt;
- QRectF sceneRect;
+ QRectF rect;
QGraphicsSceneInsertItemBspTreeVisitor *insertVisitor;
QGraphicsSceneRemoveItemBspTreeVisitor *removeVisitor;
@@ -139,8 +130,6 @@ public:
virtual void visit(QList<QGraphicsItem *> *items) = 0;
};
-Q_DECLARE_TYPEINFO(QGraphicsSceneBspTree::Node, Q_PRIMITIVE_TYPE);
-
QT_END_NAMESPACE
#endif // QT_NO_GRAPHICSVIEW
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<QGraphicsItem *> 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<QGraphicsItem *> selectedItems;
- QList<QGraphicsItem *> indexedItems;
QList<QGraphicsItem *> dirtyItems;
QList<QGraphicsItem *> pendingUpdateItems;
QList<QGraphicsItem *> unpolishedItems;
@@ -127,21 +121,11 @@ public:
void resetDirtyItemsLater();
bool dirtyItemResetPending;
- QList<int> freeItemIndexes;
- bool regenerateIndex;
-
- bool purgePending;
void _q_removeItemLater(QGraphicsItem *item);
- QList<QGraphicsItem *> 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 <QtCore/qmath.h>
+
+#include <QtCore/qdebug.h>
+
+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<QGraphicsSceneBspTreeIndex *>(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<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(const QPointF &point)
+{
+ purgeRemovedItems();
+ QList<QGraphicsItem *> 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<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(const QRectF &rect)
+{
+ purgeRemovedItems();
+ QList<QGraphicsItem *> 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<QGraphicsItem *> 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<QGraphicsItem *> 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<QTimerEvent *>(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 <QtCore/qglobal.h>
+
+#ifndef QGRAPHICSBSPTREEINDEX_H
+#define QGRAPHICSBSPTREEINDEX_H
+
+#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
+
+QT_BEGIN_NAMESPACE
+
+#include <QtCore/qrect.h>
+#include <QtCore/qlist.h>
+#include <QtGui/qgraphicsitem.h>
+#include <QtGui/qgraphicsscene.h>
+#include <QtGui/qgraphicssceneindex.h>
+
+#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<QGraphicsItem *> items(const QPointF &point);
+ QList<QGraphicsItem *> items(const QRectF &rect);
+
+ QList<QGraphicsItem *> 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<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);
+};
+
+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<QGraphicsItem *> &items)
\sa removeItem(), removeItems(), updateItems()
*/
-void QGraphicsSceneIndex::removeItems(const QList<QGraphicsItem *> &items)
+void QGraphicsSceneIndex::removeItems(const QList<QGraphicsItem *> &items, bool itemsAreAboutToDie)
{
foreach (QGraphicsItem *item, items)
- removeItem(item);
+ removeItem(item,itemsAreAboutToDie);
}
/*!
@@ -164,6 +164,10 @@ void QGraphicsSceneIndex::updateItems(const QList<QGraphicsItem *> &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<QGraphicsItem *> &items);
- virtual void removeItems(const QList<QGraphicsItem *> &items);
+ virtual void removeItems(const QList<QGraphicsItem *> &items, bool itemsAreAboutToDie);
virtual void updateItems(const QList<QGraphicsItem *> &items);
virtual QList<QGraphicsItem *> items(const QPointF &point) = 0;
virtual QList<QGraphicsItem *> items(const QRectF &rect) = 0;
- QGraphicsScene* scene();
+ virtual QList<QGraphicsItem *> indexedItems() = 0;
+
+ virtual void updateIndex();
- QGraphicsScene* mscene;
+private:
+ QGraphicsScene *m_scene;
};
#endif // QT_NO_GRAPHICSVIEW
diff --git a/src/gui/graphicsview/qgraphicsscene_linear_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
index 41e03e4..30948d9 100644
--- a/src/gui/graphicsview/qgraphicsscene_linear_p.h
+++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
@@ -73,7 +73,8 @@ private:
QList<QGraphicsItem*> m_items;
public:
- QGraphicsSceneLinearIndex(QObject *parent = 0): QGraphicsSceneIndex(parent) {
+ QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0): QGraphicsSceneIndex(scene)
+ {
}
virtual void setRect(const QRectF &rect) {
@@ -92,7 +93,8 @@ public:
m_items << item;
}
- virtual void removeItem(QGraphicsItem *item) {
+ virtual void removeItem(QGraphicsItem *item, bool itemIsAboutToDie) {
+ Q_UNUSED(itemIsAboutToDie);
m_items.removeAll(item);
}
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 <QtTest/QtTest>
#include <QtGui/qgraphicsscene.h>
#include <QtGui/qgraphicssceneindex.h>
-#include <private/qgraphicsscene_bsp_p.h>
-#include <private/qgraphicsscene_linear_p.h>
+#include <private/qgraphicsscenebsptreeindex_p.h>
+#include <private/qgraphicsscenelinearindex_p.h>
//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));
}
generated by cgit v0.12 at 2024-11-15 14:06:36 (GMT)