diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2020-08-30 20:47:18 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2020-08-30 20:47:18 +0300 |
commit | 19c9b27ffe55470758637cfbfb11567611170388 (patch) | |
tree | 4abd406ac76e5b47b19acffa1d0674346a95f63e /source/blender/blenlib/intern | |
parent | ade8d84fe3f744e751e14904df7183343aa4c0ed (diff) |
New boolean: another performance improvement.
Instead of calculating exact normals for all faces, just do it
for those that potentially intersect. A big improvement for dense
meshes that only intersect in relatively few places.
Diffstat (limited to 'source/blender/blenlib/intern')
-rw-r--r-- | source/blender/blenlib/intern/mesh_intersect.cc | 63 |
1 files changed, 25 insertions, 38 deletions
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc index 39611953f37..f70f10ac708 100644 --- a/source/blender/blenlib/intern/mesh_intersect.cc +++ b/source/blender/blenlib/intern/mesh_intersect.cc @@ -48,7 +48,7 @@ # include "BLI_mesh_intersect.hh" -//# define PERFDEBUG +// # define PERFDEBUG namespace blender::meshintersect { @@ -2402,6 +2402,7 @@ class TriOverlaps { BVHTree *tree_{nullptr}; BVHTree *tree_b_{nullptr}; BVHTreeOverlap *overlap_{nullptr}; + Array<int> first_overlap_; uint overlap_tot_{0}; struct CBData { @@ -2458,12 +2459,8 @@ class TriOverlaps { } else { CBData cbdata{tm, shape_fn, nshapes, use_self}; - if (nshapes == 1 && use_self) { - /* Expect a lot of trivial intersects from quads that are triangulated - * and faces that share vertices. - * Filter them out with a callback. */ - overlap_ = BLI_bvhtree_overlap( - tree_, tree_, &overlap_tot_, only_nontrivial_intersects, &cbdata); + if (nshapes == 1) { + overlap_ = BLI_bvhtree_overlap(tree_, tree_, &overlap_tot_, NULL, NULL); } else { overlap_ = BLI_bvhtree_overlap( @@ -2490,6 +2487,13 @@ class TriOverlaps { std::cout << "A: " << ov.indexA << ", B: " << ov.indexB << "\n"; } } + first_overlap_ = Array<int>(tm.face_size(), -1); + for (int i = 0; i < static_cast<int>(overlap_tot_); ++i) { + int t = overlap_[i].indexA; + if (first_overlap_[t] == -1) { + first_overlap_[t] = i; + } + } } ~TriOverlaps() @@ -2510,16 +2514,12 @@ class TriOverlaps { return Span<BVHTreeOverlap>(overlap_, overlap_tot_); } - private: - static bool only_nontrivial_intersects(void *userdata, - int index_a, - int index_b, - int UNUSED(thread)) + int first_overlap_index(int t) const { - CBData *cbdata = static_cast<CBData *>(userdata); - return may_non_trivially_intersect(cbdata->tm.face(index_a), cbdata->tm.face(index_b)); + return first_overlap_[t]; } + private: static bool only_different_shapes(void *userdata, int index_a, int index_b, int UNUSED(thread)) { CBData *cbdata = static_cast<CBData *>(userdata); @@ -2730,24 +2730,6 @@ static void calc_subdivided_tris(Array<IMesh> &r_tri_subdivided, 0, overlap_tri_range_tot, &data, calc_subdivided_tri_range_func, &settings); } -/* Get first index in ov where indexA == t. Assuming sorted on indexA. */ -static int find_first_overlap_index(const TriOverlaps &ov, int t) -{ - Span<BVHTreeOverlap> span = ov.overlap(); - if (span.size() == 0) { - return -1; - } - BVHTreeOverlap bo{t, -1}; - const BVHTreeOverlap *p = std::lower_bound( - span.begin(), span.end(), bo, [](const BVHTreeOverlap &o1, const BVHTreeOverlap &o2) { - return o1.indexA < o2.indexA; - }); - if (p != span.end()) { - return p - span.begin(); - } - return -1; -} - static CDT_data calc_cluster_subdivided(const CoplanarClusterInfo &clinfo, int c, const IMesh &tm, @@ -2771,7 +2753,7 @@ static CDT_data calc_cluster_subdivided(const CoplanarClusterInfo &clinfo, if (dbg_level > 0) { std::cout << "find intersects with triangle " << t << " of cluster\n"; } - int first_i = find_first_overlap_index(ov, t); + int first_i = ov.first_overlap_index(t); if (first_i == -1) { continue; } @@ -3076,10 +3058,6 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in, std::cout << "cleaned input mesh:\n" << tm_cleaned; } } - /* Temporary, while developing: populate all plane normals exactly. */ - for (Face *f : tm_clean->faces()) { - f->populate_plane(true); - } # ifdef PERFDEBUG double clean_time = PIL_check_seconds_timer(); std::cout << "cleaned, time = " << clean_time - start_time << "\n"; @@ -3094,6 +3072,15 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in, double overlap_time = PIL_check_seconds_timer(); std::cout << "intersect overlaps calculated, time = " << overlap_time - bb_calc_time << "\n"; # endif + for (int t : tm_clean->face_index_range()) { + if (tri_ov.first_overlap_index(t) != -1) { + tm_clean->face(t)->populate_plane(true); + } + } +# ifdef PERFDEBUG + double plane_populate = PIL_check_seconds_timer(); + std::cout << "planes populated, time = " << plane_populate - overlap_time << "\n"; +# endif /* itt_map((a,b)) will hold the intersection value resulting from intersecting * triangles with indices a and b, where a < b. */ Map<std::pair<int, int>, ITT_value> itt_map; @@ -3101,7 +3088,7 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in, calc_overlap_itts(itt_map, *tm_clean, tri_ov, arena); # ifdef PERFDEBUG double itt_time = PIL_check_seconds_timer(); - std::cout << "itts found, time = " << itt_time - overlap_time << "\n"; + std::cout << "itts found, time = " << itt_time - plane_populate << "\n"; # endif CoplanarClusterInfo clinfo = find_clusters(*tm_clean, tri_bb, itt_map); if (dbg_level > 1) { |