diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2020-08-30 00:48:01 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2020-08-30 00:48:01 +0300 |
commit | 3789aa8506752df5edce8c072b4307443289f0d0 (patch) | |
tree | 03a01b441dc38e5648b24c4b2156ae535c2eec49 /source/blender/blenlib/intern/mesh_intersect.cc | |
parent | d8585e184aef90f80d1721c2c89eaf303c67e309 (diff) |
New Boolean: performance improvement.
Avoided cost of searching for coplanar clusters in many cases.
Diffstat (limited to 'source/blender/blenlib/intern/mesh_intersect.cc')
-rw-r--r-- | source/blender/blenlib/intern/mesh_intersect.cc | 72 |
1 files changed, 45 insertions, 27 deletions
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc index 8c412617b13..39611953f37 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 { @@ -1254,7 +1254,8 @@ static bool non_trivially_2d_intersect(const mpq2 *a[3], const mpq2 *b[3]) static bool non_trivially_coplanar_intersects(const IMesh &tm, int t, const CoplanarCluster &cl, - int proj_axis) + int proj_axis, + const Map<std::pair<int, int>, ITT_value> &itt_map) { const Face &tri = *tm.face(t); mpq2 v0 = project_3d_to_2d(tri[0]->co_exact, proj_axis); @@ -1266,6 +1267,10 @@ static bool non_trivially_coplanar_intersects(const IMesh &tm, v2 = tmp; } for (const int cl_t : cl) { + if (!itt_map.contains(std::pair<int, int>(t, cl_t)) && + !itt_map.contains(std::pair<int, int>(cl_t, t))) { + continue; + } const Face &cl_tri = *tm.face(cl_t); mpq2 ctv0 = project_3d_to_2d(cl_tri[0]->co_exact, proj_axis); mpq2 ctv1 = project_3d_to_2d(cl_tri[1]->co_exact, proj_axis); @@ -2572,12 +2577,9 @@ static void calc_overlap_itts_range_func(void *__restrict userdata, /** * Fill in itt_map with the vector of ITT_values that result from intersecting the triangles in ov. * Use a canonical order for triangles: (a,b) where a < b. - * Don't bother doing this if both a and b are part of the same co-planar cluster, as the - * intersection for those will be handled by CDT, later. */ static void calc_overlap_itts(Map<std::pair<int, int>, ITT_value> &itt_map, const IMesh &tm, - const CoplanarClusterInfo &clinfo, const TriOverlaps &ov, IMeshArena *arena) { @@ -2588,12 +2590,8 @@ static void calc_overlap_itts(Map<std::pair<int, int>, ITT_value> &itt_map, for (const BVHTreeOverlap &olap : ov.overlap()) { std::pair<int, int> key = canon_int_pair(olap.indexA, olap.indexB); if (!itt_map.contains(key)) { - int ca = clinfo.tri_cluster(key.first); - int cb = clinfo.tri_cluster(key.second); - if (ca == NO_INDEX || ca != cb) { - itt_map.add_new(key, ITT_value()); - data.intersect_pairs.append(key); - } + itt_map.add_new(key, ITT_value()); + data.intersect_pairs.append(key); } } int tot_intersect_pairs = data.intersect_pairs.size(); @@ -2818,19 +2816,40 @@ static IMesh union_tri_subdivides(const blender::Array<IMesh> &tri_subdivided) return IMesh(faces); } -static CoplanarClusterInfo find_clusters(const IMesh &tm, const Array<BoundingBox> &tri_bb) +static CoplanarClusterInfo find_clusters(const IMesh &tm, + const Array<BoundingBox> &tri_bb, + const Map<std::pair<int, int>, ITT_value> &itt_map) { constexpr int dbg_level = 0; if (dbg_level > 0) { std::cout << "FIND_CLUSTERS\n"; } CoplanarClusterInfo ans(tm.face_size()); + /* Use a VectorSet to get stable order from run to run. */ + VectorSet<int> maybe_coplanar_tris; + maybe_coplanar_tris.reserve(2 * itt_map.size()); + for (auto item : itt_map.items()) { + if (item.value.kind == ICOPLANAR) { + int t1 = item.key.first; + int t2 = item.key.second; + maybe_coplanar_tris.add_multiple({t1, t2}); + } + } + if (dbg_level > 0) { + std::cout << "found " << maybe_coplanar_tris.size() << " possible coplanar tris\n"; + } + if (maybe_coplanar_tris.size() == 0) { + if (dbg_level > 0) { + std::cout << "No possible coplanar tris, so no clusters\n"; + } + return ans; + } /* There can be more than one #CoplanarCluster per plane. Accumulate them in * a Vector. We will have to merge some elements of the Vector as we discover * triangles that form intersection bridges between two or more clusters. */ Map<Plane, Vector<CoplanarCluster>> plane_cls; - plane_cls.reserve(tm.face_size()); - for (int t : tm.face_index_range()) { + plane_cls.reserve(maybe_coplanar_tris.size()); + for (int t : maybe_coplanar_tris) { /* Use a canonical version of the plane for map index. * We can't just store the canonical version in the face * since canonicalizing loses the orientation of the normal. */ @@ -2855,7 +2874,7 @@ static CoplanarClusterInfo find_clusters(const IMesh &tm, const Array<BoundingBo std::cout << "consider intersecting with cluster " << cl << "\n"; } if (bbs_might_intersect(tri_bb[t], cl.bounding_box()) && - non_trivially_coplanar_intersects(tm, t, cl, proj_axis)) { + non_trivially_coplanar_intersects(tm, t, cl, proj_axis, itt_map)) { if (dbg_level > 1) { std::cout << "append to int_cls\n"; } @@ -3074,28 +3093,27 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in, # ifdef PERFDEBUG double overlap_time = PIL_check_seconds_timer(); std::cout << "intersect overlaps calculated, time = " << overlap_time - bb_calc_time << "\n"; - # endif - CoplanarClusterInfo clinfo = find_clusters(*tm_clean, tri_bb); + /* 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; + itt_map.reserve(tri_ov.overlap().size()); + 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"; +# endif + CoplanarClusterInfo clinfo = find_clusters(*tm_clean, tri_bb, itt_map); if (dbg_level > 1) { std::cout << clinfo; } # ifdef PERFDEBUG double find_cluster_time = PIL_check_seconds_timer(); - std::cout << "clusters found, time = " << find_cluster_time - overlap_time << "\n"; + std::cout << "clusters found, time = " << find_cluster_time - itt_time << "\n"; doperfmax(0, tm_in.face_size()); doperfmax(1, clinfo.tot_cluster()); doperfmax(2, tri_ov.overlap().size()); # 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; - itt_map.reserve(tri_ov.overlap().size()); - calc_overlap_itts(itt_map, *tm_clean, clinfo, tri_ov, arena); -# ifdef PERFDEBUG - double itt_time = PIL_check_seconds_timer(); - std::cout << "itts found, time = " << itt_time - find_cluster_time << "\n"; -# endif Array<IMesh> tri_subdivided(tm_clean->face_size()); calc_subdivided_tris(tri_subdivided, *tm_clean, itt_map, clinfo, tri_ov, arena); # ifdef PERFDEBUG |