qgraphicsscenebsptreeindex.cpp

Absolute File Name:/home/qt/qt5_coco/qt5/qtbase/src/widgets/graphicsview/qgraphicsscenebsptreeindex.cpp
Source codeSwitch to Preprocessed file
LineSourceCount
1/****************************************************************************-
2**-
3** Copyright (C) 2015 The Qt Company Ltd.-
4** Contact: http://www.qt.io/licensing/-
5**-
6** This file is part of the QtWidgets module of the Qt Toolkit.-
7**-
8** $QT_BEGIN_LICENSE:LGPL21$-
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 http://www.qt.io/terms-conditions. For further-
15** information use the contact form at http://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 2.1 or version 3 as published by the Free-
20** Software Foundation and appearing in the file LICENSE.LGPLv21 and-
21** LICENSE.LGPLv3 included in the packaging of this file. Please review the-
22** following information to ensure the GNU Lesser General Public License-
23** requirements will be met: https://www.gnu.org/licenses/lgpl.html and-
24** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.-
25**-
26** As a special exception, The Qt Company gives you certain additional-
27** rights. These rights are described in The Qt Company LGPL Exception-
28** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.-
29**-
30** $QT_END_LICENSE$-
31**-
32****************************************************************************/-
33-
34/*!-
35 \class QGraphicsSceneBspTreeIndex-
36 \brief The QGraphicsSceneBspTreeIndex class provides an implementation of-
37 a BSP indexing algorithm for discovering items in QGraphicsScene.-
38 \since 4.6-
39 \ingroup graphicsview-api-
40-
41 \internal-
42-
43 QGraphicsSceneBspTreeIndex index use a BSP(Binary Space Partitioning)-
44 implementation to discover items quickly. This implementation is-
45 very efficient for static scenes. It has a depth that you can set.-
46 The depth directly affects performance and memory usage; the latter-
47 growing exponentially with the depth of the tree. With an optimal tree-
48 depth, the index can instantly determine the locality of items, even-
49 for scenes with thousands or millions of items. This also greatly improves-
50 rendering performance.-
51-
52 By default, the depth value is 0, in which case Qt will guess a reasonable-
53 default depth based on the size, location and number of items in the-
54 scene. If these parameters change frequently, however, you may experience-
55 slowdowns as the index retunes the depth internally. You can avoid-
56 potential slowdowns by fixating the tree depth through setting this-
57 property.-
58-
59 The depth of the tree and the size of the scene rectangle decide the-
60 granularity of the scene's partitioning. The size of each scene segment is-
61 determined by the following algorithm:-
62-
63 The BSP tree has an optimal size when each segment contains between 0 and-
64 10 items.-
65-
66 \sa QGraphicsScene, QGraphicsView, QGraphicsSceneIndex-
67*/-
68-
69#include <QtCore/qglobal.h>-
70-
71#ifndef QT_NO_GRAPHICSVIEW-
72-
73#include <private/qgraphicsscene_p.h>-
74#include <private/qgraphicsscenebsptreeindex_p.h>-
75#include <private/qgraphicssceneindex_p.h>-
76-
77#include <QtCore/qmath.h>-
78#include <QtCore/qdebug.h>-
79-
80QT_BEGIN_NAMESPACE-
81-
82static inline int intmaxlog(int n)-
83{-
84 return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);
never executed: return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);
n > 0Description
TRUEnever evaluated
FALSEnever evaluated
0
85}-
86-
87/*!-
88 Constructs a private scene bsp index.-
89*/-
90QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene)-
91 : QGraphicsSceneIndexPrivate(scene),-
92 bspTreeDepth(0),-
93 indexTimerId(0),-
94 restartIndexTimer(false),-
95 regenerateIndex(true),-
96 lastItemCount(0),-
97 purgePending(false),-
98 sortCacheEnabled(false),-
99 updatingSortCache(false)-
100{-
101}
never executed: end of block
0
102-
103-
104/*!-
105 This method will update the BSP index by removing the items from the temporary-
106 unindexed list and add them in the indexedItems list. This will also-
107 update the growingItemsBoundingRect if needed. This will update the BSP-
108 implementation as well.-
109-
110 \internal-
111*/-
112void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex()-
113{-
114 Q_Q(QGraphicsSceneBspTreeIndex);-
115 if (!indexTimerId)
!indexTimerIdDescription
TRUEnever evaluated
FALSEnever evaluated
0
116 return;
never executed: return;
0
117-
118 q->killTimer(indexTimerId);-
119 indexTimerId = 0;-
120-
121 purgeRemovedItems();-
122-
123 // Add unindexedItems to indexedItems-
124 for (int i = 0; i < unindexedItems.size(); ++i) {
i < unindexedItems.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
125 if (QGraphicsItem *item = unindexedItems.at(i)) {
QGraphicsItem ...xedItems.at(i)Description
TRUEnever evaluated
FALSEnever evaluated
0
126 Q_ASSERT(!item->d_ptr->itemDiscovered);-
127 if (!freeItemIndexes.isEmpty()) {
!freeItemIndexes.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
128 int freeIndex = freeItemIndexes.takeFirst();-
129 item->d_func()->index = freeIndex;-
130 indexedItems[freeIndex] = item;-
131 } else {
never executed: end of block
0
132 item->d_func()->index = indexedItems.size();-
133 indexedItems << item;-
134 }
never executed: end of block
0
135 }-
136 }
never executed: end of block
0
137-
138 // Determine whether we should regenerate the BSP tree.-
139 if (bspTreeDepth == 0) {
bspTreeDepth == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
140 int oldDepth = intmaxlog(lastItemCount);-
141 bspTreeDepth = intmaxlog(indexedItems.size());-
142 static const int slack = 100;-
143 if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - indexedItems.size()) > slack)) {
bsp.leafCount() == 0Description
TRUEnever evaluated
FALSEnever evaluated
oldDepth != bspTreeDepthDescription
TRUEnever evaluated
FALSEnever evaluated
qAbs(lastItemC...ize()) > slackDescription
TRUEnever evaluated
FALSEnever evaluated
0
144 // ### Crude algorithm.-
145 regenerateIndex = true;-
146 }
never executed: end of block
0
147 }
never executed: end of block
0
148-
149 // Regenerate the tree.-
150 if (regenerateIndex) {
regenerateIndexDescription
TRUEnever evaluated
FALSEnever evaluated
0
151 regenerateIndex = false;-
152 bsp.initialize(sceneRect, bspTreeDepth);-
153 unindexedItems = indexedItems;-
154 lastItemCount = indexedItems.size();-
155 }
never executed: end of block
0
156-
157 // Insert all unindexed items into the tree.-
158 for (int i = 0; i < unindexedItems.size(); ++i) {
i < unindexedItems.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
159 if (QGraphicsItem *item = unindexedItems.at(i)) {
QGraphicsItem ...xedItems.at(i)Description
TRUEnever evaluated
FALSEnever evaluated
0
160 if (item->d_ptr->itemIsUntransformable()) {
item->d_ptr->i...ransformable()Description
TRUEnever evaluated
FALSEnever evaluated
0
161 untransformableItems << item;-
162 continue;
never executed: continue;
0
163 }-
164 if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren
item->d_ptr->a...rClipsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
165 || item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren)
item->d_ptr->a...ntainsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
166 continue;
never executed: continue;
0
167-
168 bsp.insertItem(item, item->d_ptr->sceneEffectiveBoundingRect());-
169 }
never executed: end of block
0
170 }
never executed: end of block
0
171 unindexedItems.clear();-
172}
never executed: end of block
0
173-
174-
175/*!-
176 \internal-
177-
178 Removes stale pointers from all data structures.-
179*/-
180void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems()-
181{-
182 if (!purgePending && removedItems.isEmpty())
!purgePendingDescription
TRUEnever evaluated
FALSEnever evaluated
removedItems.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
183 return;
never executed: return;
0
184-
185 // Remove stale items from the BSP tree.-
186 bsp.removeItems(removedItems);-
187 // Purge this list.-
188 removedItems.clear();-
189 freeItemIndexes.clear();-
190 for (int i = 0; i < indexedItems.size(); ++i) {
i < indexedItems.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
191 if (!indexedItems.at(i))
!indexedItems.at(i)Description
TRUEnever evaluated
FALSEnever evaluated
0
192 freeItemIndexes << i;
never executed: freeItemIndexes << i;
0
193 }
never executed: end of block
0
194 purgePending = false;-
195}
never executed: end of block
0
196-
197/*!-
198 \internal-
199-
200 Starts or restarts the timer used for reindexing unindexed items.-
201*/-
202void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer(int interval)-
203{-
204 Q_Q(QGraphicsSceneBspTreeIndex);-
205 if (indexTimerId) {
indexTimerIdDescription
TRUEnever evaluated
FALSEnever evaluated
0
206 restartIndexTimer = true;-
207 } else {
never executed: end of block
0
208 indexTimerId = q->startTimer(interval);-
209 }
never executed: end of block
0
210}-
211-
212/*!-
213 \internal-
214*/-
215void QGraphicsSceneBspTreeIndexPrivate::resetIndex()-
216{-
217 purgeRemovedItems();-
218 for (int i = 0; i < indexedItems.size(); ++i) {
i < indexedItems.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
219 if (QGraphicsItem *item = indexedItems.at(i)) {
QGraphicsItem ...xedItems.at(i)Description
TRUEnever evaluated
FALSEnever evaluated
0
220 item->d_ptr->index = -1;-
221 Q_ASSERT(!item->d_ptr->itemDiscovered);-
222 unindexedItems << item;-
223 }
never executed: end of block
0
224 }
never executed: end of block
0
225 indexedItems.clear();-
226 freeItemIndexes.clear();-
227 untransformableItems.clear();-
228 regenerateIndex = true;-
229 startIndexTimer();-
230}
never executed: end of block
0
231-
232/*!-
233 \internal-
234*/-
235void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder)-
236{-
237 if (!item->d_ptr->children.isEmpty()) {
!item->d_ptr->...dren.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
238 QList<QGraphicsItem *> childList = item->d_ptr->children;-
239 std::sort(childList.begin(), childList.end(), qt_closestLeaf);-
240 for (int i = 0; i < childList.size(); ++i) {
i < childList.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
241 QGraphicsItem *item = childList.at(i);-
242 if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))
!(item->flags(...sBehindParent)Description
TRUEnever evaluated
FALSEnever evaluated
0
243 climbTree(childList.at(i), stackingOrder);
never executed: climbTree(childList.at(i), stackingOrder);
0
244 }
never executed: end of block
0
245 item->d_ptr->globalStackingOrder = (*stackingOrder)++;-
246 for (int i = 0; i < childList.size(); ++i) {
i < childList.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
247 QGraphicsItem *item = childList.at(i);-
248 if (item->flags() & QGraphicsItem::ItemStacksBehindParent)
item->flags() ...ksBehindParentDescription
TRUEnever evaluated
FALSEnever evaluated
0
249 climbTree(childList.at(i), stackingOrder);
never executed: climbTree(childList.at(i), stackingOrder);
0
250 }
never executed: end of block
0
251 } else {
never executed: end of block
0
252 item->d_ptr->globalStackingOrder = (*stackingOrder)++;-
253 }
never executed: end of block
0
254}-
255-
256/*!-
257 \internal-
258*/-
259void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache()-
260{-
261 Q_Q(QGraphicsSceneBspTreeIndex);-
262 _q_updateIndex();-
263-
264 if (!sortCacheEnabled || !updatingSortCache)
!sortCacheEnabledDescription
TRUEnever evaluated
FALSEnever evaluated
!updatingSortCacheDescription
TRUEnever evaluated
FALSEnever evaluated
0
265 return;
never executed: return;
0
266-
267 updatingSortCache = false;-
268 int stackingOrder = 0;-
269-
270 QList<QGraphicsItem *> topLevels;-
271 const QList<QGraphicsItem *> items = q->items();-
272 for (int i = 0; i < items.size(); ++i) {
i < items.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
273 QGraphicsItem *item = items.at(i);-
274 if (item && !item->d_ptr->parent)
itemDescription
TRUEnever evaluated
FALSEnever evaluated
!item->d_ptr->parentDescription
TRUEnever evaluated
FALSEnever evaluated
0
275 topLevels << item;
never executed: topLevels << item;
0
276 }
never executed: end of block
0
277-
278 std::sort(topLevels.begin(), topLevels.end(), qt_closestLeaf);-
279 for (int i = 0; i < topLevels.size(); ++i)
i < topLevels.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
280 climbTree(topLevels.at(i), &stackingOrder);
never executed: climbTree(topLevels.at(i), &stackingOrder);
0
281}
never executed: end of block
0
282-
283/*!-
284 \internal-
285*/-
286void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache()-
287{-
288 Q_Q(QGraphicsSceneBspTreeIndex);-
289 if (!sortCacheEnabled || updatingSortCache)
!sortCacheEnabledDescription
TRUEnever evaluated
FALSEnever evaluated
updatingSortCacheDescription
TRUEnever evaluated
FALSEnever evaluated
0
290 return;
never executed: return;
0
291-
292 updatingSortCache = true;-
293 QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);-
294}
never executed: end of block
0
295-
296void QGraphicsSceneBspTreeIndexPrivate::addItem(QGraphicsItem *item, bool recursive)-
297{-
298 if (!item)
!itemDescription
TRUEnever evaluated
FALSEnever evaluated
0
299 return;
never executed: return;
0
300-
301 // Prevent reusing a recently deleted pointer: purge all removed item from our lists.-
302 purgeRemovedItems();-
303-
304 // Invalidate any sort caching; arrival of a new item means we need to resort.-
305 // Update the scene's sort cache settings.-
306 item->d_ptr->globalStackingOrder = -1;-
307 invalidateSortCache();-
308-
309 // Indexing requires sceneBoundingRect(), but because \a item might-
310 // not be completely constructed at this point, we need to store it in-
311 // a temporary list and schedule an indexing for later.-
312 if (item->d_ptr->index == -1) {
item->d_ptr->index == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
313 Q_ASSERT(!unindexedItems.contains(item));-
314 unindexedItems << item;-
315 startIndexTimer(0);-
316 } else {
never executed: end of block
0
317 Q_ASSERT(indexedItems.contains(item));-
318 qWarning("QGraphicsSceneBspTreeIndex::addItem: item has already been added to this BSP");-
319 }
never executed: end of block
0
320-
321 if (recursive) {
recursiveDescription
TRUEnever evaluated
FALSEnever evaluated
0
322 for (int i = 0; i < item->d_ptr->children.size(); ++i)
i < item->d_pt...hildren.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
323 addItem(item->d_ptr->children.at(i), recursive);
never executed: addItem(item->d_ptr->children.at(i), recursive);
0
324 }
never executed: end of block
0
325}
never executed: end of block
0
326-
327void QGraphicsSceneBspTreeIndexPrivate::removeItem(QGraphicsItem *item, bool recursive,-
328 bool moveToUnindexedItems)-
329{-
330 if (!item)
!itemDescription
TRUEnever evaluated
FALSEnever evaluated
0
331 return;
never executed: return;
0
332-
333 if (item->d_ptr->index != -1) {
item->d_ptr->index != -1Description
TRUEnever evaluated
FALSEnever evaluated
0
334 Q_ASSERT(item->d_ptr->index < indexedItems.size());-
335 Q_ASSERT(indexedItems.at(item->d_ptr->index) == item);-
336 Q_ASSERT(!item->d_ptr->itemDiscovered);-
337 freeItemIndexes << item->d_ptr->index;-
338 indexedItems[item->d_ptr->index] = 0;-
339 item->d_ptr->index = -1;-
340-
341 if (item->d_ptr->itemIsUntransformable()) {
item->d_ptr->i...ransformable()Description
TRUEnever evaluated
FALSEnever evaluated
0
342 untransformableItems.removeOne(item);-
343 } else if (item->d_ptr->inDestructor) {
never executed: end of block
item->d_ptr->inDestructorDescription
TRUEnever evaluated
FALSEnever evaluated
0
344 // Avoid virtual function calls from the destructor.-
345 purgePending = true;-
346 removedItems << item;-
347 } else if (!(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren
never executed: end of block
item->d_ptr->a...rClipsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
348 || item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren)) {
item->d_ptr->a...ntainsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
349 bsp.removeItem(item, item->d_ptr->sceneEffectiveBoundingRect());-
350 }
never executed: end of block
0
351 } else {
never executed: end of block
0
352 unindexedItems.removeOne(item);-
353 }
never executed: end of block
0
354 invalidateSortCache(); // ### Only do this when removing from BSP?-
355-
356 Q_ASSERT(item->d_ptr->index == -1);-
357 Q_ASSERT(!indexedItems.contains(item));-
358 Q_ASSERT(!unindexedItems.contains(item));-
359 Q_ASSERT(!untransformableItems.contains(item));-
360-
361 if (moveToUnindexedItems)
moveToUnindexedItemsDescription
TRUEnever evaluated
FALSEnever evaluated
0
362 addItem(item);
never executed: addItem(item);
0
363-
364 if (recursive) {
recursiveDescription
TRUEnever evaluated
FALSEnever evaluated
0
365 for (int i = 0; i < item->d_ptr->children.size(); ++i)
i < item->d_pt...hildren.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
366 removeItem(item->d_ptr->children.at(i), recursive, moveToUnindexedItems);
never executed: removeItem(item->d_ptr->children.at(i), recursive, moveToUnindexedItems);
0
367 }
never executed: end of block
0
368}
never executed: end of block
0
369-
370QList<QGraphicsItem *> QGraphicsSceneBspTreeIndexPrivate::estimateItems(const QRectF &rect, Qt::SortOrder order,-
371 bool onlyTopLevelItems)-
372{-
373 Q_Q(QGraphicsSceneBspTreeIndex);-
374 if (onlyTopLevelItems && rect.isNull())
onlyTopLevelItemsDescription
TRUEnever evaluated
FALSEnever evaluated
rect.isNull()Description
TRUEnever evaluated
FALSEnever evaluated
0
375 return q->QGraphicsSceneIndex::estimateTopLevelItems(rect, order);
never executed: return q->QGraphicsSceneIndex::estimateTopLevelItems(rect, order);
0
376-
377 purgeRemovedItems();-
378 _q_updateSortCache();-
379 Q_ASSERT(unindexedItems.isEmpty());-
380-
381 QList<QGraphicsItem *> rectItems = bsp.items(rect, onlyTopLevelItems);-
382 if (onlyTopLevelItems) {
onlyTopLevelItemsDescription
TRUEnever evaluated
FALSEnever evaluated
0
383 for (int i = 0; i < untransformableItems.size(); ++i) {
i < untransfor...leItems.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
384 QGraphicsItem *item = untransformableItems.at(i);-
385 if (!item->d_ptr->parent) {
!item->d_ptr->parentDescription
TRUEnever evaluated
FALSEnever evaluated
0
386 rectItems << item;-
387 } else {
never executed: end of block
0
388 item = item->topLevelItem();-
389 if (!rectItems.contains(item))
!rectItems.contains(item)Description
TRUEnever evaluated
FALSEnever evaluated
0
390 rectItems << item;
never executed: rectItems << item;
0
391 }
never executed: end of block
0
392 }-
393 } else {
never executed: end of block
0
394 rectItems += untransformableItems;-
395 }
never executed: end of block
0
396-
397 sortItems(&rectItems, order, sortCacheEnabled, onlyTopLevelItems);-
398 return rectItems;
never executed: return rectItems;
0
399}-
400-
401/*!-
402 Sort a list of \a itemList in a specific \a order and use the cache if requested.-
403-
404 \internal-
405*/-
406void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,-
407 bool sortCacheEnabled, bool onlyTopLevelItems)-
408{-
409 if (order == Qt::SortOrder(-1))
order == Qt::SortOrder(-1)Description
TRUEnever evaluated
FALSEnever evaluated
0
410 return;
never executed: return;
0
411-
412 if (onlyTopLevelItems) {
onlyTopLevelItemsDescription
TRUEnever evaluated
FALSEnever evaluated
0
413 if (order == Qt::DescendingOrder)
order == Qt::DescendingOrderDescription
TRUEnever evaluated
FALSEnever evaluated
0
414 std::sort(itemList->begin(), itemList->end(), qt_closestLeaf);
never executed: std::sort(itemList->begin(), itemList->end(), qt_closestLeaf);
0
415 else if (order == Qt::AscendingOrder)
order == Qt::AscendingOrderDescription
TRUEnever evaluated
FALSEnever evaluated
0
416 std::sort(itemList->begin(), itemList->end(), qt_notclosestLeaf);
never executed: std::sort(itemList->begin(), itemList->end(), qt_notclosestLeaf);
0
417 return;
never executed: return;
0
418 }-
419-
420 if (sortCacheEnabled) {
sortCacheEnabledDescription
TRUEnever evaluated
FALSEnever evaluated
0
421 if (order == Qt::DescendingOrder) {
order == Qt::DescendingOrderDescription
TRUEnever evaluated
FALSEnever evaluated
0
422 std::sort(itemList->begin(), itemList->end(), closestItemFirst_withCache);-
423 } else if (order == Qt::AscendingOrder) {
never executed: end of block
order == Qt::AscendingOrderDescription
TRUEnever evaluated
FALSEnever evaluated
0
424 std::sort(itemList->begin(), itemList->end(), closestItemLast_withCache);-
425 }
never executed: end of block
0
426 } else {
never executed: end of block
0
427 if (order == Qt::DescendingOrder) {
order == Qt::DescendingOrderDescription
TRUEnever evaluated
FALSEnever evaluated
0
428 std::sort(itemList->begin(), itemList->end(), qt_closestItemFirst);-
429 } else if (order == Qt::AscendingOrder) {
never executed: end of block
order == Qt::AscendingOrderDescription
TRUEnever evaluated
FALSEnever evaluated
0
430 std::sort(itemList->begin(), itemList->end(), qt_closestItemLast);-
431 }
never executed: end of block
0
432 }
never executed: end of block
0
433}-
434-
435/*!-
436 Constructs a BSP scene index for the given \a scene.-
437*/-
438QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)-
439 : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene)-
440{-
441-
442}
never executed: end of block
0
443-
444QGraphicsSceneBspTreeIndex::~QGraphicsSceneBspTreeIndex()-
445{-
446 Q_D(QGraphicsSceneBspTreeIndex);-
447 for (int i = 0; i < d->indexedItems.size(); ++i) {
i < d->indexedItems.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
448 // Ensure item bits are reset properly.-
449 if (QGraphicsItem *item = d->indexedItems.at(i)) {
QGraphicsItem ...xedItems.at(i)Description
TRUEnever evaluated
FALSEnever evaluated
0
450 Q_ASSERT(!item->d_ptr->itemDiscovered);-
451 item->d_ptr->index = -1;-
452 }
never executed: end of block
0
453 }
never executed: end of block
0
454}
never executed: end of block
0
455-
456/*!-
457 \internal-
458 Clear the all the BSP index.-
459*/-
460void QGraphicsSceneBspTreeIndex::clear()-
461{-
462 Q_D(QGraphicsSceneBspTreeIndex);-
463 d->bsp.clear();-
464 d->lastItemCount = 0;-
465 d->freeItemIndexes.clear();-
466 for (int i = 0; i < d->indexedItems.size(); ++i) {
i < d->indexedItems.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
467 // Ensure item bits are reset properly.-
468 if (QGraphicsItem *item = d->indexedItems.at(i)) {
QGraphicsItem ...xedItems.at(i)Description
TRUEnever evaluated
FALSEnever evaluated
0
469 Q_ASSERT(!item->d_ptr->itemDiscovered);-
470 item->d_ptr->index = -1;-
471 }
never executed: end of block
0
472 }
never executed: end of block
0
473 d->indexedItems.clear();-
474 d->unindexedItems.clear();-
475 d->untransformableItems.clear();-
476 d->regenerateIndex = true;-
477}
never executed: end of block
0
478-
479/*!-
480 Add the \a item into the BSP index.-
481*/-
482void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item)-
483{-
484 Q_D(QGraphicsSceneBspTreeIndex);-
485 d->addItem(item);-
486}
never executed: end of block
0
487-
488/*!-
489 Remove the \a item from the BSP index.-
490*/-
491void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item)-
492{-
493 Q_D(QGraphicsSceneBspTreeIndex);-
494 d->removeItem(item);-
495}
never executed: end of block
0
496-
497/*!-
498 \internal-
499 Update the BSP when the \a item 's bounding rect has changed.-
500*/-
501void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item)-
502{-
503 if (!item)
!itemDescription
TRUEnever evaluated
FALSEnever evaluated
0
504 return;
never executed: return;
0
505-
506 if (item->d_ptr->index == -1 || item->d_ptr->itemIsUntransformable()
item->d_ptr->index == -1Description
TRUEnever evaluated
FALSEnever evaluated
item->d_ptr->i...ransformable()Description
TRUEnever evaluated
FALSEnever evaluated
0
507 || (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren
item->d_ptr->a...rClipsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
508 || item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren)) {
item->d_ptr->a...ntainsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
509 return; // Item is not in BSP tree; nothing to do.
never executed: return;
0
510 }-
511-
512 Q_D(QGraphicsSceneBspTreeIndex);-
513 QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);-
514 d->removeItem(thatItem, /*recursive=*/false, /*moveToUnindexedItems=*/true);-
515 for (int i = 0; i < item->d_ptr->children.size(); ++i) // ### Do we really need this?
i < item->d_pt...hildren.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
516 prepareBoundingRectChange(item->d_ptr->children.at(i));
never executed: prepareBoundingRectChange(item->d_ptr->children.at(i));
0
517}
never executed: end of block
0
518-
519/*!-
520 Returns an estimation visible items that are either inside or-
521 intersect with the specified \a rect and return a list sorted using \a order.-
522-
523 \a deviceTransform is the transformation apply to the view.-
524-
525*/-
526QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order) const-
527{-
528 Q_D(const QGraphicsSceneBspTreeIndex);-
529 return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order);
never executed: return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order);
0
530}-
531-
532QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const-
533{-
534 Q_D(const QGraphicsSceneBspTreeIndex);-
535 return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order, /*onlyTopLevels=*/true);
never executed: return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order, true);
0
536}-
537-
538/*!-
539 \fn QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order = Qt::DescendingOrder) const;-
540-
541 Return all items in the BSP index and sort them using \a order.-
542*/-
543QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) const-
544{-
545 Q_D(const QGraphicsSceneBspTreeIndex);-
546 const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems();-
547 QList<QGraphicsItem *> itemList;-
548-
549 // If freeItemIndexes is empty, we know there are no holes in indexedItems and-
550 // unindexedItems.-
551 if (d->freeItemIndexes.isEmpty()) {
d->freeItemIndexes.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
552 if (d->unindexedItems.isEmpty()) {
d->unindexedItems.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
553 itemList = d->indexedItems;-
554 } else {
never executed: end of block
0
555 itemList = d->indexedItems + d->unindexedItems;-
556 }
never executed: end of block
0
557 } else {-
558 // Rebuild the list of items to avoid holes. ### We could also just-
559 // compress the item lists at this point.-
560 foreach (QGraphicsItem *item, d->indexedItems + d->unindexedItems) {-
561 if (item)
itemDescription
TRUEnever evaluated
FALSEnever evaluated
0
562 itemList << item;
never executed: itemList << item;
0
563 }
never executed: end of block
0
564 }
never executed: end of block
0
565 d->sortItems(&itemList, order, d->sortCacheEnabled);-
566 return itemList;
never executed: return itemList;
0
567}-
568-
569/*!-
570 \property QGraphicsSceneBspTreeIndex::bspTreeDepth-
571 \brief the depth of the BSP index tree-
572 \since 4.6-
573-
574 This value determines the depth of BSP tree. The depth-
575 directly affects performance and memory usage; the latter-
576 growing exponentially with the depth of the tree. With an optimal tree-
577 depth, the index can instantly determine the locality of items, even-
578 for scenes with thousands or millions of items. This also greatly improves-
579 rendering performance.-
580-
581 By default, the value is 0, in which case Qt will guess a reasonable-
582 default depth based on the size, location and number of items in the-
583 scene. If these parameters change frequently, however, you may experience-
584 slowdowns as the index retunes the depth internally. You can avoid-
585 potential slowdowns by fixating the tree depth through setting this-
586 property.-
587-
588 The depth of the tree and the size of the scene rectangle decide the-
589 granularity of the scene's partitioning. The size of each scene segment is-
590 determined by the following algorithm:-
591-
592 The BSP tree has an optimal size when each segment contains between 0 and-
593 10 items.-
594-
595*/-
596int QGraphicsSceneBspTreeIndex::bspTreeDepth() const-
597{-
598 Q_D(const QGraphicsSceneBspTreeIndex);-
599 return d->bspTreeDepth;
never executed: return d->bspTreeDepth;
0
600}-
601-
602void QGraphicsSceneBspTreeIndex::setBspTreeDepth(int depth)-
603{-
604 Q_D(QGraphicsSceneBspTreeIndex);-
605 if (d->bspTreeDepth == depth)
d->bspTreeDepth == depthDescription
TRUEnever evaluated
FALSEnever evaluated
0
606 return;
never executed: return;
0
607 d->bspTreeDepth = depth;-
608 d->resetIndex();-
609}
never executed: end of block
0
610-
611/*!-
612 \internal-
613-
614 This method react to the \a rect change of the scene and-
615 reset the BSP tree index.-
616*/-
617void QGraphicsSceneBspTreeIndex::updateSceneRect(const QRectF &rect)-
618{-
619 Q_D(QGraphicsSceneBspTreeIndex);-
620 d->sceneRect = rect;-
621 d->resetIndex();-
622}
never executed: end of block
0
623-
624/*!-
625 \internal-
626-
627 This method react to the \a change of the \a item and use the \a value to-
628 update the BSP tree if necessary.-
629*/-
630void QGraphicsSceneBspTreeIndex::itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value)-
631{-
632 Q_D(QGraphicsSceneBspTreeIndex);-
633 switch (change) {-
634 case QGraphicsItem::ItemFlagsChange: {
never executed: case QGraphicsItem::ItemFlagsChange:
0
635 // Handle ItemIgnoresTransformations-
636 QGraphicsItem::GraphicsItemFlags newFlags = *static_cast<const QGraphicsItem::GraphicsItemFlags *>(value);-
637 bool ignoredTransform = item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations;-
638 bool willIgnoreTransform = newFlags & QGraphicsItem::ItemIgnoresTransformations;-
639 bool clipsChildren = item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape
item->d_ptr->f...hildrenToShapeDescription
TRUEnever evaluated
FALSEnever evaluated
0
640 || item->d_ptr->flags & QGraphicsItem::ItemContainsChildrenInShape;
item->d_ptr->f...hildrenInShapeDescription
TRUEnever evaluated
FALSEnever evaluated
0
641 bool willClipChildren = newFlags & QGraphicsItem::ItemClipsChildrenToShape
newFlags & QGr...hildrenToShapeDescription
TRUEnever evaluated
FALSEnever evaluated
0
642 || newFlags & QGraphicsItem::ItemContainsChildrenInShape;
newFlags & QGr...hildrenInShapeDescription
TRUEnever evaluated
FALSEnever evaluated
0
643 if ((ignoredTransform != willIgnoreTransform) || (clipsChildren != willClipChildren)) {
(ignoredTransf...noreTransform)Description
TRUEnever evaluated
FALSEnever evaluated
(clipsChildren...lClipChildren)Description
TRUEnever evaluated
FALSEnever evaluated
0
644 QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);-
645 // Remove item and its descendants from the index and append-
646 // them to the list of unindexed items. Then, when the index-
647 // is updated, they will be put into the bsp-tree or the list-
648 // of untransformable items.-
649 d->removeItem(thatItem, /*recursive=*/true, /*moveToUnidexedItems=*/true);-
650 }
never executed: end of block
0
651 break;
never executed: break;
0
652 }-
653 case QGraphicsItem::ItemZValueChange:
never executed: case QGraphicsItem::ItemZValueChange:
0
654 d->invalidateSortCache();-
655 break;
never executed: break;
0
656 case QGraphicsItem::ItemParentChange: {
never executed: case QGraphicsItem::ItemParentChange:
0
657 d->invalidateSortCache();-
658 // Handle ItemIgnoresTransformations-
659 const QGraphicsItem *newParent = static_cast<const QGraphicsItem *>(value);-
660 bool ignoredTransform = item->d_ptr->itemIsUntransformable();-
661 bool willIgnoreTransform = (item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations)
(item->d_ptr->...ansformations)Description
TRUEnever evaluated
FALSEnever evaluated
0
662 || (newParent && newParent->d_ptr->itemIsUntransformable());
newParentDescription
TRUEnever evaluated
FALSEnever evaluated
newParent->d_p...ransformable()Description
TRUEnever evaluated
FALSEnever evaluated
0
663 bool ancestorClippedChildren = item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren
item->d_ptr->a...rClipsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
664 || item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren;
item->d_ptr->a...ntainsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
665 bool ancestorWillClipChildren = newParent
newParentDescription
TRUEnever evaluated
FALSEnever evaluated
0
666 && ((newParent->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape
newParent->d_p...hildrenToShapeDescription
TRUEnever evaluated
FALSEnever evaluated
0
667 || newParent->d_ptr->flags & QGraphicsItem::ItemContainsChildrenInShape)
newParent->d_p...hildrenInShapeDescription
TRUEnever evaluated
FALSEnever evaluated
0
668 || (newParent->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren
newParent->d_p...rClipsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
669 || newParent->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren));
newParent->d_p...ntainsChildrenDescription
TRUEnever evaluated
FALSEnever evaluated
0
670 if ((ignoredTransform != willIgnoreTransform) || (ancestorClippedChildren != ancestorWillClipChildren)) {
(ignoredTransf...noreTransform)Description
TRUEnever evaluated
FALSEnever evaluated
(ancestorClipp...lClipChildren)Description
TRUEnever evaluated
FALSEnever evaluated
0
671 QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);-
672 // Remove item and its descendants from the index and append-
673 // them to the list of unindexed items. Then, when the index-
674 // is updated, they will be put into the bsp-tree or the list-
675 // of untransformable items.-
676 d->removeItem(thatItem, /*recursive=*/true, /*moveToUnidexedItems=*/true);-
677 }
never executed: end of block
0
678 break;
never executed: break;
0
679 }-
680 default:
never executed: default:
0
681 break;
never executed: break;
0
682 }-
683}-
684/*!-
685 \reimp-
686-
687 Used to catch the timer event.-
688-
689 \internal-
690*/-
691bool QGraphicsSceneBspTreeIndex::event(QEvent *event)-
692{-
693 Q_D(QGraphicsSceneBspTreeIndex);-
694 if (event->type() == QEvent::Timer) {
event->type() == QEvent::TimerDescription
TRUEnever evaluated
FALSEnever evaluated
0
695 if (d->indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == d->indexTimerId) {
d->indexTimerIdDescription
TRUEnever evaluated
FALSEnever evaluated
static_cast<QT...->indexTimerIdDescription
TRUEnever evaluated
FALSEnever evaluated
0
696 if (d->restartIndexTimer) {
d->restartIndexTimerDescription
TRUEnever evaluated
FALSEnever evaluated
0
697 d->restartIndexTimer = false;-
698 } else {
never executed: end of block
0
699 // this call will kill the timer-
700 d->_q_updateIndex();-
701 }
never executed: end of block
0
702 }-
703 }
never executed: end of block
0
704 return QObject::event(event);
never executed: return QObject::event(event);
0
705}-
706-
707QT_END_NAMESPACE-
708-
709#include "moc_qgraphicsscenebsptreeindex_p.cpp"-
710-
711#endif // QT_NO_GRAPHICSVIEW-
712-
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9