qgraphicssceneindex.cpp

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
** Contact: http://www.qt-project.org/legal
**
** This file is part of the QtGui module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Digia.  For licensing terms and
** conditions see http://qt.digia.com/licensing.  For further information
** use the contact form at http://qt.digia.com/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 2.1 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU Lesser General Public License version 2.1 requirements
** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
**
** In addition, as a special exception, Digia gives you certain additional
** rights.  These rights are described in the Digia Qt LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3.0 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU General Public License version 3.0 requirements will be
** met: http://www.gnu.org/copyleft/gpl.html.
**
**
** $QT_END_LICENSE$
**
****************************************************************************/
#include "qdebug.h"
#include "qgraphicsscene.h"
#include "qgraphicsitem_p.h"
#include "qgraphicsscene_p.h"
#include "qgraphicswidget.h"
#include "qgraphicssceneindex_p.h"
#include "qgraphicsscenebsptreeindex_p.h"

#ifndef QT_NO_GRAPHICSVIEW

QT_BEGIN_NAMESPACE

class QGraphicsSceneIndexRectIntersector : public QGraphicsSceneIndexIntersector
{
public:
    bool intersect(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode,
                   const QTransform &deviceTransform) const
    {
        QRectF brect = item->boundingRect();
        _q_adjustRect(&brect);

        // ### Add test for this (without making things slower?)
        Q_UNUSED(exposeRect);

        bool keep = true;
        const QGraphicsItemPrivate *itemd = QGraphicsItemPrivate::get(item);
        if (itemd->itemIsUntransformable()) {
            // Untransformable items; map the scene rect to item coordinates.
            const QTransform transform = item->deviceTransform(deviceTransform);
            QRectF itemRect = (deviceTransform * transform.inverted()).mapRect(sceneRect);
            if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
                keep = itemRect.contains(brect) && itemRect != brect;
            else
                keep = itemRect.intersects(brect);
            if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
                QPainterPath itemPath;
                itemPath.addRect(itemRect);
                keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, itemPath, mode);
            }
        } else {
            Q_ASSERT(!itemd->dirtySceneTransform);
            const QRectF itemSceneBoundingRect = itemd->sceneTransformTranslateOnly
                                               ? brect.translated(itemd->sceneTransform.dx(),
                                                                  itemd->sceneTransform.dy())
                                               : itemd->sceneTransform.mapRect(brect);
            if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
                keep = sceneRect != brect && sceneRect.contains(itemSceneBoundingRect);
            else
                keep = sceneRect.intersects(itemSceneBoundingRect);
            if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
                QPainterPath rectPath;
                rectPath.addRect(sceneRect);
                if (itemd->sceneTransformTranslateOnly)
                    rectPath.translate(-itemd->sceneTransform.dx(), -itemd->sceneTransform.dy());
                else
                    rectPath = itemd->sceneTransform.inverted().map(rectPath);
                keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, rectPath, mode);
            }
        }
        return keep;
    }

    QRectF sceneRect;
};

class QGraphicsSceneIndexPointIntersector : public QGraphicsSceneIndexIntersector
{
public:
    bool intersect(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode,
                   const QTransform &deviceTransform) const
    {
        QRectF brect = item->boundingRect();
        _q_adjustRect(&brect);

        // ### Add test for this (without making things slower?)
        Q_UNUSED(exposeRect);

        bool keep = false;
        const QGraphicsItemPrivate *itemd = QGraphicsItemPrivate::get(item);
        if (itemd->itemIsUntransformable()) {
            // Untransformable items; map the scene point to item coordinates.
            const QTransform transform = item->deviceTransform(deviceTransform);
            QPointF itemPoint = (deviceTransform * transform.inverted()).map(scenePoint);
            keep = brect.contains(itemPoint);
            if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
                QPainterPath pointPath;
                pointPath.addRect(QRectF(itemPoint, QSizeF(1, 1)));
                keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, pointPath, mode);
            }
        } else {
            Q_ASSERT(!itemd->dirtySceneTransform);
            QRectF sceneBoundingRect = itemd->sceneTransformTranslateOnly
                                     ? brect.translated(itemd->sceneTransform.dx(),
                                                        itemd->sceneTransform.dy())
                                     : itemd->sceneTransform.mapRect(brect);
            keep = sceneBoundingRect.intersects(QRectF(scenePoint, QSizeF(1, 1)));
            if (keep) {
                QPointF p = itemd->sceneTransformTranslateOnly
                          ? QPointF(scenePoint.x() - itemd->sceneTransform.dx(),
                                    scenePoint.y() - itemd->sceneTransform.dy())
                          : itemd->sceneTransform.inverted().map(scenePoint);
                keep = item->contains(p);
            }
        }

        return keep;
    }

    QPointF scenePoint;
};

