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
42QT_BEGIN_NAMESPACE
43
44QBspTree::QBspTree() : depth(6), visited(0) {}
45
46void 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((1ll << depth) - 1); // resize to number of nodes
60 leaves.resize(1ll << depth); // resize to number of leaves
61}
62
63void QBspTree::destroy()
64{
65 leaves.clear();
66 nodes.clear();
67}
68
69void 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
77void 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
102void 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
131void QBspTree::insert(QList<int> &leaf, const QRect &, uint, QBspTreeData data)
132{
133 leaf.append(data.i);
134}
135
136void QBspTree::remove(QList<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
143QT_END_NAMESPACE
144