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

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