source: trunk/src/gui/graphicsview/qgraphicsscene_bsp.cpp@ 508

Last change on this file since 508 was 2, checked in by Dmitry A. Kuminov, 16 years ago

Initially imported qt-all-opensource-src-4.5.1 from Trolltech.
File size: 9.5 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
4** Contact: Qt Software Information ([email protected])
5**
6** This file is part of the QtGui module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial Usage
10** Licensees holding valid Qt Commercial licenses may use this file in
11** accordance with the Qt Commercial License Agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and Nokia.
14**
15** GNU Lesser General Public License Usage
16** Alternatively, this file may be used under the terms of the GNU Lesser
17** General Public License version 2.1 as published by the Free Software
18** Foundation and appearing in the file LICENSE.LGPL included in the
19** packaging of this file. Please review the following information to
20** ensure the GNU Lesser General Public License version 2.1 requirements
21** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
22**
23** In addition, as a special exception, Nokia gives you certain
24** additional rights. These rights are described in the Nokia Qt LGPL
25** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
26** package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you are unsure which license is appropriate for your use, please
37** contact the sales department at [email protected].
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42#include "qgraphicsscene_bsp_p.h"
43
44#ifndef QT_NO_GRAPHICSVIEW
45
46#include <QtCore/qstring.h>
47#include <private/qgraphicsitem_p.h>
48
49QT_BEGIN_NAMESPACE
50
51class QGraphicsSceneInsertItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
52{
53public:
54 QGraphicsItem *item;
55
56 void visit(QList<QGraphicsItem *> *items)
57 { items->prepend(item); }
58};
59
60class QGraphicsSceneRemoveItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
61{
62public:
63 QGraphicsItem *item;
64
65 void visit(QList<QGraphicsItem *> *items)
66 { items->removeAll(item); }
67};
68
69class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
70{
71public:
72 QList<QGraphicsItem *> *foundItems;
73
74 void visit(QList<QGraphicsItem *> *items)
75 {
76 for (int i = 0; i < items->size(); ++i) {
77 QGraphicsItem *item = items->at(i);
78 if (!item->d_func()->itemDiscovered && item->isVisible()) {
79 item->d_func()->itemDiscovered = 1;
80 foundItems->prepend(item);
81 }
82 }
83 }
84};
85
86QGraphicsSceneBspTree::QGraphicsSceneBspTree()
87 : leafCnt(0)
88{
89 insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor;
90 removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor;
91 findVisitor = new QGraphicsSceneFindItemBspTreeVisitor;
92}
93
94QGraphicsSceneBspTree::~QGraphicsSceneBspTree()
95{
96 delete insertVisitor;
97 delete removeVisitor;
98 delete findVisitor;
99}
100
101void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth)
102{
103 this->rect = rect;
104 leafCnt = 0;
105 nodes.resize((1 << (depth + 1)) - 1);
106 nodes.fill(Node());
107 leaves.resize(1 << depth);
108 leaves.fill(QList<QGraphicsItem *>());
109
110 initialize(rect, depth, 0);
111}
112
113void QGraphicsSceneBspTree::clear()
114{
115 leafCnt = 0;
116 nodes.clear();
117 leaves.clear();
118}
119
120void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect)
121{
122 insertVisitor->item = item;
123 climbTree(insertVisitor, rect);
124}
125
126void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect)
127{
128 removeVisitor->item = item;
129 climbTree(removeVisitor, rect);
130}
131
132void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items)
133{
134 for (int i = 0; i < leaves.size(); ++i) {
135 QList<QGraphicsItem *> newItemList;
136 const QList<QGraphicsItem *> &oldItemList = leaves[i];
137 for (int j = 0; j < oldItemList.size(); ++j) {
138 QGraphicsItem *item = oldItemList.at(j);
139 if (!items.contains(item))
140 newItemList << item;
141 }
142 leaves[i] = newItemList;
143 }
144}
145
146QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect)
147{
148 QList<QGraphicsItem *> tmp;
149 findVisitor->foundItems = &tmp;
150 climbTree(findVisitor, rect);
151 return tmp;
152}
153
154QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos)
155{
156 QList<QGraphicsItem *> tmp;
157 findVisitor->foundItems = &tmp;
158 climbTree(findVisitor, pos);
159 return tmp;
160}
161
162int QGraphicsSceneBspTree::leafCount() const
163{
164 return leafCnt;
165}
166
167QString QGraphicsSceneBspTree::debug(int index) const
168{
169 const Node *node = &nodes.at(index);
170
171 QString tmp;
172 if (node->type == Node::Leaf) {
173 QRectF rect = rectForIndex(index);
174 if (!leaves[node->leafIndex].isEmpty()) {
175 tmp += QString::fromLatin1("[%1, %2, %3, %4] contains %5 items\n")
176 .arg(rect.left()).arg(rect.top())
177 .arg(rect.width()).arg(rect.height())
178 .arg(leaves[node->leafIndex].size());
179 }
180 } else {
181 if (node->type == Node::Horizontal) {
182 tmp += debug(firstChildIndex(index));
183 tmp += debug(firstChildIndex(index) + 1);
184 } else {
185 tmp += debug(firstChildIndex(index));
186 tmp += debug(firstChildIndex(index) + 1);
187 }
188 }
189
190 return tmp;
191}
192
193void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index)
194{
195 Node *node = &nodes[index];
196 if (index == 0) {
197 node->type = Node::Horizontal;
198 node->offset = rect.center().x();
199 }
200
201 if (depth) {
202 Node::Type type;
203 QRectF rect1, rect2;
204 qreal offset1, offset2;
205
206 if (node->type == Node::Horizontal) {
207 type = Node::Vertical;
208 rect1.setRect(rect.left(), rect.top(), rect.width(), rect.height() / 2);
209 rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rect.height() - rect1.height());
210 offset1 = rect1.center().x();
211 offset2 = rect2.center().x();
212 } else {
213 type = Node::Horizontal;
214 rect1.setRect(rect.left(), rect.top(), rect.width() / 2, rect.height());
215 rect2.setRect(rect1.right(), rect1.top(), rect.width() - rect1.width(), rect1.height());
216 offset1 = rect1.center().y();
217 offset2 = rect2.center().y();
218 }
219
220 int childIndex = firstChildIndex(index);
221
222 Node *child = &nodes[childIndex];
223 child->offset = offset1;
224 child->type = type;
225
226 child = &nodes[childIndex + 1];
227 child->offset = offset2;
228 child->type = type;
229
230 initialize(rect1, depth - 1, childIndex);
231 initialize(rect2, depth - 1, childIndex + 1);
232 } else {
233 node->type = Node::Leaf;
234 node->leafIndex = leafCnt++;
235 }
236}
237
238void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index)
239{
240 if (nodes.isEmpty())
241 return;
242
243 const Node &node = nodes.at(index);
244 int childIndex = firstChildIndex(index);
245
246 switch (node.type) {
247 case Node::Leaf: {
248 visitor->visit(&leaves[node.leafIndex]);
249 break;
250 }
251 case Node::Vertical:
252 if (pos.x() < node.offset) {
253 climbTree(visitor, pos, childIndex);
254 } else {
255 climbTree(visitor, pos, childIndex + 1);
256 }
257 break;
258 case Node::Horizontal:
259 if (pos.y() < node.offset) {
260 climbTree(visitor, pos, childIndex);
261 } else {
262 climbTree(visitor, pos, childIndex + 1);
263 }
264 break;
265 }
266}
267
268void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index)
269{
270 if (nodes.isEmpty())
271 return;
272
273 const Node &node = nodes.at(index);
274 int childIndex = firstChildIndex(index);
275
276 switch (node.type) {
277 case Node::Leaf: {
278 visitor->visit(&leaves[node.leafIndex]);
279 break;
280 }
281 case Node::Vertical:
282 if (rect.left() < node.offset) {
283 climbTree(visitor, rect, childIndex);
284 if (rect.right() >= node.offset)
285 climbTree(visitor, rect, childIndex + 1);
286 } else {
287 climbTree(visitor, rect, childIndex + 1);
288 }
289 break;
290 case Node::Horizontal:
291 int childIndex = firstChildIndex(index);
292 if (rect.top() < node.offset) {
293 climbTree(visitor, rect, childIndex);
294 if (rect.bottom() >= node.offset)
295 climbTree(visitor, rect, childIndex + 1);
296 } else {
297 climbTree(visitor, rect, childIndex + 1);
298 }
299 }
300}
301
302QRectF QGraphicsSceneBspTree::rectForIndex(int index) const
303{
304 if (index <= 0)
305 return rect;
306
307 int parentIdx = parentIndex(index);
308 QRectF rect = rectForIndex(parentIdx);
309 const Node *parent = &nodes.at(parentIdx);
310
311 if (parent->type == Node::Horizontal) {
312 if (index & 1)
313 rect.setRight(parent->offset);
314 else
315 rect.setLeft(parent->offset);
316 } else {
317 if (index & 1)
318 rect.setBottom(parent->offset);
319 else
320 rect.setTop(parent->offset);
321 }
322
323 return rect;
324}
325
326QT_END_NAMESPACE
327
328#endif // QT_NO_GRAPHICSVIEW
Note: See TracBrowser for help on using the repository browser.