diff options
23 files changed, 2635 insertions, 1584 deletions
diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri index 4cee6d6..0c0747e 100644 --- a/src/gui/graphicsview/graphicsview.pri +++ b/src/gui/graphicsview/graphicsview.pri @@ -1,37 +1,42 @@ # Qt graphicsview module -HEADERS += graphicsview/qgraphicsitem.h \ +HEADERS += graphicsview/qgraphicsgridlayout.h \ + graphicsview/qgraphicsitem.h \ graphicsview/qgraphicsitem_p.h \ graphicsview/qgraphicsitemanimation.h \ - graphicsview/qgraphicsscene.h \ - graphicsview/qgraphicsscene_p.h \ - graphicsview/qgraphicsscene_bsp_p.h \ - graphicsview/qgraphicssceneevent.h \ - graphicsview/qgraphicsview_p.h \ - graphicsview/qgraphicsview.h -SOURCES += graphicsview/qgraphicsitem.cpp \ - graphicsview/qgraphicsitemanimation.cpp \ - graphicsview/qgraphicsscene.cpp \ - graphicsview/qgraphicsscene_bsp.cpp \ - graphicsview/qgraphicssceneevent.cpp \ - graphicsview/qgraphicsview.cpp - -# Widgets on the canvas -HEADERS += graphicsview/qgraphicslayout.h \ + graphicsview/qgraphicslayout.h \ graphicsview/qgraphicslayout_p.h \ graphicsview/qgraphicslayoutitem.h \ graphicsview/qgraphicslayoutitem_p.h \ graphicsview/qgraphicslinearlayout.h \ + graphicsview/qgraphicsproxywidget.h \ + graphicsview/qgraphicsscene.h \ + graphicsview/qgraphicsscene_bsp_p.h \ + graphicsview/qgraphicsscene_p.h \ + graphicsview/qgraphicsscenebsptreeindex_p.h \ + graphicsview/qgraphicssceneevent.h \ + graphicsview/qgraphicssceneindex_p.h \ + graphicsview/qgraphicsscenelinearindex_p.h \ + graphicsview/qgraphicsview.h \ + graphicsview/qgraphicsview_p.h \ graphicsview/qgraphicswidget.h \ graphicsview/qgraphicswidget_p.h \ - graphicsview/qgridlayoutengine_p.h \ - graphicsview/qgraphicsproxywidget.h \ - graphicsview/qgraphicsgridlayout.h -SOURCES += graphicsview/qgraphicslayout.cpp \ + graphicsview/qgridlayoutengine_p.h + +SOURCES += graphicsview/qgraphicsgridlayout.cpp \ + graphicsview/qgraphicsitem.cpp \ + graphicsview/qgraphicsitemanimation.cpp \ + graphicsview/qgraphicslayout.cpp \ graphicsview/qgraphicslayout_p.cpp \ graphicsview/qgraphicslayoutitem.cpp \ graphicsview/qgraphicslinearlayout.cpp \ + graphicsview/qgraphicsproxywidget.cpp \ + graphicsview/qgraphicsscene.cpp \ + graphicsview/qgraphicsscene_bsp.cpp \ + graphicsview/qgraphicsscenebsptreeindex.cpp \ + graphicsview/qgraphicssceneevent.cpp \ + graphicsview/qgraphicssceneindex.cpp \ + graphicsview/qgraphicsscenelinearindex.cpp \ + graphicsview/qgraphicsview.cpp \ graphicsview/qgraphicswidget.cpp \ graphicsview/qgraphicswidget_p.cpp \ - graphicsview/qgridlayoutengine.cpp \ - graphicsview/qgraphicsproxywidget.cpp \ - graphicsview/qgraphicsgridlayout.cpp + graphicsview/qgridlayoutengine.cpp diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp index 2223f5d..002eab9 100644 --- a/src/gui/graphicsview/qgraphicsitem.cpp +++ b/src/gui/graphicsview/qgraphicsitem.cpp @@ -554,6 +554,7 @@ #include "qgraphicsview.h" #include "qgraphicswidget.h" #include "qgraphicsproxywidget.h" +#include "qgraphicsscenebsptreeindex_p.h" #include <QtCore/qbitarray.h> #include <QtCore/qdebug.h> #include <QtCore/qpoint.h> @@ -585,17 +586,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); @@ -870,6 +860,11 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent) if (newParent == parent) return; + if (scene) { + // Deliver the change to the index + scene->d_func()->index->itemChange(q, QGraphicsItem::ItemParentChange, newParentVariant); + } + if (QGraphicsWidget *w = isWidget ? static_cast<QGraphicsWidget *>(q) : q->parentWidget()) { // Update the child focus chain; when reparenting a widget that has a // focus child, ensure that that focus child clears its focus child @@ -957,12 +952,6 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent) } } - if (scene) { - // Invalidate any sort caching; arrival of a new item means we need to - // resort. - scene->d_func()->invalidateSortCache(); - } - // Resolve depth. resolveDepth(parent ? parent->d_ptr->depth : -1); dirtySceneTransform = 1; @@ -1442,6 +1431,8 @@ void QGraphicsItem::setFlags(GraphicsItemFlags flags) flags = GraphicsItemFlags(itemChange(ItemFlagsChange, quint32(flags)).toUInt()); if (quint32(d_ptr->flags) == quint32(flags)) return; + if (d_ptr->scene) + d_ptr->scene->d_func()->index->itemChange(this, ItemFlagsChange, quint32(flags)); // Flags that alter the geometry of the item (or its children). const quint32 geomChangeFlagsMask = (ItemClipsChildrenToShape | ItemClipsToShape | ItemIgnoresTransformations); @@ -3621,18 +3612,20 @@ void QGraphicsItem::setZValue(qreal z) qreal newZ = qreal(newZVariant.toDouble()); if (newZ == d_ptr->z) return; + + if (d_ptr->scene) { + // Z Value has changed, we have to notify the index. + d_ptr->scene->d_func()->index->itemChange(this, ItemZValueChange, newZVariant); + } + d_ptr->z = newZ; if (d_ptr->parent) d_ptr->parent->d_ptr->needSortChildren = 1; else if (d_ptr->scene) d_ptr->scene->d_func()->needSortTopLevelItems = 1; - if (d_ptr->scene) { + if (d_ptr->scene) d_ptr->scene->d_func()->markDirty(this, QRectF(), /*invalidateChildren=*/true); - // Invalidate any sort caching; arrival of a new item means we need to - // resort. - d_ptr->scene->d_func()->invalidateSortCache(); - } itemChange(ItemZValueHasChanged, newZVariant); @@ -4098,7 +4091,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()); } @@ -6442,7 +6435,7 @@ void QGraphicsItem::addToIndex() return; } if (d_ptr->scene) - d_ptr->scene->d_func()->addToIndex(this); + d_ptr->scene->d_func()->index->addItem(this); } /*! @@ -6459,7 +6452,7 @@ void QGraphicsItem::removeFromIndex() return; } if (d_ptr->scene) - d_ptr->scene->d_func()->removeFromIndex(this); + d_ptr->scene->d_func()->index->removeItem(this); } /*! @@ -6478,10 +6471,12 @@ void QGraphicsItem::removeFromIndex() void QGraphicsItem::prepareGeometryChange() { if (d_ptr->scene) { + d_ptr->scene->d_func()->dirtyGrowingItemsBoundingRect = true; d_ptr->geometryChanged = 1; d_ptr->paintedViewBoundingRectsNeedRepaint = 1; QGraphicsScenePrivate *scenePrivate = d_ptr->scene->d_func(); + scenePrivate->index->prepareBoundingRectChange(this); scenePrivate->markDirty(this, QRectF(), /*invalidateChildren=*/true, /*maybeDirtyClipPath=*/!d_ptr->inSetPosHelper); @@ -6494,8 +6489,6 @@ void QGraphicsItem::prepareGeometryChange() || scenePrivate->views.isEmpty()) { d_ptr->scene->update(sceneTransform().mapRect(boundingRect())); } - - scenePrivate->removeFromIndex(this); } QGraphicsItem *parent = this; @@ -9815,17 +9808,11 @@ QDebug operator<<(QDebug debug, QGraphicsItem *item) return debug; } - QStringList flags; - if (item->isVisible()) flags << QLatin1String("isVisible"); - if (item->isEnabled()) flags << QLatin1String("isEnabled"); - if (item->isSelected()) flags << QLatin1String("isSelected"); - if (item->hasFocus()) flags << QLatin1String("HasFocus"); - debug << "QGraphicsItem(this =" << ((void*)item) << ", parent =" << ((void*)item->parentItem()) << ", pos =" << item->pos() - << ", z =" << item->zValue() << ", flags = {" - << flags.join(QLatin1String("|")) << " })"; + << ", z =" << item->zValue() << ", flags = " + << item->flags() << ")"; return debug; } diff --git a/src/gui/graphicsview/qgraphicsitem.h b/src/gui/graphicsview/qgraphicsitem.h index 3a3d1a1..cd59fae 100644 --- a/src/gui/graphicsview/qgraphicsitem.h +++ b/src/gui/graphicsview/qgraphicsitem.h @@ -141,7 +141,7 @@ public: QGraphicsItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -208,8 +208,8 @@ public: Qt::MouseButtons acceptedMouseButtons() const; void setAcceptedMouseButtons(Qt::MouseButtons buttons); - bool acceptsHoverEvents() const; // obsolete - void setAcceptsHoverEvents(bool enabled); // obsolete + bool acceptsHoverEvents() const; // ### obsolete + void setAcceptsHoverEvents(bool enabled); // ### obsolete bool acceptHoverEvents() const; void setAcceptHoverEvents(bool enabled); bool acceptTouchEvents() const; @@ -441,11 +441,16 @@ private: friend class QGraphicsScene; friend class QGraphicsScenePrivate; friend class QGraphicsSceneFindItemBspTreeVisitor; + friend class QGraphicsSceneBspTree; friend class QGraphicsView; friend class QGraphicsViewPrivate; 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 *); @@ -537,7 +542,7 @@ class Q_GUI_EXPORT QAbstractGraphicsShapeItem : public QGraphicsItem public: QAbstractGraphicsShapeItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -567,13 +572,13 @@ class Q_GUI_EXPORT QGraphicsPathItem : public QAbstractGraphicsShapeItem public: QGraphicsPathItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsPathItem(const QPainterPath &path, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -610,19 +615,19 @@ class Q_GUI_EXPORT QGraphicsRectItem : public QAbstractGraphicsShapeItem public: QGraphicsRectItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsRectItem(const QRectF &rect, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsRectItem(qreal x, qreal y, qreal w, qreal h, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -663,19 +668,19 @@ class Q_GUI_EXPORT QGraphicsEllipseItem : public QAbstractGraphicsShapeItem public: QGraphicsEllipseItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsEllipseItem(const QRectF &rect, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsEllipseItem(qreal x, qreal y, qreal w, qreal h, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -722,14 +727,14 @@ class Q_GUI_EXPORT QGraphicsPolygonItem : public QAbstractGraphicsShapeItem public: QGraphicsPolygonItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsPolygonItem(const QPolygonF &polygon, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -769,19 +774,19 @@ class Q_GUI_EXPORT QGraphicsLineItem : public QGraphicsItem public: QGraphicsLineItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsLineItem(const QLineF &line, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsLineItem(qreal x1, qreal y1, qreal x2, qreal y2, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -829,13 +834,13 @@ public: QGraphicsPixmapItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsPixmapItem(const QPixmap &pixmap, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -891,13 +896,13 @@ class Q_GUI_EXPORT QGraphicsTextItem : public QGraphicsObject public: QGraphicsTextItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsTextItem(const QString &text, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -992,13 +997,13 @@ class Q_GUI_EXPORT QGraphicsSimpleTextItem : public QAbstractGraphicsShapeItem public: QGraphicsSimpleTextItem(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); QGraphicsSimpleTextItem(const QString &text, QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); @@ -1038,7 +1043,7 @@ class Q_GUI_EXPORT QGraphicsItemGroup : public QGraphicsItem public: QGraphicsItemGroup(QGraphicsItem *parent = 0 #ifndef Q_QDOC - // obsolete argument + // ### obsolete argument , QGraphicsScene *scene = 0 #endif ); diff --git a/src/gui/graphicsview/qgraphicsitem_p.h b/src/gui/graphicsview/qgraphicsitem_p.h index a0d061b..a4b2c25 100644 --- a/src/gui/graphicsview/qgraphicsitem_p.h +++ b/src/gui/graphicsview/qgraphicsitem_p.h @@ -156,7 +156,7 @@ public: dirtyChildrenBoundingRect(1), paintedViewBoundingRectsNeedRepaint(0), dirtySceneTransform(1), - geometryChanged(0), + geometryChanged(1), inDestructor(0), isObject(0), ignoreVisible(0), @@ -171,6 +171,15 @@ public: inline virtual ~QGraphicsItemPrivate() { } + static const QGraphicsItemPrivate *get(const QGraphicsItem *item) + { + return item->d_ptr; + } + static QGraphicsItemPrivate *get(QGraphicsItem *item) + { + return item->d_ptr; + } + void updateAncestorFlag(QGraphicsItem::GraphicsItemFlag childFlag, AncestorFlag flag = NoFlag, bool enabled = false, bool root = true); void setIsMemberOfGroup(bool enabled); diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp index e50ee94..9de6598 100644 --- a/src/gui/graphicsview/qgraphicsscene.cpp +++ b/src/gui/graphicsview/qgraphicsscene.cpp @@ -39,7 +39,6 @@ ** ****************************************************************************/ - /*! \class QGraphicsScene \brief The QGraphicsScene class provides a surface for managing a large @@ -218,6 +217,9 @@ #include "qgraphicsview_p.h" #include "qgraphicswidget.h" #include "qgraphicswidget_p.h" +#include "qgraphicssceneindex_p.h" +#include "qgraphicsscenebsptreeindex_p.h" +#include "qgraphicsscenelinearindex_p.h" #include <QtCore/qdebug.h> #include <QtCore/qlist.h> @@ -252,67 +254,6 @@ QT_BEGIN_NAMESPACE -static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2); - -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()); @@ -332,18 +273,15 @@ static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraph QGraphicsScenePrivate::QGraphicsScenePrivate() : changedSignalMask(0), indexMethod(QGraphicsScene::BspTreeIndex), - bspTreeDepth(0), + index(0), lastItemCount(0), hasSceneRect(false), + dirtyGrowingItemsBoundingRect(true), updateAll(false), calledEmitUpdated(false), processDirtyItemsEmitted(false), selectionChanging(0), needSortTopLevelItems(true), - regenerateIndex(true), - purgePending(false), - indexTimerId(0), - restartIndexTimer(false), stickyFocus(false), hasFocus(false), focusItem(0), @@ -359,9 +297,8 @@ QGraphicsScenePrivate::QGraphicsScenePrivate() allItemsIgnoreHoverEvents(true), allItemsUseDefaultCursor(true), painterStateProtection(true), - sortCacheEnabled(false), - updatingSortCache(false), style(0), + sortCacheEnabled(false), allItemsIgnoreTouchEvents(true) { } @@ -373,6 +310,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); @@ -382,223 +321,25 @@ 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->d_ptr->isFullyTransparent()) - 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->d_ptr->isFullyTransparent()) - 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) +QGraphicsScenePrivate *QGraphicsScenePrivate::get(QGraphicsScene *q) { - return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0); + return q->d_func(); } -/*! - \internal -*/ -void QGraphicsScenePrivate::_q_updateIndex() +void QGraphicsScenePrivate::_q_emitUpdated() { - 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(); - } - } + calledEmitUpdated = false; - // 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(); - } + if (dirtyGrowingItemsBoundingRect) { + if (!hasSceneRect) { + const QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect; + growingItemsBoundingRect |= q->itemsBoundingRect(); + if (oldGrowingItemsBoundingRect != growingItemsBoundingRect) + emit q->sceneRectChanged(growingItemsBoundingRect); } + dirtyGrowingItemsBoundingRect = false; } - unindexedItems.clear(); - - // Notify scene rect changes. - if (!hasSceneRect && growingItemsBoundingRect != oldGrowingItemsBoundingRect) - emit q->sceneRectChanged(growingItemsBoundingRect); -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::_q_emitUpdated() -{ - Q_Q(QGraphicsScene); - calledEmitUpdated = false; // Ensure all views are connected if anything is connected. This disables // the optimization that items send updates directly to the views, but it @@ -647,19 +388,6 @@ void QGraphicsScenePrivate::unregisterTopLevelItem(QGraphicsItem *item) /*! \internal - - Updates all items in the pending update list. At this point, the list is - unlikely to contain partially constructed items. -*/ -void QGraphicsScenePrivate::_q_updateLater() -{ - foreach (QGraphicsItem *item, pendingUpdateItems) - item->update(); - pendingUpdateItems.clear(); -} - -/*! - \internal */ void QGraphicsScenePrivate::_q_polishItems() { @@ -684,6 +412,7 @@ void QGraphicsScenePrivate::_q_processDirtyItems() const bool wasPendingSceneUpdate = calledEmitUpdated; const QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect; processDirtyItemsRecursive(0); + dirtyGrowingItemsBoundingRect = false; if (!hasSceneRect && oldGrowingItemsBoundingRect != growingItemsBoundingRect) emit q_func()->sceneRectChanged(growingItemsBoundingRect); @@ -728,22 +457,16 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item) // Clear focus on the item to remove any reference in the focusWidget chain. item->clearFocus(); + markDirty(item, QRectF(), false, false, false, false, /*removingItemFromScene=*/true); - if (!item->d_ptr->inDestructor) { + if (item->d_ptr->inDestructor) { + // The item is actually in its destructor, we call the special method in the index. + index->deleteItem(item); + } else { // Can potentially call item->boundingRect() (virtual function), that's why // we only can call this function if the item is not in its destructor. - removeFromIndex(item); - } else if (item->d_ptr->index != -1) { - // Important: The index is useless until purgeRemovedItems() is called. - indexedItems[item->d_ptr->index] = (QGraphicsItem *)0; - if (!purgePending) - purgePending = true; - removedItems << item; - } else { - // Recently added items are purged immediately. unindexedItems() never - // contains stale items. - unindexedItems.removeAll(item); + index->removeItem(item); } if (!item->d_ptr->inDestructor && item == tabFocusFirst) { @@ -764,17 +487,6 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item) unregisterTopLevelItem(item); } - if (!item->d_ptr->inDestructor) { - // Remove from our item lists. - int index = item->d_func()->index; - if (index != -1) { - freeItemIndexes << index; - indexedItems[index] = 0; - } else { - unindexedItems.removeAll(item); - } - } - // Reset the mouse grabber and focus item data. if (item == focusItem) focusItem = 0; @@ -794,7 +506,6 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item) hoverItems.removeAll(item); cachedItemsUnderMouse.removeAll(item); unpolishedItems.removeAll(item); - pendingUpdateItems.removeAll(item); resetDirtyItem(item); //We remove all references of item from the sceneEventFilter arrays @@ -832,45 +543,6 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item) /*! \internal - - Removes stale pointers from all data structures. -*/ -void QGraphicsScenePrivate::purgeRemovedItems() -{ - 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; -} - -/*! - \internal - - Starts or restarts the timer used for reindexing unindexed items. -*/ -void QGraphicsScenePrivate::startIndexTimer(int interval) -{ - Q_Q(QGraphicsScene); - if (indexTimerId) { - restartIndexTimer = true; - } else { - indexTimerId = q->startTimer(interval); - } -} - -/*! - \internal */ void QGraphicsScenePrivate::addPopup(QGraphicsWidget *widget) { @@ -1105,41 +777,20 @@ QList<QGraphicsItem *> QGraphicsScenePrivate::itemsAtPosition(const QPoint &scre { Q_Q(const QGraphicsScene); QGraphicsView *view = widget ? qobject_cast<QGraphicsView *>(widget->parentWidget()) : 0; - QList<QGraphicsItem *> items; - if (view) - items = view->items(view->viewport()->mapFromGlobal(screenPos)); - else - items = q->items(scenePos); - return items; -} + if (!view) + return q->items(scenePos, Qt::IntersectsItemShape, Qt::AscendingOrder, QTransform()); -/*! - \internal + const QRectF pointRect(QPointF(widget->mapFromGlobal(screenPos)), QSizeF(1, 1)); + if (!view->isTransformed()) + return q->items(pointRect, Qt::IntersectsItemShape, Qt::AscendingOrder); - Checks if item collides with the path and mode, but also checks that if it - doesn't collide, maybe its frame rect will. -*/ -bool QGraphicsScenePrivate::itemCollidesWithPath(QGraphicsItem *item, - const QPainterPath &path, - Qt::ItemSelectionMode mode) -{ - if (item->collidesWithPath(path, mode)) - return true; - if (item->isWidget()) { - // Check if this is a window, and if its frame rect collides. - QGraphicsWidget *widget = static_cast<QGraphicsWidget *>(item); - if (widget->isWindow()) { - QRectF frameRect = widget->windowFrameRect(); - QPainterPath framePath; - framePath.addRect(frameRect); - bool intersects = path.intersects(frameRect); - if (mode == Qt::IntersectsItemShape || mode == Qt::IntersectsItemBoundingRect) - return intersects || path.contains(frameRect.topLeft()) - || framePath.contains(path.elementAt(0)); - return !intersects && path.contains(frameRect.topLeft()); - } + const QTransform viewTransform = view->viewportTransform(); + if (viewTransform.type() <= QTransform::TxScale) { + return q->items(viewTransform.inverted().mapRect(pointRect), Qt::IntersectsItemShape, + Qt::AscendingOrder, viewTransform); } - return false; + return q->items(viewTransform.inverted().map(pointRect), Qt::IntersectsItemShape, + Qt::AscendingOrder, viewTransform); } /*! @@ -1151,7 +802,7 @@ void QGraphicsScenePrivate::storeMouseButtonsForMouseGrabber(QGraphicsSceneMouse if (event->buttons() & i) { mouseGrabberButtonDownPos.insert(Qt::MouseButton(i), mouseGrabberItems.last()->d_ptr->genericMapFromScene(event->scenePos(), - event->widget())); + event->widget())); mouseGrabberButtonDownScenePos.insert(Qt::MouseButton(i), event->scenePos()); mouseGrabberButtonDownScreenPos.insert(Qt::MouseButton(i), event->screenPos()); } @@ -1430,9 +1081,9 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item) } QList<QGraphicsItem *> QGraphicsScenePrivate::topLevelItemsInStackingOrder(const QTransform *const viewTransform, - QRegion *exposedRegion) + const QRectF &sceneRect) { - if (indexMethod == QGraphicsScene::NoIndex || !exposedRegion) { + if (indexMethod == QGraphicsScene::NoIndex || sceneRect.isNull()) { if (needSortTopLevelItems) { needSortTopLevelItems = false; qStableSort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf); @@ -1440,27 +1091,8 @@ QList<QGraphicsItem *> QGraphicsScenePrivate::topLevelItemsInStackingOrder(const return topLevelItems; } - const QRectF exposedRect = exposedRegion->boundingRect().adjusted(-1, -1, 1, 1); - QRectF sceneRect; - QTransform invertedViewTransform(Qt::Uninitialized); - if (!viewTransform) { - sceneRect = exposedRect; - } else { - invertedViewTransform = viewTransform->inverted(); - sceneRect = invertedViewTransform.mapRect(exposedRect); - } - if (!largestUntransformableItem.isEmpty()) { - // ### Nuke this when we move the indexing code into a separate - // class. All the largestUntransformableItem code should then go - // away, and the estimate function should return untransformable - // items as well. - QRectF untr = largestUntransformableItem; - QRectF ltri = !viewTransform ? untr : invertedViewTransform.mapRect(untr); - ltri.adjust(-untr.width(), -untr.height(), untr.width(), untr.height()); - sceneRect.adjust(-ltri.width(), -ltri.height(), ltri.width(), ltri.height()); - } - - QList<QGraphicsItem *> tmp = estimateItemsInRect(sceneRect); + QList<QGraphicsItem *> tmp = index->estimateItems(sceneRect, Qt::SortOrder(-1), + viewTransform ? *viewTransform : QTransform()); for (int i = 0; i < tmp.size(); ++i) tmp.at(i)->topLevelItem()->d_ptr->itemDiscovered = 1; @@ -1486,722 +1118,6 @@ QList<QGraphicsItem *> QGraphicsScenePrivate::topLevelItemsInStackingOrder(const return tli; } -void QGraphicsScenePrivate::recursive_items_helper(QGraphicsItem *item, QRectF rect, - QList<QGraphicsItem *> *items, - const QTransform &parentTransform, - const QTransform &viewTransform, - Qt::ItemSelectionMode mode, Qt::SortOrder order, - qreal parentOpacity) const -{ - // Calculate opacity. - qreal opacity; - if (item) { - if (!item->d_ptr->visible) - return; - QGraphicsItem *p = item->d_ptr->parent; - bool itemIgnoresParentOpacity = item->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity; - bool parentDoesntPropagateOpacity = (p && (p->d_ptr->flags & QGraphicsItem::ItemDoesntPropagateOpacityToChildren)); - if (!itemIgnoresParentOpacity && !parentDoesntPropagateOpacity) { - opacity = parentOpacity * item->opacity(); - } else { - opacity = item->d_ptr->opacity; - } - if (opacity == 0.0 && !(item->d_ptr->flags & QGraphicsItem::ItemDoesntPropagateOpacityToChildren)) - return; - } else { - opacity = parentOpacity; - } - - // Calculate the full transform for this item. - QTransform transform = parentTransform; - bool keep = false; - if (item) { - item->d_ptr->combineTransformFromParent(&transform, &viewTransform); - - // ### This does not take the clip into account. - QRectF brect = item->boundingRect(); - _q_adjustRect(&brect); - - keep = true; - if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect) - keep = rect.contains(transform.mapRect(brect)) && rect != brect; - else - keep = rect.intersects(transform.mapRect(brect)); - - if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) { - QPainterPath rectPath; - rectPath.addRect(rect); - keep = itemCollidesWithPath(item, transform.inverted().map(rectPath), mode); - } - } - - bool childClip = (item && (item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape)); - bool dontProcessItem = !item || !keep; - bool dontProcessChildren = item && dontProcessItem && childClip; - - // Find and sort children. - QList<QGraphicsItem *> &children = item ? item->d_ptr->children : const_cast<QGraphicsScenePrivate *>(this)->topLevelItems; - if (!dontProcessChildren) { - if (item && item->d_ptr->needSortChildren) { - item->d_ptr->needSortChildren = 0; - qStableSort(children.begin(), children.end(), qt_notclosestLeaf); - } else if (!item && needSortTopLevelItems) { - const_cast<QGraphicsScenePrivate *>(this)->needSortTopLevelItems = false; - qStableSort(children.begin(), children.end(), qt_notclosestLeaf); - } - } - - childClip &= !dontProcessChildren & !children.isEmpty(); - - // Clip. - if (childClip) - rect &= transform.map(item->shape()).controlPointRect(); - - // Process children behind - int i = 0; - if (!dontProcessChildren) { - for (i = 0; i < children.size(); ++i) { - QGraphicsItem *child = children.at(i); - if (!(child->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent)) - break; - recursive_items_helper(child, rect, items, transform, viewTransform, - mode, order, opacity); - } - } - - // Process item - if (!dontProcessItem) - items->append(item); - - // Process children in front - if (!dontProcessChildren) { - for (; i < children.size(); ++i) - recursive_items_helper(children.at(i), rect, items, transform, viewTransform, - mode, order, opacity); - } - - if (!item && order == Qt::AscendingOrder) { - int n = items->size(); - for (int i = 0; i < n / 2; ++i) { - QGraphicsItem *tmp = (*items)[n - i - 1]; - (*items)[n - i - 1] = (*items)[i]; - (*items)[i] = tmp; - } - } -} - -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->transformData && !item->d_ptr->transformData->computedFullTransform().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->transformData && !item->d_ptr->transformData->computedFullTransform().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->transformData || item->d_ptr->transformData->computedFullTransform().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->transformData && !item->d_ptr->transformData->computedFullTransform().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->transformData && !item->d_ptr->transformData->computedFullTransform().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; -} - -static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2) -{ - return qt_closestLeaf(item2, item1); -} - -/*! - \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 @@ -2334,8 +1250,8 @@ QGraphicsScene::QGraphicsScene(QObject *parent) QGraphicsScene::QGraphicsScene(const QRectF &sceneRect, QObject *parent) : QObject(*new QGraphicsScenePrivate, parent) { - setSceneRect(sceneRect); d_func()->init(); + setSceneRect(sceneRect); } /*! @@ -2349,8 +1265,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); } /*! @@ -2387,8 +1303,19 @@ QGraphicsScene::~QGraphicsScene() QRectF QGraphicsScene::sceneRect() const { Q_D(const QGraphicsScene); - const_cast<QGraphicsScenePrivate *>(d)->_q_updateIndex(); - return d->hasSceneRect ? d->sceneRect : d->growingItemsBoundingRect; + if (d->hasSceneRect) + return d->sceneRect; + + if (d->dirtyGrowingItemsBoundingRect) { + // Lazily update the growing items bounding rect + QGraphicsScenePrivate *thatd = const_cast<QGraphicsScenePrivate *>(d); + QRectF oldGrowingBoundingRect = thatd->growingItemsBoundingRect; + thatd->growingItemsBoundingRect |= itemsBoundingRect(); + thatd->dirtyGrowingItemsBoundingRect = false; + if (oldGrowingBoundingRect != thatd->growingItemsBoundingRect) + emit const_cast<QGraphicsScene *>(this)->sceneRectChanged(thatd->growingItemsBoundingRect); + } + return d->growingItemsBoundingRect; } void QGraphicsScene::setSceneRect(const QRectF &rect) { @@ -2396,8 +1323,7 @@ void QGraphicsScene::setSceneRect(const QRectF &rect) if (rect != d->sceneRect) { d->hasSceneRect = !rect.isNull(); d->sceneRect = rect; - d->resetIndex(); - emit sceneRectChanged(rect); + emit sceneRectChanged(d->hasSceneRect ? rect : d->growingItemsBoundingRect); } } @@ -2438,6 +1364,8 @@ void QGraphicsScene::setSceneRect(const QRectF &rect) void QGraphicsScene::render(QPainter *painter, const QRectF &target, const QRectF &source, Qt::AspectRatioMode aspectRatioMode) { + // ### Switch to using the recursive rendering algorithm instead. + // Default source rect = scene rect QRectF sourceRect = source; if (sourceRect.isNull()) @@ -2532,8 +1460,19 @@ QGraphicsScene::ItemIndexMethod QGraphicsScene::itemIndexMethod() const void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method) { Q_D(QGraphicsScene); - d->resetIndex(); + if (d->indexMethod == method) + return; + d->indexMethod = method; + + QList<QGraphicsItem *> oldItems = d->index->items(Qt::AscendingOrder); + delete d->index; + if (method == BspTreeIndex) + d->index = new QGraphicsSceneBspTreeIndex(this); + else + d->index = new QGraphicsSceneLinearIndex(this); + for (int i = oldItems.size() - 1; i >= 0; --i) + d->index->addItem(oldItems.at(i)); } /*! @@ -2571,35 +1510,32 @@ 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->bspTreeDepth() : 0; } void QGraphicsScene::setBspTreeDepth(int depth) { Q_D(QGraphicsScene); - if (d->bspTreeDepth == depth) - return; - if (depth < 0) { qWarning("QGraphicsScene::setBspTreeDepth: invalid depth %d ignored; must be >= 0", 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->setBspTreeDepth(depth); } /*! \property QGraphicsScene::sortCacheEnabled \brief whether sort caching is enabled \since 4.5 + \obsolete - When enabled, this property adds a cache that speeds up sorting and - transformations for scenes with deep hierarchies (i.e., items with many - levels of descendents), at the cost of using more memory (approx. 100 more - bytes of memory per item). - - Items that are not part of a deep hierarchy suffer no penalty from this - cache. + Since Qt 4.6, this property has no effect. */ bool QGraphicsScene::isSortCacheEnabled() const { @@ -2609,10 +1545,9 @@ bool QGraphicsScene::isSortCacheEnabled() const void QGraphicsScene::setSortCacheEnabled(bool enabled) { Q_D(QGraphicsScene); - if (enabled == d->sortCacheEnabled) + if (d->sortCacheEnabled == enabled) return; - if ((d->sortCacheEnabled = enabled)) - d->invalidateSortCache(); + d->sortCacheEnabled = enabled; } /*! @@ -2624,6 +1559,7 @@ void QGraphicsScene::setSortCacheEnabled(bool enabled) */ QRectF QGraphicsScene::itemsBoundingRect() const { + // Does not take untransformable items into account. QRectF boundingRect; foreach (QGraphicsItem *item, items()) boundingRect |= item->sceneBoundingRect(); @@ -2638,29 +1574,24 @@ QRectF QGraphicsScene::itemsBoundingRect() const QList<QGraphicsItem *> QGraphicsScene::items() const { Q_D(const QGraphicsScene); - const_cast<QGraphicsScenePrivate *>(d)->purgeRemovedItems(); + return d->index->items(Qt::AscendingOrder); +} - // 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; - } +/*! + Returns an ordered list of all items on the scene. \a order decides the + sorting. - // 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; + \sa addItem(), removeItem() +*/ +QList<QGraphicsItem *> QGraphicsScene::items(Qt::SortOrder order) const +{ + Q_D(const QGraphicsScene); + return d->index->items(order); } /*! 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() @@ -2668,7 +1599,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); } /*! @@ -2687,9 +1618,7 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QPointF &pos) const QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelectionMode mode) const { Q_D(const QGraphicsScene); - QList<QGraphicsItem *> itemList; - d->recursive_items_helper(0, rect, &itemList, QTransform(), QTransform(), mode, Qt::AscendingOrder); - return itemList; + return d->index->items(rect, mode, Qt::AscendingOrder); } /*! @@ -2713,7 +1642,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); } /*! @@ -2730,7 +1659,85 @@ 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 that, depending on \a mode, are at the specified \a pos + and return a list sorted using \a order. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with \a pos are returned. + + \a deviceTransform is the transformation apply to the view. + + \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); +} + +/*! + \overload + + Returns all visible items that, depending on \a mode, are either inside or + intersect with the specified \a rect and return a list sorted using \a order. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a rect are returned. + + \a deviceTransform is the transformation apply to the view. + + \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 specified \a polygon and return a list sorted using \a order. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a polygon are returned. + + \a deviceTransform is the transformation apply to the view. + + \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 mode, are either inside or + intersect with the specified \a path and return a list sorted using \a order. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a path are returned. + + \a deviceTransform is the transformation apply to the view. + + \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); } /*! @@ -2753,12 +1760,12 @@ QList<QGraphicsItem *> QGraphicsScene::collidingItems(const QGraphicsItem *item, return QList<QGraphicsItem *>(); } + // Does not support ItemIgnoresTransformations. 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; } @@ -2778,6 +1785,13 @@ QGraphicsItem *QGraphicsScene::itemAt(const QPointF &pos) const return itemsAtPoint.isEmpty() ? 0 : itemsAtPoint.first(); } +QGraphicsItem *QGraphicsScene::itemAt(const QPointF &pos, const QTransform &deviceTransform) const +{ + QList<QGraphicsItem *> itemsAtPoint = items(pos, Qt::IntersectsItemShape, + Qt::AscendingOrder, deviceTransform); + return itemsAtPoint.isEmpty() ? 0 : itemsAtPoint.first(); +} + /*! \fn QGraphicsScene::itemAt(qreal x, qreal y) const \overload @@ -2853,6 +1867,21 @@ void QGraphicsScene::setSelectionArea(const QPainterPath &path) */ void QGraphicsScene::setSelectionArea(const QPainterPath &path, Qt::ItemSelectionMode mode) { + setSelectionArea(path, mode, QTransform()); +} + +/*! + \overload + \since 4.3 + + Sets the selection area to \a path using \a mode to determine if items are + included in the selection area. + + \sa clearSelection(), selectionArea() +*/ +void QGraphicsScene::setSelectionArea(const QPainterPath &path, Qt::ItemSelectionMode mode, + const QTransform &deviceTransform) +{ Q_D(QGraphicsScene); // Note: with boolean path operations, we can improve performance here @@ -2868,7 +1897,7 @@ void QGraphicsScene::setSelectionArea(const QPainterPath &path, Qt::ItemSelectio bool changed = false; // Set all items in path to selected. - foreach (QGraphicsItem *item, items(path, mode)) { + foreach (QGraphicsItem *item, items(path, mode, Qt::AscendingOrder, deviceTransform)) { if (item->flags() & QGraphicsItem::ItemIsSelectable) { if (!item->isSelected()) changed = true; @@ -2925,26 +1954,13 @@ void QGraphicsScene::clearSelection() void QGraphicsScene::clear() { Q_D(QGraphicsScene); - // Recursive descent delete - for (int i = 0; i < d->indexedItems.size(); ++i) { - if (QGraphicsItem *item = d->indexedItems.at(i)) { - if (!item->parentItem()) - delete 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(); + // NB! We have to clear the index before deleting items; otherwise the + // index might try to access dangling item pointers. + d->index->clear(); + const QList<QGraphicsItem *> items = d->topLevelItems; + qDeleteAll(items); + Q_ASSERT(d->topLevelItems.isEmpty()); d->lastItemCount = 0; - d->bspTree.clear(); - d->largestUntransformableItem = QRectF(); d->allItemsIgnoreHoverEvents = true; d->allItemsUseDefaultCursor = true; d->allItemsIgnoreTouchEvents = true; @@ -3066,14 +2082,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()) { @@ -3084,29 +2092,18 @@ 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(0); + // 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(). - if (!d->updateAll) { - if (d->pendingUpdateItems.isEmpty()) - QMetaObject::invokeMethod(this, "_q_updateLater", Qt::QueuedConnection); - d->pendingUpdateItems << item; - } + d->markDirty(item); + d->dirtyGrowingItemsBoundingRect = true; // Disable selectionChanged() for individual items ++d->selectionChanging; @@ -4064,16 +3061,6 @@ bool QGraphicsScene::event(QEvent *event) case QEvent::TouchEnd: d->touchEventHandler(static_cast<QTouchEvent *>(event)); 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); } @@ -5477,6 +4464,13 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, bool item->d_ptr->dirty = 0; item->d_ptr->paintedViewBoundingRectsNeedRepaint = 0; } + + if (item->d_ptr->geometryChanged) { + // Update growingItemsBoundingRect. + if (!hasSceneRect && !itemIsHidden) + growingItemsBoundingRect |= item->d_ptr->sceneTransform.mapRect(item->boundingRect()); + item->d_ptr->geometryChanged = 0; + } } // Process item. @@ -5485,13 +4479,6 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, bool const bool untransformableItem = item->d_ptr->itemIsUntransformable(); const QRectF itemBoundingRect = adjustedItemBoundingRect(item); - if (item->d_ptr->geometryChanged) { - // Update growingItemsBoundingRect. - if (!hasSceneRect) - growingItemsBoundingRect |= item->d_ptr->sceneTransform.mapRect(itemBoundingRect); - item->d_ptr->geometryChanged = 0; - } - if (useCompatUpdate && !untransformableItem && qFuzzyIsNull(item->boundingRegionGranularity())) { // This block of code is kept for compatibility. Since 4.5, by default // QGraphicsView does not connect the signal and we use the below diff --git a/src/gui/graphicsview/qgraphicsscene.h b/src/gui/graphicsview/qgraphicsscene.h index c8b147f..7eaa202 100644 --- a/src/gui/graphicsview/qgraphicsscene.h +++ b/src/gui/graphicsview/qgraphicsscene.h @@ -84,6 +84,7 @@ class QGraphicsSimpleTextItem; class QGraphicsTextItem; class QGraphicsView; class QGraphicsWidget; +class QGraphicsSceneIndex; class QHelpEvent; class QInputMethodEvent; class QKeyEvent; @@ -153,22 +154,38 @@ public: QRectF itemsBoundingRect() const; QList<QGraphicsItem *> items() 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 *> items(Qt::SortOrder order) const; // ### Qt 5: unify + + 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; // ### obsolete + QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; // ### obsolete + QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; // ### obsolete + QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; // ### obsolete + QList<QGraphicsItem *> collidingItems(const QGraphicsItem *item, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; - QGraphicsItem *itemAt(const QPointF &pos) const; + + QGraphicsItem *itemAt(const QPointF &pos) const; // ### obsolete + QGraphicsItem *itemAt(const QPointF &pos, const QTransform &deviceTransform) const; inline QList<QGraphicsItem *> items(qreal x, qreal y, qreal w, qreal h, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const - { return items(QRectF(x, y, w, h), mode); } - inline QGraphicsItem *itemAt(qreal x, qreal y) const + { return items(QRectF(x, y, w, h), mode); } // ### obsolete + inline QList<QGraphicsItem *> items(qreal x, qreal y, qreal w, qreal h, Qt::ItemSelectionMode mode, Qt::SortOrder order, + const QTransform &deviceTransform = QTransform()) const + { return items(QRectF(x, y, w, h), mode, order, deviceTransform); } + inline QGraphicsItem *itemAt(qreal x, qreal y) const // ### obsolete { return itemAt(QPointF(x, y)); } + inline QGraphicsItem *itemAt(qreal x, qreal y, const QTransform &deviceTransform) const + { return itemAt(QPointF(x, y), deviceTransform); } QList<QGraphicsItem *> selectedItems() const; QPainterPath selectionArea() const; void setSelectionArea(const QPainterPath &path); - void setSelectionArea(const QPainterPath &path, Qt::ItemSelectionMode); + void setSelectionArea(const QPainterPath &path, Qt::ItemSelectionMode mode); + void setSelectionArea(const QPainterPath &path, Qt::ItemSelectionMode mode, const QTransform &deviceTransform); QGraphicsItemGroup *createItemGroup(const QList<QGraphicsItem *> &items); void destroyItemGroup(QGraphicsItemGroup *group); @@ -276,11 +293,8 @@ Q_SIGNALS: 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_updateLater()) Q_PRIVATE_SLOT(d_func(), void _q_polishItems()) - Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache()) Q_PRIVATE_SLOT(d_func(), void _q_processDirtyItems()) friend class QGraphicsItem; friend class QGraphicsItemPrivate; @@ -288,6 +302,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 3f3e58b..5858eab 100644 --- a/src/gui/graphicsview/qgraphicsscene_bsp.cpp +++ b/src/gui/graphicsview/qgraphicsscene_bsp.cpp @@ -143,19 +143,25 @@ 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; climbTree(findVisitor, rect); + // Reset discovery bits. + for (int i = 0; i < tmp.size(); ++i) + tmp.at(i)->d_ptr->itemDiscovered = 0; return tmp; } -QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos) +QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos) const { QList<QGraphicsItem *> tmp; findVisitor->foundItems = &tmp; climbTree(findVisitor, pos); + // Reset discovery bits. + for (int i = 0; i < tmp.size(); ++i) + tmp.at(i)->d_ptr->itemDiscovered = 0; return tmp; } @@ -235,17 +241,17 @@ 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; const Node &node = nodes.at(index); - int childIndex = firstChildIndex(index); + const int childIndex = firstChildIndex(index); 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,17 +271,17 @@ 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; const Node &node = nodes.at(index); - int childIndex = firstChildIndex(index); + const int childIndex = firstChildIndex(index); switch (node.type) { case Node::Leaf: { - visitor->visit(&leaves[node.leafIndex]); + visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex])); break; } case Node::Vertical: @@ -288,7 +294,6 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con } break; case Node::Horizontal: - int childIndex = firstChildIndex(index); if (rect.top() < node.offset) { climbTree(visitor, rect, childIndex); if (rect.bottom() >= node.offset) diff --git a/src/gui/graphicsview/qgraphicsscene_bsp_p.h b/src/gui/graphicsview/qgraphicsscene_bsp_p.h index 73a937f..323cf04 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 3c3a811..4842e72 100644 --- a/src/gui/graphicsview/qgraphicsscene_p.h +++ b/src/gui/graphicsview/qgraphicsscene_p.h @@ -59,7 +59,6 @@ #include "qgraphicssceneevent.h" #include "qgraphicsview.h" -#include "qgraphicsscene_bsp_p.h" #include "qgraphicsitem_p.h" #include <private/qobject_p.h> @@ -72,10 +71,9 @@ #include <QtGui/qstyle.h> #include <QtGui/qstyleoption.h> -static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; - QT_BEGIN_NAMESPACE +class QGraphicsSceneIndex; class QGraphicsView; class QGraphicsWidget; class QGesture; @@ -87,24 +85,19 @@ public: QGraphicsScenePrivate(); void init(); + static QGraphicsScenePrivate *get(QGraphicsScene *q); + quint32 changedSignalMask; QGraphicsScene::ItemIndexMethod indexMethod; - int bspTreeDepth; + QGraphicsSceneIndex *index; - QList<QGraphicsItem *> estimateItemsInRect(const QRectF &rect) const; - void addToIndex(QGraphicsItem *item); - void removeFromIndex(QGraphicsItem *item); - void resetIndex(); - - QGraphicsSceneBspTree bspTree; - void _q_updateIndex(); int lastItemCount; QRectF sceneRect; bool hasSceneRect; + bool dirtyGrowingItemsBoundingRect; QRectF growingItemsBoundingRect; - QRectF largestUntransformableItem; void _q_emitUpdated(); QList<QRectF> updatedRects; @@ -115,9 +108,6 @@ public: QPainterPath selectionArea; int selectionChanging; QSet<QGraphicsItem *> selectedItems; - QList<QGraphicsItem *> unindexedItems; - QList<QGraphicsItem *> indexedItems; - QList<QGraphicsItem *> pendingUpdateItems; QList<QGraphicsItem *> unpolishedItems; QList<QGraphicsItem *> topLevelItems; bool needSortTopLevelItems; @@ -129,21 +119,11 @@ public: void _q_processDirtyItems(); - QList<int> freeItemIndexes; - bool regenerateIndex; - - bool purgePending; void removeItemHelper(QGraphicsItem *item); - QSet<QGraphicsItem *> removedItems; - void purgeRemovedItems(); QBrush backgroundBrush; QBrush foregroundBrush; - int indexTimerId; - bool restartIndexTimer; - void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT); - bool stickyFocus; bool hasFocus; QGraphicsItem *focusItem; @@ -182,7 +162,6 @@ public: QList<QGraphicsItem *> itemsAtPosition(const QPoint &screenPos, const QPointF &scenePos, QWidget *widget) const; - static bool itemCollidesWithPath(QGraphicsItem *item, const QPainterPath &path, Qt::ItemSelectionMode mode); void storeMouseButtonsForMouseGrabber(QGraphicsSceneMouseEvent *event); QList<QGraphicsView *> views; @@ -211,56 +190,8 @@ public: void mousePressEventHandler(QGraphicsSceneMouseEvent *mouseEvent); QGraphicsWidget *windowForItem(const QGraphicsItem *item) const; - QList<QGraphicsItem *> topLevelItemsInStackingOrder(const QTransform *const, QRegion *); - void recursive_items_helper(QGraphicsItem *item, QRectF rect, QList<QGraphicsItem *> *items, - const QTransform &parentTransform, const QTransform &viewTransform, - Qt::ItemSelectionMode mode, Qt::SortOrder order, qreal parentOpacity = 1.0) 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); + bool sortCacheEnabled; // for compatibility + QList<QGraphicsItem *> topLevelItemsInStackingOrder(const QTransform *const, const QRectF&); void drawItemHelper(QGraphicsItem *item, QPainter *painter, const QStyleOptionGraphicsItem *option, QWidget *widget, @@ -269,7 +200,13 @@ public: inline void drawItems(QPainter *painter, const QTransform *const viewTransform, QRegion *exposedRegion, QWidget *widget) { - const QList<QGraphicsItem *> tli = topLevelItemsInStackingOrder(viewTransform, exposedRegion); + QRectF exposedSceneRect; + if (exposedRegion && indexMethod != QGraphicsScene::NoIndex) { + exposedSceneRect = exposedRegion->boundingRect().adjusted(-1, -1, 1, 1); + if (viewTransform) + exposedSceneRect = viewTransform->inverted().mapRect(exposedSceneRect); + } + const QList<QGraphicsItem *> tli = topLevelItemsInStackingOrder(viewTransform, exposedSceneRect); for (int i = 0; i < tli.size(); ++i) drawSubtreeRecursive(tli.at(i), painter, viewTransform, exposedRegion, widget); return; @@ -326,6 +263,25 @@ public: void enableTouchEventsOnViews(); }; +// 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.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp new file mode 100644 index 0000000..ff9a3da --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp @@ -0,0 +1,760 @@ +/**************************************************************************** +** +** 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$ +** +****************************************************************************/ + +/*! + \class QGraphicsSceneBspTreeIndex + \brief The QGraphicsSceneBspTreeIndex class provides an implementation of + a BSP indexing algorithm for discovering items in QGraphicsScene. + \since 4.6 + \ingroup multimedia + \ingroup graphicsview-api + \mainclass + \internal + + QGraphicsSceneBspTreeIndex index use a BSP(Binary Space Partitioning) + implementation to discover items quickly. This implementation is + very efficient for static scene. It has a depth that you can set. + The depth directly affects performance and memory usage; the latter + growing exponentially with the depth of the tree. With an optimal tree + depth, the index can instantly determine the locality of items, even + for scenes with thousands or millions of items. This also greatly improves + rendering performance. + + By default, the value is 0, in which case Qt will guess a reasonable + default depth based on the size, location and number of items in the + scene. If these parameters change frequently, however, you may experience + slowdowns as the index retunes the depth internally. You can avoid + potential slowdowns by fixating the tree depth through setting this + property. + + The depth of the tree and the size of the scene rectangle decide the + granularity of the scene's partitioning. The size of each scene segment is + determined by the following algorithm: + + The BSP tree has an optimal size when each segment contains between 0 and + 10 items. + + \sa QGraphicsScene, QGraphicsView, QGraphicsSceneIndex +*/ + +#ifndef QT_NO_GRAPHICSVIEW + +#include <private/qgraphicsscene_p.h> +#include <private/qgraphicsscenebsptreeindex_p.h> +#include <private/qgraphicssceneindex_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 bsp index. +*/ +QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene) + : QGraphicsSceneIndexPrivate(scene), + bspTreeDepth(0), + indexTimerId(0), + restartIndexTimer(false), + regenerateIndex(true), + lastItemCount(0), + purgePending(false), + sortCacheEnabled(false), + updatingSortCache(false) +{ +} + + +/*! + This method will update the BSP index by removing the items from the temporary + unindexed list and add them in the indexedItems list. This will also + update the growingItemsBoundingRect if needed. This will update the BSP + implementation as well. + + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex() +{ + Q_Q(QGraphicsSceneBspTreeIndex); + if (!indexTimerId) + return; + + q->killTimer(indexTimerId); + indexTimerId = 0; + + purgeRemovedItems(); + + // Add unindexedItems to indexedItems + for (int i = 0; i < unindexedItems.size(); ++i) { + if (QGraphicsItem *item = unindexedItems.at(i)) { + Q_ASSERT(!item->d_ptr->itemDiscovered); + if (!freeItemIndexes.isEmpty()) { + int freeIndex = freeItemIndexes.takeFirst(); + item->d_func()->index = freeIndex; + indexedItems[freeIndex] = item; + } else { + item->d_func()->index = indexedItems.size(); + indexedItems << item; + } + } + } + + // 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(sceneRect, bspTreeDepth); + unindexedItems = indexedItems; + lastItemCount = indexedItems.size(); + } + + // Insert all unindexed items into the tree. + for (int i = 0; i < unindexedItems.size(); ++i) { + if (QGraphicsItem *item = unindexedItems.at(i)) { + if (item->d_ptr->itemIsUntransformable()) { + untransformableItems << item; + continue; + } + if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) + continue; + + bsp.insertItem(item, item->sceneBoundingRect()); + } + } + unindexedItems.clear(); +} + + +/*! + \internal + + Removes stale pointers from all data structures. +*/ +void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems() +{ + if (!purgePending && removedItems.isEmpty()) + return; + + // Remove stale items from the BSP tree. + bsp.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; +} + +/*! + \internal + + Starts or restarts the timer used for reindexing unindexed items. +*/ +void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer(int interval) +{ + Q_Q(QGraphicsSceneBspTreeIndex); + if (indexTimerId) { + restartIndexTimer = true; + } else { + indexTimerId = q->startTimer(interval); + } +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::resetIndex() +{ + purgeRemovedItems(); + for (int i = 0; i < indexedItems.size(); ++i) { + if (QGraphicsItem *item = indexedItems.at(i)) { + item->d_ptr->index = -1; + Q_ASSERT(!item->d_ptr->itemDiscovered); + unindexedItems << item; + } + } + indexedItems.clear(); + freeItemIndexes.clear(); + untransformableItems.clear(); + regenerateIndex = true; + startIndexTimer(); +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder) +{ + if (!item->d_ptr->children.isEmpty()) { + QList<QGraphicsItem *> childList = item->d_ptr->children; + qStableSort(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)++; + } +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache() +{ + Q_Q(QGraphicsSceneBspTreeIndex); + _q_updateIndex(); + + if (!sortCacheEnabled || !updatingSortCache) + return; + + updatingSortCache = false; + int stackingOrder = 0; + + QList<QGraphicsItem *> topLevels; + const QList<QGraphicsItem *> items = q->items(); + for (int i = 0; i < items.size(); ++i) { + QGraphicsItem *item = items.at(i); + if (item && !item->d_ptr->parent) + topLevels << item; + } + + qStableSort(topLevels.begin(), topLevels.end(), qt_closestLeaf); + for (int i = 0; i < topLevels.size(); ++i) + climbTree(topLevels.at(i), &stackingOrder); +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache() +{ + Q_Q(QGraphicsSceneBspTreeIndex); + if (!sortCacheEnabled || updatingSortCache) + return; + + updatingSortCache = true; + QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection); +} + +void QGraphicsSceneBspTreeIndexPrivate::addItem(QGraphicsItem *item, bool recursive) +{ + if (!item) + return; + + // Prevent reusing a recently deleted pointer: purge all removed item from our lists. + 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; + 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. + if (item->d_ptr->index == -1) { + Q_ASSERT(!unindexedItems.contains(item)); + unindexedItems << item; + startIndexTimer(0); + } else { + Q_ASSERT(indexedItems.contains(item)); + qWarning("QGraphicsSceneBspTreeIndex::addItem: item has already been added to this BSP"); + } + + if (recursive) { + for (int i = 0; i < item->d_ptr->children.size(); ++i) + addItem(item->d_ptr->children.at(i), recursive); + } +} + +void QGraphicsSceneBspTreeIndexPrivate::removeItem(QGraphicsItem *item, bool recursive, + bool moveToUnindexedItems) +{ + if (!item) + return; + + if (item->d_ptr->index != -1) { + Q_ASSERT(item->d_ptr->index < indexedItems.size()); + Q_ASSERT(indexedItems.at(item->d_ptr->index) == item); + Q_ASSERT(!item->d_ptr->itemDiscovered); + freeItemIndexes << item->d_ptr->index; + indexedItems[item->d_ptr->index] = 0; + item->d_ptr->index = -1; + + if (item->d_ptr->itemIsUntransformable()) { + untransformableItems.removeOne(item); + } else if (item->d_ptr->inDestructor) { + // Avoid virtual function calls from the destructor. + purgePending = true; + removedItems << item; + } else if (!(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { + bsp.removeItem(item, item->sceneBoundingRect()); + } + } else { + unindexedItems.removeOne(item); + } + invalidateSortCache(); // ### Only do this when removing from BSP? + + Q_ASSERT(item->d_ptr->index == -1); + Q_ASSERT(!indexedItems.contains(item)); + Q_ASSERT(!unindexedItems.contains(item)); + Q_ASSERT(!untransformableItems.contains(item)); + + if (moveToUnindexedItems) + addItem(item); + + if (recursive) { + for (int i = 0; i < item->d_ptr->children.size(); ++i) + removeItem(item->d_ptr->children.at(i), recursive, moveToUnindexedItems); + } +} + +/*! + 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); +} + +/*! + Sort a list of \a itemList in a specific \a order and use the cache if requested. + + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order, + bool sortCacheEnabled) +{ + if (sortCacheEnabled) { + if (order == Qt::AscendingOrder) { + qStableSort(itemList->begin(), itemList->end(), closestItemFirst_withCache); + } else if (order == Qt::DescendingOrder) { + qStableSort(itemList->begin(), itemList->end(), closestItemLast_withCache); + } + } else { + if (order == Qt::AscendingOrder) { + qStableSort(itemList->begin(), itemList->end(), closestItemFirst_withoutCache); + } else if (order == Qt::DescendingOrder) { + qStableSort(itemList->begin(), itemList->end(), closestItemLast_withoutCache); + } + } +} + +/*! + Constructs a BSP scene index for the given \a scene. +*/ +QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene) + : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene) +{ + +} + +QGraphicsSceneBspTreeIndex::~QGraphicsSceneBspTreeIndex() +{ + Q_D(QGraphicsSceneBspTreeIndex); + for (int i = 0; i < d->indexedItems.size(); ++i) { + // Ensure item bits are reset properly. + if (QGraphicsItem *item = d->indexedItems.at(i)) { + Q_ASSERT(!item->d_ptr->itemDiscovered); + item->d_ptr->index = -1; + } + } +} + +/*! + \reimp + Clear the all the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::clear() +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->bsp.clear(); + d->lastItemCount = 0; + d->freeItemIndexes.clear(); + for (int i = 0; i < d->indexedItems.size(); ++i) { + // Ensure item bits are reset properly. + if (QGraphicsItem *item = d->indexedItems.at(i)) { + Q_ASSERT(!item->d_ptr->itemDiscovered); + item->d_ptr->index = -1; + } + } + d->indexedItems.clear(); + d->unindexedItems.clear(); + d->untransformableItems.clear(); +} + +/*! + Add the \a item into the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->addItem(item); +} + +/*! + Remove the \a item from the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->removeItem(item); +} + +/*! + \reimp + Update the BSP when the \a item 's bounding rect has changed. +*/ +void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item) +{ + if (!item) + return; + + if (item->d_ptr->index == -1 || item->d_ptr->itemIsUntransformable() + || (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { + return; // Item is not in BSP tree; nothing to do. + } + + Q_D(QGraphicsSceneBspTreeIndex); + QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item); + d->removeItem(thatItem, /*recursive=*/false, /*moveToUnindexedItems=*/true); + for (int i = 0; i < item->d_ptr->children.size(); ++i) // ### Do we really need this? + prepareBoundingRectChange(item->d_ptr->children.at(i)); +} + +/*! + Returns an estimation visible items that are either inside or + intersect with the specified \a rect and return a list sorted using \a order. + + \a deviceTransform is the transformation apply to the view. + +*/ +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(); + + // ### Handle items that ignore transformations + Q_UNUSED(deviceTransform); + + 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->visible + && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { + QRectF boundingRect = item->sceneBoundingRect(); + if (QRectF_intersects(boundingRect, rect)) + rectItems << item; + } + } + } + + rectItems += d->untransformableItems; + d->sortItems(&rectItems, order, d->sortCacheEnabled); + + return rectItems; +} + + +/*! + \fn QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order = Qt::AscendingOrder) const; + + Return all items in the BSP index and sort them using \a order. +*/ +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; + } + } + itemList += d->untransformableItems; + if (order != -1) { + //We sort descending order + d->sortItems(&itemList, order, d->sortCacheEnabled); + } + return itemList; +} + +/*! + \property QGraphicsSceneBspTreeIndex::bspTreeDepth + \brief the depth of the BSP index tree + \since 4.6 + + This value determines the depth of BSP tree. The depth + directly affects performance and memory usage; the latter + growing exponentially with the depth of the tree. With an optimal tree + depth, the index can instantly determine the locality of items, even + for scenes with thousands or millions of items. This also greatly improves + rendering performance. + + By default, the value is 0, in which case Qt will guess a reasonable + default depth based on the size, location and number of items in the + scene. If these parameters change frequently, however, you may experience + slowdowns as the index retunes the depth internally. You can avoid + potential slowdowns by fixating the tree depth through setting this + property. + + The depth of the tree and the size of the scene rectangle decide the + granularity of the scene's partitioning. The size of each scene segment is + determined by the following algorithm: + + The BSP tree has an optimal size when each segment contains between 0 and + 10 items. + +*/ +int QGraphicsSceneBspTreeIndex::bspTreeDepth() +{ + Q_D(const QGraphicsSceneBspTreeIndex); + return d->bspTreeDepth; +} + +void QGraphicsSceneBspTreeIndex::setBspTreeDepth(int depth) +{ + Q_D(QGraphicsSceneBspTreeIndex); + if (d->bspTreeDepth == depth) + return; + d->bspTreeDepth = depth; + d->resetIndex(); +} + +/*! + \reimp + + This method react to the \a rect change of the scene and + reset the BSP tree index. +*/ +void QGraphicsSceneBspTreeIndex::updateSceneRect(const QRectF &rect) +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->sceneRect = rect; + d->resetIndex(); +} + +/*! + \reimp + + This method react to the \a change of the \a item and use the \a value to + update the BSP tree if necessary. + +*/ +void QGraphicsSceneBspTreeIndex::itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value) +{ + Q_D(QGraphicsSceneBspTreeIndex); + switch (change) { + case QGraphicsItem::ItemFlagsChange: { + // Handle ItemIgnoresTransformations + bool ignoredTransform = item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations; + bool willIgnoreTransform = value.toUInt() & QGraphicsItem::ItemIgnoresTransformations; + bool clipsChildren = item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape; + bool willClipChildren = value.toUInt() & QGraphicsItem::ItemClipsChildrenToShape; + if ((ignoredTransform != willIgnoreTransform) || (clipsChildren != willClipChildren)) { + QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item); + // Remove item and its descendants from the index and append + // them to the list of unindexed items. Then, when the index + // is updated, they will be put into the bsp-tree or the list + // of untransformable items. + d->removeItem(thatItem, /*recursive=*/true, /*moveToUnidexedItems=*/true); + } + break; + } + case QGraphicsItem::ItemZValueChange: + d->invalidateSortCache(); + break; + case QGraphicsItem::ItemParentChange: { + d->invalidateSortCache(); + // Handle ItemIgnoresTransformations + QGraphicsItem *newParent = qVariantValue<QGraphicsItem *>(value); + bool ignoredTransform = item->d_ptr->itemIsUntransformable(); + bool willIgnoreTransform = (item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations) + || (newParent && newParent->d_ptr->itemIsUntransformable()); + bool ancestorClippedChildren = item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren; + bool ancestorWillClipChildren = newParent + && ((newParent->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape) + || (newParent->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)); + if ((ignoredTransform != willIgnoreTransform) || (ancestorClippedChildren != ancestorWillClipChildren)) { + QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item); + // Remove item and its descendants from the index and append + // them to the list of unindexed items. Then, when the index + // is updated, they will be put into the bsp-tree or the list + // of untransformable items. + d->removeItem(thatItem, /*recursive=*/true, /*moveToUnidexedItems=*/true); + } + break; + } + default: + break; + } + return QGraphicsSceneIndex::itemChange(item, change, value); +} +/*! + \reimp + + Used to catch the timer event. + + \internal +*/ +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..7b431e6 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h @@ -0,0 +1,237 @@ +/**************************************************************************** +** +** 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$ +** +****************************************************************************/ + +// +// 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. +// + +#ifndef QGRAPHICSBSPTREEINDEX_H +#define QGRAPHICSBSPTREEINDEX_H + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Gui) + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include "qgraphicssceneindex_p.h" +#include "qgraphicsitem_p.h" +#include "qgraphicsscene_bsp_p.h" + +#include <QtCore/qglobal.h> +#include <QtCore/qrect.h> +#include <QtCore/qlist.h> + +static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; + +class QGraphicsScene; +class QGraphicsSceneBspTreeIndexPrivate; + +class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex +{ + Q_OBJECT + Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth) +public: + QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0); + ~QGraphicsSceneBspTreeIndex(); + + QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const; + + QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const; + + int bspTreeDepth(); + void setBspTreeDepth(int depth); + +protected Q_SLOTS: + void updateSceneRect(const QRectF &rect); + +protected: + bool event(QEvent *event); + void clear(); + + void addItem(QGraphicsItem *item); + void removeItem(QGraphicsItem *item); + void prepareBoundingRectChange(const QGraphicsItem *item); + + void itemChange(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; +}; + +class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate +{ + Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex) +public: + QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene); + + QGraphicsSceneBspTree bsp; + QRectF sceneRect; + int bspTreeDepth; + int indexTimerId; + bool restartIndexTimer; + bool regenerateIndex; + int lastItemCount; + + QList<QGraphicsItem *> indexedItems; + QList<QGraphicsItem *> unindexedItems; + QList<QGraphicsItem *> untransformableItems; + QList<int> freeItemIndexes; + + bool purgePending; + QSet<QGraphicsItem *> removedItems; + void purgeRemovedItems(); + + void _q_updateIndex(); + void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT); + void resetIndex(); + + void _q_updateSortCache(); + bool sortCacheEnabled; + bool updatingSortCache; + void invalidateSortCache(); + void addItem(QGraphicsItem *item, bool recursive = false); + void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false); + + 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; +} + +/*! + \internal +*/ +static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2) +{ + return qt_closestLeaf(item2, item1); +} + + +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); +} + +#endif // QT_NO_GRAPHICSVIEW + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QGRAPHICSBSPTREEINDEX_H diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp new file mode 100644 index 0000000..2f2f05e --- /dev/null +++ b/src/gui/graphicsview/qgraphicssceneindex.cpp @@ -0,0 +1,593 @@ +/**************************************************************************** +** +** 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$ +** +****************************************************************************/ +/*! + \class QGraphicsSceneIndex + \brief The QGraphicsSceneIndex class provides a base class to implement + a custom indexing algorithm for discovering items in QGraphicsScene. + \since 4.6 + \ingroup multimedia + \ingroup graphicsview-api + \mainclass + \internal + + The QGraphicsSceneIndex class provides a base class to implement + a custom indexing algorithm for discovering items in QGraphicsScene. You + need to subclass it and reimplement addItem, removeItem, estimateItems + and items in order to have an functional indexing. + + \sa QGraphicsScene, QGraphicsView +*/ + +#include "qdebug.h" +#include "qgraphicsscene.h" +#include "qgraphicsitem_p.h" +#include "qgraphicsscene_p.h" +#include "qgraphicswidget.h" +#include "qgraphicssceneindex_p.h" +#include "qgraphicsscenebsptreeindex_p.h" + +#ifndef QT_NO_GRAPHICSVIEW + +QT_BEGIN_NAMESPACE + +class QGraphicsSceneIndexRectIntersector : public QGraphicsSceneIndexIntersector +{ +public: + bool intersect(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode, + const QTransform &transform, const QTransform &deviceTransform) const + { + QRectF brect = item->boundingRect(); + _q_adjustRect(&brect); + + // ### Add test for this (without making things slower?) + Q_UNUSED(exposeRect); + + bool keep = true; + if (QGraphicsItemPrivate::get(item)->itemIsUntransformable()) { + // Untransformable items; map the scene rect to item coordinates. + QRectF itemRect = (deviceTransform * transform.inverted()).mapRect(sceneRect); + if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect) + keep = itemRect.contains(brect) && itemRect != brect; + else + keep = itemRect.intersects(brect); + if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) { + QPainterPath itemPath; + itemPath.addRect(itemRect); + keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, itemPath, mode); + } + } else { + if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect) + keep = sceneRect.contains(transform.mapRect(brect)) && sceneRect != brect; + else + keep = sceneRect.intersects(transform.mapRect(brect)); + if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) { + QPainterPath rectPath; + rectPath.addRect(sceneRect); + keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, transform.inverted().map(rectPath), mode); + } + } + return keep; + } + + QRectF sceneRect; +}; + +class QGraphicsSceneIndexPointIntersector : public QGraphicsSceneIndexIntersector +{ +public: + bool intersect(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode, + const QTransform &transform, const QTransform &deviceTransform) const + { + QRectF brect = item->boundingRect(); + _q_adjustRect(&brect); + + // ### Add test for this (without making things slower?) + Q_UNUSED(exposeRect); + + bool keep = false; + if (QGraphicsItemPrivate::get(item)->itemIsUntransformable()) { + // Untransformable items; map the scene point to item coordinates. + QPointF itemPoint = (deviceTransform * transform.inverted()).map(scenePoint); + keep = brect.contains(itemPoint); + if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) { + QPainterPath pointPath; + pointPath.addRect(QRectF(itemPoint, QSizeF(1, 1))); + keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, pointPath, mode); + } + } else { + QRectF sceneBoundingRect = transform.mapRect(brect); + keep = sceneBoundingRect.intersects(QRectF(scenePoint, QSizeF(1, 1))) && item->contains(transform.inverted().map(scenePoint)); + } + + return keep; + } + + QPointF scenePoint; +}; + +class QGraphicsSceneIndexPathIntersector : public QGraphicsSceneIndexIntersector +{ +public: + bool intersect(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode, + const QTransform &transform, const QTransform &deviceTransform) const + { + QRectF brect = item->boundingRect(); + _q_adjustRect(&brect); + + // ### Add test for this (without making things slower?) + Q_UNUSED(exposeRect); + + bool keep = true; + if (QGraphicsItemPrivate::get(item)->itemIsUntransformable()) { + // Untransformable items; map the scene rect to item coordinates. + QPainterPath itemPath = (deviceTransform * transform.inverted()).map(scenePath); + if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect) + keep = itemPath.contains(brect); + else + keep = itemPath.intersects(brect); + if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) + keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, itemPath, mode); + } else { + if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect) + keep = scenePath.contains(transform.mapRect(brect)); + else + keep = scenePath.intersects(transform.mapRect(brect)); + if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) { + QPainterPath itemPath = transform.inverted().map(scenePath); + keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, itemPath, mode); + } + } + return keep; + } + + QPainterPath scenePath; +}; + +/*! + Constructs a private scene index. +*/ +QGraphicsSceneIndexPrivate::QGraphicsSceneIndexPrivate(QGraphicsScene *scene) : scene(scene) +{ + pointIntersector = new QGraphicsSceneIndexPointIntersector; + rectIntersector = new QGraphicsSceneIndexRectIntersector; + pathIntersector = new QGraphicsSceneIndexPathIntersector; +} + +/*! + Destructor of private scene index. +*/ +QGraphicsSceneIndexPrivate::~QGraphicsSceneIndexPrivate() +{ + delete pointIntersector; + delete rectIntersector; + delete pathIntersector; +} + +/*! + \internal + + Checks if item collides with the path and mode, but also checks that if it + doesn't collide, maybe its frame rect will. +*/ +bool QGraphicsSceneIndexPrivate::itemCollidesWithPath(const QGraphicsItem *item, + const QPainterPath &path, + Qt::ItemSelectionMode mode) +{ + if (item->collidesWithPath(path, mode)) + return true; + if (item->isWidget()) { + // Check if this is a window, and if its frame rect collides. + const QGraphicsWidget *widget = static_cast<const QGraphicsWidget *>(item); + if (widget->isWindow()) { + QRectF frameRect = widget->windowFrameRect(); + QPainterPath framePath; + framePath.addRect(frameRect); + bool intersects = path.intersects(frameRect); + if (mode == Qt::IntersectsItemShape || mode == Qt::IntersectsItemBoundingRect) + return intersects || path.contains(frameRect.topLeft()) + || framePath.contains(path.elementAt(0)); + return !intersects && path.contains(frameRect.topLeft()); + } + } + return false; +} + +/*! + \internal +*/ +void QGraphicsSceneIndexPrivate::recursive_items_helper(QGraphicsItem *item, QRectF exposeRect, + QGraphicsSceneIndexIntersector *intersector, + QList<QGraphicsItem *> *items, + const QTransform &parentTransform, + const QTransform &viewTransform, + Qt::ItemSelectionMode mode, Qt::SortOrder order, + qreal parentOpacity) const +{ + Q_ASSERT(item); + if (!item->d_ptr->visible) + return; + + const qreal opacity = item->d_ptr->combineOpacityFromParent(parentOpacity); + const bool itemIsFullyTransparent = (opacity < 0.0001); + const bool itemHasChildren = !item->d_ptr->children.isEmpty(); + if (itemIsFullyTransparent && (!itemHasChildren || item->d_ptr->childrenCombineOpacity())) + return; + + // Calculate the full transform for this item. + QTransform transform(parentTransform); + item->d_ptr->combineTransformFromParent(&transform, &viewTransform); + + const bool itemClipsChildrenToShape = (item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape); + bool processItem = !itemIsFullyTransparent; + if (processItem) { + processItem = intersector->intersect(item, exposeRect, mode, transform, viewTransform); + if (!processItem && (!itemHasChildren || itemClipsChildrenToShape)) + return; + } // else we know for sure this item has children we must process. + + int i = 0; + if (itemHasChildren) { + // Sort children. + if (item->d_ptr->needSortChildren) { + item->d_ptr->needSortChildren = 0; + qStableSort(item->d_ptr->children.begin(), item->d_ptr->children.end(), qt_notclosestLeaf); + } + + // Clip to shape. + if (itemClipsChildrenToShape) + exposeRect &= transform.map(item->shape()).controlPointRect(); + + // Process children behind + for (i = 0; i < item->d_ptr->children.size(); ++i) { + QGraphicsItem *child = item->d_ptr->children.at(i); + if (!(child->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent)) + break; + if (itemIsFullyTransparent && !(child->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity)) + continue; + recursive_items_helper(child, exposeRect, intersector, items, transform, viewTransform, + mode, order, opacity); + } + } + + // Process item + if (processItem) + items->append(item); + + // Process children in front + if (itemHasChildren) { + for (; i < item->d_ptr->children.size(); ++i) { + QGraphicsItem *child = item->d_ptr->children.at(i); + if (itemIsFullyTransparent && !(child->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity)) + continue; + recursive_items_helper(child, exposeRect, intersector, items, transform, viewTransform, + mode, order, opacity); + } + } +} + +/*! + Constructs an abstract scene index for a given \a scene. +*/ +QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene) +: QObject(*new QGraphicsSceneIndexPrivate(scene), scene) +{ + if (scene) { + connect(scene, SIGNAL(sceneRectChanged(const QRectF&)), + this, SLOT(updateSceneRect(const QRectF&))); + } +} + +/*! + \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; +} + +/*! + \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, + Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform + &deviceTransform) const + + Returns all visible items that, depending on \a mode, are at the specified + \a pos and return a list sorted using \a order. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with \a pos are returned. + + \a deviceTransform is the transformation apply to the view. + + This method use the estimation of the index (estimateItems) and refine the + list to get an exact result. If you want to implement your own refinement + algorithm you can reimplement this method. + + \sa estimateItems() + +*/ +QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, Qt::ItemSelectionMode mode, + Qt::SortOrder order, const QTransform &deviceTransform) const +{ + + Q_D(const QGraphicsSceneIndex); + QList<QGraphicsItem *> itemList; + d->pointIntersector->scenePoint = pos; + d->items_helper(QRectF(pos, QSizeF(1, 1)), d->pointIntersector, &itemList, deviceTransform, mode, order); + return itemList; +} + +/*! + \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, + Qt::ItemSelectionMode mode, 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 rect and return a list sorted using \a order. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a rect are returned. + + \a deviceTransform is the transformation apply to the view. + + This method use the estimation of the index (estimateItems) and refine + the list to get an exact result. If you want to implement your own + refinement algorithm you can reimplement this method. + + \sa estimateItems() + +*/ +QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, Qt::ItemSelectionMode mode, + Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneIndex); + QRectF exposeRect = rect; + _q_adjustRect(&exposeRect); + QList<QGraphicsItem *> itemList; + d->rectIntersector->sceneRect = rect; + d->items_helper(exposeRect, d->rectIntersector, &itemList, deviceTransform, mode, order); + return itemList; +} + +/*! + \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF + &polygon, Qt::ItemSelectionMode mode, 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 polygon and return a list sorted using \a order. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a polygon are returned. + + \a deviceTransform is the transformation apply to the view. + + This method use the estimation of the index (estimateItems) and refine + the list to get an exact result. If you want to implement your own + refinement algorithm you can reimplement this method. + + \sa estimateItems() + +*/ +QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, + Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneIndex); + QList<QGraphicsItem *> itemList; + QRectF exposeRect = polygon.boundingRect(); + _q_adjustRect(&exposeRect); + QPainterPath path; + path.addPolygon(polygon); + d->pathIntersector->scenePath = path; + d->items_helper(exposeRect, d->pathIntersector, &itemList, deviceTransform, mode, order); + return itemList; +} + +/*! + \fn QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath + &path, Qt::ItemSelectionMode mode, 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 path and return a list sorted using \a order. + + The default value for \a mode is Qt::IntersectsItemShape; all items whose + exact shape intersects with or is contained by \a path are returned. + + \a deviceTransform is the transformation apply to the view. + + This method use the estimation of the index (estimateItems) and refine + the list to get an exact result. If you want to implement your own + refinement algorithm you can reimplement this method. + + \sa estimateItems() + +*/ +QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::ItemSelectionMode mode, + Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneIndex); + QList<QGraphicsItem *> itemList; + QRectF exposeRect = path.controlPointRect(); + _q_adjustRect(&exposeRect); + d->pathIntersector->scenePath = path; + d->items_helper(exposeRect, d->pathIntersector, &itemList, deviceTransform, mode, order); + return itemList; +} + +/*! + This virtual function return an estimation of items at position \a point. + This method return a list sorted using \a order. + \a deviceTransform is the transformation apply to the view. +*/ +QList<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 *> + QGraphicsSceneIndex::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 method return a list sorted using \a order. + + \a deviceTransform is the transformation apply to the view. +*/ + +/*! + \fn virtual QList<QGraphicsItem *> + QGraphicsSceneIndex::items(Qt::SortOrder order = Qt::AscendingOrder) const + = 0; This pure virtual function all items in the index and sort them using + \a order. +*/ + + +/*! + Notifies the index that the scene's scene rect has changed. \a rect + is thew new scene rect. + + \sa QGraphicsScene::sceneRect() +*/ +void QGraphicsSceneIndex::updateSceneRect(const QRectF &rect) +{ + Q_UNUSED(rect); +} + +/*! + This virtual function removes all items in the scene index. +*/ +void QGraphicsSceneIndex::clear() +{ + const QList<QGraphicsItem *> allItems = items(); + for (int i = 0 ; i < allItems.size(); ++i) + removeItem(allItems.at(i)); +} + +/*! + \fn virtual void QGraphicsSceneIndex::addItem(QGraphicsItem *item) = 0 + + This pure virtual function inserts an \a item to the scene index. + + \sa removeItem(), deleteItem() +*/ + +/*! + \fn virtual void QGraphicsSceneIndex::removeItem(QGraphicsItem *item) = 0 + + This pure virtual function removes an \a item to the scene index. + + \sa addItem(), deleteItem() +*/ + +/*! + This method is called when an \a 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 \a 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 QGraphicsItem::GraphicsItemChange +*/ +void QGraphicsSceneIndex::itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value) +{ + Q_UNUSED(item); + Q_UNUSED(change); + Q_UNUSED(value); +} + +/*! + Notify the index for a geometry change of an \a item. + + \sa QGraphicsItem::prepareGeometryChange() +*/ +void QGraphicsSceneIndex::prepareBoundingRectChange(const QGraphicsItem *item) +{ + Q_UNUSED(item); +} + +QT_END_NAMESPACE + +#include "moc_qgraphicssceneindex_p.cpp" + +#endif // QT_NO_GRAPHICSVIEW diff --git a/src/gui/graphicsview/qgraphicssceneindex_p.h b/src/gui/graphicsview/qgraphicssceneindex_p.h new file mode 100644 index 0000000..122d7ae --- /dev/null +++ b/src/gui/graphicsview/qgraphicssceneindex_p.h @@ -0,0 +1,182 @@ +/**************************************************************************** +** +** 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 + +// +// 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 "qgraphicsscene_p.h" +#include "qgraphicsscene.h" +#include <private/qobject_p.h> + +#include <QtCore/qnamespace.h> +#include <QtCore/qobject.h> +#include <QtGui/qtransform.h> + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Gui) + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +class QGraphicsSceneIndexIntersector; +class QGraphicsSceneIndexPointIntersector; +class QGraphicsSceneIndexRectIntersector; +class QGraphicsSceneIndexPathIntersector; +class QGraphicsSceneIndexPrivate; +class QPointF; +class QRectF; +template<typename T> class QList; + +class Q_AUTOTEST_EXPORT QGraphicsSceneIndex : public QObject +{ + Q_OBJECT + +public: + QGraphicsSceneIndex(QGraphicsScene *scene = 0); + virtual ~QGraphicsSceneIndex(); + + QGraphicsScene *scene() 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 Q_SLOTS: + virtual void updateSceneRect(const QRectF &rect); + +protected: + virtual void clear(); + virtual void addItem(QGraphicsItem *item) = 0; + virtual void removeItem(QGraphicsItem *item) = 0; + virtual void deleteItem(QGraphicsItem *item); + + virtual void itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange, const QVariant &value); + virtual void prepareBoundingRectChange(const QGraphicsItem *item); + + 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) +}; + +class QGraphicsSceneIndexPrivate : public QObjectPrivate +{ + Q_DECLARE_PUBLIC(QGraphicsSceneIndex) +public: + QGraphicsSceneIndexPrivate(QGraphicsScene *scene); + ~QGraphicsSceneIndexPrivate(); + + static bool itemCollidesWithPath(const QGraphicsItem *item, const QPainterPath &path, Qt::ItemSelectionMode mode); + + void recursive_items_helper(QGraphicsItem *item, QRectF exposeRect, + QGraphicsSceneIndexIntersector *intersector, QList<QGraphicsItem *> *items, + const QTransform &parentTransform, const QTransform &viewTransform, + Qt::ItemSelectionMode mode, Qt::SortOrder order, qreal parentOpacity = 1.0) const; + inline void items_helper(const QRectF &rect, QGraphicsSceneIndexIntersector *intersector, + QList<QGraphicsItem *> *items, const QTransform &viewTransform, + Qt::ItemSelectionMode mode, Qt::SortOrder order) const; + + QGraphicsScene *scene; + QGraphicsSceneIndexPointIntersector *pointIntersector; + QGraphicsSceneIndexRectIntersector *rectIntersector; + QGraphicsSceneIndexPathIntersector *pathIntersector; +}; + +inline void QGraphicsSceneIndexPrivate::items_helper(const QRectF &rect, QGraphicsSceneIndexIntersector *intersector, + QList<QGraphicsItem *> *items, const QTransform &viewTransform, + Qt::ItemSelectionMode mode, Qt::SortOrder order) const +{ + const QList<QGraphicsItem *> tli = scene->d_func()->topLevelItemsInStackingOrder(&viewTransform, rect); + const QTransform identity; + for (int i = 0; i < tli.size(); ++i) + recursive_items_helper(tli.at(i), rect, intersector, items, identity, viewTransform, mode, order); + if (order == Qt::AscendingOrder) { + const int n = items->size(); + for (int i = 0; i < n / 2; ++i) + items->swap(i, n - i - 1); + } +} + +class QGraphicsSceneIndexIntersector +{ +public: + QGraphicsSceneIndexIntersector() { } + virtual ~QGraphicsSceneIndexIntersector() { } + virtual bool intersect(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode, + const QTransform &transform, const QTransform &deviceTransform) const = 0; +}; + +#endif // QT_NO_GRAPHICSVIEW + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QGRAPHICSSCENEINDEX_H diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex.cpp b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp new file mode 100644 index 0000000..bc401f2 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp @@ -0,0 +1,65 @@ +/*! + \class QGraphicsSceneLinearIndex + \brief The QGraphicsSceneLinearIndex class provides an implementation of + a linear indexing algorithm for discovering items in QGraphicsScene. + \since 4.6 + \ingroup multimedia + \ingroup graphicsview-api + \mainclass + \internal + + QGraphicsSceneLinearIndex index is default linear implementation to discover items. + It basically store all items in a list and return them to the scene. + + \sa QGraphicsScene, QGraphicsView, QGraphicsSceneIndex, QGraphicsSceneBspTreeIndex +*/ + +#include <private/qgraphicsscenelinearindex_p.h> + +/*! + \fn QGraphicsSceneLinearIndex::QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0): + + Construct a linear index for the given \a scene. +*/ + +/*! + \fn QList<QGraphicsItem *> QGraphicsSceneLinearIndex::items(Qt::SortOrder order = Qt::AscendingOrder) const; + + Return all items in the index and sort them using \a order. +*/ + + +/*! + \fn virtual QList<QGraphicsItem *> QGraphicsSceneLinearIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const; + + Returns an estimation visible items that are either inside or + intersect with the specified \a rect and return a list sorted using \a order. + + \a deviceTransform is the transformation apply to the view. + +*/ + +/*! + \fn QRectF QGraphicsSceneLinearIndex::indexedRect() const; + \reimp + Return the rect indexed by the the index. +*/ + +/*! + \fn void QGraphicsSceneLinearIndex::clear(); + \reimp + Clear the all the BSP index. +*/ + +/*! + \fn virtual void QGraphicsSceneLinearIndex::addItem(QGraphicsItem *item); + + Add the \a item into the index. +*/ + +/*! + \fn virtual void QGraphicsSceneLinearIndex::removeItem(QGraphicsItem *item); + + Add the \a item from the index. +*/ + diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h new file mode 100644 index 0000000..9463487 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h @@ -0,0 +1,110 @@ +/**************************************************************************** +** +** 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_H +#define QGRAPHICSSCENELINEARINDEX_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> + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Gui) + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include <QtCore/qrect.h> +#include <QtCore/qlist.h> +#include <QtGui/qgraphicsitem.h> +#include <private/qgraphicssceneindex_p.h> + +class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex +{ + Q_OBJECT + +public: + QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0) : QGraphicsSceneIndex(scene) + { } + + QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const + { Q_UNUSED(order); return m_items; } + + virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const + { + Q_UNUSED(rect); + Q_UNUSED(order); + Q_UNUSED(deviceTransform); + return m_items; + } + +protected : + virtual void clear() + { m_items.clear(); } + + virtual void addItem(QGraphicsItem *item) + { m_items << item; } + + virtual void removeItem(QGraphicsItem *item) + { m_items.removeOne(item); } + +private: + QList<QGraphicsItem*> m_items; +}; + +#endif // QT_NO_GRAPHICSVIEW + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QGRAPHICSSCENELINEARINDEX_H diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp index a2adf82..995f3f3 100644 --- a/src/gui/graphicsview/qgraphicsview.cpp +++ b/src/gui/graphicsview/qgraphicsview.cpp @@ -812,19 +812,9 @@ 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 +*/ void QGraphicsViewPrivate::processPendingUpdates() { if (!scene) @@ -954,47 +944,32 @@ extern QPainterPath qt_regionToPath(const QRegion ®ion); is at risk of painting 1 pixel outside the bounding rect. Therefore we must search for items with an adjustment of (-1, -1, 1, 1). */ -QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedRegion, bool *allItems) const +QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedRegion, bool *allItems, + const QTransform &viewTransform) const { Q_Q(const QGraphicsView); // Step 1) If all items are contained within the expose region, then - // return a list of all visible items. + // return a list of all visible items. ### the scene's growing bounding + // rect does not take into account untransformable items. const QRectF exposedRegionSceneBounds = q->mapToScene(exposedRegion.boundingRect().adjusted(-1, -1, 1, 1)) .boundingRect(); if (exposedRegionSceneBounds.contains(scene->d_func()->growingItemsBoundingRect)) { Q_ASSERT(allItems); *allItems = true; - // All items are guaranteed within the exposed region, don't bother using the index. - QList<QGraphicsItem *> itemList(scene->items()); - int i = 0; - while (i < itemList.size()) { - const QGraphicsItem *item = itemList.at(i); - // But we only want to include items that are visible - // The following check is basically the same as item->d_ptr->isInvisible(), except - // that we don't check whether the item clips children to shape or propagates its - // opacity (we loop through all items, so those checks are wrong in this context). - if (!item->isVisible() || item->d_ptr->isClippedAway() || item->d_ptr->isFullyTransparent()) - itemList.removeAt(i); - else - ++i; - } - - // Sort the items. - QGraphicsScenePrivate::sortItems(&itemList, Qt::DescendingOrder, scene->d_func()->sortCacheEnabled); - return itemList; + // All items are guaranteed within the exposed region. + return scene->items(Qt::DescendingOrder); } // Step 2) If the expose region is a simple rect and the view is only // translated or scaled, search for items using // QGraphicsScene::items(QRectF). - bool simpleRectLookup = (scene->d_func()->largestUntransformableItem.isNull() - && exposedRegion.numRects() == 1 && matrix.type() <= QTransform::TxScale); + bool simpleRectLookup = exposedRegion.numRects() == 1 && matrix.type() <= QTransform::TxScale; if (simpleRectLookup) { - return scene->d_func()->items_helper(exposedRegionSceneBounds, - Qt::IntersectsItemBoundingRect, - Qt::DescendingOrder); + return scene->items(exposedRegionSceneBounds, + Qt::IntersectsItemBoundingRect, + Qt::DescendingOrder, viewTransform); } // If the region is complex or the view has a complex transform, adjust @@ -1004,16 +979,9 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg foreach (const QRect &r, exposedRegion.rects()) adjustedRegion += r.adjusted(-1, -1, 1, 1); - 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, - Qt::IntersectsItemBoundingRect, - Qt::DescendingOrder); - } - - // NB! Path must be in viewport coordinates. - return itemsInArea(exposedPath, Qt::IntersectsItemBoundingRect, Qt::DescendingOrder); + const QPainterPath exposedScenePath(q->mapToScene(qt_regionToPath(adjustedRegion))); + return scene->items(exposedScenePath, Qt::IntersectsItemBoundingRect, + Qt::DescendingOrder, viewTransform); } /*! @@ -1922,6 +1890,8 @@ void QGraphicsView::fitInView(const QGraphicsItem *item, Qt::AspectRatioMode asp void QGraphicsView::render(QPainter *painter, const QRectF &target, const QRect &source, Qt::AspectRatioMode aspectRatioMode) { + // ### Switch to using the recursive rendering algorithm instead. + Q_D(QGraphicsView); if (!d->scene || !(painter && painter->isActive())) return; @@ -2018,69 +1988,6 @@ QList<QGraphicsItem *> QGraphicsView::items() const } /*! - Returns all items in the area \a path, which is in viewport coordinates, - also taking untransformable items into consideration. This function is - considerably slower than just checking the scene directly. There is - certainly room for improvement. -*/ -QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &path, - Qt::ItemSelectionMode mode, - Qt::SortOrder order) const -{ - Q_Q(const QGraphicsView); - - // Determine the size of the largest untransformable subtree of children - // mapped to scene coordinates. - QRectF untr = scene->d_func()->largestUntransformableItem; - QRectF ltri = matrix.inverted().mapRect(untr); - ltri.adjust(-untr.width(), -untr.height(), untr.width(), untr.height()); - - QRectF rect = path.controlPointRect(); - - // Find all possible items in the relevant area. - // ### Improve this algorithm; it might be searching a too large area. - QRectF adjustedRect = q->mapToScene(rect.adjusted(-1, -1, 1, 1).toRect()).boundingRect(); - adjustedRect.adjust(-ltri.width(), -ltri.height(), ltri.width(), ltri.height()); - - // First build a (potentially large) list of all items in the vicinity - // that might be untransformable. - QList<QGraphicsItem *> allCandidates = scene->d_func()->estimateItemsInRect(adjustedRect); - - // 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); - QSet<QGraphicsItem *> candSet = QSet<QGraphicsItem *>::fromList(regularCandidates); - - QTransform viewMatrix = q->viewportTransform(); - - QList<QGraphicsItem *> result; - - // 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. - QList<QGraphicsItem *>::Iterator it = allCandidates.begin(); - while (it != allCandidates.end()) { - QGraphicsItem *item = *it; - if (item->d_ptr->itemIsUntransformable()) { - // Check if this untransformable item collides with the - // original selection rect. - QTransform itemTransform = item->deviceTransform(viewMatrix); - if (QGraphicsScenePrivate::itemCollidesWithPath(item, itemTransform.inverted().map(path), mode)) - result << item; - } else { - if (candSet.contains(item)) - result << item; - } - ++it; - } - - // ### Insertion sort would be faster. - if (order != Qt::SortOrder(-1)) - QGraphicsScenePrivate::sortItems(&result, order, scene->d_func()->sortCacheEnabled); - return result; -} - -/*! Returns a list of all the items at the position \a pos in the view. The items are listed in descending Z order (i.e., the first item in the list is the top-most item, and the last item is the bottom-most item). \a pos @@ -2099,17 +2006,22 @@ QList<QGraphicsItem *> QGraphicsView::items(const QPoint &pos) const Q_D(const QGraphicsView); if (!d->scene) return QList<QGraphicsItem *>(); - if (d->scene->d_func()->largestUntransformableItem.isNull()) { - if ((d->identityMatrix || d->matrix.type() <= QTransform::TxScale)) { - QTransform xinv = viewportTransform().inverted(); - return d->scene->items(xinv.mapRect(QRectF(pos.x(), pos.y(), 1, 1))); - } - return d->scene->items(mapToScene(pos.x(), pos.y(), 1, 1)); + // ### Unify these two, and use the items(QPointF) version in + // QGraphicsScene instead. The scene items function could use the viewport + // transform to map the point to a rect/polygon. + if ((d->identityMatrix || d->matrix.type() <= QTransform::TxScale)) { + // Use the rect version + QTransform xinv = viewportTransform().inverted(); + return d->scene->items(xinv.mapRect(QRectF(pos.x(), pos.y(), 1, 1)), + Qt::IntersectsItemShape, + Qt::AscendingOrder, + viewportTransform()); } - - QPainterPath path; - path.addRect(QRectF(pos.x(), pos.y(), 1, 1)); - return d->itemsInArea(path); + // Use the polygon version + return d->scene->items(mapToScene(pos.x(), pos.y(), 1, 1), + Qt::IntersectsItemShape, + Qt::AscendingOrder, + viewportTransform()); } /*! @@ -2136,12 +2048,7 @@ QList<QGraphicsItem *> QGraphicsView::items(const QRect &rect, Qt::ItemSelection Q_D(const QGraphicsView); if (!d->scene) return QList<QGraphicsItem *>(); - if (d->scene->d_func()->largestUntransformableItem.isNull()) - return d->scene->items(mapToScene(rect), mode); - - QPainterPath path; - path.addRect(rect); - return d->itemsInArea(path); + return d->scene->items(mapToScene(rect), mode, Qt::AscendingOrder, viewportTransform()); } /*! @@ -2169,13 +2076,7 @@ QList<QGraphicsItem *> QGraphicsView::items(const QPolygon &polygon, Qt::ItemSel Q_D(const QGraphicsView); if (!d->scene) return QList<QGraphicsItem *>(); - if (d->scene->d_func()->largestUntransformableItem.isNull()) - return d->scene->items(mapToScene(polygon), mode); - - QPainterPath path; - path.addPolygon(polygon); - path.closeSubpath(); - return d->itemsInArea(path); + return d->scene->items(mapToScene(polygon), mode, Qt::AscendingOrder, viewportTransform()); } /*! @@ -2195,9 +2096,7 @@ QList<QGraphicsItem *> QGraphicsView::items(const QPainterPath &path, Qt::ItemSe Q_D(const QGraphicsView); if (!d->scene) return QList<QGraphicsItem *>(); - if (d->scene->d_func()->largestUntransformableItem.isNull()) - return d->scene->items(mapToScene(path), mode); - return d->itemsInArea(path); + return d->scene->items(mapToScene(path), mode, Qt::AscendingOrder, viewportTransform()); } /*! @@ -3163,7 +3062,8 @@ void QGraphicsView::mouseMoveEvent(QMouseEvent *event) selectionArea.addPolygon(mapToScene(d->rubberBandRect)); selectionArea.closeSubpath(); if (d->scene) - d->scene->setSelectionArea(selectionArea, d->rubberBandSelectionMode); + d->scene->setSelectionArea(selectionArea, d->rubberBandSelectionMode, + viewportTransform()); return; } } else @@ -3376,8 +3276,7 @@ void QGraphicsView::paintEvent(QPaintEvent *event) } else { // Find all exposed items bool allItems = false; - QList<QGraphicsItem *> itemList = d->findItems(d->exposedRegion, &allItems); - + QList<QGraphicsItem *> itemList = d->findItems(d->exposedRegion, &allItems, viewTransform); if (!itemList.isEmpty()) { // Generate the style options. const int numItems = itemList.size(); diff --git a/src/gui/graphicsview/qgraphicsview_p.h b/src/gui/graphicsview/qgraphicsview_p.h index 8c62f73..7b9fd5e 100644 --- a/src/gui/graphicsview/qgraphicsview_p.h +++ b/src/gui/graphicsview/qgraphicsview_p.h @@ -84,10 +84,6 @@ public: qint64 horizontalScroll() const; qint64 verticalScroll() const; - QList<QGraphicsItem *> itemsInArea(const QPainterPath &path, - Qt::ItemSelectionMode mode = Qt::IntersectsItemShape, - Qt::SortOrder = Qt::AscendingOrder) const; - QPointF mousePressItemPoint; QPointF mousePressScenePoint; QPoint mousePressViewPoint; @@ -176,7 +172,8 @@ public: bool updateSceneSlotReimplementedChecked; QRegion exposedRegion; - QList<QGraphicsItem *> findItems(const QRegion &exposedRegion, bool *allItems) const; + QList<QGraphicsItem *> findItems(const QRegion &exposedRegion, bool *allItems, + const QTransform &viewTransform) const; QPointF mapToScene(const QPointF &point) const; QRectF mapToScene(const QRectF &rect) const; diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro index 5e4764d..6143534 100644 --- a/tests/auto/auto.pro +++ b/tests/auto/auto.pro @@ -150,6 +150,7 @@ SUBDIRS += _networkselftest \ qgraphicspolygonitem \ qgraphicsproxywidget \ qgraphicsscene \ + qgraphicssceneindex \ qgraphicsview \ qgraphicswidget \ qgridlayout \ diff --git a/tests/auto/qgraphicslayout/tst_qgraphicslayout.cpp b/tests/auto/qgraphicslayout/tst_qgraphicslayout.cpp index 536c750..bca673f 100644 --- a/tests/auto/qgraphicslayout/tst_qgraphicslayout.cpp +++ b/tests/auto/qgraphicslayout/tst_qgraphicslayout.cpp @@ -687,7 +687,6 @@ void tst_QGraphicsLayout::ownership() delete top; //don't crash after that. } - } QTEST_MAIN(tst_QGraphicsLayout) diff --git a/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp b/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp index 4247cca..24acd63 100644 --- a/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp +++ b/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp @@ -287,28 +287,46 @@ void tst_QGraphicsScene::construction() void tst_QGraphicsScene::sceneRect() { QGraphicsScene scene; + QSignalSpy sceneRectChanged(&scene, SIGNAL(sceneRectChanged(QRectF))); QCOMPARE(scene.sceneRect(), QRectF()); + QCOMPARE(sceneRectChanged.count(), 0); QGraphicsItem *item = scene.addRect(QRectF(0, 0, 10, 10)); - qApp->processEvents(); item->setPos(-5, -5); - qApp->processEvents(); + QCOMPARE(sceneRectChanged.count(), 0); QCOMPARE(scene.itemAt(0, 0), item); QCOMPARE(scene.itemAt(10, 10), (QGraphicsItem *)0); + QCOMPARE(sceneRectChanged.count(), 0); + QCOMPARE(scene.sceneRect(), QRectF(-5, -5, 10, 10)); + QCOMPARE(sceneRectChanged.count(), 1); + QCOMPARE(sceneRectChanged.last().at(0).toRectF(), scene.sceneRect()); + + item->setPos(0, 0); QCOMPARE(scene.sceneRect(), QRectF(-5, -5, 15, 15)); + QCOMPARE(sceneRectChanged.count(), 2); + QCOMPARE(sceneRectChanged.last().at(0).toRectF(), scene.sceneRect()); scene.setSceneRect(-100, -100, 10, 10); + QCOMPARE(sceneRectChanged.count(), 3); + QCOMPARE(sceneRectChanged.last().at(0).toRectF(), scene.sceneRect()); QCOMPARE(scene.itemAt(0, 0), item); QCOMPARE(scene.itemAt(10, 10), (QGraphicsItem *)0); QCOMPARE(scene.sceneRect(), QRectF(-100, -100, 10, 10)); + item->setPos(10, 10); + QCOMPARE(scene.sceneRect(), QRectF(-100, -100, 10, 10)); + QCOMPARE(sceneRectChanged.count(), 3); + QCOMPARE(sceneRectChanged.last().at(0).toRectF(), scene.sceneRect()); scene.setSceneRect(QRectF()); - QCOMPARE(scene.itemAt(0, 0), item); - QCOMPARE(scene.itemAt(10, 10), (QGraphicsItem *)0); - QCOMPARE(scene.sceneRect(), QRectF(-5, -5, 15, 15)); + QCOMPARE(scene.itemAt(10, 10), item); + QCOMPARE(scene.itemAt(20, 20), (QGraphicsItem *)0); + QCOMPARE(sceneRectChanged.count(), 4); + QCOMPARE(scene.sceneRect(), QRectF(-5, -5, 25, 25)); + QCOMPARE(sceneRectChanged.count(), 5); + QCOMPARE(sceneRectChanged.last().at(0).toRectF(), scene.sceneRect()); } void tst_QGraphicsScene::itemIndexMethod() @@ -397,8 +415,7 @@ void tst_QGraphicsScene::items() for (int x = minX; x < maxX; x += 100) items << scene.addRect(QRectF(0, 0, 10, 10)); } - - QCOMPARE(scene.items(), items); + QCOMPARE(scene.items().size(), items.size()); scene.itemAt(0, 0); // trigger indexing scene.removeItem(items.at(5)); @@ -413,6 +430,9 @@ void tst_QGraphicsScene::items() QGraphicsLineItem *l2 = scene.addLine(0, -5, 0, 5); QVERIFY(!l1->sceneBoundingRect().intersects(l2->sceneBoundingRect())); QVERIFY(!l2->sceneBoundingRect().intersects(l1->sceneBoundingRect())); + QList<QGraphicsItem *> items; + items<<l1<<l2; + QCOMPARE(scene.items().size(), items.size()); QVERIFY(scene.items(-1, -1, 2, 2).contains(l1)); QVERIFY(scene.items(-1, -1, 2, 2).contains(l2)); } @@ -2740,8 +2760,8 @@ void tst_QGraphicsScene::update() qRegisterMetaType<QList<QRectF> >("QList<QRectF>"); QSignalSpy spy(&scene, SIGNAL(changed(QList<QRectF>))); - // When deleted, the item will lazy-remove itself - delete rect; + // We update the scene. + scene.update(); // This function forces a purge, which will post an update signal scene.itemAt(0, 0); diff --git a/tests/auto/qgraphicssceneindex/qgraphicssceneindex.pro b/tests/auto/qgraphicssceneindex/qgraphicssceneindex.pro new file mode 100644 index 0000000..740a23e --- /dev/null +++ b/tests/auto/qgraphicssceneindex/qgraphicssceneindex.pro @@ -0,0 +1,3 @@ +load(qttest_p4) +SOURCES += tst_qgraphicssceneindex.cpp + diff --git a/tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp b/tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp new file mode 100644 index 0000000..ac21e20 --- /dev/null +++ b/tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp @@ -0,0 +1,219 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the test suite 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 <QtTest/QtTest> +#include <QtGui/qgraphicsscene.h> +#include <private/qgraphicsscenebsptreeindex_p.h> +#include <private/qgraphicssceneindex_p.h> +#include <private/qgraphicsscenelinearindex_p.h> + +//TESTED_CLASS= +//TESTED_FILES= + +class tst_QGraphicsSceneIndex : public QObject +{ + Q_OBJECT +public slots: + void initTestCase(); + +private slots: + void customIndex_data(); + void customIndex(); + void scatteredItems_data(); + void scatteredItems(); + void overlappedItems_data(); + void overlappedItems(); + void movingItems_data(); + void movingItems(); + +private: + void common_data(); + QGraphicsSceneIndex *createIndex(const QString &name); +}; + +void tst_QGraphicsSceneIndex::initTestCase() +{ +} + +void tst_QGraphicsSceneIndex::common_data() +{ + QTest::addColumn<QString>("indexMethod"); + + QTest::newRow("BSP") << QString("bsp"); + QTest::newRow("Linear") << QString("linear"); +} + +QGraphicsSceneIndex *tst_QGraphicsSceneIndex::createIndex(const QString &indexMethod) +{ + QGraphicsSceneIndex *index = 0; + QGraphicsScene *scene = new QGraphicsScene(); + if (indexMethod == "bsp") + index = new QGraphicsSceneBspTreeIndex(scene); + + if (indexMethod == "linear") + index = new QGraphicsSceneLinearIndex(scene); + + return index; +} + +void tst_QGraphicsSceneIndex::customIndex_data() +{ + common_data(); +} + +void tst_QGraphicsSceneIndex::customIndex() +{ +#if 0 + QFETCH(QString, indexMethod); + QGraphicsSceneIndex *index = createIndex(indexMethod); + + QGraphicsScene scene; + scene.setSceneIndex(index); + + scene.addRect(0, 0, 30, 40); + QCOMPARE(scene.items(QRectF(0, 0, 10, 10)).count(), 1); +#endif +} + +void tst_QGraphicsSceneIndex::scatteredItems_data() +{ + common_data(); +} + +void tst_QGraphicsSceneIndex::scatteredItems() +{ + QFETCH(QString, indexMethod); + + QGraphicsScene scene; +#if 1 + scene.setItemIndexMethod(indexMethod == "linear" ? QGraphicsScene::NoIndex : QGraphicsScene::BspTreeIndex); +#else + QGraphicsSceneIndex *index = createIndex(indexMethod); + scene.setSceneIndex(index); +#endif + + for (int i = 0; i < 10; ++i) + scene.addRect(i*50, i*50, 40, 35); + + QCOMPARE(scene.items(QPointF(5, 5)).count(), 1); + QCOMPARE(scene.items(QPointF(55, 55)).count(), 1); + QCOMPARE(scene.items(QPointF(-100, -100)).count(), 0); + + QCOMPARE(scene.items(QRectF(0, 0, 10, 10)).count(), 1); + QCOMPARE(scene.items(QRectF(0, 0, 1000, 1000)).count(), 10); + QCOMPARE(scene.items(QRectF(-100, -1000, 0, 0)).count(), 0); +} + +void tst_QGraphicsSceneIndex::overlappedItems_data() +{ + common_data(); +} + +void tst_QGraphicsSceneIndex::overlappedItems() +{ + QFETCH(QString, indexMethod); + + QGraphicsScene scene; +#if 1 + scene.setItemIndexMethod(indexMethod == "linear" ? QGraphicsScene::NoIndex : QGraphicsScene::BspTreeIndex); +#else + QGraphicsSceneIndex *index = createIndex(indexMethod); + scene.setSceneIndex(index); +#endif + + for (int i = 0; i < 10; ++i) + for (int j = 0; j < 10; ++j) + scene.addRect(i*50, j*50, 200, 200); + + QCOMPARE(scene.items(QPointF(5, 5)).count(), 1); + QCOMPARE(scene.items(QPointF(55, 55)).count(), 4); + QCOMPARE(scene.items(QPointF(105, 105)).count(), 9); + QCOMPARE(scene.items(QPointF(-100, -100)).count(), 0); + + QCOMPARE(scene.items(QRectF(0, 0, 1000, 1000)).count(), 100); + QCOMPARE(scene.items(QRectF(-100, -1000, 0, 0)).count(), 0); + QCOMPARE(scene.items(QRectF(0, 0, 200, 200)).count(), 16); + QCOMPARE(scene.items(QRectF(0, 0, 100, 100)).count(), 4); + QCOMPARE(scene.items(QRectF(0, 0, 1, 100)).count(), 2); + QCOMPARE(scene.items(QRectF(0, 0, 1, 1000)).count(), 10); +} + +void tst_QGraphicsSceneIndex::movingItems_data() +{ + common_data(); +} + +void tst_QGraphicsSceneIndex::movingItems() +{ + QFETCH(QString, indexMethod); + + QGraphicsScene scene; +#if 1 + scene.setItemIndexMethod(indexMethod == "linear" ? QGraphicsScene::NoIndex : QGraphicsScene::BspTreeIndex); +#else + QGraphicsSceneIndex *index = createIndex(indexMethod); + scene.setSceneIndex(index); +#endif + + for (int i = 0; i < 10; ++i) + scene.addRect(i*50, i*50, 40, 35); + + QGraphicsRectItem *box = scene.addRect(0, 0, 10, 10); + QCOMPARE(scene.items(QPointF(5, 5)).count(), 2); + QCOMPARE(scene.items(QPointF(-1, -1)).count(), 0); + QCOMPARE(scene.items(QRectF(0, 0, 5, 5)).count(), 2); + + box->setPos(10, 10); + QCOMPARE(scene.items(QPointF(9, 9)).count(), 1); + QCOMPARE(scene.items(QPointF(15, 15)).count(), 2); + QCOMPARE(scene.items(QRectF(0, 0, 1, 1)).count(), 1); + + box->setPos(-5, -5); + QCOMPARE(scene.items(QPointF(-1, -1)).count(), 1); + QCOMPARE(scene.items(QRectF(0, 0, 1, 1)).count(), 2); + + QCOMPARE(scene.items(QRectF(0, 0, 1000, 1000)).count(), 11); +} + + +QTEST_MAIN(tst_QGraphicsSceneIndex) +#include "tst_qgraphicssceneindex.moc" diff --git a/tests/auto/qgraphicsview/tst_qgraphicsview.cpp b/tests/auto/qgraphicsview/tst_qgraphicsview.cpp index d24e437..6db8f27 100644 --- a/tests/auto/qgraphicsview/tst_qgraphicsview.cpp +++ b/tests/auto/qgraphicsview/tst_qgraphicsview.cpp @@ -371,6 +371,7 @@ void tst_QGraphicsView::interactive() QCOMPARE(item->events.size(), 0); QPoint itemPoint = view.mapFromScene(item->scenePos()); + QVERIFY(view.itemAt(itemPoint)); for (int i = 0; i < 100; ++i) { @@ -2106,12 +2107,12 @@ void tst_QGraphicsView::resizeAnchor() view.setResizeAnchor(QGraphicsView::AnchorViewCenter); } view.centerOn(0, 0); - QTest::qWait(100); + QTest::qWait(250); QPointF f = view.mapToScene(50, 50); QPointF center = view.mapToScene(view.viewport()->rect().center()); - QTest::qWait(100); + QTest::qWait(250); for (int size = 200; size <= 400; size += 25) { view.resize(size, size); @@ -2126,7 +2127,7 @@ void tst_QGraphicsView::resizeAnchor() QVERIFY(qAbs(newCenter.x() - center.x()) < slack); QVERIFY(qAbs(newCenter.y() - center.y()) < slack); } - QTest::qWait(100); + QTest::qWait(250); } } } @@ -2988,14 +2989,7 @@ void tst_QGraphicsView::embeddedViews() v2->QWidget::render(&actual); QTransform b = item->transform; -#ifdef Q_WS_MAC - // We don't use shared painter on the Mac, so the - // transform should be exactly the same. QVERIFY(a == b); -#else - QVERIFY(a != b); -#endif - delete v1; } @@ -3092,7 +3086,7 @@ void tst_QGraphicsView::moveItemWhileScrolling() #ifdef Q_WS_X11 qt_x11_wait_for_window_manager(&view); #endif - QTest::qWait(100); + QTest::qWait(200); view.lastPaintedRegion = QRegion(); view.horizontalScrollBar()->setValue(view.horizontalScrollBar()->value() + 10); |