1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4//
5// W A R N I N G
6// -------------
7//
8// This file is not part of the Qt API. It exists for the convenience
9// of other Qt classes. This header file may change from version to
10// version without notice, or even be removed.
11//
12// We mean it.
13//
14
15#ifndef QGRAPHICSBSPTREEINDEX_H
16#define QGRAPHICSBSPTREEINDEX_H
17
18#include <QtWidgets/private/qtwidgetsglobal_p.h>
19
20#include "qgraphicssceneindex_p.h"
21#include "qgraphicsitem_p.h"
22#include "qgraphicsscene_bsp_p.h"
23
24#include <QtCore/qrect.h>
25#include <QtCore/qlist.h>
26
27QT_REQUIRE_CONFIG(graphicsview);
28
29QT_BEGIN_NAMESPACE
30
31static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
32
33class QGraphicsScene;
34class QGraphicsSceneBspTreeIndexPrivate;
35
36class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
37{
38 Q_OBJECT
39 Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth)
40public:
41 QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = nullptr);
42 ~QGraphicsSceneBspTreeIndex();
43
44 QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const override;
45 QList<QGraphicsItem *> estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const override;
46 QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const override;
47
48 int bspTreeDepth() const;
49 void setBspTreeDepth(int depth);
50
51protected Q_SLOTS:
52 void updateSceneRect(const QRectF &rect) override;
53
54protected:
55 bool event(QEvent *event) override;
56 void clear() override;
57
58 void addItem(QGraphicsItem *item) override;
59 void removeItem(QGraphicsItem *item) override;
60 void prepareBoundingRectChange(const QGraphicsItem *item) override;
61
62 void itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value) override;
63
64private :
65 Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex)
66 Q_DISABLE_COPY_MOVE(QGraphicsSceneBspTreeIndex)
67 Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
68 Q_PRIVATE_SLOT(d_func(), void _q_updateIndex())
69
70 friend class QGraphicsScene;
71 friend class QGraphicsScenePrivate;
72};
73
74class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate
75{
76 Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)
77public:
78 QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);
79
80 QGraphicsSceneBspTree bsp;
81 QRectF sceneRect;
82 int bspTreeDepth;
83 int indexTimerId;
84 bool restartIndexTimer;
85 bool regenerateIndex;
86 int lastItemCount;
87
88 QList<QGraphicsItem *> indexedItems;
89 QList<QGraphicsItem *> unindexedItems;
90 QList<QGraphicsItem *> untransformableItems;
91 QList<int> freeItemIndexes;
92
93 bool purgePending;
94 QSet<QGraphicsItem *> removedItems;
95 void purgeRemovedItems();
96
97 void _q_updateIndex();
98 void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
99 void resetIndex();
100
101 void _q_updateSortCache();
102 bool sortCacheEnabled;
103 bool updatingSortCache;
104 void invalidateSortCache();
105 void addItem(QGraphicsItem *item, bool recursive = false);
106 void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false);
107 QList<QGraphicsItem *> estimateItems(const QRectF &, Qt::SortOrder, bool b = false);
108
109 static void climbTree(QGraphicsItem *item, int *stackingOrder);
110
111 static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
112 {
113 return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
114 }
115 static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
116 {
117 return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
118 }
119
120 static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
121 bool cached, bool onlyTopLevelItems = false);
122};
123
124static inline bool QRectF_intersects(const QRectF &s, const QRectF &r)
125{
126 qreal xp = s.left();
127 qreal yp = s.top();
128 qreal w = s.width();
129 qreal h = s.height();
130 qreal l1 = xp;
131 qreal r1 = xp;
132 if (w < 0)
133 l1 += w;
134 else
135 r1 += w;
136
137 qreal l2 = r.left();
138 qreal r2 = r.left();
139 if (w < 0)
140 l2 += r.width();
141 else
142 r2 += r.width();
143
144 if (l1 >= r2 || l2 >= r1)
145 return false;
146
147 qreal t1 = yp;
148 qreal b1 = yp;
149 if (h < 0)
150 t1 += h;
151 else
152 b1 += h;
153
154 qreal t2 = r.top();
155 qreal b2 = r.top();
156 if (r.height() < 0)
157 t2 += r.height();
158 else
159 b2 += r.height();
160
161 return !(t1 >= b2 || t2 >= b1);
162}
163
164QT_END_NAMESPACE
165
166#endif // QGRAPHICSBSPTREEINDEX_H
167

source code of qtbase/src/widgets/graphicsview/qgraphicsscenebsptreeindex_p.h