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