summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/gui/graphicsview/graphicsview.pri1
-rw-r--r--src/gui/graphicsview/qgraphicsscene.cpp12
-rw-r--r--src/gui/graphicsview/qgraphicsscene_p.h4
-rw-r--r--src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp145
-rw-r--r--src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h5
-rw-r--r--src/gui/graphicsview/qgraphicssceneindex.cpp27
-rw-r--r--src/gui/graphicsview/qgraphicsscenelinearindex_p.h37
7 files changed, 198 insertions, 33 deletions
diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri
index 9dc4112..a4d142a 100644
--- a/src/gui/graphicsview/graphicsview.pri
+++ b/src/gui/graphicsview/graphicsview.pri
@@ -18,6 +18,7 @@ SOURCES += graphicsview/qgraphicsitem.cpp \
graphicsview/qgraphicsscene.cpp \
graphicsview/qgraphicsscene_bsp.cpp \
graphicsview/qgraphicsscenebsptreeindex_p.cpp \
+ graphicsview/qgraphicsscenelinearindex.cpp \
graphicsview/qgraphicssceneindex.cpp \
graphicsview/qgraphicssceneevent.cpp \
graphicsview/qgraphicsview.cpp
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 0729a9d..328ab4c 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -271,9 +271,8 @@ static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraph
QGraphicsScenePrivate::QGraphicsScenePrivate()
: changedSignalMask(0),
indexMethod(QGraphicsScene::BspTreeIndex),
- bspTreeDepth(0),
- lastItemCount(0),
index(0),
+ lastItemCount(0),
hasSceneRect(false),
updateAll(false),
calledEmitUpdated(false),
@@ -1642,14 +1641,11 @@ int QGraphicsScene::bspTreeDepth() const
{
Q_D(const QGraphicsScene);
QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index);
- return bspTree ? bspTree->bspDepth() : 0;
+ 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;
@@ -1660,8 +1656,10 @@ void QGraphicsScene::setBspTreeDepth(int depth)
qWarning("QGraphicsScene::setBspTreeDepth: can not apply if indexing method is not BSP");
return;
}
+ if (bspTree->bspTreeDepth() == depth)
+ return;
- bspTree->setBspDepth(depth);
+ bspTree->setBspTreeDepth(depth);
}
/*!
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index c63e121..db401ef 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -90,12 +90,10 @@ public:
quint32 changedSignalMask;
QGraphicsScene::ItemIndexMethod indexMethod;
- int bspTreeDepth;
+ QGraphicsSceneIndex *index;
int lastItemCount;
- QGraphicsSceneIndex *index;
-
QRectF sceneRect;
bool hasSceneRect;
QRectF growingItemsBoundingRect;
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
index acadcbd..b19248a 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
@@ -39,6 +39,40 @@
**
****************************************************************************/
+/*!
+ \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"
@@ -61,7 +95,7 @@ static inline int intmaxlog(int n)
}
/*!
- Constructs a private scene index.
+ Constructs a private scene bsp index.
*/
QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene)
: QGraphicsSceneIndexPrivate(scene),
@@ -78,6 +112,11 @@ QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsSc
/*!
+ 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()
@@ -223,6 +262,9 @@ void QGraphicsSceneBspTreeIndexPrivate::resetIndex()
startIndexTimer();
}
+/*!
+ \internal
+*/
void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder)
{
if (!item->d_ptr->children.isEmpty()) {
@@ -244,6 +286,9 @@ void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stac
}
}
+/*!
+ \internal
+*/
void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache()
{
Q_Q(QGraphicsSceneBspTreeIndex);
@@ -268,6 +313,9 @@ void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache()
climbTree(topLevels.at(i), &stackingOrder);
}
+/*!
+ \internal
+*/
void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache()
{
Q_Q(QGraphicsSceneBspTreeIndex);
@@ -342,6 +390,11 @@ bool QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withoutCache(const QGrap
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)
{
@@ -360,12 +413,19 @@ void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList<QGraphicsItem *> *itemLi
}
}
+/*!
+ 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);
@@ -373,6 +433,10 @@ QRectF QGraphicsSceneBspTreeIndex::indexedRect() const
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);
@@ -383,6 +447,9 @@ void QGraphicsSceneBspTreeIndex::clear()
d->unindexedItems.clear();
}
+/*!
+ Add the \a item into the BSP index.
+*/
void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item)
{
Q_D(QGraphicsSceneBspTreeIndex);
@@ -405,6 +472,7 @@ void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item)
}
/*!
+ This really add the item in the BSP.
\internal
*/
void QGraphicsSceneBspTreeIndexPrivate::addToIndex(QGraphicsItem *item)
@@ -421,6 +489,9 @@ void QGraphicsSceneBspTreeIndexPrivate::addToIndex(QGraphicsItem *item)
}
}
+/*!
+ Remove the \a item from the BSP index.
+*/
void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item)
{
Q_D(QGraphicsSceneBspTreeIndex);
@@ -443,6 +514,10 @@ void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item)
}
}
+/*!
+ \reimp
+ Delete the \a item from the BSP index (without accessing its boundingRect).
+*/
void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item)
{
Q_D(QGraphicsSceneBspTreeIndex);
@@ -469,6 +544,7 @@ void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item)
}
/*!
+ Really remove the item from the BSP
\internal
*/
void QGraphicsSceneBspTreeIndexPrivate::removeFromIndex(QGraphicsItem *item)
@@ -492,6 +568,10 @@ void QGraphicsSceneBspTreeIndexPrivate::removeFromIndex(QGraphicsItem *item)
startIndexTimer();
}
+/*!
+ \reimp
+ Update the BSP when the \a item 's bounding rect has changed.
+*/
void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item)
{
Q_D(QGraphicsSceneBspTreeIndex);
@@ -501,6 +581,13 @@ void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *
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);
@@ -530,6 +617,12 @@ QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &r
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);
@@ -558,19 +651,52 @@ QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) co
return itemList;
}
-int QGraphicsSceneBspTreeIndex::bspDepth()
+/*!
+ \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::setBspDepth(int depth)
+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);
@@ -578,6 +704,13 @@ void QGraphicsSceneBspTreeIndex::sceneRectChanged(const QRectF &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);
@@ -592,7 +725,13 @@ void QGraphicsSceneBspTreeIndex::itemChanged(const QGraphicsItem *item, QGraphic
}
return QGraphicsSceneIndex::itemChanged(item, change, value);
}
+/*!
+ \reimp
+ Used to catch the timer event.
+
+ \internal
+*/
bool QGraphicsSceneBspTreeIndex::event(QEvent *event)
{
Q_D(QGraphicsSceneBspTreeIndex);
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
index b1ea977..40b8f0b 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
@@ -60,6 +60,7 @@ 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;
@@ -68,8 +69,8 @@ public:
QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const;
- int bspDepth();
- void setBspDepth(int depth);
+ int bspTreeDepth();
+ void setBspTreeDepth(int depth);
protected:
bool event(QEvent *event);
diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp
index b713452..05ec28b 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.cpp
+++ b/src/gui/graphicsview/qgraphicssceneindex.cpp
@@ -147,6 +147,9 @@ QGraphicsSceneIndexPrivate::~QGraphicsSceneIndexPrivate()
delete pathIntersector;
}
+/*!
+ \internal
+*/
void QGraphicsSceneIndexPrivate::recursive_items_helper(QGraphicsItem *item, QGraphicsSceneIndexIntersector *intersector,
QList<QGraphicsItem *> *items,
const QTransform &parentTransform,
@@ -297,6 +300,12 @@ QRectF QGraphicsSceneIndex::indexedRect() const
\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
{
@@ -322,6 +331,12 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, Qt::ItemSe
\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
{
@@ -346,6 +361,12 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, Qt::ItemSe
\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
{
@@ -375,6 +396,12 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF &polygon, Qt::
\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
{
diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
index 3057b4a..d21475c 100644
--- a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
@@ -68,23 +68,32 @@ class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex
{
Q_OBJECT
-private:
- QRectF m_sceneRect;
- QList<QGraphicsItem*> m_items;
-
public:
QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0): QGraphicsSceneIndex(scene)
{
}
- virtual void setRect(const QRectF &rect) {
- m_sceneRect = rect;
+ 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 rect() const {
+ virtual QRectF indexedRect() const {
return m_sceneRect;
}
+protected :
+ void sceneRectChanged(const QRectF &rect) {
+ m_sceneRect = rect;
+ }
+
virtual void clear() {
m_items.clear();
}
@@ -97,17 +106,9 @@ public:
m_items.removeAll(item);
}
- virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const {
- QList<QGraphicsItem*> result;
- foreach (QGraphicsItem *item, m_items)
- if (item->sceneBoundingRect().intersects(rect))
- result << item;
- return result;
- }
-
- QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const {
- return m_items;
- }
+private:
+ QRectF m_sceneRect;
+ QList<QGraphicsItem*> m_items;
};
QT_END_NAMESPACE
generated by cgit v0.12 at 2024-11-18 12:59:17 (GMT)