[Bf-blender-cvs] [16e3e9f3e2f] newboolean: A lot of progress towards working boolean library function.
Howard Trickey
noreply at git.blender.org
Thu Jun 11 04:03:00 CEST 2020
Commit: 16e3e9f3e2f0b6f9c419bed5b69c7245a63bd885
Author: Howard Trickey
Date: Wed Jun 10 22:00:08 2020 -0400
Branches: newboolean
https://developer.blender.org/rB16e3e9f3e2f0b6f9c419bed5b69c7245a63bd885
A lot of progress towards working boolean library function.
The code to partition space into cells is mostly done.
The code to propagate winding numbers and flag cells according to the
boolean function is mostly done.
Only final extraction code is left, and a few other things.
===================================================================
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_boolean_test.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 d5a2a609503..255122aa347 100644
--- a/source/blender/blenlib/BLI_mesh_intersect.hh
+++ b/source/blender/blenlib/BLI_mesh_intersect.hh
@@ -89,6 +89,16 @@ class IndexedTriangle {
{
return m_v[i];
}
+ bool operator==(const IndexedTriangle &other)
+ {
+ /* Let equality happen with any cyclic ordering difference, but not orientation difference. */
+ return (((m_v[0] == other.m_v[0] && m_v[1] == other.m_v[1] && m_v[2] == other.m_v[2]) ||
+ (m_v[0] == other.m_v[1] && m_v[1] == other.m_v[2] && m_v[2] == other.m_v[0]) ||
+ (m_v[0] == other.m_v[2] && m_v[1] == other.m_v[0] && m_v[2] == other.m_v[1])
+ )
+ && m_orig == other.m_orig
+ );
+ }
private:
int m_v[3]{-1, -1, -1};
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index adc84e240d7..2d8873531e6 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -19,11 +19,13 @@
#include "gmpxx.h"
#include "BLI_array.hh"
+#include "BLI_array_ref.hh"
#include "BLI_assert.h"
#include "BLI_hash.hh"
#include "BLI_map.hh"
#include "BLI_mesh_intersect.hh"
#include "BLI_mpq3.hh"
+#include "BLI_set.hh"
#include "BLI_stack.hh"
#include "BLI_vector.hh"
@@ -74,21 +76,34 @@ 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)
+
+static std::ostream &operator<<(std::ostream &os, const ArrayRef<int> &a)
{
- for (uint i = 0; i < ivec.size(); ++i) {
- os << ivec[i];
- if (i != ivec.size() - 1) {
- std::cout << " ";
+ for (uint i = 0; i < a.size(); ++i) {
+ os << a[i];
+ if (i != a.size() - 1) {
+ os << " ";
}
}
return os;
}
+static std::ostream &operator<<(std::ostream &os, const Vector<int> &ivec)
+{
+ os << ArrayRef<int>(ivec);
+ return os;
+}
+
+static std::ostream &operator<<(std::ostream &os, const Array<int> &iarr)
+{
+ os << ArrayRef<int>(iarr);
+ return os;
+}
+
class TriMeshTopology {
public:
TriMeshTopology(const TriMesh *tm);
- ~TriMeshTopology() = default;
+ ~TriMeshTopology();
/* 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
@@ -106,6 +121,10 @@ class TriMeshTopology {
return -1;
}
}
+ const Vector<int> *edge_tris(Edge e) const
+ {
+ return m_edge_tri.lookup_default(e, nullptr);
+ }
private:
Map<Edge, Vector<int> *> m_edge_tri; /* Triangles that contain a given Edge (either order). */
@@ -142,6 +161,12 @@ TriMeshTopology::TriMeshTopology(const TriMesh *tm)
}
}
+TriMeshTopology::~TriMeshTopology()
+{
+ auto deletef = [](const Edge &UNUSED(e), const Vector<int> *vec) { delete vec; };
+ m_edge_tri.foreach_item(deletef);
+}
+
/* A Patch is a maximal set of faces that share manifold edges only. */
class Patch {
public:
@@ -156,6 +181,9 @@ class Patch {
{
return m_tri;
}
+
+ int cell_above{-1};
+ int cell_below{-1};
private:
Vector<int> m_tri; /* Indices of triangles in the Patch. */
@@ -164,6 +192,10 @@ class Patch {
static std::ostream &operator<<(std::ostream &os, const Patch &patch)
{
os << "Patch " << patch.tri();
+ if (patch.cell_above != -1) {
+ os << " cell_above=" << patch.cell_above
+ << " cell_below=" << patch.cell_below;
+ }
return os;
}
@@ -172,6 +204,7 @@ class PatchesInfo {
explicit PatchesInfo(int ntri)
{
m_tri_patch = Array<int>(ntri, -1);
+ m_pp_edge.reserve(30);
}
int tri_patch(int t) const
{
@@ -195,20 +228,141 @@ class PatchesInfo {
{
return m_patch[patch_index];
}
+ Patch &patch(int patch_index)
+ {
+ return m_patch[patch_index];
+ }
int tot_patch() const
{
return static_cast<int>(m_patch.size());
}
+ void add_new_patch_patch_edge(int p1, int p2, Edge e)
+ {
+ m_pp_edge.add_new(std::pair<int, int>(p1, p2), e);
+ m_pp_edge.add_new(std::pair<int, int>(p2, p1), e);
+ }
+ Edge patch_patch_edge(int p1, int p2)
+ {
+ return m_pp_edge.lookup_default(std::pair<int, int>(p1, p2), Edge(-1, -1));
+ }
private:
Vector<Patch> m_patch;
Array<int> m_tri_patch; /* Patch index for corresponding triangle. */
+ Map<std::pair<int, int>, Edge>
+ m_pp_edge; /* Shared edge for incident patches; (-1,-1) if none. */
+};
+
+static bool apply_bool_op(int bool_optype, const Array<int> &winding);
+
+/* A Cell is a volume of 3-space, surrounded by patches.
+ * We will partition all 3-space into Cells.
+ * One cell, the Ambient cell, contains all other cells.
+ */
+class Cell {
+public:
+ Cell() = default;
+
+ void add_patch(int p)
+ {
+ m_patches.append(p);
+ }
+
+ const Vector<int> &patches() const
+ {
+ return m_patches;
+ }
+
+ const Array<int> &winding() const
+ {
+ return m_winding;
+ }
+
+ void init_winding(int winding_len)
+ {
+ m_winding = Array<int>(winding_len);
+ }
+
+ void seed_ambient_winding()
+ {
+ m_winding.fill(0);
+ m_winding_assigned = true;
+ }
+
+ void set_winding_and_flag(const Cell &from_cell, int shape, int delta, int bool_optype)
+ {
+ std::copy(from_cell.winding().begin(), from_cell.winding().end(), m_winding.begin());
+ m_winding[shape] += delta;
+ m_winding_assigned = true;
+ m_flag = apply_bool_op(bool_optype, m_winding);
+ }
+
+ bool flag() const {
+ return m_flag;
+ }
+
+ bool winding_assigned() const {
+ return m_winding_assigned;
+ }
+
+private:
+ Vector<int> m_patches;
+ Array<int> m_winding;
+ bool m_winding_assigned{false};
+ bool m_flag{false};
+};
+
+static std::ostream &operator<<(std::ostream &os, const Cell &cell)
+{
+ os << "Cell patches " << cell.patches();
+ if (cell.winding().size() > 0) {
+ os << " winding " << cell.winding();
+ os << " flag " << cell.flag();
+ }
+ return os;
+}
+
+/* Information about all the Cells. */
+class CellsInfo
+{
+public:
+ CellsInfo() = default;
+
+ int add_cell() {
+ uint index = m_cell.append_and_get_index(Cell());
+ return static_cast<int>(index);
+ }
+
+ Cell &cell(int c)
+ {
+ return m_cell[c];
+ }
+
+ const Cell &cell(int c) const
+ {
+ return m_cell[c];
+ }
+
+ int tot_cell() const
+ {
+ return static_cast<int>(m_cell.size());
+ }
+
+ void init_windings(int winding_len)
+ {
+ for (Cell &cell : m_cell) {
+ cell.init_winding(winding_len);
+ }
+ }
+
+private:
+ Vector<Cell> m_cell;
};
/* Partition the triangles of tm into Patches. */
static PatchesInfo find_patches(const TriMesh &tm, const TriMeshTopology &tmtopo)
{
- const int dbg_level = 0;
+ const int dbg_level = 1;
if (dbg_level > 0) {
std::cout << "\nFIND_PATCHES\n";
}
@@ -236,8 +390,29 @@ static PatchesInfo find_patches(const TriMesh &tm, const TriMeshTopology &tmtopo
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 (t_other != -1) {
+ if (!pinfo.tri_is_assigned(t_other)) {
+ cur_patch_grow.push(t_other);
+ }
+ }
+ else {
+ /* e is non-manifold. Set any patch-patch incidences we can. */
+ const Vector<int> *etris = tmtopo.edge_tris(e);
+ if (etris) {
+ for (uint i = 0; i < etris->size(); ++i) {
+ int t_other = (*etris)[i];
+ if (t_other != tcand && pinfo.tri_is_assigned(t_other)) {
+ int p_other = pinfo.tri_patch(t_other);
+ if (pinfo.patch_patch_edge(cur_patch_index, p_other) == Edge(-1, -1)) {
+ pinfo.add_new_patch_patch_edge(cur_patch_index, p_other, e);
+ if (dbg_level > 1) {
+ std::cout << "added patch_patch_edge (" << cur_patch_index << "," << p_other
+ << ") = " << e << "\n";
+ }
+ }
+ }
+ }
+ }
}
}
}
@@ -248,14 +423,482 @@ static PatchesInfo find_patches(const TriMesh &tm, const TriMeshTopology &tmtopo
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";
+ if (dbg_level > 1) {
+ 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";
+ }
+ }
+ std::cout << "\npatch-patch incidences\n";
+ for (int p1 = 0; p1 < pinfo.tot_patch(); ++p1) {
+ for (int p2 = 0; p2 < pinfo.tot_patch(); ++p2) {
+ Edge e = pinfo.patch_patch_edge(p1, p2);
+ if (!(e == Edge(-1, -1))) {
+ std::cout << "p" << p1 << " and p" << p2 << " share edge " << e << "\n";
+ }
+ }
}
}
return pinfo;
}
+/* If e is an edge in tri, return the vertex that isn't part of tri,
+ * the "flap" vertex, or -1 if e is not part of tri.
+ * Also, e may be reversed in tri.
+ * Set *r_rev to true if it is reversed, else false.
+ */
+int find_flap_vert(const IndexedTriangle &tri, const Edge e, bool *r_rev)
+{
+ *r_rev = false;
+ int flapv;
+ if (tri.v0() == e.v0()) {
+ if (tri.v1() == e.v1()) {
+ *r_rev = false;
+ flapv = tri.v2();
+ }
+ else {
+ if (tri.v2() != e.v1()) {
+ return -1;
+ }
+ *r_rev = true;
+ flapv = tri.v1();
+ }
+ }
+ else if (tri.v1() == e.v0()) {
+ if (tri.v2() == e.v1()) {
+ *r_rev = false;
+ flapv = tri.v0();
+ }
+ else {
+ if (tri.v0() != e.v1()) {
+ return -1;
+ }
+ *r_rev = true;
+ flapv = tri.v2();
+ }
+ }
+ else {
+ if (tri.v2() != e.v0()) {
+ return -1;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list