[Bf-blender-cvs] [9105af1b39b] newboolean: Added code that partitions triangle mesh into patches.
Howard Trickey
noreply at git.blender.org
Sun Jun 7 22:21:08 CEST 2020
Commit: 9105af1b39b4131f6ebcd3afcf36672ca36270d5
Author: Howard Trickey
Date: Sun Jun 7 16:19:44 2020 -0400
Branches: newboolean
https://developer.blender.org/rB9105af1b39b4131f6ebcd3afcf36672ca36270d5
Added code that partitions triangle mesh into patches.
A patch is a set of triangles connected only by manifold edges.
Each patch will either appear or not appear in the boolean output
as a whole.
===================================================================
M source/blender/blenlib/BLI_mesh_intersect.hh
M source/blender/blenlib/intern/boolean.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M tests/gtests/blenlib/BLI_mesh_intersect_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_mesh_intersect.hh b/source/blender/blenlib/BLI_mesh_intersect.hh
index 77addf51f0e..d5a2a609503 100644
--- a/source/blender/blenlib/BLI_mesh_intersect.hh
+++ b/source/blender/blenlib/BLI_mesh_intersect.hh
@@ -41,18 +41,28 @@ namespace MeshIntersect {
* and it packs nicely into this structure, so keeping it here will save
* memory.
*/
-struct IndexedTriangle {
- IndexedTriangle() : m_v{-1, -1, -1}, m_orig{-1}
+class IndexedTriangle {
+ public:
+ IndexedTriangle() = default;
+ IndexedTriangle(int v0, int v1, int v2, int orig) : m_v{v0, v1, v2}, m_orig{orig}
{
}
- IndexedTriangle(int v0, int v1, int v2, int orig) : m_v{v0, v1, v2}, m_orig{orig}
+ IndexedTriangle(const IndexedTriangle &other)
{
+ m_v[0] = other.m_v[0];
+ m_v[1] = other.m_v[1];
+ m_v[2] = other.m_v[2];
+ m_orig = other.m_orig;
}
- IndexedTriangle(const IndexedTriangle &other) : m_orig{other.m_orig}
+ IndexedTriangle &operator=(const IndexedTriangle &other)
{
- for (int i = 0; i < 3; ++i) {
- this->m_v[i] = other.m_v[i];
+ if (this != &other) {
+ m_v[0] = other.m_v[0];
+ m_v[1] = other.m_v[1];
+ m_v[2] = other.m_v[2];
+ m_orig = other.m_orig;
}
+ return *this;
}
int v0() const
@@ -81,8 +91,8 @@ struct IndexedTriangle {
}
private:
- int m_v[3];
- int m_orig;
+ int m_v[3]{-1, -1, -1};
+ int m_orig{-1};
};
struct TriMesh {
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index ae4422dabec..adc84e240d7 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -20,14 +20,242 @@
#include "BLI_array.hh"
#include "BLI_assert.h"
+#include "BLI_hash.hh"
+#include "BLI_map.hh"
#include "BLI_mesh_intersect.hh"
#include "BLI_mpq3.hh"
+#include "BLI_stack.hh"
+#include "BLI_vector.hh"
#include "BLI_boolean.h"
namespace BLI {
namespace MeshIntersect {
+/* Edge as two vert indices, in a canonical order (lower vert index first). */
+class Edge {
+ public:
+ Edge() = default;
+ Edge(int v0, int v1)
+ {
+ if (v0 <= v1) {
+ m_v[0] = v0;
+ m_v[1] = v1;
+ }
+ else {
+ m_v[0] = v1;
+ m_v[1] = v0;
+ }
+ }
+
+ int v0() const
+ {
+ return m_v[0];
+ }
+ int v1() const
+ {
+ return m_v[1];
+ }
+ int operator[](int i) const
+ {
+ return m_v[i];
+ }
+ bool operator==(Edge other) const
+ {
+ return m_v[0] == other.m_v[0] && m_v[1] == other.m_v[1];
+ }
+
+ private:
+ int m_v[2]{-1, -1};
+};
+
+static std::ostream &operator<<(std::ostream &os, const Edge &e)
+{
+ os << "(" << e.v0() << "," << e.v1() << ")";
+ return os;
+}
+static std::ostream &operator<<(std::ostream &os, const Vector<int> &ivec)
+{
+ for (uint i = 0; i < ivec.size(); ++i) {
+ os << ivec[i];
+ if (i != ivec.size() - 1) {
+ std::cout << " ";
+ }
+ }
+ return os;
+}
+
+class TriMeshTopology {
+ public:
+ TriMeshTopology(const TriMesh *tm);
+ ~TriMeshTopology() = default;
+
+ /* If e is manifold, return index of the other triangle (not t) that has it. Else return -1. */
+ int other_tri_if_manifold(Edge e, int t) const
+ {
+ if (m_edge_tri.contains(e)) {
+ auto p = m_edge_tri.lookup(e);
+ if (p->size() == 2) {
+ return ((*p)[0] == t) ? (*p)[1] : (*p)[0];
+ }
+ else {
+ return -1;
+ }
+ }
+ else {
+ return -1;
+ }
+ }
+
+ private:
+ Map<Edge, Vector<int> *> m_edge_tri; /* Triangles that contain a given Edge (either order). */
+};
+
+TriMeshTopology::TriMeshTopology(const TriMesh *tm)
+{
+ const int dbg_level = 0;
+ if (dbg_level > 0) {
+ std::cout << "TriMeshTopology construction\n";
+ }
+ /* If everything were manifold, there would be about 3V edges (from Euler's formula). */
+ const uint estimate_num_edges = 4 * tm->vert.size();
+ this->m_edge_tri.reserve(estimate_num_edges);
+ int ntri = static_cast<int>(tm->tri.size());
+ for (int t = 0; t < ntri; ++t) {
+ const IndexedTriangle &tri = tm->tri[t];
+ for (int i = 0; i < 3; ++i) {
+ Edge e(tri[i], tri[(i + 1) % 3]);
+ auto createf = [t](Vector<int> **pvec) { *pvec = new Vector<int>{t}; };
+ auto modifyf = [t](Vector<int> **pvec) { (*pvec)->append_non_duplicates(t); };
+ this->m_edge_tri.add_or_modify(e, createf, modifyf);
+ }
+ }
+ /* Debugging. */
+ if (dbg_level > 0) {
+ std::cout << "After TriMeshTopology construction\n";
+ for (auto item : m_edge_tri.items()) {
+ std::cout << item.key << ": " << *item.value << "\n";
+ if (false) {
+ m_edge_tri.print_table();
+ }
+ }
+ }
+}
+
+/* A Patch is a maximal set of faces that share manifold edges only. */
+class Patch {
+ public:
+ Patch() = default;
+
+ void add_tri(int t)
+ {
+ m_tri.append(t);
+ }
+
+ const Vector<int> &tri() const
+ {
+ return m_tri;
+ }
+
+ private:
+ Vector<int> m_tri; /* Indices of triangles in the Patch. */
+};
+
+static std::ostream &operator<<(std::ostream &os, const Patch &patch)
+{
+ os << "Patch " << patch.tri();
+ return os;
+}
+
+class PatchesInfo {
+ public:
+ explicit PatchesInfo(int ntri)
+ {
+ m_tri_patch = Array<int>(ntri, -1);
+ }
+ int tri_patch(int t) const
+ {
+ return m_tri_patch[t];
+ }
+ int add_patch()
+ {
+ int patch_index = static_cast<int>(m_patch.append_and_get_index(Patch()));
+ return patch_index;
+ }
+ void grow_patch(int patch_index, int t)
+ {
+ m_tri_patch[t] = patch_index;
+ m_patch[patch_index].add_tri(t);
+ }
+ bool tri_is_assigned(int t) const
+ {
+ return m_tri_patch[t] != -1;
+ }
+ const Patch &patch(int patch_index) const
+ {
+ return m_patch[patch_index];
+ }
+ int tot_patch() const
+ {
+ return static_cast<int>(m_patch.size());
+ }
+
+ private:
+ Vector<Patch> m_patch;
+ Array<int> m_tri_patch; /* Patch index for corresponding triangle. */
+};
+
+/* Partition the triangles of tm into Patches. */
+static PatchesInfo find_patches(const TriMesh &tm, const TriMeshTopology &tmtopo)
+{
+ const int dbg_level = 0;
+ if (dbg_level > 0) {
+ std::cout << "\nFIND_PATCHES\n";
+ }
+ int ntri = static_cast<int>(tm.tri.size());
+ PatchesInfo pinfo(ntri);
+ /* Algorithm: Grow patches across manifold edges as long as there are unassigned triangles. */
+ Stack<int> cur_patch_grow;
+ for (int t = 0; t < ntri; ++t) {
+ if (pinfo.tri_patch(t) == -1) {
+ cur_patch_grow.push(t);
+ int cur_patch_index = pinfo.add_patch();
+ while (!cur_patch_grow.is_empty()) {
+ int tcand = cur_patch_grow.pop();
+ if (pinfo.tri_is_assigned(tcand)) {
+ continue;
+ }
+ if (dbg_level > 1) {
+ std::cout << "grow patch from seed tcand=" << tcand << "\n";
+ }
+ pinfo.grow_patch(cur_patch_index, tcand);
+ const IndexedTriangle &tri = tm.tri[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);
+ if (dbg_level > 1) {
+ std::cout << " edge " << e << " generates t_other=" << t_other << "\n";
+ }
+ if (t_other != -1 && !pinfo.tri_is_assigned(t_other)) {
+ cur_patch_grow.push(t_other);
+ }
+ }
+ }
+ }
+ }
+ if (dbg_level > 0) {
+ std::cout << "\nafter FIND_PATCHES: found " << pinfo.tot_patch() << " patches\n";
+ for (int p = 0; p < pinfo.tot_patch(); ++p) {
+ std::cout << p << ": " << pinfo.patch(p) << "\n";
+ }
+ std::cout << "\ntriangle map\n";
+ for (int t = 0; t < static_cast<int>(tm.tri.size()); ++t) {
+ std::cout << t << ": patch " << pinfo.tri_patch(t) << "\n";
+ }
+ }
+ return pinfo;
+}
+
static TriMesh self_boolean(const TriMesh &tm_in, int bool_optype)
{
constexpr int dbg_level = 0;
@@ -35,11 +263,23 @@ static TriMesh self_boolean(const TriMesh &tm_in, int bool_optype)
std::cout << "\nSELF_BOOLEAN op=" << bool_optype << "\n";
}
TriMesh tm_si = trimesh_self_intersect(tm_in);
+ TriMeshTopology tm_si_topo(&tm_si);
+ PatchesInfo pinfo = find_patches(tm_si, tm_si_topo);
return tm_si;
}
-} /* namespace MeshIntersect */
-} /* namespace BLI */
+} // namespace MeshIntersect
+
+template<> struct DefaultHash<MeshIntersect::Edge> {
+ uint32_t operator()(const MeshIntersect::Edge &value) const
+ {
+ uint32_t hash0 = DefaultHash<int>{}(value.v0());
+ uint32_t hash1 = DefaultHash<int>{}(value.v1());
+ return hash0 ^ (hash1 * 33);
+ }
+};
+
+} // namespace BLI
extern "C" Boolean_trimesh_output *BLI_boolean_trimesh(const Boolean_trimesh_input *input,
int bool_optype)
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index e168aa04f65..ca77e5e2ff4 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -1355,7 +1355,7 @@ static TriMesh tmesh_to_trimesh(const TMesh &tm)
/* This is the main routine for calculating the self_intersection of a TriMesh. */
static TriMesh tpl_trimesh_self_intersect(const TriMesh &tm_in)
{
- constexpr int dbg_level = 1;
+ constexpr int dbg_level = 0;
if (dbg_level > 0) {
std::cout << "\nTRIMESH_SELF_INTERSECT\n";
}
diff --git a/tests/gtests/blenlib/BLI_mesh_intersect_test.cc b/tests/gtests/blenlib/BLI_mesh_intersect_test.cc
index 2d854f0a20d..6e33d29bc17 100644
--- a/tests/gtests/blenlib/BLI_mesh_intersect_test.cc
+++ b/tests/gtests/blenlib/BLI_mesh_intersect_test.cc
@@ -154,7 +154,7 @@ TEST(mesh_intersect, TwoTris)
int co1_i = 3 * tri1_index;
int co2_i = 3 * tri2_index;
- const bool verbose = true;
+ const bool verbose = false;
if (verbose) {
std::cout << "\nTest " << test << ": T" << tri1_index << " intersect T" << tri2_index
More information about the Bf-blender-cvs
mailing list