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 QtWidgets 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 #include "qgraphicsscene_bsp_p.h"
41
42 #include <QtCore/qstring.h>
43 #include <private/qgraphicsitem_p.h>
44
45 QT_BEGIN_NAMESPACE
46
47 class QGraphicsSceneInsertItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
48 {
49 public:
50 QGraphicsItem *item;
51
visit(QList<QGraphicsItem * > * items)52 void visit(QList<QGraphicsItem *> *items) override
53 { items->prepend(item); }
54 };
55
56 class QGraphicsSceneRemoveItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
57 {
58 public:
59 QGraphicsItem *item;
60
visit(QList<QGraphicsItem * > * items)61 void visit(QList<QGraphicsItem *> *items) override
62 { items->removeAll(item); }
63 };
64
65 class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
66 {
67 public:
68 QList<QGraphicsItem *> *foundItems;
69 bool onlyTopLevelItems;
70
visit(QList<QGraphicsItem * > * items)71 void visit(QList<QGraphicsItem *> *items) override
72 {
73 for (int i = 0; i < items->size(); ++i) {
74 QGraphicsItem *item = items->at(i);
75 if (onlyTopLevelItems && item->d_ptr->parent)
76 item = item->topLevelItem();
77 if (!item->d_func()->itemDiscovered && item->d_ptr->visible) {
78 item->d_func()->itemDiscovered = 1;
79 foundItems->prepend(item);
80 }
81 }
82 }
83 };
84
QGraphicsSceneBspTree()85 QGraphicsSceneBspTree::QGraphicsSceneBspTree()
86 : leafCnt(0)
87 {
88 insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor;
89 removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor;
90 findVisitor = new QGraphicsSceneFindItemBspTreeVisitor;
91 }
92
~QGraphicsSceneBspTree()93 QGraphicsSceneBspTree::~QGraphicsSceneBspTree()
94 {
95 delete insertVisitor;
96 delete removeVisitor;
97 delete findVisitor;
98 }
99
initialize(const QRectF & rect,int depth)100 void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth)
101 {
102 this->rect = rect;
103 leafCnt = 0;
104 nodes.resize((1 << (depth + 1)) - 1);
105 nodes.fill(Node());
106 leaves.resize(1 << depth);
107 leaves.fill(QList<QGraphicsItem *>());
108
109 initialize(rect, depth, 0);
110 }
111
clear()112 void QGraphicsSceneBspTree::clear()
113 {
114 leafCnt = 0;
115 nodes.clear();
116 leaves.clear();
117 }
118
insertItem(QGraphicsItem * item,const QRectF & rect)119 void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect)
120 {
121 insertVisitor->item = item;
122 climbTree(insertVisitor, rect);
123 }
124
removeItem(QGraphicsItem * item,const QRectF & rect)125 void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect)
126 {
127 removeVisitor->item = item;
128 climbTree(removeVisitor, rect);
129 }
130
removeItems(const QSet<QGraphicsItem * > & items)131 void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items)
132 {
133 for (int i = 0; i < leaves.size(); ++i) {
134 QList<QGraphicsItem *> newItemList;
135 const QList<QGraphicsItem *> &oldItemList = leaves[i];
136 for (int j = 0; j < oldItemList.size(); ++j) {
137 QGraphicsItem *item = oldItemList.at(j);
138 if (!items.contains(item))
139 newItemList << item;
140 }
141 leaves[i] = newItemList;
142 }
143 }
144
items(const QRectF & rect,bool onlyTopLevelItems) const145 QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const
146 {
147 QList<QGraphicsItem *> tmp;
148 findVisitor->foundItems = &tmp;
149 findVisitor->onlyTopLevelItems = onlyTopLevelItems;
150 climbTree(findVisitor, rect);
151 // Reset discovery bits.
152 for (int i = 0; i < tmp.size(); ++i)
153 tmp.at(i)->d_ptr->itemDiscovered = 0;
154 return tmp;
155 }
156
leafCount() const157 int QGraphicsSceneBspTree::leafCount() const
158 {
159 return leafCnt;
160 }
161
debug(int index) const162 QString QGraphicsSceneBspTree::debug(int index) const
163 {
164 const Node *node = &nodes.at(index);
165
166 QString tmp;
167 if (node->type == Node::Leaf) {
168 QRectF rect = rectForIndex(index);
169 if (!leaves[node->leafIndex].isEmpty()) {
170 tmp += QString::fromLatin1("[%1, %2, %3, %4] contains %5 items\n")
171 .arg(rect.left()).arg(rect.top())
172 .arg(rect.width()).arg(rect.height())
173 .arg(leaves[node->leafIndex].size());
174 }
175 } else {
176 if (node->type == Node::Horizontal) {
177 tmp += debug(firstChildIndex(index));
178 tmp += debug(firstChildIndex(index) + 1);
179 } else {
180 tmp += debug(firstChildIndex(index));
181 tmp += debug(firstChildIndex(index) + 1);
182 }
183 }
184
185 return tmp;
186 }
187
initialize(const QRectF & rect,int depth,int index)188 void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index)
189 {
190 Node *node = &nodes[index];
191 if (index == 0) {
192 node->type = Node::Horizontal;
193 node->offset = rect.center().y();
194 }
195
196 if (depth) {
197 Node::Type type;
198 QRectF rect1, rect2;
199 qreal offset1, offset2;
200
201 if (node->type == Node::Horizontal) {
202 type = Node::Vertical;
203 rect1.setRect(rect.left(), rect.top(), rect.width(), rect.height() / 2);
204 rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rect.height() - rect1.height());
205 offset1 = rect1.center().x();
206 offset2 = rect2.center().x();
207 } else {
208 type = Node::Horizontal;
209 rect1.setRect(rect.left(), rect.top(), rect.width() / 2, rect.height());
210 rect2.setRect(rect1.right(), rect1.top(), rect.width() - rect1.width(), rect1.height());
211 offset1 = rect1.center().y();
212 offset2 = rect2.center().y();
213 }
214
215 int childIndex = firstChildIndex(index);
216
217 Node *child = &nodes[childIndex];
218 child->offset = offset1;
219 child->type = type;
220
221 child = &nodes[childIndex + 1];
222 child->offset = offset2;
223 child->type = type;
224
225 initialize(rect1, depth - 1, childIndex);
226 initialize(rect2, depth - 1, childIndex + 1);
227 } else {
228 node->type = Node::Leaf;
229 node->leafIndex = leafCnt++;
230 }
231 }
232
climbTree(QGraphicsSceneBspTreeVisitor * visitor,const QRectF & rect,int index) const233 void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) const
234 {
235 if (nodes.isEmpty())
236 return;
237
238 const Node &node = nodes.at(index);
239 const int childIndex = firstChildIndex(index);
240
241 switch (node.type) {
242 case Node::Leaf: {
243 visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));
244 break;
245 }
246 case Node::Vertical:
247 if (rect.left() < node.offset) {
248 climbTree(visitor, rect, childIndex);
249 if (rect.right() >= node.offset)
250 climbTree(visitor, rect, childIndex + 1);
251 } else {
252 climbTree(visitor, rect, childIndex + 1);
253 }
254 break;
255 case Node::Horizontal:
256 if (rect.top() < node.offset) {
257 climbTree(visitor, rect, childIndex);
258 if (rect.bottom() >= node.offset)
259 climbTree(visitor, rect, childIndex + 1);
260 } else {
261 climbTree(visitor, rect, childIndex + 1);
262 }
263 }
264 }
265
rectForIndex(int index) const266 QRectF QGraphicsSceneBspTree::rectForIndex(int index) const
267 {
268 if (index <= 0)
269 return rect;
270
271 int parentIdx = parentIndex(index);
272 QRectF rect = rectForIndex(parentIdx);
273 const Node *parent = &nodes.at(parentIdx);
274
275 if (parent->type == Node::Vertical) {
276 if (index & 1)
277 rect.setRight(parent->offset);
278 else
279 rect.setLeft(parent->offset);
280 } else {
281 if (index & 1)
282 rect.setBottom(parent->offset);
283 else
284 rect.setTop(parent->offset);
285 }
286
287 return rect;
288 }
289
290 QT_END_NAMESPACE
291