class QGraphicsSceneIndexPathIntersector : public QGraphicsSceneIndexIntersector
{
public:
    bool intersect(const QGraphicsItem *item, const QRectF &exposeRect, Qt::ItemSelectionMode mode,
                   const QTransform &deviceTransform) const
    {
        QRectF brect = item->boundingRect();
        _q_adjustRect(&brect);

        // ### Add test for this (without making things slower?)
        Q_UNUSED(exposeRect);

        bool keep = true;
        const QGraphicsItemPrivate *itemd = QGraphicsItemPrivate::get(item);
        if (itemd->itemIsUntransformable()) {
            // Untransformable items; map the scene rect to item coordinates.
            const QTransform transform = item->deviceTransform(deviceTransform);
            QPainterPath itemPath = (deviceTransform * transform.inverted()).map(scenePath);
            if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
                keep = itemPath.contains(brect);
            else
                keep = itemPath.intersects(brect);
            if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape))
                keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, itemPath, mode);
        } else {
            Q_ASSERT(!itemd->dirtySceneTransform);
            const QRectF itemSceneBoundingRect = itemd->sceneTransformTranslateOnly
                                               ? brect.translated(itemd->sceneTransform.dx(),
                                                                  itemd->sceneTransform.dy())
                                               : itemd->sceneTransform.mapRect(brect);
            if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
                keep = scenePath.contains(itemSceneBoundingRect);
            else
                keep = scenePath.intersects(itemSceneBoundingRect);
            if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
                QPainterPath itemPath = itemd->sceneTransformTranslateOnly
                                      ? scenePath.translated(-itemd->sceneTransform.dx(),
                                                             -itemd->sceneTransform.dy())
                                      : itemd->sceneTransform.inverted().map(scenePath);
                keep = QGraphicsSceneIndexPrivate::itemCollidesWithPath(item, itemPath, mode);
            }
        }
        return keep;
    }

    QPainterPath scenePath;
};

QGraphicsSceneIndexPrivate::QGraphicsSceneIndexPrivate(QGraphicsScene *scene) : scene(scene)
{
    pointIntersector = new QGraphicsSceneIndexPointIntersector;
    rectIntersector = new QGraphicsSceneIndexRectIntersector;
    pathIntersector =  new QGraphicsSceneIndexPathIntersector;
}

QGraphicsSceneIndexPrivate::~QGraphicsSceneIndexPrivate()
{
    delete pointIntersector;
    delete rectIntersector;
    delete pathIntersector;
}

bool QGraphicsSceneIndexPrivate::itemCollidesWithPath(const QGraphicsItem *item,
                                                      const QPainterPath &path,
                                                      Qt::ItemSelectionMode mode)
{
    if (item->collidesWithPath(path, mode))
        return true;
    if (item->isWidget()) {
        // Check if this is a window, and if its frame rect collides.
        const QGraphicsWidget *widget = static_cast<const QGraphicsWidget *>(item);
        if (widget->isWindow()) {
            QRectF frameRect = widget->windowFrameRect();
            QPainterPath framePath;
            framePath.addRect(frameRect);
            bool intersects = path.intersects(frameRect);
            if (mode == Qt::IntersectsItemShape || mode == Qt::IntersectsItemBoundingRect)
                return intersects || path.contains(frameRect.topLeft())
                    || framePath.contains(path.elementAt(0));
            return !intersects && path.contains(frameRect.topLeft());
        }
    }
    return false;
}

