summaryrefslogtreecommitdiffstats
path: root/dev/MinGfx/src/bvh.h
diff options
context:
space:
mode:
authorunknown <paulx161@umn.edu>2021-02-03 14:22:28 -0600
committerunknown <paulx161@umn.edu>2021-02-03 14:22:28 -0600
commit9b83919815f6a6ce5d73da1c28483970d0ca5589 (patch)
tree4558864445dccc1605e5315e0bb11c46d2018da1 /dev/MinGfx/src/bvh.h
parentAdded worksheet and support code for assignment 2 (diff)
downloadcsci4611-9b83919815f6a6ce5d73da1c28483970d0ca5589.tar
csci4611-9b83919815f6a6ce5d73da1c28483970d0ca5589.tar.gz
csci4611-9b83919815f6a6ce5d73da1c28483970d0ca5589.tar.bz2
csci4611-9b83919815f6a6ce5d73da1c28483970d0ca5589.tar.lz
csci4611-9b83919815f6a6ce5d73da1c28483970d0ca5589.tar.xz
csci4611-9b83919815f6a6ce5d73da1c28483970d0ca5589.tar.zst
csci4611-9b83919815f6a6ce5d73da1c28483970d0ca5589.zip
added dev/MinGfx/
Diffstat (limited to '')
-rw-r--r--dev/MinGfx/src/bvh.h106
1 files changed, 106 insertions, 0 deletions
diff --git a/dev/MinGfx/src/bvh.h b/dev/MinGfx/src/bvh.h
new file mode 100644
index 0000000..46b15ce
--- /dev/null
+++ b/dev/MinGfx/src/bvh.h
@@ -0,0 +1,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