1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
5 **
6 ** This file is part of the QtCore module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see https://www.qt.io/terms-conditions. For further
15 ** information use the contact form at https://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or (at your option) the GNU General
28 ** Public license version 3 or any later version approved by the KDE Free
29 ** Qt Foundation. The licenses are as published by the Free Software
30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31 ** included in the packaging of this file. Please review the following
32 ** information to ensure the GNU General Public License requirements will
33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34 ** https://www.gnu.org/licenses/gpl-3.0.html.
35 **
36 ** $QT_END_LICENSE$
37 **
38 ****************************************************************************/
39
40 //
41 // W A R N I N G
42 // -------------
43 //
44 // This file is not part of the Qt API. It exists for the convenience
45 // of other Qt classes. This header file may change from version to
46 // version without notice, or even be removed.
47 //
48 // We mean it.
49 //
50
51 #ifndef QGRAPHICSBSPTREEINDEX_H
52 #define QGRAPHICSBSPTREEINDEX_H
53
54 #include <QtWidgets/private/qtwidgetsglobal_p.h>
55
56 #include "qgraphicssceneindex_p.h"
57 #include "qgraphicsitem_p.h"
58 #include "qgraphicsscene_bsp_p.h"
59
60 #include <QtCore/qrect.h>
61 #include <QtCore/qlist.h>
62
63 QT_REQUIRE_CONFIG(graphicsview);
64
65 QT_BEGIN_NAMESPACE
66
67 static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
68
69 class QGraphicsScene;
70 class QGraphicsSceneBspTreeIndexPrivate;
71
72 class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
73 {
74 Q_OBJECT
75 Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth)
76 public:
77 QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = nullptr);
78 ~QGraphicsSceneBspTreeIndex();
79
80 QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const override;
81 QList<QGraphicsItem *> estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const override;
82 QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const override;
83
84 int bspTreeDepth() const;
85 void setBspTreeDepth(int depth);
86
87 protected Q_SLOTS:
88 void updateSceneRect(const QRectF &rect) override;
89
90 protected:
91 bool event(QEvent *event) override;
92 void clear() override;
93
94 void addItem(QGraphicsItem *item) override;
95 void removeItem(QGraphicsItem *item) override;
96 void prepareBoundingRectChange(const QGraphicsItem *item) override;
97
98 void itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value) override;
99
100 private :
101 Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex)
102 Q_DISABLE_COPY_MOVE(QGraphicsSceneBspTreeIndex)
103 Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
104 Q_PRIVATE_SLOT(d_func(), void _q_updateIndex())
105
106 friend class QGraphicsScene;
107 friend class QGraphicsScenePrivate;
108 };
109
110 class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate
111 {
112 Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)
113 public:
114 QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);
115
116 QGraphicsSceneBspTree bsp;
117 QRectF sceneRect;
118 int bspTreeDepth;
119 int indexTimerId;
120 bool restartIndexTimer;
121 bool regenerateIndex;
122 int lastItemCount;
123
124 QList<QGraphicsItem *> indexedItems;
125 QList<QGraphicsItem *> unindexedItems;
126 QList<QGraphicsItem *> untransformableItems;
127 QList<int> freeItemIndexes;
128
129 bool purgePending;
130 QSet<QGraphicsItem *> removedItems;
131 void purgeRemovedItems();
132
133 void _q_updateIndex();
134 void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
135 void resetIndex();
136
137 void _q_updateSortCache();
138 bool sortCacheEnabled;
139 bool updatingSortCache;
140 void invalidateSortCache();
141 void addItem(QGraphicsItem *item, bool recursive = false);
142 void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false);
143 QList<QGraphicsItem *> estimateItems(const QRectF &, Qt::SortOrder, bool b = false);
144
145 static void climbTree(QGraphicsItem *item, int *stackingOrder);
146
closestItemFirst_withCache(const QGraphicsItem * item1,const QGraphicsItem * item2)147 static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
148 {
149 return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
150 }
closestItemLast_withCache(const QGraphicsItem * item1,const QGraphicsItem * item2)151 static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
152 {
153 return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
154 }
155
156 static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
157 bool cached, bool onlyTopLevelItems = false);
158 };
159
QRectF_intersects(const QRectF & s,const QRectF & r)160 static inline bool QRectF_intersects(const QRectF &s, const QRectF &r)
161 {
162 qreal xp = s.left();
163 qreal yp = s.top();
164 qreal w = s.width();
165 qreal h = s.height();
166 qreal l1 = xp;
167 qreal r1 = xp;
168 if (w < 0)
169 l1 += w;
170 else
171 r1 += w;
172
173 qreal l2 = r.left();
174 qreal r2 = r.left();
175 if (w < 0)
176 l2 += r.width();
177 else
178 r2 += r.width();
179
180 if (l1 >= r2 || l2 >= r1)
181 return false;
182
183 qreal t1 = yp;
184 qreal b1 = yp;
185 if (h < 0)
186 t1 += h;
187 else
188 b1 += h;
189
190 qreal t2 = r.top();
191 qreal b2 = r.top();
192 if (r.height() < 0)
193 t2 += r.height();
194 else
195 b2 += r.height();
196
197 return !(t1 >= b2 || t2 >= b1);
198 }
199
200 QT_END_NAMESPACE
201
202 #endif // QGRAPHICSBSPTREEINDEX_H
203