diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2021-06-02 21:18:00 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2021-06-02 21:18:00 +0300 |
commit | dc960a81d1bdc8c91a6967f85d1943896b06dc47 (patch) | |
tree | 3ec69f212811d9bbb310240f6ab0525fedc8c41d /source/blender | |
parent | 4f8edc8e7fc9389b03543bc9a20f6c936e32b531 (diff) |
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.
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/intern/mesh_boolean.cc | 23 |
1 files changed, 23 insertions, 0 deletions
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; } } } |