1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    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 scene. 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 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 

    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 */

    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 */

   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 */

   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 */

   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 */

   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 */

   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 */

   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 */

   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 

   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 

   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 

   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 */

   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 */

   444 QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)

   445     : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene)

   446 {

   447 

   448 }

   449 

   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 */

   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 */

   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 */

   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 */

   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 */

   531 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 

   537 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 */

   548 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 */

   604 int QGraphicsSceneBspTreeIndex::bspTreeDepth()

   605 {

   606     Q_D(const QGraphicsSceneBspTreeIndex);

   607     return d->bspTreeDepth;

   608 }

   609 

   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 */

   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 */

   638 void QGraphicsSceneBspTreeIndex::itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value)

   639 {

   640     Q_D(QGraphicsSceneBspTreeIndex);

   641     switch (change) {

   642     case QGraphicsItem::ItemFlagsChange: {

   643         // Handle ItemIgnoresTransformations

   644         bool ignoredTransform = item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations;

   645         bool willIgnoreTransform = value.toUInt() & QGraphicsItem::ItemIgnoresTransformations;

   646         bool clipsChildren = item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape;

   647         bool willClipChildren = value.toUInt() & QGraphicsItem::ItemClipsChildrenToShape;

   648         if ((ignoredTransform != willIgnoreTransform) || (clipsChildren != willClipChildren)) {

   649             QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);

   650             // Remove item and its descendants from the index and append

   651             // them to the list of unindexed items. Then, when the index

   652             // is updated, they will be put into the bsp-tree or the list

   653             // of untransformable items.

   654             d->removeItem(thatItem, /*recursive=*/true, /*moveToUnidexedItems=*/true);

   655         }

   656         break;

   657     }

   658     case QGraphicsItem::ItemZValueChange:

   659         d->invalidateSortCache();

   660         break;

   661     case QGraphicsItem::ItemParentChange: {

   662         d->invalidateSortCache();

   663         // Handle ItemIgnoresTransformations

   664         QGraphicsItem *newParent = qVariantValue<QGraphicsItem *>(value);

   665         bool ignoredTransform = item->d_ptr->itemIsUntransformable();

   666         bool willIgnoreTransform = (item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations)

   667                                    || (newParent && newParent->d_ptr->itemIsUntransformable());

   668         bool ancestorClippedChildren = item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren;

   669         bool ancestorWillClipChildren = newParent

   670                             && ((newParent->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape)

   671                                 || (newParent->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren));

   672         if ((ignoredTransform != willIgnoreTransform) || (ancestorClippedChildren != ancestorWillClipChildren)) {

   673             QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);

   674             // Remove item and its descendants from the index and append

   675             // them to the list of unindexed items. Then, when the index

   676             // is updated, they will be put into the bsp-tree or the list

   677             // of untransformable items.

   678             d->removeItem(thatItem, /*recursive=*/true, /*moveToUnidexedItems=*/true);

   679         }

   680         break;

   681     }

   682     default:

   683         break;

   684     }

   685     return QGraphicsSceneIndex::itemChange(item, change, value);

   686 }

   687 /*!

   688     \reimp

   689 

   690     Used to catch the timer event.

   691 

   692     \internal

   693 */

   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