From b8115f0c5bd91f6aa9d70eb6bafab61b2051b003 Mon Sep 17 00:00:00 2001 From: Howard Trickey Date: Mon, 5 Jul 2021 09:56:38 -0400 Subject: Fix performance regression in Exact boolean due to exact triangulation. Went back to using Blender's polyfill for triangulation, which is much faster (time for a 3.1M face boolean went from 103s to 48s). Had to put in detection for the case that needs the exact triangulator (bug T86805), and also a fix for non-convex quads (bug T89330). --- source/blender/blenlib/intern/mesh_intersect.cc | 137 +++++++++++++++++------- 1 file changed, 100 insertions(+), 37 deletions(-) (limited to 'source/blender/blenlib') diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc index 4882ad7d740..c8028231e81 100644 --- a/source/blender/blenlib/intern/mesh_intersect.cc +++ b/source/blender/blenlib/intern/mesh_intersect.cc @@ -1918,9 +1918,22 @@ static Face *cdt_tri_as_imesh_face( return facep; } +/* Like BLI_math's is_quad_flip_v3_first_third_fast_with_normal, with const double3's. */ +static bool is_quad_flip_first_third(const double3 &v1, + const double3 &v2, + const double3 &v3, + const double3 &v4, + const double3 &normal) +{ + double3 dir_v3v1 = v3 - v1; + double3 tangent = double3::cross_high_precision(dir_v3v1, normal); + double dot = double3::dot(v1, tangent); + return (double3::dot(v4, tangent) >= dot) || (double3::dot(v2, tangent) <= dot); +} + /** * Tessellate face f into triangles and return an array of `const Face *` - * giving that triangulation. Intended to be used when f has > 4 vertices. + * giving that triangulation. Intended to be used when f has => 4 vertices. * Care is taken so that the original edge index associated with * each edge in the output triangles either matches the original edge * for the (identical) edge of f, or else is -1. So diagonals added @@ -1934,15 +1947,34 @@ static Array polyfill_triangulate_poly(Face *f, IMeshArena *arena) { /* Similar to loop body in #BM_mesh_calc_tessellation. */ int flen = f->size(); - BLI_assert(flen > 4); + BLI_assert(flen >= 4); if (!f->plane_populated()) { f->populate_plane(false); } - /* Project along negative face normal so (x,y) can be used in 2d. */ const double3 &poly_normal = f->plane->norm; float no[3] = {float(poly_normal[0]), float(poly_normal[1]), float(poly_normal[2])}; normalize_v3(no); - float axis_mat[3][3]; + if (flen == 4) { + const Vert *v0 = (*f)[0]; + const Vert *v1 = (*f)[1]; + const Vert *v2 = (*f)[2]; + const Vert *v3 = (*f)[3]; + int eo_01 = f->edge_orig[0]; + int eo_12 = f->edge_orig[1]; + int eo_23 = f->edge_orig[2]; + int eo_30 = f->edge_orig[3]; + Face *f0, *f1; + if (UNLIKELY(is_quad_flip_first_third(v0->co, v1->co, v2->co, v3->co, f->plane->norm))) { + f0 = arena->add_face({v0, v1, v3}, f->orig, {eo_01, -1, eo_30}, {false, false, false}); + f1 = arena->add_face({v1, v2, v3}, f->orig, {eo_12, eo_23, -1}, {false, false, false}); + } + else { + f0 = arena->add_face({v0, v1, v2}, f->orig, {eo_01, eo_12, -1}, {false, false, false}); + f1 = arena->add_face({v0, v2, v3}, f->orig, {-1, eo_23, eo_30}, {false, false, false}); + } + return Array{f0, f1}; + } + /* Project along negative face normal so (x,y) can be used in 2d. */ float axis_mat[3][3]; float(*projverts)[2]; unsigned int(*tris)[3]; const int totfilltri = flen - 2; @@ -1986,11 +2018,7 @@ static Array polyfill_triangulate_poly(Face *f, IMeshArena *arena) /** * Tessellate face f into triangles and return an array of `const Face *` - * giving that triangulation. - * Care is taken so that the original edge index associated with - * each edge in the output triangles either matches the original edge - * for the (identical) edge of f, or else is -1. So diagonals added - * for triangulation can later be identified by having #NO_INDEX for original. + * giving that triangulation, using an exact triangulation method. * * The method used is to use the CDT triangulation. Usually that triangulation * will only use the existing vertices. However, if the face self-intersects @@ -2003,7 +2031,7 @@ static Array polyfill_triangulate_poly(Face *f, IMeshArena *arena) * is by far the usual case, we need to know if the quad is convex when * projected before doing so, and that takes a fair amount of computation by itself. */ -static Array triangulate_poly(Face *f, IMeshArena *arena) +static Array exact_triangulate_poly(Face *f, IMeshArena *arena) { int flen = f->size(); CDT_input cdt_in; @@ -2086,6 +2114,68 @@ static Array triangulate_poly(Face *f, IMeshArena *arena) return ans; } +static bool face_is_degenerate(const Face *f) +{ + const Face &face = *f; + const Vert *v0 = face[0]; + const Vert *v1 = face[1]; + const Vert *v2 = face[2]; + if (v0 == v1 || v0 == v2 || v1 == v2) { + return true; + } + double3 da = v2->co - v0->co; + double3 db = v2->co - v1->co; + double3 dab = double3::cross_high_precision(da, db); + double dab_length_squared = dab.length_squared(); + double err_bound = supremum_dot_cross(dab, dab) * index_dot_cross * DBL_EPSILON; + if (dab_length_squared > err_bound) { + return false; + } + mpq3 a = v2->co_exact - v0->co_exact; + mpq3 b = v2->co_exact - v1->co_exact; + mpq3 ab = mpq3::cross(a, b); + if (ab.x == 0 && ab.y == 0 && ab.z == 0) { + return true; + } + + return false; +} + +/** Fast check for degenerate tris. Only tests for when verts are identical, + * not cases where there are zero-length edges. */ +static bool any_degenerate_tris_fast(const Array triangulation) +{ + for (const Face *f : triangulation) { + const Vert *v0 = (*f)[0]; + const Vert *v1 = (*f)[1]; + const Vert *v2 = (*f)[2]; + if (v0 == v1 || v0 == v2 || v1 == v2) { + return true; + } + } + return false; +} + +/** + * Tessellate face f into triangles and return an array of `const Face *` + * giving that triangulation. + * Care is taken so that the original edge index associated with + * each edge in the output triangles either matches the original edge + * for the (identical) edge of f, or else is -1. So diagonals added + * for triangulation can later be identified by having #NO_INDEX for original. + */ +static Array triangulate_poly(Face *f, IMeshArena *arena) +{ + /* Try the much faster method using Blender's BLI_polyfill_calc. */ + Array ans = polyfill_triangulate_poly(f, arena); + + /* This may create degenerate triangles. If so, try the exact CDT-based triangulator. */ + if (any_degenerate_tris_fast(ans)) { + return exact_triangulate_poly(f, arena); + } + return ans; +} + /** * Return an #IMesh that is a triangulation of a mesh with general * polygonal faces, #IMesh. @@ -2725,33 +2815,6 @@ static CoplanarClusterInfo find_clusters(const IMesh &tm, return ans; } -static bool face_is_degenerate(const Face *f) -{ - const Face &face = *f; - const Vert *v0 = face[0]; - const Vert *v1 = face[1]; - const Vert *v2 = face[2]; - if (v0 == v1 || v0 == v2 || v1 == v2) { - return true; - } - double3 da = v2->co - v0->co; - double3 db = v2->co - v1->co; - double3 dab = double3::cross_high_precision(da, db); - double dab_length_squared = dab.length_squared(); - double err_bound = supremum_dot_cross(dab, dab) * index_dot_cross * DBL_EPSILON; - if (dab_length_squared > err_bound) { - return false; - } - mpq3 a = v2->co_exact - v0->co_exact; - mpq3 b = v2->co_exact - v1->co_exact; - mpq3 ab = mpq3::cross(a, b); - if (ab.x == 0 && ab.y == 0 && ab.z == 0) { - return true; - } - - return false; -} - /* Data and functions to test triangle degeneracy in parallel. */ struct DegenData { const IMesh &tm; -- cgit v1.2.3