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#include "qgraphicsscene_bsp_p.h"
5
6#include <QtCore/qstring.h>
7#include <private/qgraphicsitem_p.h>
8
9QT_BEGIN_NAMESPACE
10
11
12QGraphicsSceneBspTree::QGraphicsSceneBspTree()
13 : leafCnt(0)
14{
15}
16
17QGraphicsSceneBspTree::~QGraphicsSceneBspTree()
18{
19}
20
21void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth)
22{
23 this->rect = rect;
24 leafCnt = 0;
25 nodes.resize(size: (1 << (depth + 1)) - 1);
26 nodes.fill(t: Node());
27 leaves.resize(size: 1ll << depth);
28 leaves.fill(t: QList<QGraphicsItem *>());
29
30 initialize(rect, depth, index: 0);
31}
32
33void QGraphicsSceneBspTree::clear()
34{
35 leafCnt = 0;
36 nodes.clear();
37 leaves.clear();
38}
39
40void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect)
41{
42 climbTree(visitor: [item](QList<QGraphicsItem *> *items){
43 items->prepend(t: item);
44 }, rect);
45}
46
47void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect)
48{
49 climbTree(visitor: [item](QList<QGraphicsItem *> *items){
50 items->removeAll(t: item);
51 }, rect);
52}
53
54void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items)
55{
56 for (int i = 0; i < leaves.size(); ++i) {
57 QList<QGraphicsItem *> newItemList;
58 const QList<QGraphicsItem *> &oldItemList = leaves[i];
59 for (int j = 0; j < oldItemList.size(); ++j) {
60 QGraphicsItem *item = oldItemList.at(i: j);
61 if (!items.contains(value: item))
62 newItemList << item;
63 }
64 leaves[i] = newItemList;
65 }
66}
67
68QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const
69{
70 QList<QGraphicsItem *> foundItems;
71 climbTree(visitor: [&foundItems, onlyTopLevelItems](QList<QGraphicsItem *> *items) {
72 for (int i = 0; i < items->size(); ++i) {
73 QGraphicsItem *item = items->at(i);
74 if (onlyTopLevelItems && item->d_ptr->parent)
75 item = item->topLevelItem();
76 if (!item->d_func()->itemDiscovered && item->d_ptr->visible) {
77 item->d_func()->itemDiscovered = 1;
78 foundItems.prepend(t: item);
79 }
80 }
81 }, rect);
82 // Reset discovery bits.
83 for (const auto &foundItem : std::as_const(t&: foundItems))
84 foundItem->d_ptr->itemDiscovered = 0;
85 return foundItems;
86}
87
88int QGraphicsSceneBspTree::leafCount() const
89{
90 return leafCnt;
91}
92
93QString QGraphicsSceneBspTree::debug(int index) const
94{
95 const Node *node = &nodes.at(i: index);
96
97 QString tmp;
98 if (node->type == Node::Leaf) {
99 QRectF rect = rectForIndex(index);
100 if (!leaves[node->leafIndex].isEmpty()) {
101 tmp += QString::fromLatin1(ba: "[%1, %2, %3, %4] contains %5 items\n")
102 .arg(a: rect.left()).arg(a: rect.top())
103 .arg(a: rect.width()).arg(a: rect.height())
104 .arg(a: leaves[node->leafIndex].size());
105 }
106 } else {
107 if (node->type == Node::Horizontal) {
108 tmp += debug(index: firstChildIndex(index));
109 tmp += debug(index: firstChildIndex(index) + 1);
110 } else {
111 tmp += debug(index: firstChildIndex(index));
112 tmp += debug(index: firstChildIndex(index) + 1);
113 }
114 }
115
116 return tmp;
117}
118
119void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index)
120{
121 Node *node = &nodes[index];
122 if (index == 0) {
123 node->type = Node::Horizontal;
124 node->offset = rect.center().y();
125 }
126
127 if (depth) {
128 Node::Type type;
129 QRectF rect1, rect2;
130 qreal offset1, offset2;
131
132 if (node->type == Node::Horizontal) {
133 type = Node::Vertical;
134 rect1.setRect(ax: rect.left(), ay: rect.top(), aaw: rect.width(), aah: rect.height() / 2);
135 rect2.setRect(ax: rect1.left(), ay: rect1.bottom(), aaw: rect1.width(), aah: rect.height() - rect1.height());
136 offset1 = rect1.center().x();
137 offset2 = rect2.center().x();
138 } else {
139 type = Node::Horizontal;
140 rect1.setRect(ax: rect.left(), ay: rect.top(), aaw: rect.width() / 2, aah: rect.height());
141 rect2.setRect(ax: rect1.right(), ay: rect1.top(), aaw: rect.width() - rect1.width(), aah: rect1.height());
142 offset1 = rect1.center().y();
143 offset2 = rect2.center().y();
144 }
145
146 int childIndex = firstChildIndex(index);
147
148 Node *child = &nodes[childIndex];
149 child->offset = offset1;
150 child->type = type;
151
152 child = &nodes[childIndex + 1];
153 child->offset = offset2;
154 child->type = type;
155
156 initialize(rect: rect1, depth: depth - 1, index: childIndex);
157 initialize(rect: rect2, depth: depth - 1, index: childIndex + 1);
158 } else {
159 node->type = Node::Leaf;
160 node->leafIndex = leafCnt++;
161 }
162}
163
164template<typename Visitor>
165void QGraphicsSceneBspTree::climbTree(Visitor &&visitor, const QRectF &rect, int index) const
166{
167 if (nodes.isEmpty())
168 return;
169
170 const Node &node = nodes.at(i: index);
171 const int childIndex = firstChildIndex(index);
172
173 switch (node.type) {
174 case Node::Leaf: {
175 visitor(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));
176 break;
177 }
178 case Node::Vertical:
179 if (rect.left() < node.offset) {
180 climbTree(visitor, rect, childIndex);
181 if (rect.right() >= node.offset)
182 climbTree(visitor, rect, childIndex + 1);
183 } else {
184 climbTree(visitor, rect, childIndex + 1);
185 }
186 break;
187 case Node::Horizontal:
188 if (rect.top() < node.offset) {
189 climbTree(visitor, rect, childIndex);
190 if (rect.bottom() >= node.offset)
191 climbTree(visitor, rect, childIndex + 1);
192 } else {
193 climbTree(visitor, rect, childIndex + 1);
194 }
195 }
196}
197
198QRectF QGraphicsSceneBspTree::rectForIndex(int index) const
199{
200 if (index <= 0)
201 return rect;
202
203 int parentIdx = parentIndex(index);
204 QRectF rect = rectForIndex(index: parentIdx);
205 const Node *parent = &nodes.at(i: parentIdx);
206
207 if (parent->type == Node::Vertical) {
208 if (index & 1)
209 rect.setRight(parent->offset);
210 else
211 rect.setLeft(parent->offset);
212 } else {
213 if (index & 1)
214 rect.setBottom(parent->offset);
215 else
216 rect.setTop(parent->offset);
217 }
218
219 return rect;
220}
221
222QT_END_NAMESPACE
223

source code of qtbase/src/widgets/graphicsview/qgraphicsscene_bsp.cpp