Qt 4.8
qbsptree.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
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 Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/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 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #include "qbsptree_p.h"
43 
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 
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 
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 
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 
134 {
135  leaf.append(data.i);
136 }
137 
139 {
140  int i = leaf.indexOf(data.i);
141  if (i != -1)
142  leaf.remove(i);
143 }
144 
double d
Definition: qnumeric_p.h:62
int type
Definition: qmetatype.cpp:239
void setBottom(int pos)
Sets the bottom edge of the rectangle to the given y coordinate.
Definition: qrect.h:267
unsigned char c[8]
Definition: qnumeric_p.h:62
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
void remove(int i)
Removes the element at index position i.
Definition: qvector.h:374
QVector< int > & leaf(int i)
Definition: qbsptree_p.h:96
void init(const QRect &area, NodeType type)
Definition: qbsptree_p.h:91
int left() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:240
QVector< QVector< int > > leaves
Definition: qbsptree_p.h:114
int firstChildIndex(int i) const
Definition: qbsptree_p.h:105
QBspTree()
Definition: qbsptree.cpp:46
int bottom() const
Returns the y-coordinate of the rectangle&#39;s bottom edge.
Definition: qrect.h:249
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
void resize(int size)
Sets the size of the vector to size.
Definition: qvector.h:342
static void remove(QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)
Definition: qbsptree.cpp:138
void callback(QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)
Definition: qbsptree_p.h:84
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
void clear()
Removes all the elements from the vector and releases the memory used by the vector.
Definition: qvector.h:347
void setTop(int pos)
Sets the top edge of the rectangle to the given y coordinate.
Definition: qrect.h:261
void setRight(int pos)
Sets the right edge of the rectangle to the given x coordinate.
Definition: qrect.h:264
void append(const T &t)
Inserts value at the end of the vector.
Definition: qvector.h:573
uint depth
Definition: qbsptree_p.h:111
static const char * data(const QByteArray &arr)
unsigned int uint
Definition: qglobal.h:996
static void insert(QVector< int > &leaf, const QRect &area, uint visited, QBspTreeData data)
Definition: qbsptree.cpp:133
void climbTree(const QRect &rect, callback *function, QBspTreeData data)
Definition: qbsptree.cpp:71
int indexOf(const T &t, int from=0) const
Returns the index position of the first occurrence of value in the vector, searching forward from ind...
Definition: qvector.h:698
void destroy()
Definition: qbsptree.cpp:65
QVector< Node > nodes
Definition: qbsptree_p.h:113
Q_CORE_EXPORT QTextStream & center(QTextStream &s)
QPoint center() const
Returns the center point of the rectangle.
Definition: qrect.h:300
int top() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:243
uint visited
Definition: qbsptree_p.h:112
int right() const
Returns the x-coordinate of the rectangle&#39;s right edge.
Definition: qrect.h:246
void setLeft(int pos)
Sets the left edge of the rectangle to the given x coordinate.
Definition: qrect.h:258
The QPoint class defines a point in the plane using integer precision.
Definition: qpoint.h:53
The QRect class defines a rectangle in the plane using integer precision.
Definition: qrect.h:58
int y() const
Returns the y coordinate of this point.
Definition: qpoint.h:131
quint16 index
int x() const
Returns the x coordinate of this point.
Definition: qpoint.h:128
static int area(const QSize &s)
Definition: qicon.cpp:155
void create(int n, int d=-1)
Definition: qbsptree.cpp:48