1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
#include "qbsptree_p.h"
QT_BEGIN_NAMESPACE
QBspTree::QBspTree() : depth(6), visited(0) {}
void QBspTree::create(int n, int d)
{
// simple heuristics to find the best tree depth
if (d == -1) {
int c;
for (c = 0; n; ++c)
n = n / 10;
depth = c << 1;
} else {
depth = d;
}
depth = qMax(depth, uint(1));
nodes.resize((1ll << depth) - 1); // resize to number of nodes
leaves.resize(1ll << depth); // resize to number of leaves
}
void QBspTree::destroy()
{
leaves.clear();
nodes.clear();
}
void QBspTree::climbTree(const QRect &rect, callback *function, QBspTreeData data)
{
if (nodes.isEmpty())
return;
++visited;
climbTree(rect, function, data, 0);
}
void QBspTree::climbTree(const QRect &area, callback *function, QBspTreeData data, int index)
{
if (index >= nodes.count()) { // the index points to a leaf
Q_ASSERT(!nodes.isEmpty());
function(leaf(index - nodes.count()), area, visited, data);
return;
}
Node::Type t = (Node::Type) nodes.at(index).type;
int pos = nodes.at(index).pos;
int idx = firstChildIndex(index);
if (t == Node::VerticalPlane) {
if (area.left() < pos)
climbTree(area, function, data, idx); // back
if (area.right() >= pos)
climbTree(area, function, data, idx + 1); // front
} else {
if (area.top() < pos)
climbTree(area, function, data, idx); // back
if (area.bottom() >= pos)
climbTree(area, function, data, idx + 1); // front
}
}
void QBspTree::init(const QRect &area, int depth, NodeType type, int index)
{
Node::Type t = Node::None; // t should never have this value
if (type == Node::Both) // if both planes are specified, use 2d bsp
t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;
else
t = type;
QPoint center = area.center();
nodes[index].pos = (t == Node::VerticalPlane ? center.x() : center.y());
nodes[index].type = t;
QRect front = area;
QRect back = area;
if (t == Node::VerticalPlane) {
front.setLeft(center.x());
back.setRight(center.x() - 1); // front includes the center
} else { // t == Node::HorizontalPlane
front.setTop(center.y());
back.setBottom(center.y() - 1);
}
int idx = firstChildIndex(index);
if (--depth) {
init(back, depth, type, idx);
init(front, depth, type, idx + 1);
}
}
void QBspTree::insert(QList<int> &leaf, const QRect &, uint, QBspTreeData data)
{
leaf.append(data.i);
}
void QBspTree::remove(QList<int> &leaf, const QRect &, uint, QBspTreeData data)
{
int i = leaf.indexOf(data.i);
if (i != -1)
leaf.remove(i);
}
QT_END_NAMESPACE
|
