1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://www.qt.io/licensing/
5 **
6 ** This file is part of the QtGui 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 http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 or version 3 as published by the Free
20 ** Software Foundation and appearing in the file LICENSE.LGPLv21 and
21 ** LICENSE.LGPLv3 included in the packaging of this file. Please review the
22 ** following information to ensure the GNU Lesser General Public License
23 ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
24 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
25 **
26 ** As a special exception, The Qt Company gives you certain additional
27 ** rights. These rights are described in The Qt Company LGPL Exception
28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 **
30 ** GNU General Public License Usage
31 ** Alternatively, this file may be used under the terms of the GNU
32 ** General Public License version 3.0 as published by the Free Software
33 ** Foundation and appearing in the file LICENSE.GPL included in the
34 ** packaging of this file. Please review the following information to
35 ** ensure the GNU General Public License version 3.0 requirements will be
36 ** met: http://www.gnu.org/copyleft/gpl.html.
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41
42 /*!
43 \class QGraphicsSceneBspTreeIndex
44 \brief The QGraphicsSceneBspTreeIndex class provides an implementation of
45 a BSP indexing algorithm for discovering items in QGraphicsScene.
46 \since 4.6
47 \ingroup graphicsview-api
48
49 \internal
50
51 QGraphicsSceneBspTreeIndex index use a BSP(Binary Space Partitioning)
52 implementation to discover items quickly. This implementation is
53 very efficient for static scenes. It has a depth that you can set.
54 The depth directly affects performance and memory usage; the latter
55 growing exponentially with the depth of the tree. With an optimal tree
56 depth, the index can instantly determine the locality of items, even
57 for scenes with thousands or millions of items. This also greatly improves
58 rendering performance.
59
60 By default, the depth value is 0, in which case Qt will guess a reasonable
61 default depth based on the size, location and number of items in the
62 scene. If these parameters change frequently, however, you may experience
63 slowdowns as the index retunes the depth internally. You can avoid
64 potential slowdowns by fixating the tree depth through setting this
65 property.
66
67 The depth of the tree and the size of the scene rectangle decide the
68 granularity of the scene's partitioning. The size of each scene segment is
69 determined by the following algorithm:
70
71 The BSP tree has an optimal size when each segment contains between 0 and
72 10 items.
73
74 \sa QGraphicsScene, QGraphicsView, QGraphicsSceneIndex
75 */
76
77 #include <QtCore/qglobal.h>
78
79 #ifndef QT_NO_GRAPHICSVIEW
80
81 #include <private/qgraphicsscene_p.h>
82 #include <private/qgraphicsscenebsptreeindex_p.h>
83 #include <private/qgraphicssceneindex_p.h>
84
85 #include <QtCore/qmath.h>
86 #include <QtCore/qdebug.h>
87
88 QT_BEGIN_NAMESPACE
89
intmaxlog(int n)90 static inline int intmaxlog(int n)
91 {
92 return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);
93 }
94
95 /*!
96 Constructs a private scene bsp index.
97 */
QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene * scene)98 QGraphicsSceneBspTreeIndexPrivate::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 }
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 */
_q_updateIndex()120 void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex()
121 {
122 Q_Q(QGraphicsSceneBspTreeIndex);
123 if (!indexTimerId)
124 return;
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) {
133 if (QGraphicsItem *item = unindexedItems.at(i)) {
134 Q_ASSERT(!item->d_ptr->itemDiscovered);
135 if (!freeItemIndexes.isEmpty()) {
136 int freeIndex = freeItemIndexes.takeFirst();
137 item->d_func()->index = freeIndex;
138 indexedItems[freeIndex] = item;
139 } else {
140 item->d_func()->index = indexedItems.size();
141 indexedItems << item;
142 }
143 }
144 }
145
146 // Determine whether we should regenerate the BSP tree.
147 if (bspTreeDepth == 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)) {
152 // ### Crude algorithm.
153 regenerateIndex = true;
154 }
155 }
156
157 // Regenerate the tree.
158 if (regenerateIndex) {
159 regenerateIndex = false;
160 bsp.initialize(sceneRect, bspTreeDepth);
161 unindexedItems = indexedItems;
162 lastItemCount = indexedItems.size();
163 }
164
165 // Insert all unindexed items into the tree.
166 for (int i = 0; i < unindexedItems.size(); ++i) {
167 if (QGraphicsItem *item = unindexedItems.at(i)) {
168 if (item->d_ptr->itemIsUntransformable()) {
169 untransformableItems << item;
170 continue;
171 }
172 if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)
173 continue;
174
175 bsp.insertItem(item, item->d_ptr->sceneEffectiveBoundingRect());
176 }
177 }
178 unindexedItems.clear();
179 }
180
181
182 /*!
183 \internal
184
185 Removes stale pointers from all data structures.
186 */
purgeRemovedItems()187 void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems()
188 {
189 if (!purgePending && removedItems.isEmpty())
190 return;
191
192 // Remove stale items from the BSP tree.
193 bsp.removeItems(removedItems);
194 // Purge this list.
195 removedItems.clear();
196 freeItemIndexes.clear();
197 for (int i = 0; i < indexedItems.size(); ++i) {
198 if (!indexedItems.at(i))
199 freeItemIndexes << i;
200 }
201 purgePending = false;
202 }
203
204 /*!
205 \internal
206
207 Starts or restarts the timer used for reindexing unindexed items.
208 */
startIndexTimer(int interval)209 void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer(int interval)
210 {
211 Q_Q(QGraphicsSceneBspTreeIndex);
212 if (indexTimerId) {
213 restartIndexTimer = true;
214 } else {
215 indexTimerId = q->startTimer(interval);
216 }
217 }
218
219 /*!
220 \internal
221 */
resetIndex()222 void QGraphicsSceneBspTreeIndexPrivate::resetIndex()
223 {
224 purgeRemovedItems();
225 for (int i = 0; i < indexedItems.size(); ++i) {
226 if (QGraphicsItem *item = indexedItems.at(i)) {
227 item->d_ptr->index = -1;
228 Q_ASSERT(!item->d_ptr->itemDiscovered);
229 unindexedItems << item;
230 }
231 }
232 indexedItems.clear();
233 freeItemIndexes.clear();
234 untransformableItems.clear();
235 regenerateIndex = true;
236 startIndexTimer();
237 }
238
239 /*!
240 \internal
241 */
climbTree(QGraphicsItem * item,int * stackingOrder)242 void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder)
243 {
244 if (!item->d_ptr->children.isEmpty()) {
245 QList<QGraphicsItem *> childList = item->d_ptr->children;
246 qSort(childList.begin(), childList.end(), qt_closestLeaf);
247 for (int i = 0; i < childList.size(); ++i) {
248 QGraphicsItem *item = childList.at(i);
249 if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))
250 climbTree(childList.at(i), stackingOrder);
251 }
252 item->d_ptr->globalStackingOrder = (*stackingOrder)++;
253 for (int i = 0; i < childList.size(); ++i) {
254 QGraphicsItem *item = childList.at(i);
255 if (item->flags() & QGraphicsItem::ItemStacksBehindParent)
256 climbTree(childList.at(i), stackingOrder);
257 }
258 } else {
259 item->d_ptr->globalStackingOrder = (*stackingOrder)++;
260 }
261 }
262
263 /*!
264 \internal
265 */
_q_updateSortCache()266 void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache()
267 {
268 Q_Q(QGraphicsSceneBspTreeIndex);
269 _q_updateIndex();
270
271 if (!sortCacheEnabled || !updatingSortCache)
272 return;
273
274 updatingSortCache = false;
275 int stackingOrder = 0;
276
277 QList<QGraphicsItem *> topLevels;
278 const QList<QGraphicsItem *> items = q->items();
279 for (int i = 0; i < items.size(); ++i) {
280 QGraphicsItem *item = items.at(i);
281 if (item && !item->d_ptr->parent)
282 topLevels << item;
283 }
284
285 qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
286 for (int i = 0; i < topLevels.size(); ++i)
287 climbTree(topLevels.at(i), &stackingOrder);
288 }
289
290 /*!
291 \internal
292 */
invalidateSortCache()293 void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache()
294 {
295 Q_Q(QGraphicsSceneBspTreeIndex);
296 if (!sortCacheEnabled || updatingSortCache)
297 return;
298
299 updatingSortCache = true;
300 QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);
301 }
302
addItem(QGraphicsItem * item,bool recursive)303 void QGraphicsSceneBspTreeIndexPrivate::addItem(QGraphicsItem *item, bool recursive)
304 {
305 if (!item)
306 return;
307
308 // Prevent reusing a recently deleted pointer: purge all removed item from our lists.
309 purgeRemovedItems();
310
311 // Invalidate any sort caching; arrival of a new item means we need to resort.
312 // Update the scene's sort cache settings.
313 item->d_ptr->globalStackingOrder = -1;
314 invalidateSortCache();
315
316 // Indexing requires sceneBoundingRect(), but because \a item might
317 // not be completely constructed at this point, we need to store it in
318 // a temporary list and schedule an indexing for later.
319 if (item->d_ptr->index == -1) {
320 Q_ASSERT(!unindexedItems.contains(item));
321 unindexedItems << item;
322 startIndexTimer(0);
323 } else {
324 Q_ASSERT(indexedItems.contains(item));
325 qWarning("QGraphicsSceneBspTreeIndex::addItem: item has already been added to this BSP");
326 }
327
328 if (recursive) {
329 for (int i = 0; i < item->d_ptr->children.size(); ++i)
330 addItem(item->d_ptr->children.at(i), recursive);
331 }
332 }
333
removeItem(QGraphicsItem * item,bool recursive,bool moveToUnindexedItems)334 void QGraphicsSceneBspTreeIndexPrivate::removeItem(QGraphicsItem *item, bool recursive,
335 bool moveToUnindexedItems)
336 {
337 if (!item)
338 return;
339
340 if (item->d_ptr->index != -1) {
341 Q_ASSERT(item->d_ptr->index < indexedItems.size());
342 Q_ASSERT(indexedItems.at(item->d_ptr->index) == item);
343 Q_ASSERT(!item->d_ptr->itemDiscovered);
344 freeItemIndexes << item->d_ptr->index;
345 indexedItems[item->d_ptr->index] = 0;
346 item->d_ptr->index = -1;
347
348 if (item->d_ptr->itemIsUntransformable()) {
349 untransformableItems.removeOne(item);
350 } else if (item->d_ptr->inDestructor) {
351 // Avoid virtual function calls from the destructor.
352 purgePending = true;
353 removedItems << item;
354 } else if (!(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) {
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
estimateItems(const QRectF & rect,Qt::SortOrder order,bool onlyTopLevelItems)376 QList<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 */
sortItems(QList<QGraphicsItem * > * itemList,Qt::SortOrder order,bool sortCacheEnabled,bool onlyTopLevelItems)412 void 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 qSort(itemList->begin(), itemList->end(), qt_closestLeaf);
421 else if (order == Qt::AscendingOrder)
422 qSort(itemList->begin(), itemList->end(), qt_notclosestLeaf);
423 return;
424 }
425
426 if (sortCacheEnabled) {
427 if (order == Qt::DescendingOrder) {
428 qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
429 } else if (order == Qt::AscendingOrder) {
430 qSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
431 }
432 } else {
433 if (order == Qt::DescendingOrder) {
434 qSort(itemList->begin(), itemList->end(), qt_closestItemFirst);
435 } else if (order == Qt::AscendingOrder) {
436 qSort(itemList->begin(), itemList->end(), qt_closestItemLast);
437 }
438 }
439 }
440
441 /*!
442 Constructs a BSP scene index for the given \a scene.
443 */
QGraphicsSceneBspTreeIndex(QGraphicsScene * scene)444 QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)
445 : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene)
446 {
447
448 }
449
~QGraphicsSceneBspTreeIndex()450 QGraphicsSceneBspTreeIndex::~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 */
clear()466 void 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 */
addItem(QGraphicsItem * item)488 void 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 */
removeItem(QGraphicsItem * item)497 void 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 */
prepareBoundingRectChange(const QGraphicsItem * item)507 void 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 return; // Item is not in BSP tree; nothing to do.
515 }
516
517 Q_D(QGraphicsSceneBspTreeIndex);
518 QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);
519 d->removeItem(thatItem, /*recursive=*/false, /*moveToUnindexedItems=*/true);
520 for (int i = 0; i < item->d_ptr->children.size(); ++i) // ### Do we really need this?
521 prepareBoundingRectChange(item->d_ptr->children.at(i));
522 }
523
524 /*!
525 Returns an estimation visible items that are either inside or
526 intersect with the specified \a rect and return a list sorted using \a order.
527
528 \a deviceTransform is the transformation apply to the view.
529
530 */
estimateItems(const QRectF & rect,Qt::SortOrder order) const531 QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order) const
532 {
533 Q_D(const QGraphicsSceneBspTreeIndex);
534 return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order);
535 }
536
estimateTopLevelItems(const QRectF & rect,Qt::SortOrder order) const537 QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const
538 {
539 Q_D(const QGraphicsSceneBspTreeIndex);
540 return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order, /*onlyTopLevels=*/true);
541 }
542
543 /*!
544 \fn QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order = Qt::DescendingOrder) const;
545
546 Return all items in the BSP index and sort them using \a order.
547 */
items(Qt::SortOrder order) const548 QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) const
549 {
550 Q_D(const QGraphicsSceneBspTreeIndex);
551 const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems();
552 QList<QGraphicsItem *> itemList;
553
554 // If freeItemIndexes is empty, we know there are no holes in indexedItems and
555 // unindexedItems.
556 if (d->freeItemIndexes.isEmpty()) {
557 if (d->unindexedItems.isEmpty()) {
558 itemList = d->indexedItems;
559 } else {
560 itemList = d->indexedItems + d->unindexedItems;
561 }
562 } else {
563 // Rebuild the list of items to avoid holes. ### We could also just
564 // compress the item lists at this point.
565 foreach (QGraphicsItem *item, d->indexedItems + d->unindexedItems) {
566 if (item)
567 itemList << item;
568 }
569 }
570 if (order != -1) {
571 //We sort descending order
572 d->sortItems(&itemList, order, d->sortCacheEnabled);
573 }
574 return itemList;
575 }
576
577 /*!
578 \property QGraphicsSceneBspTreeIndex::bspTreeDepth
579 \brief the depth of the BSP index tree
580 \since 4.6
581
582 This value determines the depth of BSP tree. The depth
583 directly affects performance and memory usage; the latter
584 growing exponentially with the depth of the tree. With an optimal tree
585 depth, the index can instantly determine the locality of items, even
586 for scenes with thousands or millions of items. This also greatly improves
587 rendering performance.
588
589 By default, the value is 0, in which case Qt will guess a reasonable
590 default depth based on the size, location and number of items in the
591 scene. If these parameters change frequently, however, you may experience
592 slowdowns as the index retunes the depth internally. You can avoid
593 potential slowdowns by fixating the tree depth through setting this
594 property.
595
596 The depth of the tree and the size of the scene rectangle decide the
597 granularity of the scene's partitioning. The size of each scene segment is
598 determined by the following algorithm:
599
600 The BSP tree has an optimal size when each segment contains between 0 and
601 10 items.
602
603 */
bspTreeDepth()604 int QGraphicsSceneBspTreeIndex::bspTreeDepth()
605 {
606 Q_D(const QGraphicsSceneBspTreeIndex);
607 return d->bspTreeDepth;
608 }
609
setBspTreeDepth(int depth)610 void QGraphicsSceneBspTreeIndex::setBspTreeDepth(int depth)
611 {
612 Q_D(QGraphicsSceneBspTreeIndex);
613 if (d->bspTreeDepth == depth)
614 return;
615 d->bspTreeDepth = depth;
616 d->resetIndex();
617 }
618
619 /*!
620 \internal
621
622 This method react to the \a rect change of the scene and
623 reset the BSP tree index.
624 */
updateSceneRect(const QRectF & rect)625 void QGraphicsSceneBspTreeIndex::updateSceneRect(const QRectF &rect)
626 {
627 Q_D(QGraphicsSceneBspTreeIndex);
628 d->sceneRect = rect;
629 d->resetIndex();
630 }
631
632 /*!
633 \internal
634
635 This method react to the \a change of the \a item and use the \a value to
636 update the BSP tree if necessary.
637 */
itemChange(const QGraphicsItem * item,QGraphicsItem::GraphicsItemChange change,const void * const value)638 void QGraphicsSceneBspTreeIndex::itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value)
639 {
640 Q_D(QGraphicsSceneBspTreeIndex);
641 switch (change) {
642 case QGraphicsItem::ItemFlagsChange: {
643 // Handle ItemIgnoresTransformations
644 QGraphicsItem::GraphicsItemFlags newFlags = *static_cast<const QGraphicsItem::GraphicsItemFlags *>(value);
645 bool ignoredTransform = item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations;
646 bool willIgnoreTransform = newFlags & QGraphicsItem::ItemIgnoresTransformations;
647 bool clipsChildren = item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape;
648 bool willClipChildren = newFlags & QGraphicsItem::ItemClipsChildrenToShape;
649 if ((ignoredTransform != willIgnoreTransform) || (clipsChildren != willClipChildren)) {
650 QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);
651 // Remove item and its descendants from the index and append
652 // them to the list of unindexed items. Then, when the index
653 // is updated, they will be put into the bsp-tree or the list
654 // of untransformable items.
655 d->removeItem(thatItem, /*recursive=*/true, /*moveToUnidexedItems=*/true);
656 }
657 break;
658 }
659 case QGraphicsItem::ItemZValueChange:
660 d->invalidateSortCache();
661 break;
662 case QGraphicsItem::ItemParentChange: {
663 d->invalidateSortCache();
664 // Handle ItemIgnoresTransformations
665 const QGraphicsItem *newParent = static_cast<const QGraphicsItem *>(value);
666 bool ignoredTransform = item->d_ptr->itemIsUntransformable();
667 bool willIgnoreTransform = (item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations)
668 || (newParent && newParent->d_ptr->itemIsUntransformable());
669 bool ancestorClippedChildren = item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren;
670 bool ancestorWillClipChildren = newParent
671 && ((newParent->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape)
672 || (newParent->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren));
673 if ((ignoredTransform != willIgnoreTransform) || (ancestorClippedChildren != ancestorWillClipChildren)) {
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 }
681 break;
682 }
683 default:
684 break;
685 }
686 }
687 /*!
688 \reimp
689
690 Used to catch the timer event.
691
692 \internal
693 */
event(QEvent * event)694 bool QGraphicsSceneBspTreeIndex::event(QEvent *event)
695 {
696 Q_D(QGraphicsSceneBspTreeIndex);
697 switch (event->type()) {
698 case QEvent::Timer:
699 if (d->indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == d->indexTimerId) {
700 if (d->restartIndexTimer) {
701 d->restartIndexTimer = false;
702 } else {
703 // this call will kill the timer
704 d->_q_updateIndex();
705 }
706 }
707 // Fallthrough intended - support timers in subclasses.
708 default:
709 return QObject::event(event);
710 }
711 return true;
712 }
713
714 QT_END_NAMESPACE
715
716 #include "moc_qgraphicsscenebsptreeindex_p.cpp"
717
718 #endif // QT_NO_GRAPHICSVIEW
719
720