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

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