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