[Bf-blender-cvs] [7a775b80886] newboolean: Made binary version of boolean and hooked up to Boolean tool.
Howard Trickey
noreply at git.blender.org
Sun Jun 14 01:55:43 CEST 2020
Commit: 7a775b80886fcc8e7a5cab74e51497069fca2e47
Author: Howard Trickey
Date: Sat Jun 13 19:54:17 2020 -0400
Branches: newboolean
https://developer.blender.org/rB7a775b80886fcc8e7a5cab74e51497069fca2e47
Made binary version of boolean and hooked up to Boolean tool.
Union seems to work. Other ops are flaky because I haven't
quite got the winding number propagation right yet.
===================================================================
M source/blender/blenlib/BLI_boolean.h
M source/blender/blenlib/intern/boolean.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M source/blender/bmesh/tools/bmesh_boolean.c
M source/blender/editors/mesh/editmesh_intersect.c
M tests/gtests/blenlib/BLI_boolean_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_boolean.h b/source/blender/blenlib/BLI_boolean.h
index 203526f5946..d9105e025a1 100644
--- a/source/blender/blenlib/BLI_boolean.h
+++ b/source/blender/blenlib/BLI_boolean.h
@@ -47,7 +47,9 @@ typedef struct Boolean_trimesh_output {
int (*tri)[3];
} Boolean_trimesh_output;
-Boolean_trimesh_output *BLI_boolean_trimesh(const Boolean_trimesh_input *input, int bool_optype);
+Boolean_trimesh_output *BLI_boolean_trimesh(const Boolean_trimesh_input *in0,
+ const Boolean_trimesh_input *in1,
+ int bool_optype);
void BLI_boolean_trimesh_free(Boolean_trimesh_output *output);
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index 96e789d5d97..5761e60b6f2 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -149,7 +149,7 @@ class TriMeshTopology {
TriMeshTopology::TriMeshTopology(const TriMesh *tm)
{
- const int dbg_level = 1;
+ const int dbg_level = 0;
if (dbg_level > 0) {
std::cout << "TriMeshTopology construction\n";
}
@@ -215,6 +215,16 @@ class Patch {
return m_tri;
}
+ int tot_tri() const
+ {
+ return static_cast<int>(m_tri.size());
+ }
+
+ int tri(int i) const
+ {
+ return m_tri[i];
+ }
+
int cell_above{-1};
int cell_below{-1};
@@ -393,10 +403,37 @@ class CellsInfo {
Vector<Cell> m_cell;
};
+/* Concatenate two TriMeshes to make a new one. */
+static TriMesh concat_trimeshes(const TriMesh &tm_a, const TriMesh &tm_b)
+{
+ int a_tot_v = static_cast<int>(tm_a.vert.size());
+ int b_tot_v = static_cast<int>(tm_b.vert.size());
+ int a_tot_t = static_cast<int>(tm_a.tri.size());
+ int b_tot_t = static_cast<int>(tm_b.tri.size());
+ TriMesh tm;
+ tm.vert = Array<mpq3>(a_tot_v + b_tot_v);
+ tm.tri = Array<IndexedTriangle>(a_tot_t + b_tot_t);
+ for (int v = 0; v < a_tot_v; ++v) {
+ tm.vert[v] = tm_a.vert[v];
+ }
+ for (int v = 0; v < b_tot_v; ++v) {
+ tm.vert[v + a_tot_v] = tm_b.vert[v];
+ }
+ for (int t = 0; t < a_tot_t; ++t) {
+ tm.tri[t] = tm_a.tri[t];
+ }
+ for (int t = 0; t < b_tot_t; ++t) {
+ const IndexedTriangle &tri = tm_b.tri[t];
+ tm.tri[t + a_tot_t] = IndexedTriangle(
+ tri.v0() + a_tot_v, tri.v1() + a_tot_v, tri.v2() + a_tot_v, tri.orig());
+ }
+ return tm;
+}
+
/* Partition the triangles of tm into Patches. */
static PatchesInfo find_patches(const TriMesh &tm, const TriMeshTopology &tmtopo)
{
- const int dbg_level = 1;
+ const int dbg_level = 0;
if (dbg_level > 0) {
std::cout << "\nFIND_PATCHES\n";
}
@@ -551,7 +588,7 @@ static int sort_tris_class(const IndexedTriangle &tri,
const Edge e,
const mpq3 *extra_coord)
{
- const int dbg_level = 1;
+ const int dbg_level = 0;
if (dbg_level > 0) {
std::cout << "classify e = " << e << "\n";
}
@@ -621,7 +658,7 @@ static Array<int> sort_tris_around_edge(const TriMesh &tm,
* be only 3 or 4 - so OK to make copies of arrays instead of swapping
* around in a single array.
*/
- const int dbg_level = 2;
+ const int dbg_level = 0;
if (tris.size() == 0) {
return Array<int>();
}
@@ -710,7 +747,7 @@ static void find_cells_from_edge(const TriMesh &tm,
CellsInfo &cinfo,
const Edge e)
{
- const int dbg_level = 2;
+ const int dbg_level = 0;
if (dbg_level > 0) {
std::cout << "find_cells_from_edge " << e << "\n";
}
@@ -833,8 +870,7 @@ static CellsInfo find_cells(const TriMesh &tm, const TriMeshTopology &tmtopo, Pa
*/
static int find_ambient_cell(const TriMesh &tm,
const TriMeshTopology &tmtopo,
- const PatchesInfo pinfo,
- const CellsInfo cinfo)
+ const PatchesInfo pinfo)
{
int dbg_level = 0;
if (dbg_level > 0) {
@@ -921,8 +957,12 @@ static int find_ambient_cell(const TriMesh &tm,
/* Starting with ambient cell c_ambient, with all zeros for winding numbers,
* propagate winding numbers to all the other cells.
+ * There will be a vector of nshapes winding numbers in each cell, one per
+ * input shape.
* As one crosses a patch into a new cell, the original shape (mesh part)
* that that patch was part of dictates which winding number changes.
+ * The shape_fn(triangle_number) function should return the shape that the
+ * triangle is part of.
* Also, as soon as the winding numbers for a cell are set, use bool_optype
* to decide whether that cell is included or excluded from the boolean output.
* If included, the cell's flag will be set to true.
@@ -930,9 +970,11 @@ static int find_ambient_cell(const TriMesh &tm,
static void propagate_windings_and_flag(PatchesInfo &pinfo,
CellsInfo &cinfo,
int c_ambient,
- int bool_optype)
+ int bool_optype,
+ int nshapes,
+ std::function<int(int)> shape_fn)
{
- int dbg_level = 1;
+ int dbg_level = 2;
if (dbg_level > 0) {
std::cout << "PROPAGATE_WINDINGS, ambient cell = " << c_ambient << "\n";
}
@@ -960,7 +1002,12 @@ static void propagate_windings_and_flag(PatchesInfo &pinfo,
Cell &cell_neighbor = cinfo.cell(c_neighbor);
if (!cell_neighbor.winding_assigned()) {
int winding_delta = p_above_c ? -1 : 1;
- int shape = 0; /* TODO: recover shape from a triangle in p. */
+ int t = patch.tri(0);
+ int shape = shape_fn(t);
+ BLI_assert(shape < nshapes);
+ if (dbg_level > 1) {
+ std::cout << " representative tri " << t << ": in shape " << shape << "\n";
+ }
cell_neighbor.set_winding_and_flag(cell, shape, winding_delta, bool_optype);
if (dbg_level > 1) {
std::cout << " now cell_neighbor = " << cell_neighbor << "\n";
@@ -1016,7 +1063,7 @@ static bool apply_bool_op(int bool_optype, const Array<int> &winding)
return true;
}
for (int i = 1; i < nw; ++i) {
- if (winding[0] == 0) {
+ if (winding[i] == 0) {
return true;
}
}
@@ -1113,78 +1160,133 @@ static TriMesh extract_from_flag_diffs(const TriMesh &tm_subdivided,
return tm_out;
}
-static TriMesh self_boolean(const TriMesh &tm_in, int bool_optype)
+static const char *bool_optype_name(int bool_optype)
{
- constexpr int dbg_level = 0;
+ switch (bool_optype) {
+ case BOOLEAN_NONE:
+ return "none";
+ break;
+ case BOOLEAN_ISECT:
+ return "intersect";
+ break;
+ case BOOLEAN_UNION:
+ return "union";
+ break;
+ case BOOLEAN_DIFFERENCE:
+ return "difference";
+ default:
+ return "<unknown>";
+ }
+}
+
+/*
+ * This function does a boolean operation on nshapes inputs.
+ * All the shapes are combined in tm_in.
+ * The shape_fn function should take a triangle index in tm_in and return
+ * a number in the range 0 to nshapes-1, to say which shape that triangle is in.
+ */
+static TriMesh nary_boolean(const TriMesh &tm_in,
+ int bool_optype,
+ int nshapes,
+ std::function<int(int)> shape_fn)
+{
+ constexpr int dbg_level = 1;
if (dbg_level > 0) {
- std::cout << "\nSELF_BOOLEAN op=" << bool_optype << "\n";
+ std::cout << "BOOLEAN of " << nshapes << " operand" << (nshapes == 1 ? "" : "s")
+ << " op=" << bool_optype_name(bool_optype) << "\n";
}
if (tm_in.vert.size() == 0 || tm_in.tri.size() == 0) {
- return tm_in;
+ return TriMesh(tm_in);
}
TriMesh tm_si = trimesh_self_intersect(tm_in);
- if (bool_optype == BOOLEAN_NONE) {
+ /* It is possible for tm_si to be empty if all the input triangles are bogus/degenerate. */
+ if (tm_si.tri.size() == 0 || bool_optype == BOOLEAN_NONE) {
return tm_si;
}
TriMeshTopology tm_si_topo(&tm_si);
PatchesInfo pinfo = find_patches(tm_si, tm_si_topo);
CellsInfo cinfo = find_cells(tm_si, tm_si_topo, pinfo);
- cinfo.init_windings(1);
- int c_ambient = find_ambient_cell(tm_si, tm_si_topo, pinfo, cinfo);
- propagate_windings_and_flag(pinfo, cinfo, c_ambient, bool_optype);
+ cinfo.init_windings(nshapes);
+ int c_ambient = find_ambient_cell(tm_si, tm_si_topo, pinfo);
+ propagate_windings_and_flag(pinfo, cinfo, c_ambient, bool_optype, nshapes, shape_fn);
TriMesh tm_out = extract_from_flag_diffs(tm_si, pinfo, cinfo);
return tm_out;
}
+static TriMesh self_boolean(const TriMesh &tm_in, int bool_optype)
+{
+ return nary_boolean(tm_in, bool_optype, 1, [](int UNUSED(t)) { return 0; });
+}
+
+static TriMesh binary_boolean(const TriMesh &tm_in_a, const TriMesh &tm_in_b, int bool_optype)
+{
+ /* Just combine the two pieces. We can tell by original triangle number which side it came
+ * from.
+ */
+ TriMesh tm_in = concat_trimeshes(tm_in_a, tm_in_b);
+ int b_tri_start = static_cast<int>(tm_in_a.tri.size());
+ auto shape_fn = [b_tri_start](int t) { return (t >= b_tri_start ? 1 : 0); };
+ return nary_boolean(tm_in, bool_optype, 2, shape_fn);
+}
+
} // namespace meshintersect
} // namespace blender
-extern "C" Boolean_trimesh_output *BLI_boolean_trimesh(const Boolean_trimesh_input *input,
- int bool_optype)
+static blender::meshintersect::TriMesh trimesh_from_input(const Boolean_trimesh_input *in,
+ int side)
{
- constexpr int dbg_level = 2;
- if (dbg_level > 0) {
- std::cout << "BLI_BOOLEAN_TRIMESH op=";
- switch (bool_optype) {
- case BOOLEAN_NONE:
- std::cout << "none\n";
- break;
- case BOOLEAN_ISECT:
- std::cout << "intersect\n";
- break;
- case BOOLEAN_UNION:
- std::cout << "union\n";
- break;
- case BOOLEAN_DIFFERENCE:
- std::cout << "difference\n";
- }
- }
+ constexpr int dbg_level =
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list