[Bf-blender-cvs] [d6e3ba3416e] newboolean: Fix the knife boolean modes.
Howard Trickey
noreply at git.blender.org
Sun Jul 26 03:21:57 CEST 2020
Commit: d6e3ba3416e4a25896449e617ecae416dc306084
Author: Howard Trickey
Date: Sat Jul 25 21:19:39 2020 -0400
Branches: newboolean
https://developer.blender.org/rBd6e3ba3416e4a25896449e617ecae416dc306084
Fix the knife boolean modes.
Had to track the intersect edges through from mesh_intersect
through to the bmesh boolean.
===================================================================
M source/blender/blenlib/BLI_mesh_intersect.hh
M source/blender/blenlib/intern/boolean.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M source/blender/bmesh/tools/bmesh_boolean.cc
M source/blender/bmesh/tools/bmesh_edgesplit.h
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 1b3a7d81181..30a7f43f3b0 100644
--- a/source/blender/blenlib/BLI_mesh_intersect.hh
+++ b/source/blender/blenlib/BLI_mesh_intersect.hh
@@ -112,12 +112,16 @@ std::ostream &operator<<(std::ostream &os, const Plane &plane);
* to the caller for the edge starting from the corresponding face position.
* A "face position" is the index of a vertex around a face.
* Faces don't own the memory pointed at by the vert array.
+ * Also indexed by face position, the is_intersect array says
+ * for each edge whether or not it is the result of intersecting
+ * with another face in the intersect algorithm.
* Since the intersect algorithm needs the plane for each face,
* a Face also stores the Plane of the face.
*/
struct Face {
Array<Vertp> vert;
Array<int> edge_orig;
+ Array<bool> is_intersect;
Plane plane;
int id = NO_INDEX;
int orig = NO_INDEX;
@@ -125,7 +129,8 @@ struct Face {
using FacePos = int;
Face() = default;
- Face(Span<Vertp> verts, int id, int orig, Span<int> edge_origs);
+ Face(Span<Vertp> verts, int id, int orig, Span<int> edge_origs, Span<bool> is_intersect);
+ Face(Span<Vertp> verts, int id, int orig);
Face(const Face &other);
Face(Face &&other) noexcept;
@@ -221,7 +226,9 @@ class MArena {
Vertp add_or_find_vert(const mpq3 &co, int orig);
Vertp add_or_find_vert(const double3 &co, int orig);
+ Facep add_face(Span<Vertp> verts, int orig, Span<int> edge_origs, Span<bool> is_intersect);
Facep add_face(Span<Vertp> verts, int orig, Span<int> edge_origs);
+ Facep add_face(Span<Vertp> verts, int orig);
/* The following return nullptr if not found. */
Vertp find_vert(const mpq3 &co) const;
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index 57c3726495f..9be59f93151 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -1083,8 +1083,10 @@ static int find_ambient_cell(const Mesh &tm,
p_in_ambient.x += 1;
const Vector<int> *ehull_edge_tris = tmtopo.edge_tris(ehull);
Vertp dummy_vert = arena->add_or_find_vert(p_in_ambient, NO_INDEX);
- Facep dummy_tri = arena->add_face(
- {ehull.v0(), ehull.v1(), dummy_vert}, NO_INDEX, {NO_INDEX, NO_INDEX, NO_INDEX});
+ Facep dummy_tri = arena->add_face({ehull.v0(), ehull.v1(), dummy_vert},
+ NO_INDEX,
+ {NO_INDEX, NO_INDEX, NO_INDEX},
+ {false, false, false});
Array<int> edge_tris(ehull_edge_tris->size() + 1);
std::copy(ehull_edge_tris->begin(), ehull_edge_tris->end(), edge_tris.begin());
edge_tris[edge_tris.size() - 1] = EXTRA_TRI_INDEX;
@@ -1277,7 +1279,10 @@ static Mesh extract_from_flag_diffs(const Mesh &tm_subdivided,
const Face &tri = *f;
Array<Vertp> flipped_vs = {tri[0], tri[2], tri[1]};
Array<int> flipped_e_origs = {tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]};
- Facep flipped_f = arena->add_face(flipped_vs, f->orig, flipped_e_origs);
+ Array<bool> flipped_is_intersect = {
+ tri.is_intersect[2], tri.is_intersect[1], tri.is_intersect[0]};
+ Facep flipped_f = arena->add_face(
+ flipped_vs, f->orig, flipped_e_origs, flipped_is_intersect);
out_tris.append(flipped_f);
}
else {
@@ -1378,7 +1383,8 @@ static Array<Facep> triangulate_poly(Facep f, MArena *arena)
}
}
}
- ans[t] = arena->add_face({v[0], v[1], v[2]}, f->orig, {eo[0], eo[1], eo[2]});
+ ans[t] = arena->add_face(
+ {v[0], v[1], v[2]}, f->orig, {eo[0], eo[1], eo[2]}, {false, false, false});
}
return ans;
}
@@ -1408,8 +1414,8 @@ static Mesh triangulate_polymesh(Mesh &pm, MArena *arena)
int eo_12 = f->edge_orig[1];
int eo_23 = f->edge_orig[2];
int eo_30 = f->edge_orig[3];
- Facep f0 = arena->add_face({v0, v1, v2}, f->orig, {eo_01, eo_12, -1});
- Facep f1 = arena->add_face({v0, v2, v3}, f->orig, {-1, eo_23, eo_30});
+ Facep f0 = arena->add_face({v0, v1, v2}, f->orig, {eo_01, eo_12, -1}, {false, false, false});
+ Facep 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);
}
@@ -1450,6 +1456,7 @@ struct MergeEdge {
int orig = -1; /* An edge orig index that can be used for this edge. */
/* Is it allowed to dissolve this edge? */
bool dissolvable = false;
+ bool is_intersect = false; /* Is this an intersect edge? */
MergeEdge() = default;
@@ -1507,7 +1514,7 @@ static std::ostream &operator<<(std::ostream &os, const FaceMergeState &fms)
const MergeEdge &me = fms.edge[e];
std::cout << e << ": (" << me.v1 << "," << me.v2 << ") left=" << me.left_face
<< " right=" << me.right_face << " dis=" << me.dissolvable << " orig=" << me.orig
- << "\n";
+ << " is_int=" << me.is_intersect << "\n";
}
return os;
}
@@ -1525,6 +1532,9 @@ static void init_face_merge_state(FaceMergeState *fms, const Vector<int> &tris,
for (int t : tris.index_range()) {
MergeFace mf;
const Face &tri = *tm.face(tris[t]);
+ if (dbg_level > 0) {
+ std::cout << "process tri = " << &tri << "\n";
+ }
mf.vert.append(tri[0]);
mf.vert.append(tri[1]);
mf.vert.append(tri[2]);
@@ -1539,7 +1549,8 @@ static void init_face_merge_state(FaceMergeState *fms, const Vector<int> &tris,
double3 vec = new_me.v2->co - new_me.v1->co;
new_me.len_squared = vec.length_squared();
new_me.orig = tri.edge_orig[i];
- new_me.dissolvable = (new_me.orig == NO_INDEX);
+ new_me.is_intersect = tri.is_intersect[i];
+ new_me.dissolvable = (new_me.orig == NO_INDEX && !new_me.is_intersect);
fms->edge.append(new_me);
me_index = static_cast<int>(fms->edge.size()) - 1;
fms->edge_map.add_new(canon_vs, me_index);
@@ -1549,6 +1560,10 @@ static void init_face_merge_state(FaceMergeState *fms, const Vector<int> &tris,
me.dissolvable = false;
me.orig = tri.edge_orig[i];
}
+ if (me.dissolvable && tri.is_intersect[i]) {
+ me.dissolvable = false;
+ me.is_intersect = true;
+ }
/* This face is left or right depending on orientation of edge. */
if (me.v1 == mf.vert[i]) {
BLI_assert(me.left_face == -1);
@@ -1726,6 +1741,11 @@ static Vector<Facep> merge_tris_for_face(Vector<int> tris,
const Mesh &pm_in,
MArena *arena)
{
+ constexpr int dbg_level = 0;
+ if (dbg_level > 0) {
+ std::cout << "merge_tris_for_face\n";
+ std::cout << "tris: " << tris << "\n";
+ }
Vector<Facep> ans;
bool done = false;
if (tris.size() == 1) {
@@ -1742,12 +1762,20 @@ static Vector<Facep> merge_tris_for_face(Vector<int> tris,
if (in_face->size() == 4) {
std::pair<int, int> estarts = find_tris_common_edge(tri1, tri2);
if (estarts.first != -1 && tri1.edge_orig[estarts.first] == NO_INDEX) {
+ if (dbg_level > 0) {
+ std::cout << "try recovering orig quad case\n";
+ std::cout << "tri1 = " << &tri1 << "\n";
+ std::cout << "tri1 = " << &tri2 << "\n";
+ }
int i0 = estarts.first;
int i1 = (i0 + 1) % 3;
int i2 = (i0 + 2) % 3;
int j2 = (estarts.second + 2) % 3;
- Face tryface({tri1[i1], tri1[i2], tri1[i0], tri2[j2]}, -1, -1, {});
+ Face tryface({tri1[i1], tri1[i2], tri1[i0], tri2[j2]}, -1, -1, {}, {});
if (tryface.cyclic_equal(*in_face)) {
+ if (dbg_level > 0) {
+ std::cout << "quad recovery worked\n";
+ }
ans.append(in_face);
done = true;
}
@@ -1761,14 +1789,22 @@ static Vector<Facep> merge_tris_for_face(Vector<int> tris,
FaceMergeState fms;
init_face_merge_state(&fms, tris, tm);
do_dissolve(&fms);
+ if (dbg_level > 0) {
+ std::cout << "faces in merged result:\n";
+ }
for (const MergeFace &mf : fms.face) {
if (mf.merge_to == -1) {
Array<int> e_orig(mf.edge.size());
+ Array<bool> is_intersect(mf.edge.size());
for (int i : mf.edge.index_range()) {
e_orig[i] = fms.edge[mf.edge[i]].orig;
+ is_intersect[i] = fms.edge[mf.edge[i]].is_intersect;
}
- Facep facep = arena->add_face(mf.vert, mf.orig, e_orig);
+ Facep facep = arena->add_face(mf.vert, mf.orig, e_orig, is_intersect);
ans.append(facep);
+ if (dbg_level > 0) {
+ std::cout << " " << facep << "\n";
+ }
}
}
return ans;
@@ -2050,6 +2086,10 @@ Mesh boolean_mesh(Mesh &pm,
tm_in = &our_triangulation;
}
Mesh tm_out = boolean_trimesh(*tm_in, op, nshapes, shape_fn, use_self, arena);
+ if (dbg_level > 1) {
+ std::cout << "bool_trimesh_output:\n" << tm_out;
+ write_obj_mesh(tm_out, "bool_trimesh_output");
+ }
Mesh ans = polymesh_from_trimesh_with_dissolve(tm_out, pm, arena);
if (dbg_level > 0) {
std::cout << "boolean_mesh output:\n" << ans;
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 48ccb20a2eb..b19f254fe83 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -160,8 +160,27 @@ std::ostream &operator<<(std::ostream &os, const Plane &plane)
return os;
}
-Face::Face(Span<Vertp> verts, int id, int orig, Span<int> edge_origs)
- : vert(verts), edge_orig(edge_origs), id(id), orig(orig)
+Face::Face(Span<Vertp> verts, int id, int orig, Span<int> edge_origs, Span<bool> is_intersect)
+ : vert(verts), edge_orig(edge_origs), is_intersect(is_intersect), id(id), orig(orig)
+{
+ mpq3 normal;
+ if (vert.size() > 3) {
+ Array<mpq3> co(vert.size());
+ for (int i : index_range()) {
+ co[i] = vert[i]->co_exact;
+ }
+ normal = mpq3::cross_poly(co);
+ }
+ else {
+ mpq3 tr02 = vert[0]->co_exact - vert[2]->co_exact;
+ mpq3 tr12 = vert[1]->co_exact - vert[2]->co_exact;
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list