1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
5 **
6 ** This file is part of the QtWidgets 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 https://www.qt.io/terms-conditions. For further
15 ** information use the contact form at https://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 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or (at your option) the GNU General
28 ** Public license version 3 or any later version approved by the KDE Free
29 ** Qt Foundation. The licenses are as published by the Free Software
30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31 ** included in the packaging of this file. Please review the following
32 ** information to ensure the GNU General Public License requirements will
33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34 ** https://www.gnu.org/licenses/gpl-3.0.html.
35 **
36 ** $QT_END_LICENSE$
37 **
38 ****************************************************************************/
39
40 #include "qbsptree_p.h"
41
42 QT_BEGIN_NAMESPACE
43
QBspTree()44 QBspTree::QBspTree() : depth(6), visited(0) {}
45
create(int n,int d)46 void QBspTree::create(int n, int d)
47 {
48 // simple heuristics to find the best tree depth
49 if (d == -1) {
50 int c;
51 for (c = 0; n; ++c)
52 n = n / 10;
53 depth = c << 1;
54 } else {
55 depth = d;
56 }
57 depth = qMax(depth, uint(1));
58
59 nodes.resize((1 << depth) - 1); // resize to number of nodes
60 leaves.resize(1 << depth); // resize to number of leaves
61 }
62
destroy()63 void QBspTree::destroy()
64 {
65 leaves.clear();
66 nodes.clear();
67 }
68
climbTree(const QRect & rect,callback * function,QBspTreeData data)69 void QBspTree::climbTree(const QRect &rect, callback *function, QBspTreeData data)
70 {
71 if (nodes.isEmpty())
72 return;
73 ++visited;
74 climbTree(rect, function, data, 0);
75 }
76
climbTree(const QRect & area,callback * function,QBspTreeData data,int index)77 void QBspTree::climbTree(const QRect &area, callback *function, QBspTreeData data, int index)
78 {
79 if (index >= nodes.count()) { // the index points to a leaf
80 Q_ASSERT(!nodes.isEmpty());
81 function(leaf(index - nodes.count()), area, visited, data);
82 return;
83 }
84
85 Node::Type t = (Node::Type) nodes.at(index).type;
86
87 int pos = nodes.at(index).pos;
88 int idx = firstChildIndex(index);
89 if (t == Node::VerticalPlane) {
90 if (area.left() < pos)
91 climbTree(area, function, data, idx); // back
92 if (area.right() >= pos)
93 climbTree(area, function, data, idx + 1); // front
94 } else {
95 if (area.top() < pos)
96 climbTree(area, function, data, idx); // back
97 if (area.bottom() >= pos)
98 climbTree(area, function, data, idx + 1); // front
99 }
100 }
101
init(const QRect & area,int depth,NodeType type,int index)102 void QBspTree::init(const QRect &area, int depth, NodeType type, int index)
103 {
104 Node::Type t = Node::None; // t should never have this value
105 if (type == Node::Both) // if both planes are specified, use 2d bsp
106 t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;
107 else
108 t = type;
109 QPoint center = area.center();
110 nodes[index].pos = (t == Node::VerticalPlane ? center.x() : center.y());
111 nodes[index].type = t;
112
113 QRect front = area;
114 QRect back = area;
115
116 if (t == Node::VerticalPlane) {
117 front.setLeft(center.x());
118 back.setRight(center.x() - 1); // front includes the center
119 } else { // t == Node::HorizontalPlane
120 front.setTop(center.y());
121 back.setBottom(center.y() - 1);
122 }
123
124 int idx = firstChildIndex(index);
125 if (--depth) {
126 init(back, depth, type, idx);
127 init(front, depth, type, idx + 1);
128 }
129 }
130
insert(QVector<int> & leaf,const QRect &,uint,QBspTreeData data)131 void QBspTree::insert(QVector<int> &leaf, const QRect &, uint, QBspTreeData data)
132 {
133 leaf.append(data.i);
134 }
135
remove(QVector<int> & leaf,const QRect &,uint,QBspTreeData data)136 void QBspTree::remove(QVector<int> &leaf, const QRect &, uint, QBspTreeData data)
137 {
138 int i = leaf.indexOf(data.i);
139 if (i != -1)
140 leaf.remove(i);
141 }
142
143 QT_END_NAMESPACE
144