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/qbasictimer.h>
25#include <QtCore/qrect.h>
26#include <QtCore/qlist.h>
27
28QT_REQUIRE_CONFIG(graphicsview);
29
30QT_BEGIN_NAMESPACE
31
32static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
33
34class QGraphicsScene;
35class QGraphicsSceneBspTreeIndexPrivate;
36
37class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
38{
39 Q_OBJECT
40 Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth)
41public:
42 QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = nullptr);
43 ~QGraphicsSceneBspTreeIndex();
44
45 QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const override;
46 QList<QGraphicsItem *> estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const override;
47 QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const override;
48
49 int bspTreeDepth() const;
50 void setBspTreeDepth(int depth);
51
52protected Q_SLOTS:
53 void updateSceneRect(const QRectF &rect) override;
54
55protected:
56 bool event(QEvent *event) override;
57 void clear() override;
58
59 void addItem(QGraphicsItem *item) override;
60 void removeItem(QGraphicsItem *item) override;
61 void prepareBoundingRectChange(const QGraphicsItem *item) override;
62
63 void itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value) override;
64
65private :
66 Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex)
67 Q_DISABLE_COPY_MOVE(QGraphicsSceneBspTreeIndex)
68 Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
69 Q_PRIVATE_SLOT(d_func(), void _q_updateIndex())
70
71 friend class QGraphicsScene;
72 friend class QGraphicsScenePrivate;
73};
74
75class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate
76{
77 Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)
78public:
79 QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);
80
81 QGraphicsSceneBspTree bsp;
82 QRectF sceneRect;
83 int bspTreeDepth;
84 QBasicTimer indexTimer;
85 bool restartIndexTimer;
86 bool regenerateIndex;
87 int lastItemCount;
88
89 QList<QGraphicsItem *> indexedItems;
90 QList<QGraphicsItem *> unindexedItems;
91 QList<QGraphicsItem *> untransformableItems;
92 QList<int> freeItemIndexes;
93
94 bool purgePending;
95 QSet<QGraphicsItem *> removedItems;
96 void purgeRemovedItems();
97
98 void _q_updateIndex();
99 void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
100 void resetIndex();
101
102 void _q_updateSortCache();
103 bool sortCacheEnabled;
104 bool updatingSortCache;
105 void invalidateSortCache();
106 void addItem(QGraphicsItem *item, bool recursive = false);
107 void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false);
108 QList<QGraphicsItem *> estimateItems(const QRectF &, Qt::SortOrder, bool b = false);
109
110 static void climbTree(QGraphicsItem *item, int *stackingOrder);
111
112 static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
113 {
114 return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
115 }
116 static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
117 {
118 return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
119 }
120
121 static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
122 bool cached, bool onlyTopLevelItems = false);
123};
124
125static inline bool QRectF_intersects(const QRectF &s, const QRectF &r)
126{
127 qreal xp = s.left();
128 qreal yp = s.top();
129 qreal w = s.width();
130 qreal h = s.height();
131 qreal l1 = xp;
132 qreal r1 = xp;
133 if (w < 0)
134 l1 += w;
135 else
136 r1 += w;
137
138 qreal l2 = r.left();
139 qreal r2 = r.left();
140 if (w < 0)
141 l2 += r.width();
142 else
143 r2 += r.width();
144
145 if (l1 >= r2 || l2 >= r1)
146 return false;
147
148 qreal t1 = yp;
149 qreal b1 = yp;
150 if (h < 0)
151 t1 += h;
152 else
153 b1 += h;
154
155 qreal t2 = r.top();
156 qreal b2 = r.top();
157 if (r.height() < 0)
158 t2 += r.height();
159 else
160 b2 += r.height();
161
162 return !(t1 >= b2 || t2 >= b1);
163}
164
165QT_END_NAMESPACE
166
167#endif // QGRAPHICSBSPTREEINDEX_H
168

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