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
45QT_BEGIN_NAMESPACE
46
47class QGraphicsSceneInsertItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
48{
49public:
50 QGraphicsItem *item;
51
52 void visit(QList<QGraphicsItem *> *items) override
53 { items->prepend(item); }
54};
55
56class QGraphicsSceneRemoveItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
57{
58public:
59 QGraphicsItem *item;
60
61 void visit(QList<QGraphicsItem *> *items) override
62 { items->removeAll(item); }
63};
64
65class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
66{
67public:
68 QList<QGraphicsItem *> *foundItems;
69 bool onlyTopLevelItems;
70
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
85QGraphicsSceneBspTree::QGraphicsSceneBspTree()
86 : leafCnt(0)
87{
88 insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor;
89 removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor;
90 findVisitor = new QGraphicsSceneFindItemBspTreeVisitor;
91}
92
93QGraphicsSceneBspTree::~QGraphicsSceneBspTree()
94{
95 delete insertVisitor;
96 delete removeVisitor;
97 delete findVisitor;
98}
99
100void 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
112void QGraphicsSceneBspTree::clear()
113{
114 leafCnt = 0;
115 nodes.clear();
116 leaves.clear();
117}
118
119void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect)
120{
121 insertVisitor->item = item;
122 climbTree(insertVisitor, rect);
123}
124
125void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect)
126{
127 removeVisitor->item = item;
128 climbTree(removeVisitor, rect);
129}
130
131void 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
145QList<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
157int QGraphicsSceneBspTree::leafCount() const
158{
159 return leafCnt;
160}
161
162QString 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
188void 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
233void 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
266QRectF 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
290QT_END_NAMESPACE
291