diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2021-05-02 23:37:05 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2021-05-02 23:37:05 +0300 |
commit | 28bf1d4037496397e3bc5d69ce51d8ac9b8a2738 (patch) | |
tree | ed7bee1928c96cc6901f07dddf379e4edcf46329 /source/blender/blenlib/intern/mesh_boolean.cc | |
parent | 52e977d51895d25c24d0a70208b37f5c04762cec (diff) |
Fix T87554 Exact Boolean performance bug.
There was a quadratic algorithm extracting triangles from a coplanar
cluster. This is now linear.
Also found and fixed a bug in the same area related to the triangulator
added recently: it didn't get the right correspondence between new
edges and original edges.
Diffstat (limited to 'source/blender/blenlib/intern/mesh_boolean.cc')
-rw-r--r-- | source/blender/blenlib/intern/mesh_boolean.cc | 217 |
1 files changed, 1 insertions, 216 deletions
diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc index 16f2220af4c..25291b8c3b0 100644 --- a/source/blender/blenlib/intern/mesh_boolean.cc +++ b/source/blender/blenlib/intern/mesh_boolean.cc @@ -38,7 +38,6 @@ # include "BLI_math_mpq.hh" # include "BLI_mesh_intersect.hh" # include "BLI_mpq3.hh" -# include "BLI_polyfill_2d.h" # include "BLI_set.hh" # include "BLI_span.hh" # include "BLI_stack.hh" @@ -2680,224 +2679,10 @@ static IMesh raycast_patches_boolean(const IMesh &tm, } } BLI_bvhtree_free(tree); - ans.set_faces(out_faces); - return ans; -} -/** - * Tessellate face f into triangles and return an array of `const Face *` - * 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 - * for triangulation can later be identified by having #NO_INDEX for original. - * - * This code uses Blenlib's BLI_polyfill_calc to do triangulation, and is therefore quite fast. - * Unfortunately, it can product degenerate triangles that mesh_intersect will remove, leaving - * the mesh non-PWN. - */ -static Array<Face *> polyfill_triangulate_poly(Face *f, IMeshArena *arena) -{ - /* Similar to loop body in BM_mesh_calc_tesselation. */ - int flen = f->size(); - 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]; - float(*projverts)[2]; - unsigned int(*tris)[3]; - const int totfilltri = flen - 2; - /* Prepare projected vertices and array to receive triangles in tesselation. */ - tris = static_cast<unsigned int(*)[3]>(MEM_malloc_arrayN(totfilltri, sizeof(*tris), __func__)); - projverts = static_cast<float(*)[2]>(MEM_malloc_arrayN(flen, sizeof(*projverts), __func__)); - axis_dominant_v3_to_m3_negate(axis_mat, no); - for (int j = 0; j < flen; ++j) { - const double3 &dco = (*f)[j]->co; - float co[3] = {float(dco[0]), float(dco[1]), float(dco[2])}; - mul_v2_m3v3(projverts[j], axis_mat, co); - } - BLI_polyfill_calc(projverts, flen, 1, tris); - /* Put tesselation triangles into Face form. Record original edges where they exist. */ - Array<Face *> ans(totfilltri); - for (int t = 0; t < totfilltri; ++t) { - unsigned int *tri = tris[t]; - int eo[3]; - const Vert *v[3]; - for (int k = 0; k < 3; k++) { - BLI_assert(tri[k] < flen); - v[k] = (*f)[tri[k]]; - /* If tri edge goes between two successive indices in - * the original face, then it is an original edge. */ - if ((tri[k] + 1) % flen == tri[(k + 1) % 3]) { - eo[k] = f->edge_orig[tri[k]]; - } - else { - eo[k] = NO_INDEX; - } - ans[t] = arena->add_face( - {v[0], v[1], v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {false, false, false}); - } - } - - MEM_freeN(tris); - MEM_freeN(projverts); - - return ans; -} - -/** - * Which CDT output edge index is for an edge between output verts - * v1 and v2 (in either order)? - * \return -1 if none. - */ -static int find_cdt_edge(const CDT_result<mpq_class> &cdt_out, int v1, int v2) -{ - for (int e : cdt_out.edge.index_range()) { - const std::pair<int, int> &edge = cdt_out.edge[e]; - if ((edge.first == v1 && edge.second == v2) || (edge.first == v2 && edge.second == v1)) { - return e; - } - } - return -1; -} - -/** - * 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. - * - * The method used is to use the CDT triangulation. Usually that triangulation - * will only use the existing vertices. However, if the face self-intersects - * then the CDT triangulation will include the intersection points. - * If this happens, we use the polyfill triangulator instead. We don't - * use the polyfill triangulator by default because it can create degenerate - * triangles (which we can handle but they'll create non-manifold meshes). - */ -static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena) -{ - int flen = f->size(); - CDT_input<mpq_class> cdt_in; - cdt_in.vert = Array<mpq2>(flen); - cdt_in.face = Array<Vector<int>>(1); - cdt_in.face[0].reserve(flen); - for (int i : f->index_range()) { - cdt_in.face[0].append(i); - } - /* Project poly along dominant axis of normal to get 2d coords. */ - if (!f->plane_populated()) { - f->populate_plane(false); - } - const double3 &poly_normal = f->plane->norm; - int axis = double3::dominant_axis(poly_normal); - /* If project down y axis as opposed to x or z, the orientation - * of the polygon will be reversed. - * Yet another reversal happens if the poly normal in the dominant - * direction is opposite that of the positive dominant axis. */ - bool rev1 = (axis == 1); - bool rev2 = poly_normal[axis] < 0; - bool rev = rev1 ^ rev2; - for (int i = 0; i < flen; ++i) { - int ii = rev ? flen - i - 1 : i; - mpq2 &p2d = cdt_in.vert[ii]; - int k = 0; - for (int j = 0; j < 3; ++j) { - if (j != axis) { - p2d[k++] = (*f)[ii]->co_exact[j]; - } - } - } - CDT_result<mpq_class> cdt_out = delaunay_2d_calc(cdt_in, CDT_INSIDE); - int n_tris = cdt_out.face.size(); - Array<Face *> ans(n_tris); - for (int t = 0; t < n_tris; ++t) { - int i_v_out[3]; - const Vert *v[3]; - int eo[3]; - bool needs_steiner = false; - for (int i = 0; i < 3; ++i) { - i_v_out[i] = cdt_out.face[t][i]; - if (cdt_out.vert_orig[i_v_out[i]].size() == 0) { - needs_steiner = true; - break; - } - v[i] = (*f)[cdt_out.vert_orig[i_v_out[i]][0]]; - } - if (needs_steiner) { - /* Fall back on the polyfill triangulator. */ - return polyfill_triangulate_poly(f, arena); - } - for (int i = 0; i < 3; ++i) { - int e_out = find_cdt_edge(cdt_out, i_v_out[i], i_v_out[(i + 1) % 3]); - BLI_assert(e_out != -1); - eo[i] = NO_INDEX; - for (int orig : cdt_out.edge_orig[e_out]) { - if (orig != NO_INDEX) { - eo[i] = orig; - break; - } - } - } - if (rev) { - ans[t] = arena->add_face( - {v[0], v[2], v[1]}, f->orig, {eo[2], eo[1], eo[0]}, {false, false, false}); - } - else { - ans[t] = arena->add_face( - {v[0], v[1], v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {false, false, false}); - } - } + ans.set_faces(out_faces); return ans; } - -/** - * Return an #IMesh that is a triangulation of a mesh with general - * polygonal faces, #IMesh. - * Added diagonals will be distinguishable by having edge original - * indices of #NO_INDEX. - */ -static IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena) -{ - Vector<Face *> face_tris; - constexpr int estimated_tris_per_face = 3; - face_tris.reserve(estimated_tris_per_face * imesh.face_size()); - for (Face *f : imesh.faces()) { - /* Tessellate face f, following plan similar to #BM_face_calc_tesselation. */ - int flen = f->size(); - if (flen == 3) { - face_tris.append(f); - } - else 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 = arena->add_face({v0, v1, v2}, f->orig, {eo_01, eo_12, -1}, {false, false, false}); - Face *f1 = arena->add_face({v0, v2, v3}, f->orig, {-1, eo_23, eo_30}, {false, false, false}); - face_tris.append(f0); - face_tris.append(f1); - } - else { - Array<Face *> tris = triangulate_poly(f, arena); - for (Face *tri : tris) { - face_tris.append(tri); - } - } - } - return IMesh(face_tris); -} - /** * If \a tri1 and \a tri2 have a common edge (in opposite orientation), * return the indices into \a tri1 and \a tri2 where that common edge starts. Else return (-1,-1). |