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
|
/*
This file is part of the MinGfx Project.
Copyright (c) 2017,2018 Regents of the University of Minnesota.
All Rights Reserved.
Original Author(s) of this File:
David Schroeder, 2010-ish, University of Minnesota
Author(s) of Significant Updates/Modifications to the File:
Dan Keefe, 2018, University of Minnesota
...
*/
#ifndef SRC_BVH_H_
#define SRC_BVH_H_
#include "aabb.h"
#include "point3.h"
namespace mingfx {
// forward declarations
class Mesh;
class Ray;
/** A Bounding Volume Hierarchy (BVH) data structure that can be used to
accelerate ray-object intersection tests by carving up space into a hierarchy
of partitions represented in a tree. Each node of the tree is represented
as an AABB (Axis-Aligned Bounding Box) that contains all of the nodes under it.
Different objects can be stored inside each bounding box. For example, when
a BVH is created for a mesh, each leaf node can contain a AABB that contains
just a single triangle. Or, when a BVH is created for an entire scene, you
could have each leaf node contain an entire mesh or other object within the
scene. In each case, use AABB's set_user_data() and user_data() methods to
store a handle for whetever you want to store inside the nodes.
*/
class BVH {
public:
/// Initializes the class with an empty hierarchy.
BVH();
virtual ~BVH();
/** Creates a bounding volume hierarchy where each leaf node contains a single
triangle from the mesh. For leaf nodes, the triangle index can be retrieved
with:
~~~
int tri_id = leafnode->box.user_data();
~~~
The user_data will be -1 for non-leaf nodes. Once the structure has been
created, it can be used to perform fast ray-mesh intersection tests. See
Ray::FastIntersectMesh().
*/
void CreateFromMesh(const Mesh &mesh);
/** Creates a BVH where each leaf node contains one of the boxes passed in
to the function.
*/
void CreateFromListOfBoxes(const std::vector<AABB> &boxes);
/** Traverse the BVH to find leaf nodes whose AABBs are intersected by the
ray. These are candidates to test more thoroughly using whatever ray-object
intersection test is appropriate for the objects stored inside the AABB.
This routine returns the user_data for each AABB leaf node. In the case of
a BVH created using CreateFromMesh, this means it stores the indices to
the mesh triangles that should be tested for ray-triangle intersection.
*/
std::vector<int> IntersectAndReturnUserData(const Ray &r) const;
private:
// Simple internal data structure for storing each node of the BVH tree.
class Node {
public:
Node() : child1(NULL), child2(NULL) {}
// Links to children
Node *child1;
Node *child2;
// Contains all geometry below this node.
AABB box;
};
// for now, the copy constructor is private so no copies are allowed.
// eventually, this would be good to implement and then it can be made public.
BVH(const BVH &other);
void BuildHierarchyRecursive(Node *node, std::vector<AABB> boxes);
void IntersectRecursive(const Ray &r, Node *node, std::vector<int> *data_list) const;
void FreeNodeRecursive(Node* node);
Node* root_;
};
} // end namespace
#endif
|
