[Bf-blender-cvs] [0beb3002f27] soc-2020-soft-body: added BVH
over0219
noreply at git.blender.org
Tue Jun 16 22:51:42 CEST 2020
Commit: 0beb3002f27642b442f01e991ffcc4db76585cef
Author: over0219
Date: Tue Jun 16 12:26:16 2020 -0500
Branches: soc-2020-soft-body
https://developer.blender.org/rB0beb3002f27642b442f01e991ffcc4db76585cef
added BVH
===================================================================
M extern/softbody/CMakeLists.txt
A extern/softbody/LICENSE
A extern/softbody/src/admmpd_bvh.cpp
A extern/softbody/src/admmpd_bvh.h
M extern/softbody/src/admmpd_collision.cpp
M extern/softbody/src/admmpd_collision.h
M extern/softbody/src/admmpd_energy.cpp
M extern/softbody/src/admmpd_energy.h
M extern/softbody/src/admmpd_lattice.cpp
M extern/softbody/src/admmpd_lattice.h
M extern/softbody/src/admmpd_math.cpp
M extern/softbody/src/admmpd_math.h
M extern/softbody/src/admmpd_solver.cpp
M extern/softbody/src/admmpd_solver.h
===================================================================
diff --git a/extern/softbody/CMakeLists.txt b/extern/softbody/CMakeLists.txt
index 05caac30633..63961cbb334 100644
--- a/extern/softbody/CMakeLists.txt
+++ b/extern/softbody/CMakeLists.txt
@@ -24,7 +24,7 @@ set(INC
set(INC_SYS
${EIGEN3_INCLUDE_DIRS}
- ../../source/blender/blenlib
+ ../../source/blender/blenlib # BLI_task for threading
)
set(SRC
@@ -38,6 +38,10 @@ set(SRC
src/admmpd_solver.cpp
src/admmpd_collision.h
src/admmpd_collision.cpp
+ src/admmpd_bvh.h
+ src/admmpd_bvh.cpp
+ src/admmpd_bvh_traverse.h
+ src/admmpd_bvh_traverse.cpp
)
set(LIB
diff --git a/extern/softbody/LICENSE b/extern/softbody/LICENSE
new file mode 100644
index 00000000000..dcd0e693ed1
--- /dev/null
+++ b/extern/softbody/LICENSE
@@ -0,0 +1,21 @@
+The MIT License (MIT)
+
+Copyright (c) 2020 Matthew Overby
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/extern/softbody/src/admmpd_bvh.cpp b/extern/softbody/src/admmpd_bvh.cpp
new file mode 100644
index 00000000000..97c39271199
--- /dev/null
+++ b/extern/softbody/src/admmpd_bvh.cpp
@@ -0,0 +1,222 @@
+// Copyright Matt Overby 2020.
+// Distributed under the MIT License.
+
+#include "admmpd_bvh.h"
+#include <numeric> // iota
+
+// Adapted from:
+// https://github.com/mattoverby/mclscene/blob/master/include/MCL/BVH.hpp
+
+namespace admmpd {
+
+template <typename T, int DIM>
+void AABBTree<T,DIM>::clear()
+{
+ root = std::make_shared<Node>();
+}
+
+template <typename T, int DIM>
+void AABBTree<T,DIM>::init(const std::vector<AABB> &leaves)
+{
+ root = std::make_shared<Node>();
+ int np = leaves.size();
+ if (np==0)
+ return;
+ std::vector<int> queue(np);
+ std::iota(queue.begin(), queue.end(), 0);
+ create_children(root.get(), queue, leaves);
+}
+
+template <typename T, int DIM>
+void AABBTree<T,DIM>::update(const std::vector<AABB> &leaves)
+{
+ if (!root || (int)leaves.size()==0)
+ return;
+ update_children(root.get(), leaves);
+}
+
+template <typename T, int DIM>
+bool AABBTree<T,DIM>::traverse(Traverser<T,DIM> &traverser) const
+{
+ if (!root)
+ return false;
+ return traverse_children(root.get(), traverser);
+}
+
+// If we are traversing with function pointers, we'll just
+// wrap our own traverser that calls these functions to
+// avoid duplicate traverse_children code.
+template <typename T, int DIM>
+class TraverserFromFunctionPtrs : public Traverser<T,DIM>
+{
+using typename Traverser<T,DIM>::AABB;
+public:
+ std::function<void(const AABB&, bool&, const AABB&, bool&, bool&)> t;
+ std::function<bool(const AABB&, int)> s;
+ void traverse(
+ const AABB &left_aabb, bool &go_left,
+ const AABB &right_aabb, bool &go_right,
+ bool &go_left_first)
+ {
+ t(left_aabb, go_left, right_aabb, go_right, go_left_first);
+ }
+ bool stop_traversing(const AABB &aabb, int prim)
+ {
+ return s(aabb,prim);
+ }
+};
+
+template <typename T, int DIM>
+bool AABBTree<T,DIM>::traverse(
+ std::function<void(const AABB&, bool&, const AABB&, bool&, bool&)> t,
+ std::function<bool(const AABB&, int)> s) const
+{
+ if (!root)
+ return false;
+ TraverserFromFunctionPtrs<T,DIM> traverser;
+ traverser.t = t;
+ traverser.s = s;
+ return traverse_children(root.get(), traverser);
+}
+
+template <typename T, int DIM>
+void AABBTree<T,DIM>::create_children(
+ Node *node,
+ std::vector<int> &queue,
+ const std::vector<AABB> &leaves)
+{
+ node->aabb.setEmpty();
+ int n_queue = queue.size();
+ if (n_queue == 1)
+ {
+ node->prims.emplace_back(queue[0]);
+ node->aabb = leaves[queue[0]];
+ return;
+ }
+
+ for (int i=0; i<n_queue; ++i)
+ {
+ int q = queue[i];
+ node->aabb.extend(leaves[q]);
+ }
+
+ struct SortByAxis
+ {
+ int axis;
+ const std::vector<AABB> &aabbs;
+ SortByAxis(int axis_, const std::vector<AABB> &aabbs_) :
+ axis(axis_), aabbs(aabbs_) {}
+ bool operator()(size_t l, size_t r) const
+ {
+ return aabbs[l].center()[axis] < aabbs[r].center()[axis];
+ }
+ };
+
+ // Sort tree and split queue
+ int sort_axis = 0;
+ VecType sizes = node->aabb.sizes();
+ sizes.maxCoeff(&sort_axis);
+ std::sort(queue.begin(), queue.end(), SortByAxis(sort_axis,leaves));
+ std::vector<int> left_queue(queue.begin(), queue.begin()+(n_queue/2));
+ std::vector<int> right_queue(queue.begin()+(n_queue/2), queue.end());
+
+ // Recursive top-down constructrion
+ node->left = new Node();
+ create_children(node->left, left_queue, leaves);
+ node->right = new Node();
+ create_children(node->right, right_queue, leaves);
+
+} // end create children
+
+template <typename T, int DIM>
+void AABBTree<T,DIM>::update_children(
+ Node *node,
+ const std::vector<AABB> &leaves)
+{
+ node->aabb.setEmpty();
+
+ if (node->is_leaf())
+ {
+ int np = node->prims.size();
+ for (int i=0; i<np; ++i)
+ {
+ node->aabb.extend(leaves[node->prims[i]]);
+ }
+ return;
+ }
+
+ if (node->left != nullptr)
+ {
+ update_children(node->left, leaves);
+ node->aabb.extend(node->left->aabb);
+ }
+ if (node->right != nullptr)
+ {
+ update_children(node->right, leaves);
+ node->aabb.extend(node->right->aabb);
+ }
+
+} // end update children
+
+template <typename T, int DIM>
+bool AABBTree<T,DIM>::traverse_children(
+ const Node *node,
+ Traverser<T,DIM> &traverser ) const
+{
+ if( node->is_leaf() ){
+ int np = node->prims.size();
+ for(int i=0; i<np; ++i)
+ {
+ if(traverser.stop_traversing(node->aabb, node->prims[i]))
+ return true;
+ }
+ return false;
+ }
+
+ bool go_left = true;
+ bool go_right = true;
+ bool go_left_first = true;
+ const AABB &left_aabb = (node->left == nullptr ? AABB() : node->left->aabb);
+ const AABB &right_aabb = (node->right == nullptr ? AABB() : node->right->aabb);
+ traverser.traverse(
+ left_aabb, go_left,
+ right_aabb, go_right,
+ go_left_first );
+
+ if (go_left && go_right)
+ {
+ if (go_left_first)
+ {
+ if (traverse_children(node->left, traverser)) { return true; }
+ else { return traverse_children(node->right, traverser); }
+ }
+ else
+ {
+ if (traverse_children(node->right, traverser)) { return true; }
+ else { return traverse_children(node->left, traverser); }
+ }
+ }
+ if (go_left && !go_right)
+ {
+ return traverse_children(node->left, traverser);
+ }
+ if (!go_left && go_right)
+ {
+ return traverse_children(node->right, traverser);
+ }
+
+ return false;
+
+} // end traverse children
+
+// Compile types
+template class admmpd::AABBTree<double,2>;
+template class admmpd::AABBTree<double,3>;
+template class admmpd::AABBTree<float,2>;
+template class admmpd::AABBTree<float,3>;
+template class admmpd::TraverserFromFunctionPtrs<double,2>;
+template class admmpd::TraverserFromFunctionPtrs<double,3>;
+template class admmpd::TraverserFromFunctionPtrs<float,2>;
+template class admmpd::TraverserFromFunctionPtrs<float,3>;
+
+} // namespace admmpd
\ No newline at end of file
diff --git a/extern/softbody/src/admmpd_bvh.h b/extern/softbody/src/admmpd_bvh.h
new file mode 100644
index 00000000000..dca84e6803f
--- /dev/null
+++ b/extern/softbody/src/admmpd_bvh.h
@@ -0,0 +1,81 @@
+// 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;
+
+protected:
+
+ struct Node
+ {
+ AABB aabb;
+ Node *left, *right;
+ std::vector<int> prims;
+ bool is_leaf() const { return prims.size()>0; }
+ Node() : left(nullptr), right(nullptr) {}
+ ~Node()
+ {
+ if(left){ delete left; }
+ if(right){ delete right; }
+ }
+ };
+
+ 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
+
+} // namespace admmpd
+
+#endif // ADMMPD_BVH_H_
+
diff --g
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list