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 | |
147 | static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2) |
148 | { |
149 | return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder; |
150 | } |
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 | |
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 | |