blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 749 Projects 19 Wiki Activity

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.
This commit is contained in:
Howard Trickey 2021-06-02 11:18:00 -07:00
parent 4f8edc8e7f
commit dc960a81d1
1 changed files with 23 additions and 0 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

23
source/blender/blenlib/intern/mesh_boolean.cc
View File

@ -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;
}
}
}