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 #include "qbsptree_p.h"

    43 

    44 QT_BEGIN_NAMESPACE

    45 

    46 QBspTree::QBspTree() : depth(6), visited(0) {}

    47 

    48 void QBspTree::create(int n, int d)

    49 {

    50     // simple heuristics to find the best tree depth

    51     if (d == -1) {

    52         int c;

    53         for (c = 0; n; ++c)

    54             n = n / 10;

    55         depth = c << 1;

    56     } else {

    57         depth = d;

    58     }

    59     depth = qMax(depth, uint(1));

    60 

    61     nodes.resize((1 << depth) - 1); // resize to number of nodes

    62     leaves.resize(1 << depth); // resize to number of leaves

    63 }

    64 

    65 void QBspTree::destroy()

    66 {

    67     leaves.clear();

    68     nodes.clear();

    69 }

    70 

    71 void QBspTree::climbTree(const QRect &rect, callback *function, QBspTreeData data)

    72 {

    73     if (nodes.isEmpty())

    74         return;

    75     ++visited;

    76     climbTree(rect, function, data, 0);

    77 }

    78 

    79 void QBspTree::climbTree(const QRect &area, callback *function, QBspTreeData data, int index)

    80 {

    81     if (index >= nodes.count()) { // the index points to a leaf

    82         Q_ASSERT(!nodes.isEmpty());

    83         function(leaf(index - nodes.count()), area, visited, data);

    84         return;

    85     }

    86 

    87     Node::Type t = (Node::Type) nodes.at(index).type;

    88 

    89     int pos = nodes.at(index).pos;

    90     int idx = firstChildIndex(index);

    91     if (t == Node::VerticalPlane) {

    92         if (area.left() < pos)

    93             climbTree(area, function, data, idx); // back

    94         if (area.right() >= pos)

    95             climbTree(area, function, data, idx + 1); // front

    96     } else {

    97         if (area.top() < pos)

    98             climbTree(area, function, data, idx); // back

    99         if (area.bottom() >= pos)

   100             climbTree(area, function, data, idx + 1); // front

   101     }

   102 }

   103 

   104 void QBspTree::init(const QRect &area, int depth, NodeType type, int index)

   105 {

   106     Node::Type t = Node::None; // t should never have this value

   107     if (type == Node::Both) // if both planes are specified, use 2d bsp

   108         t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;

   109     else

   110         t = type;

   111     QPoint center = area.center();

   112     nodes[index].pos = (t == Node::VerticalPlane ? center.x() : center.y());

   113     nodes[index].type = t;

   114 

   115     QRect front = area;

   116     QRect back = area;

   117 

   118     if (t == Node::VerticalPlane) {

   119         front.setLeft(center.x());

   120         back.setRight(center.x() - 1); // front includes the center

   121     } else { // t == Node::HorizontalPlane

   122         front.setTop(center.y());

   123         back.setBottom(center.y() - 1);

   124     }

   125 

   126     int idx = firstChildIndex(index);

   127     if (--depth) {

   128         init(back, depth, type, idx);

   129         init(front, depth, type, idx + 1);

   130     }

   131 }

   132 

   133 void QBspTree::insert(QVector<int> &leaf, const QRect &, uint, QBspTreeData data)

   134 {

   135     leaf.append(data.i);

   136 }

   137 

   138 void QBspTree::remove(QVector<int> &leaf, const QRect &, uint, QBspTreeData data)

   139 {

   140     int i = leaf.indexOf(data.i);

   141     if (i != -1)

   142         leaf.remove(i);

   143 }

   144 

   145 QT_END_NAMESPACE