diff options
24 files changed, 2512 insertions, 1178 deletions
diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri index 4cee6d6..a4d142a 100644 --- a/src/gui/graphicsview/graphicsview.pri +++ b/src/gui/graphicsview/graphicsview.pri @@ -5,6 +5,11 @@ HEADERS += graphicsview/qgraphicsitem.h \ graphicsview/qgraphicsscene.h \ graphicsview/qgraphicsscene_p.h \ graphicsview/qgraphicsscene_bsp_p.h \ + graphicsview/qgraphicsscenelinearindex_p.h \ + graphicsview/qgraphicssceneindex.h \ + graphicsview/qgraphicssceneindex_p.h \ + graphicsview/qgraphicsscenebsptreeindex_p.h \ + graphicsview/qgraphicsscenebsptreeindex_p_p.h \ graphicsview/qgraphicssceneevent.h \ graphicsview/qgraphicsview_p.h \ graphicsview/qgraphicsview.h @@ -12,9 +17,13 @@ SOURCES += graphicsview/qgraphicsitem.cpp \ graphicsview/qgraphicsitemanimation.cpp \ graphicsview/qgraphicsscene.cpp \ graphicsview/qgraphicsscene_bsp.cpp \ + graphicsview/qgraphicsscenebsptreeindex_p.cpp \ + graphicsview/qgraphicsscenelinearindex.cpp \ + graphicsview/qgraphicssceneindex.cpp \ graphicsview/qgraphicssceneevent.cpp \ graphicsview/qgraphicsview.cpp + # Widgets on the canvas HEADERS += graphicsview/qgraphicslayout.h \ graphicsview/qgraphicslayout_p.h \ diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp index 555f7b0..39ad447 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_p.h" #include <QtCore/qbitarray.h> #include <QtCore/qdebug.h> #include <QtCore/qpoint.h> @@ -584,17 +585,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); @@ -954,12 +944,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; @@ -967,6 +951,11 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent) // Deliver post-change notification q->itemChange(QGraphicsItem::ItemParentHasChanged, newParentVariant); + if (scene) { + // Deliver the change to the index + scene->d_func()->index->itemChanged(q, QGraphicsItem::ItemParentHasChanged, newParentVariant); + } + if (isObject) emit static_cast<QGraphicsObject *>(q)->parentChanged(); } @@ -3596,9 +3585,8 @@ void QGraphicsItem::setZValue(qreal z) 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(); + //Z Value has changed, we have to notify the index. + d_ptr->scene->d_func()->index->itemChanged(this, ItemZValueChange, z); } itemChange(ItemZValueHasChanged, newZVariant); @@ -4065,7 +4053,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()); } @@ -6295,7 +6283,7 @@ void QGraphicsItem::addToIndex() return; } if (d_ptr->scene) - d_ptr->scene->d_func()->addToIndex(this); + d_ptr->scene->d_func()->index->addItem(this); } /*! @@ -6312,7 +6300,7 @@ void QGraphicsItem::removeFromIndex() return; } if (d_ptr->scene) - d_ptr->scene->d_func()->removeFromIndex(this); + d_ptr->scene->d_func()->index->removeItem(this); } /*! @@ -6335,6 +6323,7 @@ void QGraphicsItem::prepareGeometryChange() 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); @@ -6347,8 +6336,6 @@ void QGraphicsItem::prepareGeometryChange() || scenePrivate->views.isEmpty()) { d_ptr->scene->update(sceneTransform().mapRect(boundingRect())); } - - scenePrivate->removeFromIndex(this); } QGraphicsItem *parent = this; diff --git a/src/gui/graphicsview/qgraphicsitem.h b/src/gui/graphicsview/qgraphicsitem.h index aeb4691..ec16d26 100644 --- a/src/gui/graphicsview/qgraphicsitem.h +++ b/src/gui/graphicsview/qgraphicsitem.h @@ -439,6 +439,10 @@ private: friend class QGraphicsWidget; friend class QGraphicsWidgetPrivate; friend class QGraphicsProxyWidgetPrivate; + friend class QGraphicsSceneIndex; + friend class QGraphicsSceneIndexPrivate; + friend class QGraphicsSceneBspTreeIndex; + friend class QGraphicsSceneBspTreeIndexPrivate; friend class ::tst_QGraphicsItem; friend bool qt_closestLeaf(const QGraphicsItem *, const QGraphicsItem *); friend bool qt_closestItemFirst(const QGraphicsItem *, const QGraphicsItem *); diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp index 811e0d3..5a3028c 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 @@ -202,6 +201,8 @@ however, is done in constant time. This approach is ideal for dynamic scenes, where many items are added, moved or removed continuously. + \omitvalue CustomIndex + \sa setItemIndexMethod(), bspTreeDepth */ @@ -218,6 +219,8 @@ #include "qgraphicsview_p.h" #include "qgraphicswidget.h" #include "qgraphicswidget_p.h" +#include "qgraphicssceneindex.h" +#include "qgraphicsscenebsptreeindex_p_p.h" #include <QtCore/qdebug.h> #include <QtCore/qlist.h> @@ -249,67 +252,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()); @@ -329,7 +271,7 @@ static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraph QGraphicsScenePrivate::QGraphicsScenePrivate() : changedSignalMask(0), indexMethod(QGraphicsScene::BspTreeIndex), - bspTreeDepth(0), + index(0), lastItemCount(0), hasSceneRect(false), updateAll(false), @@ -337,10 +279,6 @@ QGraphicsScenePrivate::QGraphicsScenePrivate() processDirtyItemsEmitted(false), selectionChanging(0), needSortTopLevelItems(true), - regenerateIndex(true), - purgePending(false), - indexTimerId(0), - restartIndexTimer(false), stickyFocus(false), hasFocus(false), focusItem(0), @@ -356,8 +294,6 @@ QGraphicsScenePrivate::QGraphicsScenePrivate() allItemsIgnoreHoverEvents(true), allItemsUseDefaultCursor(true), painterStateProtection(true), - sortCacheEnabled(false), - updatingSortCache(false), style(0) { } @@ -369,6 +305,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); @@ -378,219 +316,11 @@ 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) -{ - return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0); -} - -/*! - \internal -*/ -void QGraphicsScenePrivate::_q_updateIndex() +QGraphicsScenePrivate *QGraphicsScenePrivate::get(QGraphicsScene *q) { - if (!indexTimerId) - return; - - Q_Q(QGraphicsScene); - q->killTimer(indexTimerId); - indexTimerId = 0; - - purgeRemovedItems(); - - // Add unindexedItems to indexedItems - QRectF unindexedItemsBoundingRect; - for (int i = 0; i < unindexedItems.size(); ++i) { - if (QGraphicsItem *item = unindexedItems.at(i)) { - unindexedItemsBoundingRect |= item->sceneBoundingRect(); - if (!freeItemIndexes.isEmpty()) { - int freeIndex = freeItemIndexes.takeFirst(); - item->d_func()->index = freeIndex; - indexedItems[freeIndex] = item; - } else { - item->d_func()->index = indexedItems.size(); - indexedItems << item; - } - } - } - - // Update growing scene rect. - QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect; - growingItemsBoundingRect |= unindexedItemsBoundingRect; - - // Determine whether we should regenerate the BSP tree. - if (indexMethod == QGraphicsScene::BspTreeIndex) { - int depth = bspTreeDepth; - if (depth == 0) { - int oldDepth = intmaxlog(lastItemCount); - depth = intmaxlog(indexedItems.size()); - static const int slack = 100; - if (bspTree.leafCount() == 0 || (oldDepth != depth && qAbs(lastItemCount - indexedItems.size()) > slack)) { - // ### Crude algorithm. - regenerateIndex = true; - } - } - - // Regenerate the tree. - if (regenerateIndex) { - regenerateIndex = false; - bspTree.initialize(q->sceneRect(), depth); - unindexedItems = indexedItems; - lastItemCount = indexedItems.size(); - q->update(); - - // Take this opportunity to reset our largest-item counter for - // untransformable items. When the items are inserted into the BSP - // tree, we'll get an accurate calculation. - largestUntransformableItem = QRectF(); - } - } - - // Insert all unindexed items into the tree. - for (int i = 0; i < unindexedItems.size(); ++i) { - if (QGraphicsItem *item = unindexedItems.at(i)) { - QRectF rect = item->sceneBoundingRect(); - if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) - continue; - if (indexMethod == QGraphicsScene::BspTreeIndex) - bspTree.insertItem(item, rect); - - // If the item ignores view transformations, update our - // largest-item-counter to ensure that the view can accurately - // discover untransformable items when drawing. - if (item->d_ptr->itemIsUntransformable()) { - QGraphicsItem *topmostUntransformable = item; - while (topmostUntransformable && (topmostUntransformable->d_ptr->ancestorFlags - & QGraphicsItemPrivate::AncestorIgnoresTransformations)) { - topmostUntransformable = topmostUntransformable->parentItem(); - } - // ### Verify that this is the correct largest untransformable rectangle. - largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect(); - } - } - } - unindexedItems.clear(); - - // Notify scene rect changes. - if (!hasSceneRect && growingItemsBoundingRect != oldGrowingItemsBoundingRect) - emit q->sceneRectChanged(growingItemsBoundingRect); + return q->d_func(); } -/*! - \internal -*/ void QGraphicsScenePrivate::_q_emitUpdated() { Q_Q(QGraphicsScene); @@ -724,22 +454,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) { @@ -760,17 +484,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; @@ -828,45 +541,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) { @@ -1528,618 +1202,6 @@ void QGraphicsScenePrivate::recursive_items_helper(QGraphicsItem *item, QRectF r } } -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 @@ -2272,8 +1334,8 @@ QGraphicsScene::QGraphicsScene(QObject *parent) QGraphicsScene::QGraphicsScene(const QRectF &sceneRect, QObject *parent) : QObject(*new QGraphicsScenePrivate, parent) { - setSceneRect(sceneRect); d_func()->init(); + setSceneRect(sceneRect); } /*! @@ -2287,8 +1349,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); } /*! @@ -2325,8 +1387,7 @@ QGraphicsScene::~QGraphicsScene() QRectF QGraphicsScene::sceneRect() const { Q_D(const QGraphicsScene); - const_cast<QGraphicsScenePrivate *>(d)->_q_updateIndex(); - return d->hasSceneRect ? d->sceneRect : d->growingItemsBoundingRect; + return d->index->indexedRect(); } void QGraphicsScene::setSceneRect(const QRectF &rect) { @@ -2334,7 +1395,7 @@ void QGraphicsScene::setSceneRect(const QRectF &rect) if (rect != d->sceneRect) { d->hasSceneRect = !rect.isNull(); d->sceneRect = rect; - d->resetIndex(); + d->index->sceneRectChanged(rect); emit sceneRectChanged(rect); } } @@ -2467,14 +1528,84 @@ QGraphicsScene::ItemIndexMethod QGraphicsScene::itemIndexMethod() const Q_D(const QGraphicsScene); return d->indexMethod; } + +// Possibilities +// NoIndex -> CustomIndex : warning +// BspTreeIndex -> CustomIndex : warning +// CustomIndex -> CustomIndex : warning +// NoIndex -> BspTreeIndex : create an empty BSP if necessary +// BspTreeIndex -> BspTreeIndex : nothing +// CustomIndex -> BspTreeIndex : create BSP and transfer items +// NoIndex -> NoIndex : nothing +// BspTreeIndex -> NoIndex : nothing +// CustomIndex -> NoIndex : create BSP tree but do not populate void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method) { Q_D(QGraphicsScene); - d->resetIndex(); + if (method == CustomIndex) { + qWarning("QGraphicsScene: Invalid index type %d", CustomIndex); + return; + } + if (d->indexMethod == method) { + return; + } + + if (d->indexMethod == NoIndex && method == BspTreeIndex) { + QGraphicsSceneBspTreeIndex *tree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index); + if (!tree) { + delete d->index; + d->index = new QGraphicsSceneBspTreeIndex(this); + } + } + + if (d->indexMethod == CustomIndex && method == BspTreeIndex) { + //We re-add in the new index all items from the old index + QGraphicsSceneIndex *oldIndex = d->index; + d->index = new QGraphicsSceneBspTreeIndex(this); + for (int i = 0 ; i < oldIndex->items().size() ; ++ i) + d->index->addItem(oldIndex->items().at(i)); + } + + if (d->indexMethod == CustomIndex && method == NoIndex) { + d->index = new QGraphicsSceneLinearIndex(this); + } + d->indexMethod = method; } /*! + \brief the item indexing method. + This method allow to apply an indexing algorithm \a index to the scene, to speed up + item discovery functions like items() and itemAt(). + + \sa sceneIndex(), QGraphicsSceneIndex +*/ +void QGraphicsScene::setSceneIndex(QGraphicsSceneIndex *index) +{ + Q_D(QGraphicsScene); + if (!index) { + qWarning("QGraphicsScene::setSceneIndex: Attempt to insert a null indexer"); + } else { + if (d->indexMethod == BspTreeIndex) { + delete d->index; + } + d->indexMethod = CustomIndex; + d->index = index; + } +} + +/*! + This method return the current indexing algorithm of the scene. + + \sa setSceneIndex(), QGraphicsSceneIndex +*/ +QGraphicsSceneIndex* QGraphicsScene::sceneIndex() const +{ + Q_D(const QGraphicsScene); + return d->index; +} + +/*! \property QGraphicsScene::bspTreeDepth \brief the depth of QGraphicsScene's BSP index tree \since 4.3 @@ -2509,21 +1640,26 @@ 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; + } + if (bspTree->bspTreeDepth() == depth) + return; + + bspTree->setBspTreeDepth(depth); } /*! @@ -2542,15 +1678,25 @@ void QGraphicsScene::setBspTreeDepth(int depth) bool QGraphicsScene::isSortCacheEnabled() const { Q_D(const QGraphicsScene); - return d->sortCacheEnabled; + QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index); + if (!bspTree) { + qWarning("QGraphicsScene::isSortCacheEnabled: can not apply if indexing method is not BSP"); + return false; + } + return bspTree->d_func()->sortCacheEnabled; } void QGraphicsScene::setSortCacheEnabled(bool enabled) { Q_D(QGraphicsScene); - if (enabled == d->sortCacheEnabled) + QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index); + if (!bspTree) { + qWarning("QGraphicsScene::isSortCacheEnabled: can not apply if indexing method is not BSP"); + return; + } + if (enabled == bspTree->d_func()->sortCacheEnabled) return; - if ((d->sortCacheEnabled = enabled)) - d->invalidateSortCache(); + if ((bspTree->d_func()->sortCacheEnabled = enabled)) + bspTree->d_func()->invalidateSortCache(); } /*! @@ -2576,29 +1722,12 @@ QRectF QGraphicsScene::itemsBoundingRect() const QList<QGraphicsItem *> QGraphicsScene::items() const { Q_D(const QGraphicsScene); - const_cast<QGraphicsScenePrivate *>(d)->purgeRemovedItems(); - - // If freeItemIndexes is empty, we know there are no holes in indexedItems and - // unindexedItems. - if (d->freeItemIndexes.isEmpty()) { - if (d->unindexedItems.isEmpty()) - return d->indexedItems; - return d->indexedItems + d->unindexedItems; - } - - // Rebuild the list of items to avoid holes. ### We could also just - // compress the item lists at this point. - QList<QGraphicsItem *> itemList; - foreach (QGraphicsItem *item, d->indexedItems + d->unindexedItems) { - if (item) - itemList << item; - } - return itemList; + return d->index->items(); } /*! Returns all visible items at position \a pos in the scene. The items are - listed in descending Z order (i.e., the first item in the list is the + listed in descending stacking order (i.e., the first item in the list is the top-most item, and the last item is the bottom-most item). \sa itemAt() @@ -2606,7 +1735,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); } /*! @@ -2625,9 +1754,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); } /*! @@ -2651,7 +1778,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); } /*! @@ -2668,7 +1795,81 @@ 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); } /*! @@ -2692,11 +1893,10 @@ QList<QGraphicsItem *> QGraphicsScene::collidingItems(const QGraphicsItem *item, } QList<QGraphicsItem *> tmp; - foreach (QGraphicsItem *itemInVicinity, d->estimateItemsInRect(item->sceneBoundingRect())) { + foreach (QGraphicsItem *itemInVicinity, d->index->estimateItems(item->sceneBoundingRect(), Qt::AscendingOrder, QTransform())) { if (item != itemInVicinity && item->collidesWithItem(itemInVicinity, mode)) tmp << itemInVicinity; } - d->sortItems(&tmp, Qt::AscendingOrder, d->sortCacheEnabled); return tmp; } @@ -2863,25 +2063,19 @@ void QGraphicsScene::clearSelection() void QGraphicsScene::clear() { Q_D(QGraphicsScene); + QList<QGraphicsItem *> items = d->index->items(); + QList<QGraphicsItem *> toDelete; // Recursive descent delete - for (int i = 0; i < d->indexedItems.size(); ++i) { - if (QGraphicsItem *item = d->indexedItems.at(i)) { + for (int i = 0; i < items.size(); ++i) { + if (QGraphicsItem *item = items.at(i)) { if (!item->parentItem()) - delete item; + toDelete << item; } } - QList<QGraphicsItem *> unindexedParents; - for (int i = 0; i < d->unindexedItems.size(); ++i) { - QGraphicsItem *item = d->unindexedItems.at(i); - if (!item->parentItem()) - unindexedParents << item; - } - d->unindexedItems.clear(); - qDeleteAll(unindexedParents); - d->indexedItems.clear(); - d->freeItemIndexes.clear(); + //We delete all top level items + qDeleteAll(toDelete); d->lastItemCount = 0; - d->bspTree.clear(); + d->index->clear(); d->largestUntransformableItem = QRectF(); d->allItemsIgnoreHoverEvents = true; d->allItemsUseDefaultCursor = true; @@ -3003,14 +2197,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()) { @@ -3021,21 +2207,13 @@ void QGraphicsScene::addItem(QGraphicsItem *item) // Add the item to this scene item->d_func()->scene = targetScene; - // Indexing requires sceneBoundingRect(), but because \a item might - // not be completely constructed at this point, we need to store it in - // a temporary list and schedule an indexing for later. - d->unindexedItems << item; - item->d_func()->index = -1; - d->startIndexTimer(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(). @@ -3946,16 +3124,6 @@ bool QGraphicsScene::event(QEvent *event) // geometries that do not have an explicit style set. update(); break; - case QEvent::Timer: - if (d->indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == d->indexTimerId) { - if (d->restartIndexTimer) { - d->restartIndexTimer = false; - } else { - // this call will kill the timer - d->_q_updateIndex(); - } - } - // Fallthrough intended - support timers in subclasses. default: return QObject::event(event); } @@ -5131,7 +4299,7 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter * ltri.adjust(-untr.width(), -untr.height(), untr.width(), untr.height()); sceneRect.adjust(-ltri.width(), -ltri.height(), ltri.width(), ltri.height()); } - tmp = estimateItemsInRect(sceneRect); + tmp = index->estimateItems(sceneRect, Qt::DescendingOrder, viewTransform); QList<QGraphicsItem *> tli; for (int i = 0; i < tmp.size(); ++i) diff --git a/src/gui/graphicsview/qgraphicsscene.h b/src/gui/graphicsview/qgraphicsscene.h index 1d4a617..36374c8 100644 --- a/src/gui/graphicsview/qgraphicsscene.h +++ b/src/gui/graphicsview/qgraphicsscene.h @@ -83,6 +83,7 @@ class QGraphicsSimpleTextItem; class QGraphicsTextItem; class QGraphicsView; class QGraphicsWidget; +class QGraphicsSceneIndex; class QHelpEvent; class QInputMethodEvent; class QKeyEvent; @@ -113,6 +114,7 @@ class Q_GUI_EXPORT QGraphicsScene : public QObject public: enum ItemIndexMethod { BspTreeIndex, + CustomIndex, NoIndex = -1 }; @@ -142,6 +144,8 @@ public: ItemIndexMethod itemIndexMethod() const; void setItemIndexMethod(ItemIndexMethod method); + void setSceneIndex(QGraphicsSceneIndex *index); + QGraphicsSceneIndex* sceneIndex() const; bool isSortCacheEnabled() const; void setSortCacheEnabled(bool enabled); @@ -152,10 +156,17 @@ public: QRectF itemsBoundingRect() const; QList<QGraphicsItem *> items() const; + + QList<QGraphicsItem *> items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + QList<QGraphicsItem *> items(const QPointF &pos) const; QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; + QList<QGraphicsItem *> collidingItems(const QGraphicsItem *item, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const; QGraphicsItem *itemAt(const QPointF &pos) const; @@ -273,11 +284,9 @@ 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; @@ -285,6 +294,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..eaeec54 100644 --- a/src/gui/graphicsview/qgraphicsscene_bsp.cpp +++ b/src/gui/graphicsview/qgraphicsscene_bsp.cpp @@ -143,7 +143,7 @@ void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items) } } -QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect) +QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect) const { QList<QGraphicsItem *> tmp; findVisitor->foundItems = &tmp; @@ -151,7 +151,7 @@ QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect) return tmp; } -QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos) +QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos) const { QList<QGraphicsItem *> tmp; findVisitor->foundItems = &tmp; @@ -235,7 +235,7 @@ void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index) } } -void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index) +void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index) const { if (nodes.isEmpty()) return; @@ -245,7 +245,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con switch (node.type) { case Node::Leaf: { - visitor->visit(&leaves[node.leafIndex]); + visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex])); break; } case Node::Vertical: @@ -265,7 +265,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con } } -void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) +void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) const { if (nodes.isEmpty()) return; @@ -275,7 +275,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con switch (node.type) { case Node::Leaf: { - visitor->visit(&leaves[node.leafIndex]); + visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex])); break; } case Node::Vertical: diff --git a/src/gui/graphicsview/qgraphicsscene_bsp_p.h b/src/gui/graphicsview/qgraphicsscene_bsp_p.h index 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 cd463ee..72ae158 100644 --- a/src/gui/graphicsview/qgraphicsscene_p.h +++ b/src/gui/graphicsview/qgraphicsscene_p.h @@ -57,8 +57,10 @@ #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW +#include "qgraphicsscenebsptreeindex_p.h" +#include "qgraphicsscenelinearindex_p.h" +#include "qgraphicssceneindex.h" #include "qgraphicsview.h" -#include "qgraphicsscene_bsp_p.h" #include "qgraphicsitem_p.h" #include <private/qobject_p.h> @@ -71,8 +73,6 @@ #include <QtGui/qstyle.h> #include <QtGui/qstyleoption.h> -static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; - QT_BEGIN_NAMESPACE class QGraphicsView; @@ -85,18 +85,13 @@ 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; @@ -113,8 +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; @@ -127,21 +120,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; @@ -210,52 +193,6 @@ public: 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); - void drawItemHelper(QGraphicsItem *item, QPainter *painter, const QStyleOptionGraphicsItem *option, QWidget *widget, bool painterStateProtection); @@ -293,6 +230,65 @@ public: QStyleOptionGraphicsItem styleOptionTmp; }; +static inline bool QRectF_intersects(const QRectF &s, const QRectF &r) +{ + qreal xp = s.left(); + qreal yp = s.top(); + qreal w = s.width(); + qreal h = s.height(); + qreal l1 = xp; + qreal r1 = xp; + if (w < 0) + l1 += w; + else + r1 += w; + + qreal l2 = r.left(); + qreal r2 = r.left(); + if (w < 0) + l2 += r.width(); + else + r2 += r.width(); + + if (l1 >= r2 || l2 >= r1) + return false; + + qreal t1 = yp; + qreal b1 = yp; + if (h < 0) + t1 += h; + else + b1 += h; + + qreal t2 = r.top(); + qreal b2 = r.top(); + if (r.height() < 0) + t2 += r.height(); + else + b2 += r.height(); + + return !(t1 >= b2 || t2 >= b1); +} + +// QRectF::intersects() returns false always if either the source or target +// rectangle's width or height are 0. This works around that problem. +static inline void _q_adjustRect(QRectF *rect) +{ + Q_ASSERT(rect); + if (!rect->width()) + rect->adjust(-0.00001, 0, 0.00001, 0); + if (!rect->height()) + rect->adjust(0, -0.00001, 0, 0.00001); +} + +static inline QRectF adjustedItemBoundingRect(const QGraphicsItem *item) +{ + Q_ASSERT(item); + QRectF boundingRect(item->boundingRect()); + _q_adjustRect(&boundingRect); + return boundingRect; +} + QT_END_NAMESPACE #endif // QT_NO_GRAPHICSVIEW diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp new file mode 100644 index 0000000..b19248a --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.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 + + 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 +*/ + +#include "qgraphicsscenebsptreeindex_p.h" + +#ifndef QT_NO_GRAPHICSVIEW + +#include "qgraphicsscenebsptreeindex_p_p.h" +#include "qgraphicssceneindex_p.h" +#include "qgraphicsitem_p.h" +#include "qgraphicsscene_p.h" + +#include <QtCore/qmath.h> + +#include <QtCore/qdebug.h> + +QT_BEGIN_NAMESPACE + +static inline int intmaxlog(int n) +{ + return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0); +} + +/*! + Constructs a private scene 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; + + QGraphicsScenePrivate * scenePrivate = q->scene()->d_func(); + q->killTimer(indexTimerId); + indexTimerId = 0; + + purgeRemovedItems(); + + // Add unindexedItems to indexedItems + QRectF unindexedItemsBoundingRect; + for (int i = 0; i < unindexedItems.size(); ++i) { + if (QGraphicsItem *item = unindexedItems.at(i)) { + unindexedItemsBoundingRect |= item->sceneBoundingRect(); + if (!freeItemIndexes.isEmpty()) { + int freeIndex = freeItemIndexes.takeFirst(); + item->d_func()->index = freeIndex; + indexedItems[freeIndex] = item; + } else { + item->d_func()->index = indexedItems.size(); + indexedItems << item; + } + } + } + + // Update growing scene rect. + QRectF oldGrowingItemsBoundingRect = scenePrivate->growingItemsBoundingRect; + scenePrivate->growingItemsBoundingRect |= unindexedItemsBoundingRect; + + // Determine whether we should regenerate the BSP tree. + if (bspTreeDepth == 0) { + int oldDepth = intmaxlog(lastItemCount); + bspTreeDepth = intmaxlog(indexedItems.size()); + static const int slack = 100; + if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - indexedItems.size()) > slack)) { + // ### Crude algorithm. + regenerateIndex = true; + } + } + + // Regenerate the tree. + if (regenerateIndex) { + regenerateIndex = false; + bsp.initialize(q->scene()->sceneRect(), bspTreeDepth); + unindexedItems = indexedItems; + lastItemCount = indexedItems.size(); + q->scene()->update(); + + // Take this opportunity to reset our largest-item counter for + // untransformable items. When the items are inserted into the BSP + // tree, we'll get an accurate calculation. + scenePrivate->largestUntransformableItem = QRectF(); + } + + // Insert all unindexed items into the tree. + for (int i = 0; i < unindexedItems.size(); ++i) { + if (QGraphicsItem *item = unindexedItems.at(i)) { + QRectF rect = item->sceneBoundingRect(); + if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) + continue; + + bsp.insertItem(item, rect); + + // If the item ignores view transformations, update our + // largest-item-counter to ensure that the view can accurately + // discover untransformable items when drawing. + if (item->d_ptr->itemIsUntransformable()) { + QGraphicsItem *topmostUntransformable = item; + while (topmostUntransformable && (topmostUntransformable->d_ptr->ancestorFlags + & QGraphicsItemPrivate::AncestorIgnoresTransformations)) { + topmostUntransformable = topmostUntransformable->parentItem(); + } + // ### Verify that this is the correct largest untransformable rectangle. + scenePrivate->largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect(); + } + } + } + unindexedItems.clear(); + + // Notify scene rect changes. + if (!scenePrivate->hasSceneRect && scenePrivate->growingItemsBoundingRect != oldGrowingItemsBoundingRect) + emit q->scene()->sceneRectChanged(scenePrivate->growingItemsBoundingRect); +} + + +/*! + \internal + + Removes stale pointers from all data structures. +*/ +void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems() +{ + 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; + unindexedItems << item; + } + } + indexedItems.clear(); + freeItemIndexes.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; + 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)++; + } +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache() +{ + Q_Q(QGraphicsSceneBspTreeIndex); + _q_updateIndex(); + + if (!sortCacheEnabled || !updatingSortCache) + return; + + updatingSortCache = false; + int stackingOrder = 0; + + QList<QGraphicsItem *> topLevels; + + for (int i = 0; i < q->items().count(); ++i) { + QGraphicsItem *item = q->items().at(i); + if (item && item->parentItem() == 0) + topLevels << item; + } + + qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf); + for (int i = 0; i < topLevels.size(); ++i) + climbTree(topLevels.at(i), &stackingOrder); +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache() +{ + Q_Q(QGraphicsSceneBspTreeIndex); + if (!sortCacheEnabled || updatingSortCache) + return; + + updatingSortCache = true; + QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection); +} + +/*! + Returns true if \a item1 is on top of \a item2. + + \internal +*/ +bool QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2) +{ + // Siblings? Just check their z-values. + const QGraphicsItemPrivate *d1 = item1->d_ptr; + const QGraphicsItemPrivate *d2 = item2->d_ptr; + if (d1->parent == d2->parent) + return qt_closestLeaf(item1, item2); + + // Find common ancestor, and each item's ancestor closest to the common + // ancestor. + int item1Depth = d1->depth; + int item2Depth = d2->depth; + const QGraphicsItem *p = item1; + const QGraphicsItem *t1 = item1; + while (item1Depth > item2Depth && (p = p->d_ptr->parent)) { + if (p == item2) { + // item2 is one of item1's ancestors; item1 is on top + return !(t1->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent); + } + t1 = p; + --item1Depth; + } + p = item2; + const QGraphicsItem *t2 = item2; + while (item2Depth > item1Depth && (p = p->d_ptr->parent)) { + if (p == item1) { + // item1 is one of item2's ancestors; item1 is not on top + return (t2->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent); + } + t2 = p; + --item2Depth; + } + + // item1Ancestor is now at the same level as item2Ancestor, but not the same. + const QGraphicsItem *a1 = t1; + const QGraphicsItem *a2 = t2; + while (a1) { + const QGraphicsItem *p1 = a1; + const QGraphicsItem *p2 = a2; + a1 = a1->parentItem(); + a2 = a2->parentItem(); + if (a1 && a1 == a2) + return qt_closestLeaf(p1, p2); + } + + // No common ancestor? Then just compare the items' toplevels directly. + return qt_closestLeaf(t1->topLevelItem(), t2->topLevelItem()); +} + +/*! + Returns true if \a item2 is on top of \a item1. + + \internal +*/ +bool QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2) +{ + return closestItemFirst_withoutCache(item2, item1); +} + +/*! + 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) { + 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); + } + } +} + +/*! + Constructs a BSP scene index for the given \a scene. +*/ +QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene) + : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene) +{ + +} + +/*! + \reimp + Return the rect indexed by the BSP index. +*/ +QRectF QGraphicsSceneBspTreeIndex::indexedRect() const +{ + Q_D(const QGraphicsSceneBspTreeIndex); + const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->_q_updateIndex(); + return scene()->d_func()->hasSceneRect ? scene()->d_func()->sceneRect : scene()->d_func()->growingItemsBoundingRect; +} + +/*! + \reimp + Clear the all the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::clear() +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->bsp.clear(); + d->lastItemCount = 0; + d->freeItemIndexes.clear(); + d->indexedItems.clear(); + d->unindexedItems.clear(); +} + +/*! + Add the \a item into the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + // Prevent reusing a recently deleted pointer: purge all removed items + // from our lists. + d->purgeRemovedItems(); + + // Invalidate any sort caching; arrival of a new item means we need to + // resort. + // Update the scene's sort cache settings. + item->d_ptr->globalStackingOrder = -1; + d->invalidateSortCache(); + + // Indexing requires sceneBoundingRect(), but because \a item might + // not be completely constructed at this point, we need to store it in + // a temporary list and schedule an indexing for later. + d->unindexedItems << item; + item->d_func()->index = -1; + d->startIndexTimer(0); +} + +/*! + This really add the item in the BSP. + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::addToIndex(QGraphicsItem *item) +{ + if (item->d_func()->index != -1) { + bsp.insertItem(item, item->sceneBoundingRect()); + foreach (QGraphicsItem *child, item->children()) + child->addToIndex(); + } else { + // The BSP tree is regenerated if the number of items grows to a + // certain threshold, or if the bounding rect of the graph doubles in + // size. + startIndexTimer(); + } +} + +/*! + Remove the \a item from the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + // Note: This will access item's sceneBoundingRect(), which (as this is + // C++) is why we cannot call removeItem() from QGraphicsItem's + // destructor. + d->removeFromIndex(item); + + // Invalidate any sort caching; arrival of a new item means we need to + // resort. + d->invalidateSortCache(); + + // Remove from our item lists. + int index = item->d_func()->index; + if (index != -1) { + d->freeItemIndexes << index; + d->indexedItems[index] = 0; + } else { + d->unindexedItems.removeAll(item); + } +} + +/*! + \reimp + Delete the \a item from the BSP index (without accessing its boundingRect). +*/ +void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + // Invalidate any sort caching; arrival of a new item means we need to + // resort. + d->invalidateSortCache(); + + int index = item->d_func()->index; + if (index != -1) { + // Important: The index is useless until purgeRemovedItems() is + // called. + d->indexedItems[index] = (QGraphicsItem *)0; + if (!d->purgePending) { + d->purgePending = true; + scene()->update(); + } + d->removedItems << item; + } else { + // Recently added items are purged immediately. unindexedItems() never + // contains stale items. + d->unindexedItems.removeAll(item); + scene()->update(); + } +} + +/*! + Really remove the item from the BSP + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::removeFromIndex(QGraphicsItem *item) +{ + if (item->d_func()->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) { + // ### remove from child index only if applicable + return; + } + int index = item->d_func()->index; + if (index != -1) { + bsp.removeItem(item, item->sceneBoundingRect()); + freeItemIndexes << index; + indexedItems[index] = 0; + item->d_func()->index = -1; + unindexedItems << item; + + //prepareGeometryChange will call prepareBoundingRectChange + foreach (QGraphicsItem *child, item->children()) + child->prepareGeometryChange(); + } + startIndexTimer(); +} + +/*! + \reimp + Update the BSP when the \a item 's bounding rect has changed. +*/ +void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + // Note: This will access item's sceneBoundingRect(), which (as this is + // C++) is why we cannot call removeItem() from QGraphicsItem's + // destructor. + d->removeFromIndex(const_cast<QGraphicsItem *>(item)); +} + +/*! + 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(); + + QList<QGraphicsItem *> rectItems = d->bsp.items(rect); + // Fill in with any unindexed items + for (int i = 0; i < d->unindexedItems.size(); ++i) { + if (QGraphicsItem *item = d->unindexedItems.at(i)) { + if (!item->d_ptr->itemDiscovered && item->d_ptr->visible && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) { + QRectF boundingRect = item->sceneBoundingRect(); + if (QRectF_intersects(boundingRect, rect)) { + item->d_ptr->itemDiscovered = 1; + rectItems << item; + } + } + } + } + + // Reset the discovered state of all discovered items + for (int i = 0; i < rectItems.size(); ++i) + rectItems.at(i)->d_func()->itemDiscovered = 0; + + d->sortItems(&rectItems, order, d->sortCacheEnabled); + + return rectItems; +} + + +/*! + \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; + } + } + 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); + 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::sceneRectChanged(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::itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value) +{ + Q_D(QGraphicsSceneBspTreeIndex); + switch (change) { + case QGraphicsItem::ItemZValueChange: + case QGraphicsItem::ItemParentChange: { + d->invalidateSortCache(); + break; + } + default: + break; + } + return QGraphicsSceneIndex::itemChanged(item, change, value); +} +/*! + \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..40b8f0b --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h @@ -0,0 +1,101 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtCore/qglobal.h> + +#ifndef QGRAPHICSBSPTREEINDEX_H +#define QGRAPHICSBSPTREEINDEX_H + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +QT_BEGIN_NAMESPACE + +#include <QtCore/qrect.h> +#include <QtCore/qlist.h> +#include <QtGui/qgraphicsitem.h> +#include <QtGui/qgraphicsscene.h> +#include <QtGui/qgraphicssceneindex.h> + +#include "qgraphicsscene_bsp_p.h" + +class QGraphicsSceneBspTreeIndexPrivate; +class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex +{ + Q_OBJECT + Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth) +public: + QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0); + QRectF indexedRect() const; + + QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const; + + QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const; + + int bspTreeDepth(); + void setBspTreeDepth(int depth); + +protected: + bool event(QEvent *event); + void clear(); + + void addItem(QGraphicsItem *item); + void removeItem(QGraphicsItem *item); + void deleteItem(QGraphicsItem *item); + void prepareBoundingRectChange(const QGraphicsItem *item); + + void sceneRectChanged(const QRectF &rect); + void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value); + +private : + Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex) + Q_DISABLE_COPY(QGraphicsSceneBspTreeIndex) + Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache()) + Q_PRIVATE_SLOT(d_func(), void _q_updateIndex()) + + friend class QGraphicsScene; + friend class QGraphicsScenePrivate; +}; + +QT_END_NAMESPACE + +#endif // QT_NO_GRAPHICSVIEW + +#endif // QGRAPHICSBSPTREEINDEX_H diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h new file mode 100644 index 0000000..30f6e26 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h @@ -0,0 +1,150 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QGRAPHICSSCENEBSPTREEINDEX_P_P_H +#define QGRAPHICSSCENEBSPTREEINDEX_P_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of qapplication_*.cpp, qwidget*.cpp and qfiledialog.cpp. This header +// file may change from version to version without notice, or even be removed. +// +// We mean it. +// + +#include "qgraphicsscenebsptreeindex_p.h" + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include <private/qgraphicssceneindex_p.h> +#include <private/qgraphicsitem_p.h> + +QT_BEGIN_NAMESPACE + +static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; + +class QGraphicsScene; + +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<int> freeItemIndexes; + + bool purgePending; + QSet<QGraphicsItem *> removedItems; + void purgeRemovedItems(); + + void _q_updateIndex(); + void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT); + void resetIndex(); + + void addToIndex(QGraphicsItem *item); + void removeFromIndex(QGraphicsItem *item); + + void _q_updateSortCache(); + bool sortCacheEnabled; + bool updatingSortCache; + void invalidateSortCache(); + + static void climbTree(QGraphicsItem *item, int *stackingOrder); + static bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2); + static bool closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2); + + static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2) + { + return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder; + } + static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2) + { + return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder; + } + + static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order, bool cached); +}; + + +/*! + \internal +*/ +inline bool qt_closestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2) +{ + // Return true if sibling item1 is on top of item2. + const QGraphicsItemPrivate *d1 = item1->d_ptr; + const QGraphicsItemPrivate *d2 = item2->d_ptr; + bool f1 = d1->flags & QGraphicsItem::ItemStacksBehindParent; + bool f2 = d2->flags & QGraphicsItem::ItemStacksBehindParent; + if (f1 != f2) return f2; + qreal z1 = d1->z; + qreal z2 = d2->z; + return z1 > z2; +} + +/*! + \internal +*/ +static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2) +{ + return qt_closestLeaf(item2, item1); +} + + +QT_END_NAMESPACE + +#endif // QGRAPHICSSCENEBSPTREEINDEX_P_P_H + +#endif + diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp new file mode 100644 index 0000000..05ec28b --- /dev/null +++ b/src/gui/graphicsview/qgraphicssceneindex.cpp @@ -0,0 +1,526 @@ +/**************************************************************************** +** +** 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 + + 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 "qgraphicssceneindex.h" +#include "qgraphicssceneindex_p.h" +#include "qgraphicsscenebsptreeindex_p_p.h" +#include "qgraphicsscene.h" +#include "qgraphicsitem_p.h" +#include "qgraphicsscene_p.h" + +#ifndef QT_NO_GRAPHICSVIEW + +QT_BEGIN_NAMESPACE + +class QGraphicsSceneIndexRectIntersector : public QGraphicsSceneIndexIntersector +{ +public: + QGraphicsSceneIndexRectIntersector(QGraphicsScene *scene) : QGraphicsSceneIndexIntersector(scene) {} + bool intersect(const QRectF &brect) const + { + bool 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 = QGraphicsScenePrivate::get(scene)->itemCollidesWithPath(item, transform.inverted().map(rectPath), mode); + } + return keep; + } +}; + +class QGraphicsSceneIndexPointIntersector : public QGraphicsSceneIndexIntersector +{ +public: + QGraphicsSceneIndexPointIntersector(QGraphicsScene *scene) : QGraphicsSceneIndexIntersector(scene) {} + bool intersect(const QRectF &brect) const + { + bool keep = false; + if (rect.intersects(transform.mapRect(brect))) + if (item->contains(transform.inverted().map(pos))) + keep = true; + if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) { + QPainterPath rectPath; + rectPath.addRect(rect); + keep = QGraphicsScenePrivate::get(scene)->itemCollidesWithPath(item, transform.inverted().map(rectPath), mode); + } + return keep; + } + QPointF pos; +}; + +class QGraphicsSceneIndexPathIntersector : public QGraphicsSceneIndexIntersector +{ +public: + QGraphicsSceneIndexPathIntersector(QGraphicsScene *scene) : QGraphicsSceneIndexIntersector(scene) {} + bool intersect(const QRectF &brect) const + { + bool 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)) { + keep = QGraphicsScenePrivate::get(scene)->itemCollidesWithPath(item, transform.inverted().map(path), mode); + } + return keep; + } + QPainterPath path; +}; + +/*! + Constructs a private scene index. +*/ +QGraphicsSceneIndexPrivate::QGraphicsSceneIndexPrivate(QGraphicsScene *scene) : scene(scene) +{ + pointIntersector = new QGraphicsSceneIndexPointIntersector(scene); + rectIntersector = new QGraphicsSceneIndexRectIntersector(scene); + pathIntersector = new QGraphicsSceneIndexPathIntersector(scene); +} + +/*! + Destructor of private scene index. +*/ +QGraphicsSceneIndexPrivate::~QGraphicsSceneIndexPrivate() +{ + delete pointIntersector; + delete rectIntersector; + delete pathIntersector; +} + +/*! + \internal +*/ +void QGraphicsSceneIndexPrivate::recursive_items_helper(QGraphicsItem *item, QGraphicsSceneIndexIntersector *intersector, + 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); + + //We fill the intersector with needed informations + intersector->transform = transform; + intersector->item = item; + keep = intersector->intersect(brect); + } + + 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 *>(scene->d_func())->topLevelItems; + if (!dontProcessChildren) { + if (item && item->d_ptr->needSortChildren) { + item->d_ptr->needSortChildren = 0; + qStableSort(children.begin(), children.end(), qt_notclosestLeaf); + } else if (!item && scene->d_func()->needSortTopLevelItems) { + const_cast<QGraphicsScenePrivate *>(scene->d_func())->needSortTopLevelItems = false; + qStableSort(children.begin(), children.end(), qt_notclosestLeaf); + } + } + + childClip &= !dontProcessChildren & !children.isEmpty(); + + // Clip. + if (childClip) + intersector->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, intersector, 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), intersector, 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; + } + } +} + +/*! + Constructs an abstract scene index for a given \a scene. +*/ +QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene) +: QObject(*new QGraphicsSceneIndexPrivate(scene), scene) +{ +} + +/*! + \internal +*/ +QGraphicsSceneIndex::QGraphicsSceneIndex(QObjectPrivate &dd, QGraphicsScene *scene) + : QObject(dd, scene) +{ +} + +/*! + Destroys the scene index. +*/ +QGraphicsSceneIndex::~QGraphicsSceneIndex() +{ + +} + +/*! + Returns the scene of this index. +*/ +QGraphicsScene* QGraphicsSceneIndex::scene() const +{ + Q_D(const QGraphicsSceneIndex); + return d->scene; +} + +/*! + Returns the indexed area for the index +*/ +QRectF QGraphicsSceneIndex::indexedRect() const +{ + Q_D(const QGraphicsSceneIndex); + return d->scene->d_func()->sceneRect; +} + +/*! + \fn QList<QGraphicsItem *> 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->mode = mode; + d->pointIntersector->rect = QRectF(pos, QSize(1,1)); + d->pointIntersector->pos = pos; + d->recursive_items_helper(0, d->pointIntersector, &itemList, QTransform(), 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); + QList<QGraphicsItem *> itemList; + d->rectIntersector->mode = mode; + d->rectIntersector->rect = rect; + d->recursive_items_helper(0, d->rectIntersector, &itemList, QTransform(), 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 polyRect(polygon.boundingRect()); + _q_adjustRect(&polyRect); + d->pathIntersector->mode = mode; + d->pathIntersector->rect = polyRect; + QPainterPath path; + path.addPolygon(polygon); + d->pathIntersector->path = path; + d->recursive_items_helper(0, d->pathIntersector, &itemList, QTransform(), 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 pathRect(path.controlPointRect()); + _q_adjustRect(&pathRect); + d->pathIntersector->mode = mode; + d->pathIntersector->rect = pathRect; + d->pathIntersector->path = path; + d->recursive_items_helper(0, d->pathIntersector, &itemList, QTransform(), 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. +*/ + +/*! + This virtual function removes all items in the scene index. +*/ +void QGraphicsSceneIndex::clear() +{ + for (int i = 0 ; i < items().size(); ++i) + removeItem(items().at(i)); +} + +/*! + \fn virtual void 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::itemChanged(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); +} + +/*! + This virtual function is called when the scene changes its bounding + rectangle. \a rect is the new value of the scene rectangle. + \sa QGraphicsScene::sceneRect() +*/ +void QGraphicsSceneIndex::sceneRectChanged(const QRectF &rect) +{ + Q_UNUSED(rect); +} + +QT_END_NAMESPACE + +#include "moc_qgraphicssceneindex.cpp" + +#endif // QT_NO_GRAPHICSVIEW diff --git a/src/gui/graphicsview/qgraphicssceneindex.h b/src/gui/graphicsview/qgraphicssceneindex.h new file mode 100644 index 0000000..084a623 --- /dev/null +++ b/src/gui/graphicsview/qgraphicssceneindex.h @@ -0,0 +1,112 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QGRAPHICSSCENEINDEX_H +#define QGRAPHICSSCENEINDEX_H + +#include <QtCore/qnamespace.h> +#include <QtCore/qobject.h> +#include <QtGui/qtransform.h> +#include <QtGui/qgraphicsitem.h> + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Gui) + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +class QGraphicsSceneIndexPrivate; +class QGraphicsScene; +class QRectF; +class QPointF; +template<typename T> class QList; + +class Q_GUI_EXPORT QGraphicsSceneIndex: public QObject +{ + Q_OBJECT + +public: + QGraphicsSceneIndex(QGraphicsScene *scene = 0); + virtual ~QGraphicsSceneIndex(); + + QGraphicsScene *scene() const; + + virtual QRectF indexedRect() const; + + virtual QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const = 0; + virtual QList<QGraphicsItem *> items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + virtual QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + virtual QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + virtual QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const; + virtual QList<QGraphicsItem *> estimateItems(const QPointF &point, Qt::SortOrder order, const QTransform &deviceTransform) const; + virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const = 0; + +protected: + virtual void clear(); + virtual void addItem(QGraphicsItem *item) = 0; + virtual void removeItem(QGraphicsItem *item) = 0; + virtual void deleteItem(QGraphicsItem *item); + + virtual void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange, const QVariant &value); + virtual void prepareBoundingRectChange(const QGraphicsItem *item); + virtual void sceneRectChanged(const QRectF &rect); + + QGraphicsSceneIndex(QObjectPrivate &dd, QGraphicsScene *scene); + + friend class QGraphicsScene; + friend class QGraphicsScenePrivate; + friend class QGraphicsItem; + friend class QGraphicsItemPrivate; + friend class QGraphicsSceneBspTreeIndex; +private: + Q_DISABLE_COPY(QGraphicsSceneIndex) + Q_DECLARE_PRIVATE(QGraphicsSceneIndex) +}; + +#endif // QT_NO_GRAPHICSVIEW + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QGRAPHICSSCENEINDEX_H diff --git a/src/gui/graphicsview/qgraphicssceneindex_p.h b/src/gui/graphicsview/qgraphicssceneindex_p.h new file mode 100644 index 0000000..d0d181b --- /dev/null +++ b/src/gui/graphicsview/qgraphicssceneindex_p.h @@ -0,0 +1,104 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QGRAPHICSSCENEINDEX_P_H +#define QGRAPHICSSCENEINDEX_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of qapplication_*.cpp, qwidget*.cpp and qfiledialog.cpp. This header +// file may change from version to version without notice, or even be removed. +// +// We mean it. +// + +#include "qgraphicssceneindex.h" + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include <private/qobject_p.h> +#include <private/qgraphicsitem_p.h> + +QT_BEGIN_NAMESPACE + +class QGraphicsScene; +class QGraphicsSceneIndexIntersector; +class QGraphicsSceneIndexRectIntersector; +class QGraphicsSceneIndexPointIntersector; +class QGraphicsSceneIndexPathIntersector; + +class QGraphicsSceneIndexPrivate : public QObjectPrivate +{ + Q_DECLARE_PUBLIC(QGraphicsSceneIndex) +public: + QGraphicsSceneIndexPrivate(QGraphicsScene *scene); + ~QGraphicsSceneIndexPrivate(); + + void recursive_items_helper(QGraphicsItem *item, QGraphicsSceneIndexIntersector *intersector, QList<QGraphicsItem *> *items, + const QTransform &parentTransform, const QTransform &viewTransform, + Qt::ItemSelectionMode mode, Qt::SortOrder order, qreal parentOpacity = 1.0) const; + QGraphicsScene *scene; + QGraphicsSceneIndexPointIntersector *pointIntersector; + QGraphicsSceneIndexRectIntersector *rectIntersector; + QGraphicsSceneIndexPathIntersector *pathIntersector; +}; + +class QGraphicsSceneIndexIntersector +{ +public: + QGraphicsSceneIndexIntersector(QGraphicsScene *scene) : scene(scene) { } + virtual ~QGraphicsSceneIndexIntersector() { } + virtual bool intersect(const QRectF &rect) const = 0; + Qt::ItemSelectionMode mode; + QGraphicsItem *item; + QGraphicsScene *scene; + QRectF rect; + QTransform transform; +}; + +QT_END_NAMESPACE + +#endif // QGRAPHICSSCENEINDEX_P_H + +#endif diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex.cpp b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp new file mode 100644 index 0000000..1c898bc --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp @@ -0,0 +1,70 @@ +#include "qgraphicsscenelinearindex_p.h" + +/*! + \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 + + 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 +*/ + +/*! + \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::sceneRectChanged(const QRectF &rect); + \reimp + This method react to the \a rect change of the scene. +*/ + +/*! + \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..d21475c --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h @@ -0,0 +1,118 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QGRAPHICSSCENELINEARINDEX_P_H +#define QGRAPHICSSCENELINEARINDEX_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/qlist.h> + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include <QtCore/qrect.h> +#include <QtCore/qlist.h> +#include <QtGui/qgraphicssceneindex.h> +#include <QtGui/qgraphicsitem.h> + +QT_BEGIN_NAMESPACE + +class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex +{ + Q_OBJECT + +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; + } + + virtual QRectF indexedRect() const { + return m_sceneRect; + } + +protected : + void sceneRectChanged(const QRectF &rect) { + m_sceneRect = rect; + } + + virtual void clear() { + m_items.clear(); + } + + virtual void addItem(QGraphicsItem *item) { + m_items << item; + } + + virtual void removeItem(QGraphicsItem *item) { + m_items.removeAll(item); + } + +private: + QRectF m_sceneRect; + QList<QGraphicsItem*> m_items; +}; + +QT_END_NAMESPACE + +#endif // QT_NO_GRAPHICSVIEW + +#endif // QGRAPHICSSCENELINEARINDEX_P_H diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp index e349992..8c40878 100644 --- a/src/gui/graphicsview/qgraphicsview.cpp +++ b/src/gui/graphicsview/qgraphicsview.cpp @@ -788,19 +788,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) @@ -937,7 +927,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg *allItems = true; // All items are guaranteed within the exposed region, don't bother using the index. - QList<QGraphicsItem *> itemList(scene->items()); + QList<QGraphicsItem *> itemList(scene->d_func()->index->items(Qt::DescendingOrder)); int i = 0; while (i < itemList.size()) { const QGraphicsItem *item = itemList.at(i); @@ -950,9 +940,6 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg else ++i; } - - // Sort the items. - QGraphicsScenePrivate::sortItems(&itemList, Qt::DescendingOrder, scene->d_func()->sortCacheEnabled); return itemList; } @@ -962,7 +949,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg bool simpleRectLookup = (scene->d_func()->largestUntransformableItem.isNull() && exposedRegion.numRects() == 1 && matrix.type() <= QTransform::TxScale); if (simpleRectLookup) { - return scene->d_func()->items_helper(exposedRegionSceneBounds, + return scene->d_func()->index->items(exposedRegionSceneBounds, Qt::IntersectsItemBoundingRect, Qt::DescendingOrder); } @@ -977,7 +964,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg const QPainterPath exposedPath(qt_regionToPath(adjustedRegion)); if (scene->d_func()->largestUntransformableItem.isNull()) { const QPainterPath exposedScenePath(q->mapToScene(exposedPath)); - return scene->d_func()->items_helper(exposedScenePath, + return scene->d_func()->index->items(exposedScenePath, Qt::IntersectsItemBoundingRect, Qt::DescendingOrder); } @@ -2011,17 +1998,19 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat // First build a (potentially large) list of all items in the vicinity // that might be untransformable. - QList<QGraphicsItem *> allCandidates = scene->d_func()->estimateItemsInRect(adjustedRect); + QList<QGraphicsItem *> allCandidates = scene->d_func()->index->estimateItems(adjustedRect, order, q->transform()); // Then find the minimal list of items that are inside \a path, and // convert it to a set. - QList<QGraphicsItem *> regularCandidates = scene->items(q->mapToScene(path), mode); + QList<QGraphicsItem *> regularCandidates = scene->items(q->mapToScene(path), mode, order, q->transform()); QSet<QGraphicsItem *> candSet = QSet<QGraphicsItem *>::fromList(regularCandidates); QTransform viewMatrix = q->viewportTransform(); QList<QGraphicsItem *> result; + //### this will disapear + // Run through all candidates and keep all items that are in candSet, or // are untransformable and collide with \a path. ### We can improve this // algorithm. @@ -2040,10 +2029,6 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat } ++it; } - - // ### Insertion sort would be faster. - if (order != Qt::SortOrder(-1)) - QGraphicsScenePrivate::sortItems(&result, order, scene->d_func()->sortCacheEnabled); return result; } diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro index a8b1059..ea05cc6 100644 --- a/tests/auto/auto.pro +++ b/tests/auto/auto.pro @@ -149,6 +149,7 @@ SUBDIRS += _networkselftest \ qgraphicspolygonitem \ qgraphicsproxywidget \ qgraphicsscene \ + qgraphicssceneindex \ qgraphicsview \ qgraphicswidget \ qgridlayout \ diff --git a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp index e8a6d10..2b936d6 100644 --- a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp +++ b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp @@ -4710,6 +4710,11 @@ void tst_QGraphicsItem::itemClipsChildrenToShape() scene.render(&painter); painter.end(); + QGraphicsView view(&scene); + view.show(); + + QTest::qWait(5000); + QCOMPARE(image.pixel(16, 16), QColor(255, 0, 0).rgba()); QCOMPARE(image.pixel(32, 32), QColor(0, 0, 255).rgba()); QCOMPARE(image.pixel(50, 50), QColor(0, 255, 0).rgba()); diff --git a/tests/auto/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 6439125..1d03ef1 100644 --- a/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp +++ b/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp @@ -381,8 +381,7 @@ void tst_QGraphicsScene::items() for (int x = minX; x < maxX; x += 100) items << scene.addRect(QRectF(0, 0, 10, 10)); } - - QCOMPARE(scene.items(), items); + QCOMPARE(scene.items().size(), items.size()); scene.itemAt(0, 0); // trigger indexing scene.removeItem(items.at(5)); @@ -397,6 +396,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)); } @@ -2724,8 +2726,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..6b352ab --- /dev/null +++ b/tests/auto/qgraphicssceneindex/tst_qgraphicssceneindex.cpp @@ -0,0 +1,221 @@ +/**************************************************************************** +** +** 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 <QtGui/qgraphicssceneindex.h> +#include <private/qgraphicsscenebsptreeindex_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 sceneRect_data(); + void sceneRect(); + 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::sceneRect_data() +{ + common_data(); +} + +void tst_QGraphicsSceneIndex::sceneRect() +{ + QGraphicsScene *scene = new QGraphicsScene(); + QGraphicsSceneIndex *index = new QGraphicsSceneBspTreeIndex(scene); + scene->setSceneRect(QRectF(0, 0, 2000, 2000)); + QCOMPARE(index->indexedRect(), QRectF(0, 0, 2000, 2000)); +} + +void tst_QGraphicsSceneIndex::customIndex_data() +{ + common_data(); +} + +void tst_QGraphicsSceneIndex::customIndex() +{ + 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); +} + +void tst_QGraphicsSceneIndex::scatteredItems_data() +{ + common_data(); +} + +void tst_QGraphicsSceneIndex::scatteredItems() +{ + QFETCH(QString, indexMethod); + QGraphicsSceneIndex *index = createIndex(indexMethod); + + QGraphicsScene scene; + scene.setSceneIndex(index); + + 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); + QGraphicsSceneIndex *index = createIndex(indexMethod); + + QGraphicsScene scene; + scene.setSceneIndex(index); + + 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); + QGraphicsSceneIndex *index = createIndex(indexMethod); + + QGraphicsScene scene; + scene.setSceneIndex(index); + + 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..c8c032a 100644 --- a/tests/auto/qgraphicsview/tst_qgraphicsview.cpp +++ b/tests/auto/qgraphicsview/tst_qgraphicsview.cpp @@ -2106,12 +2106,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 +2126,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); } } } |