Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/blenlib/intern/mesh_boolean.cc
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/blenlib/intern/mesh_boolean.cc')
-rw-r--r--source/blender/blenlib/intern/mesh_boolean.cc204
1 files changed, 134 insertions, 70 deletions
diff --git a/source/blender/blenlib/intern/mesh_boolean.cc b/source/blender/blenlib/intern/mesh_boolean.cc
index 9f7824a0029..8b8850c7cdb 100644
--- a/source/blender/blenlib/intern/mesh_boolean.cc
+++ b/source/blender/blenlib/intern/mesh_boolean.cc
@@ -21,6 +21,7 @@
#ifdef WITH_GMP
# include <algorithm>
+# include <atomic>
# include <fstream>
# include <iostream>
@@ -50,6 +51,7 @@
# include "BLI_mesh_boolean.hh"
# ifdef WITH_TBB
+# include "tbb/parallel_reduce.h"
# include "tbb/spin_mutex.h"
# endif
@@ -201,9 +203,14 @@ TriMeshTopology::TriMeshTopology(const IMesh &tm)
BLI_assert(edges != nullptr);
}
edges->append_non_duplicates(e);
- auto createf = [t](Vector<int> **pvec) { *pvec = new Vector<int>{t}; };
- auto modifyf = [t](Vector<int> **pvec) { (*pvec)->append_non_duplicates(t); };
- this->edge_tri_.add_or_modify(Edge(v, vnext), createf, modifyf);
+
+ auto p = edge_tri_.lookup_ptr(Edge(v, vnext));
+ if (p == nullptr) {
+ edge_tri_.add_new(e, new Vector<int>{t});
+ }
+ else {
+ (*p)->append_non_duplicates(t);
+ }
}
}
/* Debugging. */
@@ -228,9 +235,18 @@ TriMeshTopology::TriMeshTopology(const IMesh &tm)
TriMeshTopology::~TriMeshTopology()
{
- for (const Vector<int> *vec : edge_tri_.values()) {
- delete vec;
+ Vector<Vector<int> *> values;
+
+ /* Deconstructing is faster in parallel, so it is worth building an array of things to delete. */
+ for (auto item : edge_tri_.values()) {
+ values.append(item);
}
+
+ threading::parallel_for(values.index_range(), 256, [&](IndexRange range) {
+ for (int i : range) {
+ delete values[i];
+ }
+ });
}
/** A Patch is a maximal set of triangles that share manifold edges only. */
@@ -719,6 +735,18 @@ static PatchesInfo find_patches(const IMesh &tm, const TriMeshTopology &tmtopo)
PatchesInfo pinfo(ntri);
/* Algorithm: Grow patches across manifold edges as long as there are unassigned triangles. */
Stack<int> cur_patch_grow;
+
+ /* Create an Array containing indices of adjacent faces. */
+ Array<std::array<int, 3>> t_others(tm.face_size());
+ threading::parallel_for(tm.face_index_range(), 2048, [&](IndexRange range) {
+ for (int t : range) {
+ const Face &tri = *tm.face(t);
+ for (int i = 0; i < 3; ++i) {
+ Edge e(tri[i], tri[(i + 1) % 3]);
+ t_others[t][i] = tmtopo.other_tri_if_manifold(e, t);
+ }
+ }
+ });
for (int t : tm.face_index_range()) {
if (pinfo.tri_patch(t) == -1) {
cur_patch_grow.push(t);
@@ -739,7 +767,7 @@ static PatchesInfo find_patches(const IMesh &tm, const TriMeshTopology &tmtopo)
const Face &tri = *tm.face(tcand);
for (int i = 0; i < 3; ++i) {
Edge e(tri[i], tri[(i + 1) % 3]);
- int t_other = tmtopo.other_tri_if_manifold(e, tcand);
+ int t_other = t_others[tcand][i];
if (dbg_level > 1) {
std::cout << " edge " << e << " generates t_other=" << t_other << "\n";
}
@@ -953,12 +981,8 @@ static void sort_by_signed_triangle_index(Vector<int> &g,
* To accommodate this:
* If extra_tri is non-null, then an index of EXTRA_TRI_INDEX should use it for the triangle.
*/
-static Array<int> sort_tris_around_edge(const IMesh &tm,
- const TriMeshTopology &tmtopo,
- const Edge e,
- const Span<int> tris,
- const int t0,
- const Face *extra_tri)
+static Array<int> sort_tris_around_edge(
+ const IMesh &tm, const Edge e, const Span<int> tris, const int t0, const Face *extra_tri)
{
/* Divide and conquer, quick-sort-like sort.
* Pick a triangle t0, then partition into groups:
@@ -1023,14 +1047,14 @@ static Array<int> sort_tris_around_edge(const IMesh &tm,
}
}
if (g3.size() > 1) {
- Array<int> g3sorted = sort_tris_around_edge(tm, tmtopo, e, g3, t0, extra_tri);
+ Array<int> g3sorted = sort_tris_around_edge(tm, e, g3, t0, extra_tri);
std::copy(g3sorted.begin(), g3sorted.end(), g3.begin());
if (dbg_level > 1) {
std::cout << "g3 sorted: " << g3 << "\n";
}
}
if (g4.size() > 1) {
- Array<int> g4sorted = sort_tris_around_edge(tm, tmtopo, e, g4, t0, extra_tri);
+ Array<int> g4sorted = sort_tris_around_edge(tm, e, g4, t0, extra_tri);
std::copy(g4sorted.begin(), g4sorted.end(), g4.begin());
if (dbg_level > 1) {
std::cout << "g4 sorted: " << g4 << "\n";
@@ -1076,7 +1100,7 @@ static void find_cells_from_edge(const IMesh &tm,
const Vector<int> *edge_tris = tmtopo.edge_tris(e);
BLI_assert(edge_tris != nullptr);
Array<int> sorted_tris = sort_tris_around_edge(
- tm, tmtopo, e, Span<int>(*edge_tris), (*edge_tris)[0], nullptr);
+ tm, e, Span<int>(*edge_tris), (*edge_tris)[0], nullptr);
int n_edge_tris = edge_tris->size();
Array<int> edge_patches(n_edge_tris);
@@ -1338,34 +1362,46 @@ static bool patch_cell_graph_ok(const CellsInfo &cinfo, const PatchesInfo &pinfo
static bool is_pwn(const IMesh &tm, const TriMeshTopology &tmtopo)
{
constexpr int dbg_level = 0;
+ std::atomic<bool> is_pwn = true;
+ Vector<std::pair<Edge, Vector<int> *>> tris;
+
for (auto item : tmtopo.edge_tri_map_items()) {
- const Edge &edge = item.key;
- int tot_orient = 0;
- /* For each face t attached to edge, add +1 if the edge
- * is positively in t, and -1 if negatively in t. */
- for (int t : *item.value) {
- const Face &face = *tm.face(t);
- BLI_assert(face.size() == 3);
- for (int i : face.index_range()) {
- if (face[i] == edge.v0()) {
- if (face[(i + 1) % 3] == edge.v1()) {
- ++tot_orient;
- }
- else {
- BLI_assert(face[(i + 3 - 1) % 3] == edge.v1());
- --tot_orient;
+ tris.append(std::pair<Edge, Vector<int> *>(item.key, item.value));
+ }
+
+ threading::parallel_for(tris.index_range(), 2048, [&](IndexRange range) {
+ for (int j : range) {
+ const Edge &edge = tris[j].first;
+ int tot_orient = 0;
+ /* For each face t attached to edge, add +1 if the edge
+ * is positively in t, and -1 if negatively in t. */
+ for (int t : *tris[j].second) {
+ const Face &face = *tm.face(t);
+ BLI_assert(face.size() == 3);
+ for (int i : face.index_range()) {
+ if (face[i] == edge.v0()) {
+ if (face[(i + 1) % 3] == edge.v1()) {
+ ++tot_orient;
+ }
+ else {
+ BLI_assert(face[(i + 3 - 1) % 3] == edge.v1());
+ --tot_orient;
+ }
}
}
}
- }
- if (tot_orient != 0) {
- if (dbg_level > 0) {
- std::cout << "edge causing non-pwn: " << edge << "\n";
+ if (tot_orient != 0) {
+ if (dbg_level > 0) {
+ std::cout << "edge causing non-pwn: " << edge << "\n";
+ }
+ is_pwn = false;
+# ifdef WITH_TBB
+ tbb::task::self().cancel_group_execution();
+# endif
}
- return false;
}
- }
- return true;
+ });
+ return is_pwn.load();
}
/**
@@ -1396,8 +1432,7 @@ static int find_cell_for_point_near_edge(mpq3 p,
Array<int> edge_tris(etris->size() + 1);
std::copy(etris->begin(), etris->end(), edge_tris.begin());
edge_tris[edge_tris.size() - 1] = EXTRA_TRI_INDEX;
- Array<int> sorted_tris = sort_tris_around_edge(
- tm, tmtopo, e, edge_tris, edge_tris[0], dummy_tri);
+ Array<int> sorted_tris = sort_tris_around_edge(tm, e, edge_tris, edge_tris[0], dummy_tri);
if (dbg_level > 0) {
std::cout << "sorted tris = " << sorted_tris << "\n";
}
@@ -1452,39 +1487,66 @@ static int find_ambient_cell(const IMesh &tm,
/* First find a vertex with the maximum x value. */
/* Prefer not to populate the verts in the #IMesh just for this. */
const Vert *v_extreme;
- mpq_class extreme_x;
+ auto max_x_vert = [](const Vert *a, const Vert *b) {
+ return (a->co_exact.x > b->co_exact.x) ? a : b;
+ };
if (component_patches == nullptr) {
- v_extreme = (*tm.face(0))[0];
- extreme_x = v_extreme->co_exact.x;
- for (const Face *f : tm.faces()) {
- for (const Vert *v : *f) {
- const mpq_class &x = v->co_exact.x;
- if (x > extreme_x) {
- v_extreme = v;
- extreme_x = x;
- }
- }
- }
+ v_extreme = threading::parallel_reduce(
+ tm.face_index_range(),
+ 2048,
+ (*tm.face(0))[0],
+ [&](IndexRange range, const Vert *init) {
+ const Vert *ans = init;
+ for (int i : range) {
+ const Face *f = tm.face(i);
+ for (const Vert *v : *f) {
+ if (v->co_exact.x > ans->co_exact.x) {
+ ans = v;
+ }
+ }
+ }
+ return ans;
+ },
+ max_x_vert);
}
else {
if (dbg_level > 0) {
std::cout << "restrict to patches " << *component_patches << "\n";
}
int p0 = (*component_patches)[0];
- v_extreme = (*tm.face(pinfo.patch(p0).tri(0)))[0];
- extreme_x = v_extreme->co_exact.x;
- for (int p : *component_patches) {
- for (int t : pinfo.patch(p).tris()) {
- const Face *f = tm.face(t);
- for (const Vert *v : *f) {
- const mpq_class &x = v->co_exact.x;
- if (x > extreme_x) {
- v_extreme = v;
- extreme_x = x;
+ v_extreme = threading::parallel_reduce(
+ component_patches->index_range(),
+ 2048,
+ (*tm.face(pinfo.patch(p0).tri(0)))[0],
+ [&](IndexRange range, const Vert *init) {
+ const Vert *ans = init;
+ for (int pi : range) {
+ int p = (*component_patches)[pi];
+ const Vert *tris_ans = threading::parallel_reduce(
+ IndexRange(pinfo.patch(p).tot_tri()),
+ 2048,
+ init,
+ [&](IndexRange tris_range, const Vert *t_init) {
+ const Vert *v_ans = t_init;
+ for (int i : tris_range) {
+ int t = pinfo.patch(p).tri(i);
+ const Face *f = tm.face(t);
+ for (const Vert *v : *f) {
+ if (v->co_exact.x > v_ans->co_exact.x) {
+ v_ans = v;
+ }
+ }
+ }
+ return v_ans;
+ },
+ max_x_vert);
+ if (tris_ans->co_exact.x > ans->co_exact.x) {
+ ans = tris_ans;
+ }
}
- }
- }
- }
+ return ans;
+ },
+ max_x_vert);
}
if (dbg_level > 0) {
std::cout << "v_extreme = " << v_extreme << "\n";
@@ -1493,7 +1555,8 @@ static int find_ambient_cell(const IMesh &tm,
* when projected onto the XY plane. That edge is guaranteed to
* be on the convex hull of the mesh. */
const Vector<Edge> &edges = tmtopo.vert_edges(v_extreme);
- const mpq_class extreme_y = v_extreme->co_exact.y;
+ const mpq_class &extreme_x = v_extreme->co_exact.x;
+ const mpq_class &extreme_y = v_extreme->co_exact.y;
Edge ehull;
mpq_class max_abs_slope = -1;
for (Edge e : edges) {
@@ -1514,8 +1577,8 @@ static int find_ambient_cell(const IMesh &tm,
if (dbg_level > 0) {
std::cout << "ehull = " << ehull << " slope = " << max_abs_slope << "\n";
}
- /* Sort triangles around ehull, including a dummy triangle that include a known point in ambient
- * cell. */
+ /* Sort triangles around ehull, including a dummy triangle that include a known point in
+ * ambient cell. */
mpq3 p_in_ambient = v_extreme->co_exact;
p_in_ambient.x += 1;
int c_ambient = find_cell_for_point_near_edge(p_in_ambient, ehull, tm, tmtopo, pinfo, arena);
@@ -2816,7 +2879,8 @@ static IMesh raycast_patches_boolean(const IMesh &tm,
}
/**
* 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).
+ * return the indices into \a tri1 and \a tri2 where that common edge starts. Else return
+ * (-1,-1).
*/
static std::pair<int, int> find_tris_common_edge(const Face &tri1, const Face &tri2)
{
@@ -3378,8 +3442,8 @@ static void dissolve_verts(IMesh *imesh, const Array<bool> dissolve, IMeshArena
* will have an original edge that is NO_INDEX.
* Not all triangulation edges can be removed: if they ended up non-trivially overlapping a real
* input edge, then we need to keep it. Also, some are necessary to make the output satisfy
- * the "valid #BMesh" property: we can't produce output faces that have repeated vertices in them,
- * or have several disconnected boundaries (e.g., faces with holes).
+ * the "valid #BMesh" property: we can't produce output faces that have repeated vertices in
+ * them, or have several disconnected boundaries (e.g., faces with holes).
*/
static IMesh polymesh_from_trimesh_with_dissolve(const IMesh &tm_out,
const IMesh &imesh_in,
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-23 21:26:19 +0300