[Bf-blender-cvs] [28bf1d40374] blender-v2.93-release: Fix T87554 Exact Boolean performance bug.
Howard Trickey
noreply at git.blender.org
Sun May 2 22:39:50 CEST 2021
Commit: 28bf1d4037496397e3bc5d69ce51d8ac9b8a2738
Author: Howard Trickey
Date: Sun May 2 16:37:05 2021 -0400
Branches: blender-v2.93-release
https://developer.blender.org/rB28bf1d4037496397e3bc5d69ce51d8ac9b8a2738
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.
===================================================================
M source/blender/blenlib/BLI_mesh_intersect.hh
M source/blender/blenlib/intern/mesh_boolean.cc
M source/blender/blenlib/intern/mesh_intersect.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_mesh_intersect.hh b/source/blender/blenlib/BLI_mesh_intersect.hh
index a7996939bb1..7000349c5af 100644
--- a/source/blender/blenlib/BLI_mesh_intersect.hh
+++ b/source/blender/blenlib/BLI_mesh_intersect.hh
@@ -357,6 +357,9 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in,
bool use_self,
IMeshArena *arena);
+/** Return an IMesh that is a triangulation of a mesh with general polygonal faces. */
+IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena);
+
/** This has the side effect of populating verts in the #IMesh. */
void write_obj_mesh(IMesh &m, const std::string &objname);
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).
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index ce3a5b55f98..3558dfad81d 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -39,6 +39,7 @@
# include "BLI_math_mpq.hh"
# include "BLI_mpq2.hh"
# include "BLI_mpq3.hh"
+# include "BLI_polyfill_2d.h"
# include "BLI_set.hh"
# include "BLI_span.hh"
# include "BLI_task.h"
@@ -1576,6 +1577,9 @@ struct CDT_data {
Vector<bool> is_reversed;
/** Result of running CDT on input with (vert, edge, face). */
CDT_result<mpq_class> cdt_out;
+ /** To speed up get_cdt_edge_orig, sometimes populate this map from vertex pair to output edge.
+ */
+ Map<std::pair<int, int>, int> verts_to_edge;
int proj_axis;
};
@@ -1734,6 +1738,32 @@ static CDT_data prepare_cdt_input_for_cluster(const IMesh &tm,
return ans;
}
+/* Return a copy of the argument wi
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list