diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/gui/graphicsview/graphicsview.pri | 7 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsitem.cpp | 43 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsitem.h | 6 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscene.cpp | 1221 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscene.h | 17 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscene_bsp.cpp | 12 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscene_bsp_p.h | 8 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscene_p.h | 130 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp | 625 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h | 100 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h | 140 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicssceneindex.cpp | 639 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicssceneindex.h | 112 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicssceneindex_p.h | 97 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsscenelinearindex_p.h | 117 | ||||
| -rw-r--r-- | src/gui/graphicsview/qgraphicsview.cpp | 32 |
16 files changed, 2132 insertions, 1174 deletions
diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri index 02d9bb1..a4a79e8 100644 --- a/src/gui/graphicsview/graphicsview.pri +++ b/src/gui/graphicsview/graphicsview.pri @@ -6,7 +6,12 @@ HEADERS += \ graphicsview/qgraphicsitemanimation.h \ 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 \ + graphicsview/qgraphicssceneindex_p.h \ graphicsview/qgraphicssceneevent.h \ graphicsview/qgraphicsview_p.h \ graphicsview/qgraphicsview.h @@ -16,6 +21,8 @@ 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 b9e462b..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> @@ -567,17 +568,6 @@ QT_BEGIN_NAMESPACE -// QRectF::intersects() returns false always if either the source or target -// rectangle's width or height are 0. This works around that problem. -static inline void _q_adjustRect(QRectF *rect) -{ - Q_ASSERT(rect); - if (!rect->width()) - rect->adjust(-0.00001, 0, 0.00001, 0); - if (!rect->height()) - rect->adjust(0, -0.00001, 0, 0.00001); -} - static inline void _q_adjustRect(QRect *rect) { Q_ASSERT(rect); @@ -899,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(); @@ -916,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); + } } /*! @@ -3539,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); } @@ -4002,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()); } @@ -6357,7 +6344,7 @@ void QGraphicsItem::addToIndex() return; } if (d_ptr->scene) - d_ptr->scene->d_func()->addToIndex(this); + d_ptr->scene->d_func()->index->addItem(this); d_ptr->updateHelper(); } @@ -6370,13 +6357,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); } /*! @@ -6397,7 +6380,7 @@ void QGraphicsItem::prepareGeometryChange() if (d_ptr->scene) { d_ptr->updateHelper(QRectF(), false, /*maybeDirtyClipPath=*/!d_ptr->inSetPosHelper); QGraphicsScenePrivate *scenePrivate = d_ptr->scene->d_func(); - scenePrivate->removeFromIndex(this); + scenePrivate->index->prepareBoundingRectChange(this); } if (d_ptr->inSetPosHelper) diff --git a/src/gui/graphicsview/qgraphicsitem.h b/src/gui/graphicsview/qgraphicsitem.h index f6ee197..7874033 100644 --- a/src/gui/graphicsview/qgraphicsitem.h +++ b/src/gui/graphicsview/qgraphicsitem.h @@ -409,6 +409,8 @@ protected: virtual void setExtension(Extension extension, const QVariant &variant); virtual QVariant extension(const QVariant &variant) const; + bool operator<(const QGraphicsItem *other) const; + protected: QGraphicsItem(QGraphicsItemPrivate &dd, QGraphicsItem *parent, QGraphicsScene *scene); @@ -430,6 +432,10 @@ private: friend class QGraphicsWidget; friend class QGraphicsWidgetPrivate; friend class QGraphicsProxyWidgetPrivate; + 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 49c2329..cf851c0 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 @@ -219,6 +217,8 @@ static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; #include "qgraphicsview_p.h" #include "qgraphicswidget.h" #include "qgraphicswidget_p.h" +#include "qgraphicssceneindex.h" +#include "qgraphicsscenebsptreeindex_p_p.h" #include <QtCore/qdebug.h> #include <QtCore/qlist.h> @@ -250,65 +250,6 @@ static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; QT_BEGIN_NAMESPACE -static inline bool QRectF_intersects(const QRectF &s, const QRectF &r) -{ - qreal xp = s.left(); - qreal yp = s.top(); - qreal w = s.width(); - qreal h = s.height(); - qreal l1 = xp; - qreal r1 = xp; - if (w < 0) - l1 += w; - else - r1 += w; - - qreal l2 = r.left(); - qreal r2 = r.left(); - if (w < 0) - l2 += r.width(); - else - r2 += r.width(); - - if (l1 >= r2 || l2 >= r1) - return false; - - qreal t1 = yp; - qreal b1 = yp; - if (h < 0) - t1 += h; - else - b1 += h; - - qreal t2 = r.top(); - qreal b2 = r.top(); - if (r.height() < 0) - t2 += r.height(); - else - b2 += r.height(); - - return !(t1 >= b2 || t2 >= b1); -} - -// QRectF::intersects() returns false always if either the source or target -// rectangle's width or height are 0. This works around that problem. -static inline void _q_adjustRect(QRectF *rect) -{ - Q_ASSERT(rect); - if (!rect->width()) - rect->adjust(-0.00001, 0, 0.00001, 0); - if (!rect->height()) - rect->adjust(0, -0.00001, 0, 0.00001); -} - -static inline QRectF adjustedItemBoundingRect(const QGraphicsItem *item) -{ - Q_ASSERT(item); - QRectF boundingRect(item->boundingRect()); - _q_adjustRect(&boundingRect); - return boundingRect; -} - static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraphicsSceneMouseEvent *mouseEvent) { hover->setWidget(mouseEvent->widget()); @@ -330,15 +271,12 @@ QGraphicsScenePrivate::QGraphicsScenePrivate() indexMethod(QGraphicsScene::BspTreeIndex), bspTreeDepth(0), lastItemCount(0), + 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), @@ -354,8 +292,6 @@ QGraphicsScenePrivate::QGraphicsScenePrivate() allItemsIgnoreHoverEvents(true), allItemsUseDefaultCursor(true), painterStateProtection(true), - sortCacheEnabled(false), - updatingSortCache(false), style(0) { } @@ -367,6 +303,8 @@ void QGraphicsScenePrivate::init() { Q_Q(QGraphicsScene); + index = new QGraphicsSceneBspTreeIndex(q); + // Keep this index so we can check for connected slots later on. changedSignalMask = (1 << q->metaObject()->indexOfSignal("changed(QList<QRectF>)")); qApp->d_func()->scene_list.append(q); @@ -376,219 +314,6 @@ void QGraphicsScenePrivate::init() /*! \internal */ -QList<QGraphicsItem *> QGraphicsScenePrivate::estimateItemsInRect(const QRectF &rect) const -{ - const_cast<QGraphicsScenePrivate *>(this)->purgeRemovedItems(); - const_cast<QGraphicsScenePrivate *>(this)->_q_updateSortCache(); - - if (indexMethod == QGraphicsScene::BspTreeIndex) { - // ### Only do this once in a while. - QGraphicsScenePrivate *that = const_cast<QGraphicsScenePrivate *>(this); - - // Get items from BSP tree - QList<QGraphicsItem *> items = that->bspTree.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 (QRectF_intersects(boundingRect, rect)) { - 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; - for (int i = 0; i < unindexedItems.size(); ++i) { - if (QGraphicsItem *item = unindexedItems.at(i)) { - if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) - continue; - if (item->d_ptr->visible && item->effectiveOpacity() > qreal(0.0)) - itemsInRect << item; - } - } - 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; - } - } - - return itemsInRect; -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::addToIndex(QGraphicsItem *item) -{ - if (indexMethod == QGraphicsScene::BspTreeIndex) { - if (item->d_func()->index != -1) { - bspTree.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(); - } - } -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::removeFromIndex(QGraphicsItem *item) -{ - if (indexMethod == QGraphicsScene::BspTreeIndex) { - int index = item->d_func()->index; - if (index != -1) { - bspTree.removeItem(item, item->sceneBoundingRect()); - freeItemIndexes << index; - indexedItems[index] = 0; - item->d_func()->index = -1; - unindexedItems << item; - - foreach (QGraphicsItem *child, item->children()) - child->removeFromIndex(); - } - - startIndexTimer(); - } -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::resetIndex() -{ - purgeRemovedItems(); - if (indexMethod == QGraphicsScene::BspTreeIndex) { - 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(); - } -} - -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; - 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 = growingItemsBoundingRect; - growingItemsBoundingRect |= unindexedItemsBoundingRect; - - // Determine whether we should regenerate the BSP tree. - if (indexMethod == QGraphicsScene::BspTreeIndex) { - int depth = bspTreeDepth; - if (depth == 0) { - int oldDepth = intmaxlog(lastItemCount); - depth = intmaxlog(indexedItems.size()); - static const int slack = 100; - if (bspTree.leafCount() == 0 || (oldDepth != depth && qAbs(lastItemCount - indexedItems.size()) > slack)) { - // ### Crude algorithm. - regenerateIndex = true; - } - } - - // Regenerate the tree. - if (regenerateIndex) { - regenerateIndex = false; - bspTree.initialize(q->sceneRect(), depth); - unindexedItems = indexedItems; - 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. - 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; - if (indexMethod == QGraphicsScene::BspTreeIndex) - bspTree.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. - largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect(); - } - } - } - unindexedItems.clear(); - - // Notify scene rect changes. - if (!hasSceneRect && growingItemsBoundingRect != oldGrowingItemsBoundingRect) - emit q->sceneRectChanged(growingItemsBoundingRect); -} - -/*! - \internal -*/ void QGraphicsScenePrivate::_q_emitUpdated() { Q_Q(QGraphicsScene); @@ -727,22 +452,10 @@ 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. - unindexedItems.removeAll(item); - q->update(); - } + // Note: This will access item's sceneBoundingRect(), which (as this is + // C++) is why we cannot call removeItem() from QGraphicsItem's + // destructor. + this->index->deleteItem(item); // Reset the mouse grabber and focus item data. if (item == focusItem) @@ -802,50 +515,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) - bspTree.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) { @@ -1403,614 +1072,6 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item) return 0; } - -QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QPointF &pos) const -{ - QList<QGraphicsItem *> items; - - // The index returns a rough estimate of what items are inside the rect. - // Refine it by iterating through all returned items. - QRectF adjustedRect = QRectF(pos, QSize(1,1)); - foreach (QGraphicsItem *item, estimateItemsInRect(adjustedRect)) { - // Find the item's scene transform in a clever way. - QTransform x = item->sceneTransform(); - bool keep = false; - - // ### _q_adjustedRect is only needed because QRectF::intersects, - // QRectF::contains and QTransform::map() and friends don't work with - // flat rectangles. - const QRectF br(adjustedItemBoundingRect(item)); - // Rect intersects/contains item's shape - if (QRectF_intersects(adjustedRect, x.mapRect(br))) { - bool ok; - QTransform xinv = x.inverted(&ok); - if (ok) { - if (item->contains(xinv.map(pos))) { - items << item; - keep = true; - } - } - } - - if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { - // Recurse into children that clip children. - bool ok; - QTransform xinv = x.inverted(&ok); - if (ok) - childItems_helper(&items, item, xinv.map(pos)); - } - } - - sortItems(&items, Qt::AscendingOrder, sortCacheEnabled); - return items; -} - -QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QRectF &rect, - Qt::ItemSelectionMode mode, - Qt::SortOrder order) const -{ - QList<QGraphicsItem *> items; - - QPainterPath path; - - // The index returns a rough estimate of what items are inside the rect. - // Refine it by iterating through all returned items. - QRectF adjustedRect(rect); - _q_adjustRect(&adjustedRect); - foreach (QGraphicsItem *item, estimateItemsInRect(adjustedRect)) { - // Find the item's scene transform in a clever way. - QTransform x = item->sceneTransform(); - bool keep = false; - - // ### _q_adjustedRect is only needed because QRectF::intersects, - // QRectF::contains and QTransform::map() and friends don't work with - // flat rectangles. - const QRectF br(adjustedItemBoundingRect(item)); - if (mode >= Qt::ContainsItemBoundingRect) { - // Rect intersects/contains item's bounding rect - QRectF mbr = x.mapRect(br); - if ((mode == Qt::IntersectsItemBoundingRect && QRectF_intersects(rect, mbr)) - || (mode == Qt::ContainsItemBoundingRect && rect != mbr && rect.contains(mbr))) { - items << item; - keep = true; - } - } else { - // Rect intersects/contains item's shape - if (QRectF_intersects(adjustedRect, x.mapRect(br))) { - bool ok; - QTransform xinv = x.inverted(&ok); - if (ok) { - if (path.isEmpty()) - path.addRect(rect); - if (itemCollidesWithPath(item, xinv.map(path), mode)) { - items << item; - keep = true; - } - } - } - } - - if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { - // Recurse into children that clip children. - bool ok; - QTransform xinv = x.inverted(&ok); - if (ok) { - if (x.type() <= QTransform::TxScale) { - // Rect - childItems_helper(&items, item, xinv.mapRect(rect), mode); - } else { - // Polygon - childItems_helper(&items, item, xinv.map(rect), mode); - } - } - } - } - - if (order != Qt::SortOrder(-1)) - sortItems(&items, order, sortCacheEnabled); - return items; -} - -QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QPolygonF &polygon, - Qt::ItemSelectionMode mode, - Qt::SortOrder order) const -{ - QList<QGraphicsItem *> items; - - QRectF polyRect(polygon.boundingRect()); - _q_adjustRect(&polyRect); - QPainterPath path; - - // The index returns a rough estimate of what items are inside the rect. - // Refine it by iterating through all returned items. - foreach (QGraphicsItem *item, estimateItemsInRect(polyRect)) { - // Find the item's scene transform in a clever way. - QTransform x = item->sceneTransform(); - bool keep = false; - - // ### _q_adjustedRect is only needed because QRectF::intersects, - // QRectF::contains and QTransform::map() and friends don't work with - // flat rectangles. - const QRectF br(adjustedItemBoundingRect(item)); - if (mode >= Qt::ContainsItemBoundingRect) { - // Polygon contains/intersects item's bounding rect - if (path == QPainterPath()) - path.addPolygon(polygon); - if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br))) - || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) { - items << item; - keep = true; - } - } else { - // Polygon contains/intersects item's shape - if (QRectF_intersects(polyRect, x.mapRect(br))) { - bool ok; - QTransform xinv = x.inverted(&ok); - if (ok) { - if (path == QPainterPath()) - path.addPolygon(polygon); - if (itemCollidesWithPath(item, xinv.map(path), mode)) { - items << item; - keep = true; - } - } - } - } - - if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { - // Recurse into children that clip children. - bool ok; - QTransform xinv = x.inverted(&ok); - if (ok) - childItems_helper(&items, item, xinv.map(polygon), mode); - } - } - - if (order != Qt::SortOrder(-1)) - sortItems(&items, order, sortCacheEnabled); - return items; -} - -QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QPainterPath &path, - Qt::ItemSelectionMode mode, - Qt::SortOrder order) const -{ - QList<QGraphicsItem *> items; - QRectF pathRect(path.controlPointRect()); - _q_adjustRect(&pathRect); - - // The index returns a rough estimate of what items are inside the rect. - // Refine it by iterating through all returned items. - foreach (QGraphicsItem *item, estimateItemsInRect(pathRect)) { - // Find the item's scene transform in a clever way. - QTransform x = item->sceneTransform(); - bool keep = false; - - // ### _q_adjustedRect is only needed because QRectF::intersects, - // QRectF::contains and QTransform::map() and friends don't work with - // flat rectangles. - const QRectF br(adjustedItemBoundingRect(item)); - if (mode >= Qt::ContainsItemBoundingRect) { - // Path contains/intersects item's bounding rect - if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br))) - || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) { - items << item; - keep = true; - } - } else { - // Path contains/intersects item's shape - if (QRectF_intersects(pathRect, x.mapRect(br))) { - bool ok; - QTransform xinv = x.inverted(&ok); - if (ok) { - if (itemCollidesWithPath(item, xinv.map(path), mode)) { - items << item; - keep = true; - } - } - } - } - - if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { - bool ok; - QTransform xinv = x.inverted(&ok); - if (ok) - childItems_helper(&items, item, xinv.map(path), mode); - } - } - - if (order != Qt::SortOrder(-1)) - sortItems(&items, order, sortCacheEnabled); - return items; -} - -void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items, - const QGraphicsItem *parent, - const QPointF &pos) const -{ - bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); - if (parentClip && parent->d_ptr->isClippedAway()) - return; - // ### is this needed? - if (parentClip && !parent->boundingRect().contains(pos)) - return; - - QList<QGraphicsItem *> &children = parent->d_ptr->children; - for (int i = 0; i < children.size(); ++i) { - QGraphicsItem *item = children.at(i); - if (item->d_ptr->hasTransform && !item->transform().isInvertible()) - continue; - - // Skip invisible items and all their children. - if (item->d_ptr->isInvisible()) - continue; - - bool keep = false; - if (!item->d_ptr->isClippedAway()) { - if (item->contains(item->mapFromParent(pos))) { - items->append(item); - keep = true; - } - } - - if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) - // Recurse into children. - childItems_helper(items, item, item->mapFromParent(pos)); - } -} - - -void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items, - const QGraphicsItem *parent, - const QRectF &rect, - Qt::ItemSelectionMode mode) const -{ - bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); - if (parentClip && parent->d_ptr->isClippedAway()) - return; - QRectF adjustedRect(rect); - _q_adjustRect(&adjustedRect); - QRectF r = !parentClip ? adjustedRect : adjustedRect.intersected(adjustedItemBoundingRect(parent)); - if (r.isEmpty()) - return; - - QPainterPath path; - QList<QGraphicsItem *> &children = parent->d_ptr->children; - for (int i = 0; i < children.size(); ++i) { - QGraphicsItem *item = children.at(i); - if (item->d_ptr->hasTransform && !item->transform().isInvertible()) - continue; - - // Skip invisible items and all their children. - if (item->d_ptr->isInvisible()) - continue; - - bool keep = false; - if (!item->d_ptr->isClippedAway()) { - // ### _q_adjustedRect is only needed because QRectF::intersects, - // QRectF::contains and QTransform::map() and friends don't work with - // flat rectangles. - const QRectF br(adjustedItemBoundingRect(item)); - QRectF mbr = item->mapRectToParent(br); - if (mode >= Qt::ContainsItemBoundingRect) { - // Rect intersects/contains item's bounding rect - if ((mode == Qt::IntersectsItemBoundingRect && QRectF_intersects(rect, mbr)) - || (mode == Qt::ContainsItemBoundingRect && rect != mbr && rect.contains(br))) { - items->append(item); - keep = true; - } - } else { - // Rect intersects/contains item's shape - if (QRectF_intersects(rect, mbr)) { - if (path == QPainterPath()) - path.addRect(rect); - if (itemCollidesWithPath(item, item->mapFromParent(path), mode)) { - items->append(item); - keep = true; - } - } - } - } - - if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) { - // Recurse into children. - if (!item->d_ptr->hasTransform || item->transform().type() <= QTransform::TxScale) { - // Rect - childItems_helper(items, item, item->mapRectFromParent(rect), mode); - } else { - // Polygon - childItems_helper(items, item, item->mapFromParent(rect), mode); - } - } - } -} - - -void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items, - const QGraphicsItem *parent, - const QPolygonF &polygon, - Qt::ItemSelectionMode mode) const -{ - bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); - if (parentClip && parent->d_ptr->isClippedAway()) - return; - QRectF polyRect(polygon.boundingRect()); - _q_adjustRect(&polyRect); - QRectF r = !parentClip ? polyRect : polyRect.intersected(adjustedItemBoundingRect(parent)); - if (r.isEmpty()) - return; - - QPainterPath path; - QList<QGraphicsItem *> &children = parent->d_ptr->children; - for (int i = 0; i < children.size(); ++i) { - QGraphicsItem *item = children.at(i); - if (item->d_ptr->hasTransform && !item->transform().isInvertible()) - continue; - - // Skip invisible items. - if (item->d_ptr->isInvisible()) - continue; - - bool keep = false; - if (!item->d_ptr->isClippedAway()) { - // ### _q_adjustedRect is only needed because QRectF::intersects, - // QRectF::contains and QTransform::map() and friends don't work with - // flat rectangles. - const QRectF br(adjustedItemBoundingRect(item)); - if (mode >= Qt::ContainsItemBoundingRect) { - // Polygon contains/intersects item's bounding rect - if (path == QPainterPath()) - path.addPolygon(polygon); - if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br))) - || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) { - items->append(item); - keep = true; - } - } else { - // Polygon contains/intersects item's shape - if (QRectF_intersects(polyRect, item->mapRectToParent(br))) { - if (path == QPainterPath()) - path.addPolygon(polygon); - if (itemCollidesWithPath(item, item->mapFromParent(path), mode)) { - items->append(item); - keep = true; - } - } - } - } - - if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) { - // Recurse into children that clip children. - childItems_helper(items, item, item->mapFromParent(polygon), mode); - } - } -} - -void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items, - const QGraphicsItem *parent, - const QPainterPath &path, - Qt::ItemSelectionMode mode) const -{ - bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); - if (parentClip && parent->d_ptr->isClippedAway()) - return; - QRectF pathRect(path.boundingRect()); - _q_adjustRect(&pathRect); - QRectF r = !parentClip ? pathRect : pathRect.intersected(adjustedItemBoundingRect(parent)); - if (r.isEmpty()) - return; - - QList<QGraphicsItem *> &children = parent->d_ptr->children; - for (int i = 0; i < children.size(); ++i) { - QGraphicsItem *item = children.at(i); - if (item->d_ptr->hasTransform && !item->transform().isInvertible()) - continue; - - // Skip invisible items. - if (item->d_ptr->isInvisible()) - continue; - - bool keep = false; - if (!item->d_ptr->isClippedAway()) { - // ### _q_adjustedRect is only needed because QRectF::intersects, - // QRectF::contains and QTransform::map() and friends don't work with - // flat rectangles. - const QRectF br(adjustedItemBoundingRect(item)); - if (mode >= Qt::ContainsItemBoundingRect) { - // Polygon contains/intersects item's bounding rect - if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br))) - || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) { - items->append(item); - keep = true; - } - } else { - // Path contains/intersects item's shape - if (QRectF_intersects(pathRect, item->mapRectToParent(br))) { - if (itemCollidesWithPath(item, item->mapFromParent(path), mode)) { - items->append(item); - keep = true; - } - } - } - } - - if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) { - // Recurse into children that clip children. - childItems_helper(items, item, item->mapFromParent(path), mode); - } - } -} - -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() -{ - _q_updateIndex(); - - if (!sortCacheEnabled || !updatingSortCache) - return; - - updatingSortCache = false; - int stackingOrder = 0; - - QList<QGraphicsItem *> topLevels; - - for (int i = 0; i < indexedItems.size(); ++i) { - QGraphicsItem *item = indexedItems.at(i); - if (item && item->parentItem() == 0) - topLevels << item; - } - for (int i = 0; i < unindexedItems.size(); ++i) { - QGraphicsItem *item = unindexedItems.at(i); - if (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 @@ -2143,8 +1204,8 @@ QGraphicsScene::QGraphicsScene(QObject *parent) QGraphicsScene::QGraphicsScene(const QRectF &sceneRect, QObject *parent) : QObject(*new QGraphicsScenePrivate, parent) { - setSceneRect(sceneRect); d_func()->init(); + setSceneRect(sceneRect); } /*! @@ -2158,8 +1219,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); } /*! @@ -2196,8 +1257,7 @@ QGraphicsScene::~QGraphicsScene() QRectF QGraphicsScene::sceneRect() const { Q_D(const QGraphicsScene); - const_cast<QGraphicsScenePrivate *>(d)->_q_updateIndex(); - return d->hasSceneRect ? d->sceneRect : d->growingItemsBoundingRect; + return d->index->indexedRect(); } void QGraphicsScene::setSceneRect(const QRectF &rect) { @@ -2205,7 +1265,7 @@ void QGraphicsScene::setSceneRect(const QRectF &rect) if (rect != d->sceneRect) { d->hasSceneRect = !rect.isNull(); d->sceneRect = rect; - d->resetIndex(); + d->index->sceneRectChanged(rect); emit sceneRectChanged(rect); } } @@ -2338,13 +1398,71 @@ QGraphicsScene::ItemIndexMethod QGraphicsScene::itemIndexMethod() const Q_D(const QGraphicsScene); return d->indexMethod; } + +// Possibilities +// NoIndex -> CustomIndex : warning +// BspTreeIndex -> CustomIndex : warning +// CustomIndex -> CustomIndex : warning +// NoIndex -> BspTreeIndex : create an empty BSP if necessary +// BspTreeIndex -> BspTreeIndex : nothing +// CustomIndex -> BspTreeIndex : create BSP and transfer items +// NoIndex -> NoIndex : nothing +// BspTreeIndex -> NoIndex : nothing +// CustomIndex -> NoIndex : create BSP tree but do not populate void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method) { Q_D(QGraphicsScene); - d->resetIndex(); + if (method == CustomIndex) { + qWarning("QGraphicsScene: Invalid index type %d", CustomIndex); + return; + } + if (d->indexMethod == method) { + return; + } + + if (d->indexMethod == NoIndex && method == BspTreeIndex) { + QGraphicsSceneBspTreeIndex *tree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index); + if (!tree) { + delete d->index; + d->index = new QGraphicsSceneBspTreeIndex(this); + } + } + + if (d->indexMethod == CustomIndex && method == BspTreeIndex) { + //We re-add in the new index all items from the old index + QGraphicsSceneIndex *oldIndex = d->index; + d->index = new QGraphicsSceneBspTreeIndex(this); + for (int i = 0 ; i < oldIndex->items().size() ; ++ i) + d->index->addItem(oldIndex->items().at(i)); + } + + if (d->indexMethod == CustomIndex && method == NoIndex) { + d->index = new QGraphicsSceneLinearIndex(this); + } + d->indexMethod = method; } +void QGraphicsScene::setSceneIndex(QGraphicsSceneIndex *index) +{ + Q_D(QGraphicsScene); + if (!index) { + qWarning("QGraphicsScene::setSceneIndex: Attempt to insert a null indexer"); + } else { + if (d->indexMethod == BspTreeIndex) { + delete d->index; + } + d->indexMethod = CustomIndex; + d->index = index; + } +} + +QGraphicsSceneIndex* QGraphicsScene::sceneIndex() const +{ + Q_D(const QGraphicsScene); + return d->index; +} + /*! \property QGraphicsScene::bspTreeDepth \brief the depth of QGraphicsScene's BSP index tree @@ -2380,7 +1498,8 @@ void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method) int QGraphicsScene::bspTreeDepth() const { Q_D(const QGraphicsScene); - return d->bspTreeDepth; + QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index); + return bspTree ? bspTree->bspDepth() : 0; } void QGraphicsScene::setBspTreeDepth(int depth) { @@ -2393,8 +1512,13 @@ void QGraphicsScene::setBspTreeDepth(int depth) return; } - d->bspTreeDepth = depth; - d->resetIndex(); + QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index); + if (!bspTree) { + qWarning("QGraphicsScene::setBspTreeDepth: can not apply if indexing method is not BSP"); + return; + } + + bspTree->setBspDepth(depth); } /*! @@ -2413,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 (enabled == bspTree->d_func()->sortCacheEnabled) return; - if ((d->sortCacheEnabled = enabled)) - d->invalidateSortCache(); + if ((bspTree->d_func()->sortCacheEnabled = enabled)) + bspTree->d_func()->invalidateSortCache(); } /*! @@ -2447,29 +1581,12 @@ 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->unindexedItems.isEmpty()) - return d->indexedItems; - return d->indexedItems + d->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, d->indexedItems + d->unindexedItems) { - if (item) - itemList << item; - } - return itemList; + return d->index->items(); } /*! Returns all visible items at position \a pos in the scene. The items are - listed in descending Z order (i.e., the first item in the list is the + listed in descending stacking order (i.e., the first item in the list is the top-most item, and the last item is the bottom-most item). \sa itemAt() @@ -2477,7 +1594,7 @@ QList<QGraphicsItem *> QGraphicsScene::items() const QList<QGraphicsItem *> QGraphicsScene::items(const QPointF &pos) const { Q_D(const QGraphicsScene); - return d->items_helper(pos); + return d->index->items(pos, Qt::IntersectsItemShape, Qt::AscendingOrder); } @@ -2497,7 +1614,7 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QPointF &pos) const QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelectionMode mode) const { Q_D(const QGraphicsScene); - return d->items_helper(rect, mode, Qt::AscendingOrder); + return d->index->items(rect, mode, Qt::AscendingOrder); } /*! @@ -2521,7 +1638,7 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelecti QList<QGraphicsItem *> QGraphicsScene::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode) const { Q_D(const QGraphicsScene); - return d->items_helper(polygon, mode, Qt::AscendingOrder); + return d->index->items(polygon, mode, Qt::AscendingOrder); } /*! @@ -2538,7 +1655,74 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QPolygonF &polygon, Qt::ItemS QList<QGraphicsItem *> QGraphicsScene::items(const QPainterPath &path, Qt::ItemSelectionMode mode) const { Q_D(const QGraphicsScene); - return d->items_helper(path, mode, Qt::AscendingOrder); + return d->index->items(path, mode, Qt::AscendingOrder); +} + +/*! + Returns all visible items at position \a pos in the scene. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a path are returned. + + \sa itemAt() +*/ +QList<QGraphicsItem *> QGraphicsScene::items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsScene); + return d->index->items(pos, mode, order, deviceTransform); +} + +/*! + \fn QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rectangle, Qt::SortOrder order, const QTransform &deviceTransform) const + + \overload + + Returns all visible items that, depending on \a mode, are either inside or + intersect with the specified \a rectangle. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a rectangle are returned. + + \sa itemAt() +*/ +QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsScene); + return d->index->items(rect, mode, order, deviceTransform); +} + +/*! + \overload + + Returns all visible items that, depending on \a mode, are either inside or + intersect with the polygon \a polygon. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a polygon are returned. + + \sa itemAt() +*/ +QList<QGraphicsItem *> QGraphicsScene::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsScene); + return d->index->items(polygon, mode, order, deviceTransform); +} + +/*! + \overload + + Returns all visible items that, depending on \a path, are either inside or + intersect with the path \a path. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a path are returned. + + \sa itemAt() +*/ +QList<QGraphicsItem *> QGraphicsScene::items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsScene); + return d->index->items(path, mode, order, deviceTransform); } /*! @@ -2562,11 +1746,10 @@ QList<QGraphicsItem *> QGraphicsScene::collidingItems(const QGraphicsItem *item, } QList<QGraphicsItem *> tmp; - foreach (QGraphicsItem *itemInVicinity, d->estimateItemsInRect(item->sceneBoundingRect())) { + foreach (QGraphicsItem *itemInVicinity, d->index->estimateItems(item->sceneBoundingRect(), Qt::AscendingOrder, QTransform())) { if (item != itemInVicinity && item->collidesWithItem(itemInVicinity, mode)) tmp << itemInVicinity; } - d->sortItems(&tmp, Qt::AscendingOrder, d->sortCacheEnabled); return tmp; } @@ -2733,25 +1916,18 @@ void QGraphicsScene::clearSelection() void QGraphicsScene::clear() { Q_D(QGraphicsScene); + QList<QGraphicsItem *> items; // 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->items().size(); ++i) { + if (QGraphicsItem *item = d->index->items().at(i)) { if (!item->parentItem()) - delete item; + items << item; } } - QList<QGraphicsItem *> unindexedParents; - for (int i = 0; i < d->unindexedItems.size(); ++i) { - QGraphicsItem *item = d->unindexedItems.at(i); - if (!item->parentItem()) - unindexedParents << item; - } - d->unindexedItems.clear(); - qDeleteAll(unindexedParents); - d->indexedItems.clear(); - d->freeItemIndexes.clear(); + //We delete all top level items + qDeleteAll(items); d->lastItemCount = 0; - d->bspTree.clear(); + d->index->clear(); d->largestUntransformableItem = QRectF(); d->allItemsIgnoreHoverEvents = true; d->allItemsUseDefaultCursor = true; @@ -2873,14 +2049,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(); - // Detach this item from its parent if the parent's scene is different // from this scene. if (QGraphicsItem *itemParent = item->parentItem()) { @@ -2891,21 +2059,13 @@ void QGraphicsScene::addItem(QGraphicsItem *item) // Add the item to this scene item->d_func()->scene = targetScene; - // 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->unindexedItems << item; - item->d_func()->index = -1; - d->startIndexTimer(); + // Add the item in the index + d->index->addItem(item); // Add to list of toplevels if this item is a toplevel. 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(). @@ -3255,10 +2415,8 @@ void QGraphicsScene::removeItem(QGraphicsItem *item) // Clear its background item->update(); - // 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); + // Remove it from the index properly + d->index->removeItem(item); if (item == d->tabFocusFirst) { QGraphicsWidget *widget = static_cast<QGraphicsWidget *>(item); @@ -3278,15 +2436,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->unindexedItems.removeAll(item); - } - // Remove from scene transform cache int transformIndex = item->d_func()->sceneTransformIndex; if (transformIndex != -1) { @@ -3915,16 +3064,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 9802f87..702813c 100644 --- a/src/gui/graphicsview/qgraphicsscene.h +++ b/src/gui/graphicsview/qgraphicsscene.h @@ -83,6 +83,7 @@ class QGraphicsSimpleTextItem; class QGraphicsTextItem; class QGraphicsView; class QGraphicsWidget; +class QGraphicsSceneIndex; class QHelpEvent; class QInputMethodEvent; class QKeyEvent; @@ -113,6 +114,7 @@ class Q_GUI_EXPORT QGraphicsScene : public QObject public: enum ItemIndexMethod { BspTreeIndex, + CustomIndex, NoIndex = -1 }; @@ -142,6 +144,8 @@ public: ItemIndexMethod itemIndexMethod() const; void setItemIndexMethod(ItemIndexMethod method); + void setSceneIndex(QGraphicsSceneIndex *index); + QGraphicsSceneIndex* sceneIndex() const; bool isSortCacheEnabled() const; void setSortCacheEnabled(bool enabled); @@ -152,10 +156,17 @@ public: QRectF itemsBoundingRect() const; QList<QGraphicsItem *> items() const; + + QList<QGraphicsItem *> items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + QList<QGraphicsItem *> items(const QPointF &pos) const; QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; + QList<QGraphicsItem *> collidingItems(const QGraphicsItem *item, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; QGraphicsItem *itemAt(const QPointF &pos) const; @@ -275,12 +286,10 @@ 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()) 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; @@ -288,6 +297,10 @@ private: friend class QGraphicsViewPrivate; friend class QGraphicsWidget; friend class QGraphicsWidgetPrivate; + 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_bsp.cpp b/src/gui/graphicsview/qgraphicsscene_bsp.cpp index f8fa450..5c1820f 100644 --- a/src/gui/graphicsview/qgraphicsscene_bsp.cpp +++ b/src/gui/graphicsview/qgraphicsscene_bsp.cpp @@ -143,7 +143,7 @@ void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items) } } -QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect) +QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect) const { QList<QGraphicsItem *> tmp; findVisitor->foundItems = &tmp; @@ -151,7 +151,7 @@ QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect) return tmp; } -QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos) +QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos) const { QList<QGraphicsItem *> tmp; findVisitor->foundItems = &tmp; @@ -235,7 +235,7 @@ void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index) } } -void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index) +void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index) const { if (nodes.isEmpty()) return; @@ -245,7 +245,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con switch (node.type) { case Node::Leaf: { - visitor->visit(&leaves[node.leafIndex]); + visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex])); break; } case Node::Vertical: @@ -265,7 +265,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con } } -void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) +void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) const { if (nodes.isEmpty()) return; @@ -275,7 +275,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con switch (node.type) { case Node::Leaf: { - visitor->visit(&leaves[node.leafIndex]); + visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex])); break; } case Node::Vertical: diff --git a/src/gui/graphicsview/qgraphicsscene_bsp_p.h b/src/gui/graphicsview/qgraphicsscene_bsp_p.h index e6ceb78..a13d862 100644 --- a/src/gui/graphicsview/qgraphicsscene_bsp_p.h +++ b/src/gui/graphicsview/qgraphicsscene_bsp_p.h @@ -92,8 +92,8 @@ public: void removeItem(QGraphicsItem *item, const QRectF &rect); void removeItems(const QSet<QGraphicsItem *> &items); - QList<QGraphicsItem *> items(const QRectF &rect); - QList<QGraphicsItem *> items(const QPointF &pos); + QList<QGraphicsItem *> items(const QRectF &rect) const; + QList<QGraphicsItem *> items(const QPointF &pos) const; int leafCount() const; inline int firstChildIndex(int index) const @@ -106,8 +106,8 @@ public: 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); + void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index = 0) const; + void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index = 0) const; void findItems(QList<QGraphicsItem *> *foundItems, const QRectF &rect, int index); void findItems(QList<QGraphicsItem *> *foundItems, const QPointF &pos, int index); diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h index 9ace725..d2a5cdb 100644 --- a/src/gui/graphicsview/qgraphicsscene_p.h +++ b/src/gui/graphicsview/qgraphicsscene_p.h @@ -57,7 +57,9 @@ #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW -#include "qgraphicsscene_bsp_p.h" +#include "qgraphicsscenebsptreeindex_p.h" +#include "qgraphicsscenelinearindex_p.h" +#include "qgraphicssceneindex.h" #include "qgraphicsitem_p.h" #include <private/qobject_p.h> @@ -86,15 +88,10 @@ public: QGraphicsScene::ItemIndexMethod indexMethod; int bspTreeDepth; - QList<QGraphicsItem *> estimateItemsInRect(const QRectF &rect) const; - void addToIndex(QGraphicsItem *item); - void removeFromIndex(QGraphicsItem *item); - void resetIndex(); - - QGraphicsSceneBspTree bspTree; - void _q_updateIndex(); int lastItemCount; + QGraphicsSceneIndex *index; + QRectF sceneRect; bool hasSceneRect; QRectF growingItemsBoundingRect; @@ -108,8 +105,6 @@ public: QPainterPath selectionArea; int selectionChanging; QSet<QGraphicsItem *> selectedItems; - QList<QGraphicsItem *> unindexedItems; - QList<QGraphicsItem *> indexedItems; QList<QGraphicsItem *> dirtyItems; QList<QGraphicsItem *> pendingUpdateItems; QList<QGraphicsItem *> unpolishedItems; @@ -124,21 +119,11 @@ public: void resetDirtyItemsLater(); bool dirtyItemResetPending; - QList<int> freeItemIndexes; - bool regenerateIndex; - - bool purgePending; void _q_removeItemLater(QGraphicsItem *item); - QSet<QGraphicsItem *> removedItems; - void purgeRemovedItems(); QBrush backgroundBrush; QBrush foregroundBrush; - int indexTimerId; - bool restartIndexTimer; - void startIndexTimer(); - bool stickyFocus; bool hasFocus; QGraphicsItem *focusItem; @@ -203,52 +188,6 @@ public: void mousePressEventHandler(QGraphicsSceneMouseEvent *mouseEvent); QGraphicsWidget *windowForItem(const QGraphicsItem *item) const; - QList<QGraphicsItem *> items_helper(const QPointF &pos) const; - QList<QGraphicsItem *> items_helper(const QRectF &rect, - Qt::ItemSelectionMode mode, - Qt::SortOrder order) const; - QList<QGraphicsItem *> items_helper(const QPolygonF &rect, - Qt::ItemSelectionMode mode, - Qt::SortOrder order) const; - QList<QGraphicsItem *> items_helper(const QPainterPath &rect, - Qt::ItemSelectionMode mode, - Qt::SortOrder order) const; - void childItems_helper(QList<QGraphicsItem *> *items, - const QGraphicsItem *parent, - const QPointF &pos) const; - void childItems_helper(QList<QGraphicsItem *> *items, - const QGraphicsItem *parent, - const QRectF &rect, - Qt::ItemSelectionMode mode) const; - void childItems_helper(QList<QGraphicsItem *> *items, - const QGraphicsItem *parent, - const QPolygonF &polygon, - Qt::ItemSelectionMode mode) const; - void childItems_helper(QList<QGraphicsItem *> *items, - const QGraphicsItem *parent, - const QPainterPath &path, - Qt::ItemSelectionMode mode) 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, bool painterStateProtection); @@ -268,6 +207,65 @@ public: mutable QVector<int> freeSceneTransformSlots; }; +static inline bool QRectF_intersects(const QRectF &s, const QRectF &r) +{ + qreal xp = s.left(); + qreal yp = s.top(); + qreal w = s.width(); + qreal h = s.height(); + qreal l1 = xp; + qreal r1 = xp; + if (w < 0) + l1 += w; + else + r1 += w; + + qreal l2 = r.left(); + qreal r2 = r.left(); + if (w < 0) + l2 += r.width(); + else + r2 += r.width(); + + if (l1 >= r2 || l2 >= r1) + return false; + + qreal t1 = yp; + qreal b1 = yp; + if (h < 0) + t1 += h; + else + b1 += h; + + qreal t2 = r.top(); + qreal b2 = r.top(); + if (r.height() < 0) + t2 += r.height(); + else + b2 += r.height(); + + return !(t1 >= b2 || t2 >= b1); +} + +// QRectF::intersects() returns false always if either the source or target +// rectangle's width or height are 0. This works around that problem. +static inline void _q_adjustRect(QRectF *rect) +{ + Q_ASSERT(rect); + if (!rect->width()) + rect->adjust(-0.00001, 0, 0.00001, 0); + if (!rect->height()) + rect->adjust(0, -0.00001, 0, 0.00001); +} + +static inline QRectF adjustedItemBoundingRect(const QGraphicsItem *item) +{ + Q_ASSERT(item); + QRectF boundingRect(item->boundingRect()); + _q_adjustRect(&boundingRect); + return boundingRect; +} + QT_END_NAMESPACE #endif // QT_NO_GRAPHICSVIEW diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp new file mode 100644 index 0000000..19aa9d5 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp @@ -0,0 +1,625 @@ +/**************************************************************************** +** +** 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" + +#ifndef QT_NO_GRAPHICSVIEW + +#include "qgraphicsscenebsptreeindex_p_p.h" +#include "qgraphicssceneindex_p.h" +#include "qgraphicsitem_p.h" +#include "qgraphicsscene_p.h" + +#include <QtCore/qmath.h> + +#include <QtCore/qdebug.h> + +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), + 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); +} + + +/*! + \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() +{ + 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. + 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. + d->unindexedItems << item; + item->d_func()->index = -1; + d->startIndexTimer(); +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::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) +{ + 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. + 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) { + d->freeItemIndexes << index; + d->indexedItems[index] = 0; + } else { + 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. + d->indexedItems[index] = (QGraphicsItem *)0; + if (!d->purgePending) { + d->purgePending = true; + scene()->update(); + } + d->removedItems << item; + } else { + // Recently added items are purged immediately. unindexedItems() never + // contains stale items. + d->unindexedItems.removeAll(item); + scene()->update(); + } +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::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; + indexedItems[index] = 0; + item->d_func()->index = -1; + unindexedItems << item; + + //prepareGeometryChange will call prepareBoundingRectChange + foreach (QGraphicsItem *child, item->children()) + child->prepareGeometryChange(); + } + startIndexTimer(); +} + +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. + d->removeFromIndex(const_cast<QGraphicsItem *>(item)); +} + +QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneBspTreeIndex); + const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems(); + const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->_q_updateSortCache(); + + QList<QGraphicsItem *> rectItems = d->bsp.items(rect); + // Fill in with any unindexed items + for (int i = 0; i < d->unindexedItems.size(); ++i) { + if (QGraphicsItem *item = d->unindexedItems.at(i)) { + if (!item->d_ptr->itemDiscovered && item->d_ptr->visible && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { + QRectF boundingRect = item->sceneBoundingRect(); + if (QRectF_intersects(boundingRect, 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; + + d->sortItems(&rectItems, order, d->sortCacheEnabled); + + return rectItems; +} + +QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) const +{ + 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 (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() +{ + Q_D(const QGraphicsSceneBspTreeIndex); + return d->bspTreeDepth; +} + +void QGraphicsSceneBspTreeIndex::setBspDepth(int depth) +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->bspTreeDepth = depth; + d->resetIndex(); +} + +void QGraphicsSceneBspTreeIndex::sceneRectChanged(const QRectF &rect) +{ + 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 (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); + } + return true; +} + +QT_END_NAMESPACE + +#include "moc_qgraphicsscenebsptreeindex_p.cpp" + +#endif // QT_NO_GRAPHICSVIEW + diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h new file mode 100644 index 0000000..b1ea977 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h @@ -0,0 +1,100 @@ +/**************************************************************************** +** +** 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 QGraphicsSceneBspTreeIndexPrivate; +class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex +{ + Q_OBJECT +public: + QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0); + QRectF indexedRect() const; + + QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const; + + QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const; + + int bspDepth(); + void setBspDepth(int depth); + +protected: + bool event(QEvent *event); + void clear(); + + void addItem(QGraphicsItem *item); + void removeItem(QGraphicsItem *item); + void deleteItem(QGraphicsItem *item); + void prepareBoundingRectChange(const QGraphicsItem *item); + + void sceneRectChanged(const QRectF &rect); + void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value); + +private : + 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 + +#endif // QT_NO_GRAPHICSVIEW + +#endif // QGRAPHICSBSPTREEINDEX_H 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 new file mode 100644 index 0000000..eeee74e --- /dev/null +++ b/src/gui/graphicsview/qgraphicssceneindex.cpp @@ -0,0 +1,639 @@ +/**************************************************************************** +** +** 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 "qgraphicssceneindex.h" +#include "qgraphicssceneindex_p.h" +#include "qgraphicsscenebsptreeindex_p_p.h" +#include "qgraphicsscene.h" +#include "qgraphicsitem_p.h" +#include "qgraphicsscene_p.h" + +#ifndef QT_NO_GRAPHICSVIEW + +QT_BEGIN_NAMESPACE + +/*! + Constructs a private scene index. +*/ +QGraphicsSceneIndexPrivate::QGraphicsSceneIndexPrivate(QGraphicsScene *scene) : scene(scene) +{ +} + +void QGraphicsSceneIndexPrivate::childItems_helper(QList<QGraphicsItem *> *items, + const QGraphicsItem *parent, + const QPointF &pos) const +{ + bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); + if (parentClip && parent->d_ptr->isClippedAway()) + return; + // ### is this needed? + if (parentClip && !parent->boundingRect().contains(pos)) + return; + + QList<QGraphicsItem *> &children = parent->d_ptr->children; + for (int i = 0; i < children.size(); ++i) { + QGraphicsItem *item = children.at(i); + if (item->d_ptr->hasTransform && !item->transform().isInvertible()) + continue; + + // Skip invisible items and all their children. + if (item->d_ptr->isInvisible()) + continue; + + bool keep = false; + if (!item->d_ptr->isClippedAway()) { + if (item->contains(item->mapFromParent(pos))) { + items->append(item); + keep = true; + } + } + + if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) + // Recurse into children. + childItems_helper(items, item, item->mapFromParent(pos)); + } +} + + +void QGraphicsSceneIndexPrivate::childItems_helper(QList<QGraphicsItem *> *items, + const QGraphicsItem *parent, + const QRectF &rect, + Qt::ItemSelectionMode mode) const +{ + bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); + if (parentClip && parent->d_ptr->isClippedAway()) + return; + QRectF adjustedRect(rect); + _q_adjustRect(&adjustedRect); + QRectF r = !parentClip ? adjustedRect : adjustedRect.intersected(adjustedItemBoundingRect(parent)); + if (r.isEmpty()) + return; + + QPainterPath path; + QList<QGraphicsItem *> &children = parent->d_ptr->children; + for (int i = 0; i < children.size(); ++i) { + QGraphicsItem *item = children.at(i); + if (item->d_ptr->hasTransform && !item->transform().isInvertible()) + continue; + + // Skip invisible items and all their children. + if (item->d_ptr->isInvisible()) + continue; + + bool keep = false; + if (!item->d_ptr->isClippedAway()) { + // ### _q_adjustedRect is only needed because QRectF::intersects, + // QRectF::contains and QTransform::map() and friends don't work with + // flat rectangles. + const QRectF br(adjustedItemBoundingRect(item)); + QRectF mbr = item->mapRectToParent(br); + if (mode >= Qt::ContainsItemBoundingRect) { + // Rect intersects/contains item's bounding rect + if ((mode == Qt::IntersectsItemBoundingRect && QRectF_intersects(rect, mbr)) + || (mode == Qt::ContainsItemBoundingRect && rect != mbr && rect.contains(br))) { + items->append(item); + keep = true; + } + } else { + // Rect intersects/contains item's shape + if (QRectF_intersects(rect, mbr)) { + if (path == QPainterPath()) + path.addRect(rect); + if (scene->d_func()->itemCollidesWithPath(item, item->mapFromParent(path), mode)) { + items->append(item); + keep = true; + } + } + } + } + + if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) { + // Recurse into children. + if (!item->d_ptr->hasTransform || item->transform().type() <= QTransform::TxScale) { + // Rect + childItems_helper(items, item, item->mapRectFromParent(rect), mode); + } else { + // Polygon + childItems_helper(items, item, item->mapFromParent(rect), mode); + } + } + } +} + + +void QGraphicsSceneIndexPrivate::childItems_helper(QList<QGraphicsItem *> *items, + const QGraphicsItem *parent, + const QPolygonF &polygon, + Qt::ItemSelectionMode mode) const +{ + bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); + if (parentClip && parent->d_ptr->isClippedAway()) + return; + QRectF polyRect(polygon.boundingRect()); + _q_adjustRect(&polyRect); + QRectF r = !parentClip ? polyRect : polyRect.intersected(adjustedItemBoundingRect(parent)); + if (r.isEmpty()) + return; + + QPainterPath path; + QList<QGraphicsItem *> &children = parent->d_ptr->children; + for (int i = 0; i < children.size(); ++i) { + QGraphicsItem *item = children.at(i); + if (item->d_ptr->hasTransform && !item->transform().isInvertible()) + continue; + + // Skip invisible items. + if (item->d_ptr->isInvisible()) + continue; + + bool keep = false; + if (!item->d_ptr->isClippedAway()) { + // ### _q_adjustedRect is only needed because QRectF::intersects, + // QRectF::contains and QTransform::map() and friends don't work with + // flat rectangles. + const QRectF br(adjustedItemBoundingRect(item)); + if (mode >= Qt::ContainsItemBoundingRect) { + // Polygon contains/intersects item's bounding rect + if (path == QPainterPath()) + path.addPolygon(polygon); + if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br))) + || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) { + items->append(item); + keep = true; + } + } else { + // Polygon contains/intersects item's shape + if (QRectF_intersects(polyRect, item->mapRectToParent(br))) { + if (path == QPainterPath()) + path.addPolygon(polygon); + if (scene->d_func()->itemCollidesWithPath(item, item->mapFromParent(path), mode)) { + items->append(item); + keep = true; + } + } + } + } + + if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) { + // Recurse into children that clip children. + childItems_helper(items, item, item->mapFromParent(polygon), mode); + } + } +} + +void QGraphicsSceneIndexPrivate::childItems_helper(QList<QGraphicsItem *> *items, + const QGraphicsItem *parent, + const QPainterPath &path, + Qt::ItemSelectionMode mode) const +{ + bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape); + if (parentClip && parent->d_ptr->isClippedAway()) + return; + QRectF pathRect(path.boundingRect()); + _q_adjustRect(&pathRect); + QRectF r = !parentClip ? pathRect : pathRect.intersected(adjustedItemBoundingRect(parent)); + if (r.isEmpty()) + return; + + QList<QGraphicsItem *> &children = parent->d_ptr->children; + for (int i = 0; i < children.size(); ++i) { + QGraphicsItem *item = children.at(i); + if (item->d_ptr->hasTransform && !item->transform().isInvertible()) + continue; + + // Skip invisible items. + if (item->d_ptr->isInvisible()) + continue; + + bool keep = false; + if (!item->d_ptr->isClippedAway()) { + // ### _q_adjustedRect is only needed because QRectF::intersects, + // QRectF::contains and QTransform::map() and friends don't work with + // flat rectangles. + const QRectF br(adjustedItemBoundingRect(item)); + if (mode >= Qt::ContainsItemBoundingRect) { + // Polygon contains/intersects item's bounding rect + if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br))) + || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) { + items->append(item); + keep = true; + } + } else { + // Path contains/intersects item's shape + if (QRectF_intersects(pathRect, item->mapRectToParent(br))) { + if (scene->d_func()->itemCollidesWithPath(item, item->mapFromParent(path), mode)) { + items->append(item); + keep = true; + } + } + } + } + + if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) { + // Recurse into children that clip children. + childItems_helper(items, item, item->mapFromParent(path), mode); + } + } +} + +/*! + Constructs an abstract scene index. +*/ +QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene) +: QObject(*new QGraphicsSceneIndexPrivate(scene), scene) +{ +} + +/*! + \internal +*/ +QGraphicsSceneIndex::QGraphicsSceneIndex(QObjectPrivate &dd, QGraphicsScene *scene) + : QObject(dd, scene) +{ +} + +/*! + Destroys the scene index. +*/ +QGraphicsSceneIndex::~QGraphicsSceneIndex() +{ + +} + +/*! + Returns the scene of this index. +*/ +QGraphicsScene* QGraphicsSceneIndex::scene() const +{ + Q_D(const QGraphicsSceneIndex); + return d->scene; +} + +/*! + Returns the indexed area for the index +*/ +QRectF QGraphicsSceneIndex::indexedRect() const +{ + Q_D(const QGraphicsSceneIndex); + return d->scene->d_func()->sceneRect; +} + +/*! + \fn QList<QGraphicsItem *> items() const = 0 + + This pure virtual function return the list of items that are actually in the index. + +*/ + +QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneIndex); + QList<QGraphicsItem *> items; + + // The index returns a rough estimate of what items are inside the rect. + // Refine it by iterating through all returned items. + QRectF adjustedRect = QRectF(pos, QSize(1,1)); + foreach (QGraphicsItem *item, estimateItems(adjustedRect, order, deviceTransform)) { + // Find the item's scene transform in a clever way. + QTransform x = item->sceneTransform(); + bool keep = false; + + // ### _q_adjustedRect is only needed because QRectF::intersects, + // QRectF::contains and QTransform::map() and friends don't work with + // flat rectangles. + const QRectF br(adjustedItemBoundingRect(item)); + // Rect intersects/contains item's shape + if (QRectF_intersects(adjustedRect, x.mapRect(br))) { + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) { + if (item->contains(xinv.map(pos))) { + items << item; + keep = true; + } + } + } + + if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { + // Recurse into children that clip children. + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) + d->childItems_helper(&items, item, xinv.map(pos)); + } + } + //### Needed but it should be handle differently + if (order != Qt::SortOrder(-1)) + QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false); + return items; +} + +QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneIndex); + QList<QGraphicsItem *> items; + + QPainterPath path; + + // The index returns a rough estimate of what items are inside the rect. + // Refine it by iterating through all returned items. + QRectF adjustedRect(rect); + _q_adjustRect(&adjustedRect); + foreach (QGraphicsItem *item, estimateItems(adjustedRect, order, deviceTransform)) { + // Find the item's scene transform in a clever way. + QTransform x = item->sceneTransform(); + bool keep = false; + + // ### _q_adjustedRect is only needed because QRectF::intersects, + // QRectF::contains and QTransform::map() and friends don't work with + // flat rectangles. + const QRectF br(adjustedItemBoundingRect(item)); + if (mode >= Qt::ContainsItemBoundingRect) { + // Rect intersects/contains item's bounding rect + QRectF mbr = x.mapRect(br); + if ((mode == Qt::IntersectsItemBoundingRect && QRectF_intersects(rect, mbr)) + || (mode == Qt::ContainsItemBoundingRect && rect != mbr && rect.contains(mbr))) { + items << item; + keep = true; + } + } else { + // Rect intersects/contains item's shape + if (QRectF_intersects(adjustedRect, x.mapRect(br))) { + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) { + if (path.isEmpty()) + path.addRect(rect); + if (d->scene->d_func()->itemCollidesWithPath(item, xinv.map(path), mode)) { + items << item; + keep = true; + } + } + } + } + + if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { + // Recurse into children that clip children. + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) { + if (x.type() <= QTransform::TxScale) { + // Rect + d->childItems_helper(&items, item, xinv.mapRect(rect), mode); + } else { + // Polygon + d->childItems_helper(&items, item, xinv.map(rect), mode); + } + } + } + } + //### Needed but it should be handle differently + if (order != Qt::SortOrder(-1)) + QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false); + return items; +} + +QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneIndex); + QList<QGraphicsItem *> items; + + QRectF polyRect(polygon.boundingRect()); + _q_adjustRect(&polyRect); + QPainterPath path; + + // The index returns a rough estimate of what items are inside the rect. + // Refine it by iterating through all returned items. + foreach (QGraphicsItem *item, estimateItems(polyRect, order, deviceTransform)) { + // Find the item's scene transform in a clever way. + QTransform x = item->sceneTransform(); + bool keep = false; + + // ### _q_adjustedRect is only needed because QRectF::intersects, + // QRectF::contains and QTransform::map() and friends don't work with + // flat rectangles. + const QRectF br(adjustedItemBoundingRect(item)); + if (mode >= Qt::ContainsItemBoundingRect) { + // Polygon contains/intersects item's bounding rect + if (path == QPainterPath()) + path.addPolygon(polygon); + if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br))) + || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) { + items << item; + keep = true; + } + } else { + // Polygon contains/intersects item's shape + if (QRectF_intersects(polyRect, x.mapRect(br))) { + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) { + if (path == QPainterPath()) + path.addPolygon(polygon); + if (d->scene->d_func()->itemCollidesWithPath(item, xinv.map(path), mode)) { + items << item; + keep = true; + } + } + } + } + + if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { + // Recurse into children that clip children. + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) + d->childItems_helper(&items, item, xinv.map(polygon), mode); + } + } + //### Needed but it should be handle differently + if (order != Qt::SortOrder(-1)) + QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false); + return items; +} +QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneIndex); + QList<QGraphicsItem *> items; + QRectF pathRect(path.controlPointRect()); + _q_adjustRect(&pathRect); + + // The index returns a rough estimate of what items are inside the rect. + // Refine it by iterating through all returned items. + foreach (QGraphicsItem *item, estimateItems(pathRect, order, deviceTransform)) { + // Find the item's scene transform in a clever way. + QTransform x = item->sceneTransform(); + bool keep = false; + + // ### _q_adjustedRect is only needed because QRectF::intersects, + // QRectF::contains and QTransform::map() and friends don't work with + // flat rectangles. + const QRectF br(adjustedItemBoundingRect(item)); + if (mode >= Qt::ContainsItemBoundingRect) { + // Path contains/intersects item's bounding rect + if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br))) + || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) { + items << item; + keep = true; + } + } else { + // Path contains/intersects item's shape + if (QRectF_intersects(pathRect, x.mapRect(br))) { + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) { + if (d->scene->d_func()->itemCollidesWithPath(item, xinv.map(path), mode)) { + items << item; + keep = true; + } + } + } + } + + if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) { + bool ok; + QTransform xinv = x.inverted(&ok); + if (ok) + d->childItems_helper(&items, item, xinv.map(path), mode); + } + } + //### Needed but it should be handle differently + if (order != Qt::SortOrder(-1)) + QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false); + return items; +} + +/*! + This pure virtual function return an estimation of items at position \a pos. + +*/ +QList<QGraphicsItem *> QGraphicsSceneIndex::estimateItems(const QPointF &point, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + return estimateItems(QRectF(point, QSize(1,1)), order, deviceTransform); +} + +/*! + \fn virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const = 0 + + This pure virtual function return an estimation of items in the \a rect. + +*/ + + +/*! + This virtual function removes all items in the scene index. +*/ +void QGraphicsSceneIndex::clear() +{ + for (int i = 0 ; i < items().size(); ++i) + removeItem(items().at(i)); +} + +/*! + \fn virtual void addItem(QGraphicsItem *item) = 0 + + This pure virtual function inserts an item to the scene index. + + \sa removeItem(), deleteItem() +*/ + +/*! + \fn virtual void removeItem(QGraphicsItem *item) = 0 + + This pure virtual function removes an item to the scene index. + + \sa addItem(), deleteItem() +*/ + +/*! + This method is called when an item has been deleted. + The default implementation call removeItem. Be carefull, + if your implementation of removeItem use pure virtual method + of QGraphicsItem like boundingRect(), then you should reimplement + this method. + + \sa addItem(), removeItem() +*/ +void QGraphicsSceneIndex::deleteItem(QGraphicsItem *item) +{ + removeItem(item); +} + +/*! + This virtual function is called by QGraphicsItem to notify the index + that some part of the item's state changes. By reimplementing this + function, your can react to a change, and in some cases, (depending on \a + change,) adjustments in the index can be made. + + \a change is the parameter of the item that is changing. \a value is the + value that changed; the type of the value depends on \a change. + + The default implementation does nothing. + + \sa GraphicsItemChange +*/ +void QGraphicsSceneIndex::itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange, const QVariant &value) +{ +} + +/*! + Notify the index for a geometry change of an item. + + \sa QGraphicsItem::prepareGeometryChange +*/ +void QGraphicsSceneIndex::prepareBoundingRectChange(const QGraphicsItem *item) +{ +} + +/*! + This virtual function is called when the scene changes its bounding + rectangle. + \sa QGraphicsScene::sceneRect +*/ +void QGraphicsSceneIndex::sceneRectChanged(const QRectF &rect) +{ +} + +QT_END_NAMESPACE + +#include "moc_qgraphicssceneindex.cpp" + +#endif // QT_NO_GRAPHICSVIEW diff --git a/src/gui/graphicsview/qgraphicssceneindex.h b/src/gui/graphicsview/qgraphicssceneindex.h new file mode 100644 index 0000000..084a623 --- /dev/null +++ b/src/gui/graphicsview/qgraphicssceneindex.h @@ -0,0 +1,112 @@ +/**************************************************************************** +** +** 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 QGRAPHICSSCENEINDEX_H +#define QGRAPHICSSCENEINDEX_H + +#include <QtCore/qnamespace.h> +#include <QtCore/qobject.h> +#include <QtGui/qtransform.h> +#include <QtGui/qgraphicsitem.h> + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Gui) + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +class QGraphicsSceneIndexPrivate; +class QGraphicsScene; +class QRectF; +class QPointF; +template<typename T> class QList; + +class Q_GUI_EXPORT QGraphicsSceneIndex: public QObject +{ + Q_OBJECT + +public: + QGraphicsSceneIndex(QGraphicsScene *scene = 0); + virtual ~QGraphicsSceneIndex(); + + QGraphicsScene *scene() const; + + virtual QRectF indexedRect() const; + + 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; + virtual QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + virtual QList<QGraphicsItem *> estimateItems(const QPointF &point, Qt::SortOrder order, const QTransform &deviceTransform) const; + virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const = 0; + +protected: + virtual void clear(); + virtual void addItem(QGraphicsItem *item) = 0; + virtual void removeItem(QGraphicsItem *item) = 0; + virtual void deleteItem(QGraphicsItem *item); + + virtual void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange, const QVariant &value); + 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) +}; + +#endif // QT_NO_GRAPHICSVIEW + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QGRAPHICSSCENEINDEX_H diff --git a/src/gui/graphicsview/qgraphicssceneindex_p.h b/src/gui/graphicsview/qgraphicssceneindex_p.h new file mode 100644 index 0000000..2014693 --- /dev/null +++ b/src/gui/graphicsview/qgraphicssceneindex_p.h @@ -0,0 +1,97 @@ +/**************************************************************************** +** +** 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 QGRAPHICSSCENEINDEX_P_H +#define QGRAPHICSSCENEINDEX_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 "qgraphicssceneindex.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 QGraphicsSceneIndexPrivate : public QObjectPrivate +{ + Q_DECLARE_PUBLIC(QGraphicsSceneIndex) +public: + QGraphicsSceneIndexPrivate(QGraphicsScene *scene); + + + void childItems_helper(QList<QGraphicsItem *> *items, + const QGraphicsItem *parent, + const QPointF &pos) const; + void childItems_helper(QList<QGraphicsItem *> *items, + const QGraphicsItem *parent, + const QRectF &rect, + Qt::ItemSelectionMode mode) const; + void childItems_helper(QList<QGraphicsItem *> *items, + const QGraphicsItem *parent, + const QPolygonF &polygon, + Qt::ItemSelectionMode mode) const; + void childItems_helper(QList<QGraphicsItem *> *items, + const QGraphicsItem *parent, + const QPainterPath &path, + Qt::ItemSelectionMode mode) const; + + QGraphicsScene *scene; +}; + +QT_END_NAMESPACE + +#endif // QGRAPHICSSCENEINDEX_P_H + +#endif diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h new file mode 100644 index 0000000..3057b4a --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h @@ -0,0 +1,117 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QGRAPHICSSCENELINEARINDEX_P_H +#define QGRAPHICSSCENELINEARINDEX_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/qlist.h> + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include <QtCore/qrect.h> +#include <QtCore/qlist.h> +#include <QtGui/qgraphicssceneindex.h> +#include <QtGui/qgraphicsitem.h> + +QT_BEGIN_NAMESPACE + +class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex +{ + Q_OBJECT + +private: + QRectF m_sceneRect; + QList<QGraphicsItem*> m_items; + +public: + QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0): QGraphicsSceneIndex(scene) + { + } + + virtual void setRect(const QRectF &rect) { + m_sceneRect = rect; + } + + virtual QRectF rect() const { + return m_sceneRect; + } + + virtual void clear() { + m_items.clear(); + } + + virtual void addItem(QGraphicsItem *item) { + m_items << item; + } + + virtual void removeItem(QGraphicsItem *item) { + m_items.removeAll(item); + } + + virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const { + QList<QGraphicsItem*> result; + foreach (QGraphicsItem *item, m_items) + if (item->sceneBoundingRect().intersects(rect)) + result << item; + return result; + } + + QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const { + return m_items; + } +}; + +QT_END_NAMESPACE + +#endif // QT_NO_GRAPHICSVIEW + +#endif // QGRAPHICSSCENELINEARINDEX_P_H diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp index 10b837a..e8330a9 100644 --- a/src/gui/graphicsview/qgraphicsview.cpp +++ b/src/gui/graphicsview/qgraphicsview.cpp @@ -791,19 +791,6 @@ QRegion QGraphicsViewPrivate::mapToViewRegion(const QGraphicsItem *item, const Q return item->boundingRegion(itv) & itv.mapRect(rect).toAlignedRect(); } -// QRectF::intersects() returns false always if either the source or target -// rectangle's width or height are 0. This works around that problem. -static inline QRectF adjustedItemBoundingRect(const QGraphicsItem *item) -{ - Q_ASSERT(item); - QRectF boundingRect(item->boundingRect()); - if (!boundingRect.width()) - boundingRect.adjust(-0.00001, 0, 0.00001, 0); - if (!boundingRect.height()) - boundingRect.adjust(0, -0.00001, 0, 0.00001); - return boundingRect; -} - /*! \internal */ @@ -1069,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); @@ -1082,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; } @@ -1094,7 +1078,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg bool simpleRectLookup = (scene->d_func()->largestUntransformableItem.isNull() && exposedRegion.numRects() == 1 && matrix.type() <= QTransform::TxScale); if (simpleRectLookup) { - return scene->d_func()->items_helper(exposedRegionSceneBounds, + return scene->d_func()->index->items(exposedRegionSceneBounds, Qt::IntersectsItemBoundingRect, Qt::DescendingOrder); } @@ -1109,7 +1093,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg const QPainterPath exposedPath(qt_regionToPath(adjustedRegion)); if (scene->d_func()->largestUntransformableItem.isNull()) { const QPainterPath exposedScenePath(q->mapToScene(exposedPath)); - return scene->d_func()->items_helper(exposedScenePath, + return scene->d_func()->index->items(exposedScenePath, Qt::IntersectsItemBoundingRect, Qt::DescendingOrder); } @@ -2143,17 +2127,19 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat // First build a (potentially large) list of all items in the vicinity // that might be untransformable. - QList<QGraphicsItem *> allCandidates = scene->d_func()->estimateItemsInRect(adjustedRect); + QList<QGraphicsItem *> allCandidates = scene->d_func()->index->estimateItems(adjustedRect, order, q->transform()); // 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(); QList<QGraphicsItem *> result; + //### this will disapear + // Run through all candidates and keep all items that are in candSet, or // are untransformable and collide with \a path. ### We can improve this // algorithm. @@ -2172,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; } |