[Bf-blender-cvs] [ad81b1993e0] newboolean: Speedup, using BVH tree to limit number of tri-tri intersect tests.
Howard Trickey
noreply at git.blender.org
Tue Jul 14 14:04:43 CEST 2020
Commit: ad81b1993e0eb153b5436eeb5aa88bea8282b8be
Author: Howard Trickey
Date: Tue Jul 14 08:01:50 2020 -0400
Branches: newboolean
https://developer.blender.org/rBad81b1993e0eb153b5436eeb5aa88bea8282b8be
Speedup, using BVH tree to limit number of tri-tri intersect tests.
Intersection of my spheresphere test with n=16 (two uvspheres
with 16 rings and 32 segments overlapping), time went from
12.8 seconds to 2.3 seconds on my Mac. The n=32 test went from
195.1s to 8.9s.
===================================================================
M source/blender/blenlib/BLI_float2.hh
M source/blender/blenlib/BLI_mpq2.hh
M source/blender/blenlib/intern/delaunay_2d.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M tests/gtests/blenlib/BLI_mesh_intersect_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_float2.hh b/source/blender/blenlib/BLI_float2.hh
index 3ed9822c388..b7d07aac23e 100644
--- a/source/blender/blenlib/BLI_float2.hh
+++ b/source/blender/blenlib/BLI_float2.hh
@@ -158,7 +158,6 @@ struct float2 {
{
return !(a == b);
}
-
};
} // namespace blender
diff --git a/source/blender/blenlib/BLI_mpq2.hh b/source/blender/blenlib/BLI_mpq2.hh
index c3a7a6bcd5b..fc4702e4c01 100644
--- a/source/blender/blenlib/BLI_mpq2.hh
+++ b/source/blender/blenlib/BLI_mpq2.hh
@@ -34,13 +34,12 @@ struct mpq2 {
mpq2(mpq_class x, mpq_class y) : x(x), y(y)
{
}
-
+
mpq2(const mpq2 &other) : x(other.x), y(other.y)
{
}
-
- mpq2(mpq2 &&other) noexcept
- : x(std::move(other.x)), y(std::move(other.y))
+
+ mpq2(mpq2 &&other) noexcept : x(std::move(other.x)), y(std::move(other.y))
{
}
@@ -54,7 +53,7 @@ struct mpq2 {
}
return *this;
}
-
+
mpq2 &operator=(mpq2 &&other) noexcept
{
x = std::move(other.x);
diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc
index 255794b3018..f03ec611117 100644
--- a/source/blender/blenlib/intern/delaunay_2d.cc
+++ b/source/blender/blenlib/intern/delaunay_2d.cc
@@ -1290,12 +1290,14 @@ template<typename T> class CrossData {
{
}
CrossData(const CrossData &other)
- : lambda(other.lambda), vert(other.vert), in(other.in), out(other.out)
+ : lambda(other.lambda), vert(other.vert), in(other.in), out(other.out)
{
}
CrossData(CrossData &&other) noexcept
- : lambda(std::move(other.lambda)), vert(std::move(other.vert)),
- in(std::move(other.in)), out(std::move(other.out))
+ : lambda(std::move(other.lambda)),
+ vert(std::move(other.vert)),
+ in(std::move(other.in)),
+ out(std::move(other.out))
{
}
~CrossData() = default;
@@ -2003,23 +2005,23 @@ template<typename T> struct EdgeToSort {
CDTEdge<T> *e{nullptr};
EdgeToSort() = default;
- EdgeToSort(const EdgeToSort &other)
- : len_squared(other.len_squared), e(other.e)
+ EdgeToSort(const EdgeToSort &other) : len_squared(other.len_squared), e(other.e)
{
}
- EdgeToSort(EdgeToSort &&other) noexcept
- : len_squared(std::move(other.len_squared)), e(other.e)
+ EdgeToSort(EdgeToSort &&other) noexcept : len_squared(std::move(other.len_squared)), e(other.e)
{
}
~EdgeToSort() = default;
- EdgeToSort &operator=(const EdgeToSort &other) {
+ EdgeToSort &operator=(const EdgeToSort &other)
+ {
if (this != &other) {
len_squared = other.len_squared;
e = other.e;
}
return *this;
}
- EdgeToSort &operator=(EdgeToSort &&other) {
+ EdgeToSort &operator=(EdgeToSort &&other)
+ {
len_squared = std::move(other.len_squared);
e = other.e;
return *this;
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 831e34b2431..8e6e1752fa3 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -22,7 +22,9 @@
#include "BLI_assert.h"
#include "BLI_delaunay_2d.h"
#include "BLI_double3.hh"
+#include "BLI_float3.hh"
#include "BLI_hash.hh"
+#include "BLI_kdopbvh.h"
#include "BLI_map.hh"
#include "BLI_math_mpq.hh"
#include "BLI_mpq2.hh"
@@ -575,6 +577,119 @@ std::ostream &operator<<(std::ostream &os, const Mesh &mesh)
return os;
}
+struct BoundingBox {
+ float3 min{FLT_MAX, FLT_MAX, FLT_MAX};
+ float3 max{-FLT_MAX, -FLT_MAX, -FLT_MAX};
+
+ BoundingBox() = default;
+ BoundingBox(const float3 &min, const float3 &max) : min(min), max(max)
+ {
+ }
+ BoundingBox(const BoundingBox &other) : min(other.min), max(other.max)
+ {
+ }
+ BoundingBox(BoundingBox &&other) noexcept : min(std::move(other.min)), max(std::move(other.max))
+ {
+ }
+ ~BoundingBox() = default;
+ BoundingBox operator=(const BoundingBox &other)
+ {
+ if (this != &other) {
+ min = other.min;
+ max = other.max;
+ }
+ return *this;
+ }
+ BoundingBox operator=(BoundingBox &&other) noexcept
+ {
+ min = std::move(other.min);
+ max = std::move(other.max);
+ return *this;
+ }
+
+ void combine(const float3 &p)
+ {
+ min.x = min_ff(min.x, p.x);
+ min.y = min_ff(min.y, p.y);
+ min.z = min_ff(min.z, p.z);
+ max.x = max_ff(max.x, p.x);
+ max.y = max_ff(max.y, p.y);
+ max.z = max_ff(max.z, p.z);
+ }
+
+ void combine(const double3 &p)
+ {
+ min.x = min_ff(min.x, static_cast<float>(p.x));
+ min.y = min_ff(min.y, static_cast<float>(p.y));
+ min.z = min_ff(min.z, static_cast<float>(p.z));
+ max.x = max_ff(max.x, static_cast<float>(p.x));
+ max.y = max_ff(max.y, static_cast<float>(p.y));
+ max.z = max_ff(max.z, static_cast<float>(p.z));
+ }
+
+ void combine(const BoundingBox &bb)
+ {
+ min.x = min_ff(min.x, bb.min.x);
+ min.y = min_ff(min.y, bb.min.y);
+ min.z = min_ff(min.z, bb.min.z);
+ max.x = max_ff(max.x, bb.max.x);
+ max.y = max_ff(max.y, bb.max.y);
+ max.z = max_ff(max.z, bb.max.z);
+ }
+
+ void expand(float pad)
+ {
+ min.x -= pad;
+ min.y -= pad;
+ min.z -= pad;
+ max.x += pad;
+ max.y += pad;
+ max.z += pad;
+ }
+};
+
+/* Assume bounding boxes have been expanded by a sufficient epislon on all sides
+ * so that the comparisons against the bb bounds are sufficient to guarantee that
+ * if an overlap or even touching could happen, this will return true.
+ */
+static bool bbs_might_intersect(const BoundingBox &bb_a, const BoundingBox &bb_b)
+{
+ return isect_aabb_aabb_v3(bb_a.min, bb_a.max, bb_b.min, bb_b.max);
+}
+
+/* We will expand the bounding boxes by an epsilon on all sides so that
+ * the "less than" tests in isect_aabb_aabb_v3 are sufficient to detect
+ * touching or overlap.
+ */
+static Array<BoundingBox> calc_face_bounding_boxes(const Mesh &m)
+{
+ double max_abs_val = 0.0;
+ Array<BoundingBox> ans(m.face_size());
+ for (uint f : m.face_index_range()) {
+ const Face &face = *m.face(f);
+ BoundingBox &bb = ans[f];
+ for (Vertp v : face) {
+ bb.combine(v->co);
+ for (int i = 0; i < 3; ++i) {
+ max_abs_val = max_dd(max_abs_val, fabs(v->co[i]));
+ }
+ }
+ }
+ float pad;
+ constexpr float pad_factor = 10.0f;
+ if (max_abs_val == 0.0f) {
+ pad = FLT_EPSILON;
+ }
+ else {
+ pad = 2 * FLT_EPSILON * max_abs_val;
+ }
+ pad *= pad_factor; /* For extra safety. */
+ for (uint f : m.face_index_range()) {
+ ans[f].expand(pad);
+ }
+ return ans;
+}
+
/* A cluster of coplanar triangles, by index.
* A pair of triangles T0 and T1 is said to "nontrivially coplanar-intersect"
* if they are coplanar, intersect, and their intersection is not just existing
@@ -585,19 +700,19 @@ std::ostream &operator<<(std::ostream &os, const Mesh &mesh)
*/
class CoplanarCluster {
Vector<uint> tris_;
+ BoundingBox bb_;
public:
CoplanarCluster() = default;
- explicit CoplanarCluster(uint t)
+ CoplanarCluster(uint t, const BoundingBox &bb)
{
- this->add_tri(t);
+ this->add_tri(t, bb);
}
- CoplanarCluster(const CoplanarCluster &other)
- : tris_(other.tris_)
+ CoplanarCluster(const CoplanarCluster &other) : tris_(other.tris_), bb_(other.bb_)
{
}
CoplanarCluster(CoplanarCluster &&other) noexcept
- : tris_(std::move(other.tris_))
+ : tris_(std::move(other.tris_)), bb_(std::move(other.bb_))
{
}
~CoplanarCluster() = default;
@@ -605,19 +720,22 @@ class CoplanarCluster {
{
if (this != &other) {
tris_ = other.tris_;
+ bb_ = other.bb_;
}
return *this;
}
CoplanarCluster &operator=(CoplanarCluster &&other) noexcept
{
tris_ = std::move(other.tris_);
+ bb_ = std::move(other.bb_);
return *this;
}
/* Assume that caller knows this will not be a duplicate. */
- void add_tri(uint t)
+ void add_tri(uint t, const BoundingBox &bb)
{
tris_.append(t);
+ bb_ = bb;
}
uint tot_tri() const
{
@@ -635,6 +753,11 @@ class CoplanarCluster {
{
return tris_.end();
}
+
+ const BoundingBox &bounding_box() const
+ {
+ return bb_;
+ }
};
/* Maintains indexed set of CoplanarCluster, with the added ability
@@ -725,18 +848,21 @@ struct ITT_value {
{
}
ITT_value(const ITT_value &other)
- : kind(other.kind), p1(other.p1), p2(other.p2), t_source(other.t_source)
+ : kind(other.kind), p1(other.p1), p2(other.p2), t_source(other.t_source)
{
}
ITT_value(ITT_value &&other) noexcept
- : kind(other.kind), p1(std::move(other.p1)), p2(std::move(other.p2)),
- t_source(other.t_source)
+ : kind(other.kind),
+ p1(std::move(other.p1)),
+ p2(std::move(other.p2)),
+ t_source(other.t_source)
{
}
~ITT_value()
{
}
- ITT_value &operator=(const ITT_value &other) {
+ ITT_value &operator=(const ITT_value &other)
+ {
if (this != &other) {
kind = other.kind;
p1 = other.p1;
@@ -1431,43 +1557,85 @@ static Mesh extract_single_tri(const Mesh &tm, uint t)
return Mesh({f});
}
-static Mesh calc_tri_subdivided(const Mesh &in_tm, uint t, MArena *arena)
+static bool bvhtreeverlap_cmp(const BVHTreeOverlap &a, const BVHTreeOverlap &b)
{
- constexpr int dbg_level = 0;
- Vector<Facep> faces;
+ if (a.indexA < b.indexA) {
+ return true;
+ }
+ if (a.indexA == b.indexA & a.indexB < b.indexB) {
+ return true;
+ }
+ return false;
+}
+/* For each triangle in tm, fill in the corresponding slot in
+ * r_tri_subdivided with the result of intersecting it with
+ * all the other triangles in the mesh, if it intersects any others.
+ * But don't do this for triangles that are part of a cluster.
+ * Also, do nothing here if the answer is just the triangle itself.
+ * TODO: parallelize this loop.
+ */
+static void calc_subdivided_tris(Array<Mesh> &r_tri_subdivided,
+ const Mesh &tm,
+ const CoplanarClusterInfo &clinfo,
+ BVHTree *tri_tree,
+ MArena *arena)
+{
+ const int dbg_level = 0;
if (dbg_level > 0) {
- std::cout << "\ncalc_tri_subdivided for tri " << t << "\n\n";
+ std::cout << "\nCALC_SUBDIVIDED_TR
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list