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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
// Copyright Matt Overby 2020.
// Distributed under the MIT License.
#ifndef ADMMPD_BVH_H_
#define ADMMPD_BVH_H_ 1
#include "admmpd_bvh_traverse.h"
#include <vector>
#include <memory>
#include <functional>
namespace admmpd {
template <typename T, int DIM>
class AABBTree
{
protected:
typedef Eigen::AlignedBox<T,DIM> AABB;
typedef Eigen::Matrix<T,DIM,1> VecType;
public:
// Removes all BVH data
void clear();
// Initializes the BVH with a list of leaf bounding boxes.
// Sorts each split by largest axis.
void init(const std::vector<AABB> &leaves);
// Recomputes the bounding boxes of leaf and parent
// nodes but does not sort the tree.
void update(const std::vector<AABB> &leaves);
// Traverse the tree. Returns result of traverser
bool traverse(Traverser<T,DIM> &traverser) const;
// Traverse the tree with function pointers instead of class:
// void traverse(
// const AABB &left_aabb, bool &go_left,
// const AABB &right_aabb, bool &go_right,
// bool &go_left_first);
// bool stop_traversing( const AABB &aabb, int prim );
bool traverse(
std::function<void(const AABB&, bool&, const AABB&, bool&, bool&)> t,
std::function<bool(const AABB&, int)> s) const;
struct Node
{
AABB aabb;
Node *left, *right;
std::vector<int> prims;
VecType normal;
T angle;
bool is_leaf() const { return prims.size()>0; }
Node() : left(nullptr), right(nullptr) {}
~Node()
{
if(left){ delete left; }
if(right){ delete right; }
}
};
protected:
std::shared_ptr<Node> root;
void create_children(
Node *node,
std::vector<int> &queue,
const std::vector<AABB> &leaves);
void update_children(
Node *node,
const std::vector<AABB> &leaves);
bool traverse_children(
const Node *node,
Traverser<T,DIM> &traverser ) const;
}; // class AABBtree
// Octree is actually a quadtree if DIM=2
template<typename T, int DIM>
class Octree
{
protected:
typedef Eigen::AlignedBox<T,DIM> AABB;
typedef Eigen::Matrix<T,DIM,1> VecType;
typedef Eigen::Matrix<T,Eigen::Dynamic,Eigen::Dynamic> MatrixXT;
static const int nchild = std::pow(2,DIM);
public:
// Removes all BVH data
void clear();
// Creates the Octree up to depth with smart subdivision
// (only create children if it contains prims) and does not
// create a cell if it is outside the mesh.
// ** Assumes a closed mesh and only defined for 3D
void init(const MatrixXT *V, const Eigen::MatrixXi *F, int stopdepth);
// Returns bounding box of the root node
AABB bounds() const;
struct Node
{
VecType center;
T halfwidth;
Node *children[4*DIM];
std::vector<int> prims; // includes childen
bool is_leaf() const;
AABB bounds() const;
Node();
~Node();
};
// Return ptr to the root node
// Becomes invalidated after init()
std::shared_ptr<Node> root() { return m_root; }
protected:
std::shared_ptr<Node> m_root;
Node* create_children(
const VecType ¢er, T halfwidth, int stopdepth,
const MatrixXT *V, const Eigen::MatrixXi *F,
const std::vector<int> &queue,
const std::vector<AABB> &boxes);
}; // class Octree
} // namespace admmpd
#endif // ADMMPD_BVH_H_
|