void QGraphicsSceneIndexPrivate::recursive_items_helper(QGraphicsItem *item, QRectF exposeRect,
                                                        QGraphicsSceneIndexIntersector *intersector,
                                                        QList<QGraphicsItem *> *items,
                                                        const QTransform &viewTransform,
                                                        Qt::ItemSelectionMode mode,
                                                        qreal parentOpacity) const
{
    Q_ASSERT(item);
    if (!item->d_ptr->visible)
        return;

    const qreal opacity = item->d_ptr->combineOpacityFromParent(parentOpacity);
    const bool itemIsFullyTransparent = QGraphicsItemPrivate::isOpacityNull(opacity);
    const bool itemHasChildren = !item->d_ptr->children.isEmpty();
    if (itemIsFullyTransparent && (!itemHasChildren || item->d_ptr->childrenCombineOpacity()))
        return;

    // Update the item's scene transform if dirty.
    const bool itemIsUntransformable = item->d_ptr->itemIsUntransformable();
    const bool wasDirtyParentSceneTransform = item->d_ptr->dirtySceneTransform && !itemIsUntransformable;
    if (wasDirtyParentSceneTransform) {
        item->d_ptr->updateSceneTransformFromParent();
        Q_ASSERT(!item->d_ptr->dirtySceneTransform);
    }

    const bool itemClipsChildrenToShape = (item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape);
    bool processItem = !itemIsFullyTransparent;
    if (processItem) {
        processItem = intersector->intersect(item, exposeRect, mode, viewTransform);
        if (!processItem && (!itemHasChildren || itemClipsChildrenToShape)) {
            if (wasDirtyParentSceneTransform)
                item->d_ptr->invalidateChildrenSceneTransform();
            return;
        }
    } // else we know for sure this item has children we must process.

    int i = 0;
    if (itemHasChildren) {
        // Sort children.
        item->d_ptr->ensureSortedChildren();

        // Clip to shape.
        if (itemClipsChildrenToShape && !itemIsUntransformable) {
            QPainterPath mappedShape = item->d_ptr->sceneTransformTranslateOnly
                                     ? item->shape().translated(item->d_ptr->sceneTransform.dx(),
                                                                item->d_ptr->sceneTransform.dy())
                                     : item->d_ptr->sceneTransform.map(item->shape());
            exposeRect &= mappedShape.controlPointRect();
        }

        // Process children behind
        for (i = 0; i < item->d_ptr->children.size(); ++i) {
            QGraphicsItem *child = item->d_ptr->children.at(i);
            if (wasDirtyParentSceneTransform)
                child->d_ptr->dirtySceneTransform = 1;
            if (!(child->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent))
                break;
            if (itemIsFullyTransparent && !(child->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity))
                continue;
            recursive_items_helper(child, exposeRect, intersector, items, viewTransform,
                                   mode, opacity);
        }
    }

    // Process item
    if (processItem)
        items->append(item);

    // Process children in front
    if (itemHasChildren) {
        for (; i < item->d_ptr->children.size(); ++i) {
            QGraphicsItem *child = item->d_ptr->children.at(i);
            if (wasDirtyParentSceneTransform)
                child->d_ptr->dirtySceneTransform = 1;
            if (itemIsFullyTransparent && !(child->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity))
                continue;
            recursive_items_helper(child, exposeRect, intersector, items, viewTransform,
                                   mode, opacity);
        }
    }
}

void QGraphicsSceneIndexPrivate::init()
{
    if (!scene)
        return;

    QObject::connect(scene, SIGNAL(sceneRectChanged(QRectF)),
                     q_func(), SLOT(updateSceneRect(QRectF)));
}

QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene)
: QObject(*new QGraphicsSceneIndexPrivate(scene), scene)
{
    d_func()->init();
}

QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsSceneIndexPrivate &dd, QGraphicsScene *scene)
    : QObject(dd, scene)
{
    d_func()->init();
}

QGraphicsSceneIndex::~QGraphicsSceneIndex()
{

}

QGraphicsScene* QGraphicsSceneIndex::scene() const
{
    Q_D(const QGraphicsSceneIndex);
    return d->scene;
}

QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, Qt::ItemSelectionMode mode,
                                                  Qt::SortOrder order, const QTransform &deviceTransform) const
{

    Q_D(const QGraphicsSceneIndex);
    QList<QGraphicsItem *> itemList;
    d->pointIntersector->scenePoint = pos;
    d->items_helper(QRectF(pos, QSizeF(1, 1)), d->pointIntersector, &itemList, deviceTransform, mode, order);
    return itemList;
}

QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, Qt::ItemSelectionMode mode,
                                                  Qt::SortOrder order, const QTransform &deviceTransform) const
{
    Q_D(const QGraphicsSceneIndex);
    QRectF exposeRect = rect;
    _q_adjustRect(&exposeRect);
    QList<QGraphicsItem *> itemList;
    d->rectIntersector->sceneRect = rect;
    d->items_helper(exposeRect, d->rectIntersector, &itemList, deviceTransform, mode, order);
    return itemList;
}

QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode,
                                                  Qt::SortOrder order, const QTransform &deviceTransform) const
{
    Q_D(const QGraphicsSceneIndex);
    QList<QGraphicsItem *> itemList;
    QRectF exposeRect = polygon.boundingRect();
    _q_adjustRect(&exposeRect);
    QPainterPath path;
    path.addPolygon(polygon);
    d->pathIntersector->scenePath = path;
    d->items_helper(exposeRect, d->pathIntersector, &itemList, deviceTransform, mode, order);
    return itemList;
}

QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::ItemSelectionMode mode,
                                                  Qt::SortOrder order, const QTransform &deviceTransform) const
{
    Q_D(const QGraphicsSceneIndex);
    QList<QGraphicsItem *> itemList;
    QRectF exposeRect = path.controlPointRect();
    _q_adjustRect(&exposeRect);
    d->pathIntersector->scenePath = path;
    d->items_helper(exposeRect, d->pathIntersector, &itemList, deviceTransform, mode, order);
    return itemList;
}

QList<QGraphicsItem *> QGraphicsSceneIndex::estimateItems(const QPointF &point, Qt::SortOrder order) const
{
    return estimateItems(QRectF(point, QSize(1, 1)), order);
}

QList<QGraphicsItem *> QGraphicsSceneIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const
{
    Q_D(const QGraphicsSceneIndex);
    Q_UNUSED(rect);
    QGraphicsScenePrivate *scened = d->scene->d_func();
    scened->ensureSortedTopLevelItems();
    if (order == Qt::DescendingOrder) {
        QList<QGraphicsItem *> sorted;
        for (int i = scened->topLevelItems.size() - 1; i >= 0; --i)
            sorted << scened->topLevelItems.at(i);
        return sorted;
    }
    return scened->topLevelItems;
}

void QGraphicsSceneIndex::updateSceneRect(const QRectF &rect)
{
    Q_UNUSED(rect);
}

void QGraphicsSceneIndex::clear()
{
    const QList<QGraphicsItem *> allItems = items();
    for (int i = 0 ; i < allItems.size(); ++i)
        removeItem(allItems.at(i));
}

void QGraphicsSceneIndex::deleteItem(QGraphicsItem *item)
{
    removeItem(item);
}

void QGraphicsSceneIndex::itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value)
{
    Q_UNUSED(item);
    Q_UNUSED(change);
    Q_UNUSED(value);
}

void QGraphicsSceneIndex::prepareBoundingRectChange(const QGraphicsItem *item)
{
    Q_UNUSED(item);
}

QT_END_NAMESPACE

#include "moc_qgraphicssceneindex_p.cpp"

#endif // QT_NO_GRAPHICSVIEW