[Bf-blender-cvs] [dc960a81d1b] master: Boolean exact: speedup when there are many components.

[Howard Trickey]

Commit: dc960a81d1bdc8c91a6967f85d1943896b06dc47
Author: Howard Trickey
Date:   Wed Jun 2 11:18:00 2021 -0700
Branches: master
https://developer.blender.org/rBdc960a81d1bdc8c91a6967f85d1943896b06dc47

Boolean exact: speedup when there are many components.

When there are many components (separate pieces of connected mesh),
a part of the algorithm to determine component containment was slow.
Using a float version of finding the nearest point on a triangle
as a prefilter sped this up enormously. A case of 25 icospheres
subdivided twice goes 11 seconds faster on my Macbook pro with this
change.

===================================================================

M	source/blender/blenlib/intern/mesh_boolean.cc

===================================================================

diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc
index cc27e9238c3..f74c17d6ee1 100644
--- a/source/blender/blenlib/intern/mesh_boolean.cc
+++ b/source/blender/blenlib/intern/mesh_boolean.cc
@@ -1829,6 +1829,19 @@ static mpq_class closest_on_tri_to_point(const mpq3 &p,
   return mpq3::distance_squared_with_buffer(p, r, m);
 }
 
+static float closest_on_tri_to_point_float_dist_squared(const float3 &p,
+                                                        const double3 &a,
+                                                        const double3 &b,
+                                                        const double3 &c)
+{
+  float3 fa, fb, fc, closest;
+  copy_v3fl_v3db(fa, a);
+  copy_v3fl_v3db(fb, b);
+  copy_v3fl_v3db(fc, c);
+  closest_on_tri_to_point_v3(closest, p, fa, fb, fc);
+  return len_squared_v3v3(p, closest);
+}
+
 struct ComponentContainer {
   int containing_component{NO_INDEX};
   int nearest_cell{NO_INDEX};
@@ -1865,6 +1878,8 @@ static Vector<ComponentContainer> find_component_containers(int comp,
   if (dbg_level > 0) {
     std::cout << "test vertex in comp: " << test_v << "\n";
   }
+  const double3 &test_v_d = test_v->co;
+  float3 test_v_f(test_v_d[0], test_v_d[1], test_v_d[2]);
 
   mpq3 buf[7];
 
@@ -1879,6 +1894,7 @@ static Vector<ComponentContainer> find_component_containers(int comp,
     int nearest_tri_close_vert = -1;
     int nearest_tri_close_edge = -1;
     mpq_class nearest_tri_dist_squared;
+    float nearest_tri_dist_squared_float = FLT_MAX;
     for (int p : components[comp_other]) {
       const Patch &patch = pinfo.patch(p);
       for (int t : patch.tris()) {
@@ -1888,6 +1904,12 @@ static Vector<ComponentContainer> find_component_containers(int comp,
         }
         int close_vert;
         int close_edge;
+        /* Try a cheap float test first. */
+        float d2_f = closest_on_tri_to_point_float_dist_squared(
+            test_v_f, tri[0]->co, tri[1]->co, tri[2]->co);
+        if (d2_f - FLT_EPSILON > nearest_tri_dist_squared_float) {
+          continue;
+        }
         mpq_class d2 = closest_on_tri_to_point(test_v->co_exact,
                                                tri[0]->co_exact,
                                                tri[1]->co_exact,
@@ -1910,6 +1932,7 @@ static Vector<ComponentContainer> find_component_containers(int comp,
           nearest_tri_close_edge = close_edge;
           nearest_tri_close_vert = close_vert;
           nearest_tri_dist_squared = d2;
+          nearest_tri_dist_squared_float = d2_f;
         }
       }
     }