[Bf-blender-cvs] [3edc33123ca] newboolean: BMesh construction now better at preserving attributes of mesh elements.
Howard Trickey
noreply at git.blender.org
Thu Jul 23 13:50:01 CEST 2020
Commit: 3edc33123cadee988f0e564090fff32e894a221a
Author: Howard Trickey
Date: Thu Jul 23 07:46:53 2020 -0400
Branches: newboolean
https://developer.blender.org/rB3edc33123cadee988f0e564090fff32e894a221a
BMesh construction now better at preserving attributes of mesh elements.
Uses existing BMVerts, BMEdges, and BMFaces if possible.
Uses good examples for BMFaces for intersected faces.
Still todo: good examples for BMEdges when partially reusing an edge,
and UV interpolation for new faces.
===================================================================
M source/blender/blenlib/intern/boolean.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M source/blender/bmesh/tools/bmesh_boolean.cc
===================================================================
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index 37fe09920d8..57c3726495f 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -1528,6 +1528,7 @@ static void init_face_merge_state(FaceMergeState *fms, const Vector<int> &tris,
mf.vert.append(tri[0]);
mf.vert.append(tri[1]);
mf.vert.append(tri[2]);
+ mf.orig = tri.orig;
int f = static_cast<int>(fms->face.append_and_get_index(mf));
for (int i = 0; i < 3; ++i) {
int inext = (i + 1) % 3;
@@ -1972,6 +1973,7 @@ Mesh boolean_trimesh(Mesh &tm_in,
std::cout << "BOOLEAN of " << nshapes << " operand" << (nshapes == 1 ? "" : "s")
<< " op=" << bool_optype_name(op) << "\n";
if (dbg_level > 1) {
+ tm_in.populate_vert();
std::cout << "boolean_trimesh input:\n" << tm_in;
write_obj_mesh(tm_in, "boolean_in");
}
@@ -2035,6 +2037,12 @@ Mesh boolean_mesh(Mesh &pm,
Mesh *pm_triangulated,
MArena *arena)
{
+ constexpr int dbg_level = 0;
+ if (dbg_level > 0) {
+ std::cout << "\nBOOLEAN_MESH\n"
+ << nshapes << " operand" << (nshapes == 1 ? "" : "s")
+ << " op=" << bool_optype_name(op) << "\n";
+ }
Mesh *tm_in = pm_triangulated;
Mesh our_triangulation;
if (tm_in == nullptr) {
@@ -2043,6 +2051,9 @@ Mesh boolean_mesh(Mesh &pm,
}
Mesh tm_out = boolean_trimesh(*tm_in, op, nshapes, shape_fn, use_self, arena);
Mesh ans = polymesh_from_trimesh_with_dissolve(tm_out, pm, arena);
+ if (dbg_level > 0) {
+ std::cout << "boolean_mesh output:\n" << ans;
+ }
return ans;
}
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 35efe4d9e4a..9b4fa6e9ebc 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -2519,6 +2519,9 @@ Mesh trimesh_nary_intersect(
BLI_assert(f->is_tri());
UNUSED_VARS_NDEBUG(f);
}
+ if (dbg_level > 1) {
+ std::cout << "input mesh:\n" << tm_in;
+ }
}
if (has_degenerate_tris(tm_in)) {
std::cout << "IMPLEMENT ME - remove degenerate and illegal tris\n";
diff --git a/source/blender/bmesh/tools/bmesh_boolean.cc b/source/blender/bmesh/tools/bmesh_boolean.cc
index 397af350d2e..7fc283d56fd 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.cc
+++ b/source/blender/bmesh/tools/bmesh_boolean.cc
@@ -99,62 +99,180 @@ static Mesh mesh_from_bm(BMesh *bm,
return Mesh(face);
}
+static bool bmvert_attached_to_wire(const BMVert *bmv)
+{
+ /* This is not quite right. It returns true if the only edges
+ * Attached to bmv are wire edges. TODO: iterate through edges
+ * attached to bmv and check BM_edge_is_wire.
+ */
+ return BM_vert_is_wire(bmv);
+}
+
+/* Use the unused _BM_ELEM_TAG_ALT bmflag to mark geometry we will keep. */
+constexpr uint KEEP_FLAG = (1 << 6);
+
static bool apply_mesh_output_to_bmesh(BMesh *bm, Mesh &m_out)
{
/* Change BMesh bm to have the mesh match m_out. Return true if there were any changes at all.
- *
- * For now, just for testing, just kill the whole old mesh and create the new one.
- * No attempt yet to use proper examples for the new elements so that they inherit the
- * proper attributes.
- * No attempt yet to leave the correct geometric elements selected.
*/
+ bool any_change = false;
m_out.populate_vert();
- /* This is not quite the right test for "no changes" but will do for now. */
- if (m_out.vert_size() == bm->totvert && m_out.face_size() == bm->totface) {
- return false;
- }
-
- /* The BM_ITER_... macros need attention to work in C++. For now, copy the old BMVerts. */
- int totvert_orig = bm->totvert;
- Array<BMVert *> orig_bmv(totvert_orig);
+ /* Initially mark all existing verts as "don't keep", except hidden verts
+ * and verts attached to wire edges.
+ */
for (int v = 0; v < bm->totvert; ++v) {
- orig_bmv[v] = BM_vert_at_index(bm, v);
- }
- for (int v = 0; v < totvert_orig; ++v) {
- BM_vert_kill(bm, orig_bmv[v]);
+ BMVert *bmv = BM_vert_at_index(bm, v);
+ if (BM_elem_flag_test(bmv, BM_ELEM_HIDDEN) || bmvert_attached_to_wire(bmv)) {
+ BM_elem_flag_enable(bmv, KEEP_FLAG);
+ }
+ else {
+ BM_elem_flag_disable(bmv, KEEP_FLAG);
+ }
}
- if (m_out.vert_size() > 0 && m_out.face_size() > 0) {
- Array<BMVert *> new_bmv(m_out.vert_size());
- for (int v : m_out.vert_index_range()) {
- Vertp vertp = m_out.vert(v);
+ /* Reuse old or make new BMVerts, depending on if there's an orig or not.
+ * For those reused, mark them "keep".
+ * Store needed old BMVerts in new_bmvs first, as the table may be unusable after
+ * creating a new BMVert.
+ */
+ Array<BMVert *> new_bmvs(m_out.vert_size());
+ for (int v : m_out.vert_index_range()) {
+ Vertp vertp = m_out.vert(v);
+ int orig = vertp->orig;
+ if (orig != NO_INDEX) {
+ BLI_assert(orig >= 0 && orig < bm->totvert);
+ BMVert *bmv = BM_vert_at_index(bm, orig);
+ new_bmvs[v] = bmv;
+ BM_elem_flag_enable(bmv, KEEP_FLAG);
+ }
+ else {
+ new_bmvs[v] = NULL;
+ }
+ }
+ for (int v : m_out.vert_index_range()) {
+ Vertp vertp = m_out.vert(v);
+ if (new_bmvs[v] == NULL) {
float co[3];
const double3 &d_co = vertp->co;
for (int i = 0; i < 3; ++i) {
co[i] = static_cast<float>(d_co[i]);
}
- new_bmv[v] = BM_vert_create(bm, co, NULL, BM_CREATE_NOP);
+ BMVert *bmv = BM_vert_create(bm, co, NULL, BM_CREATE_NOP);
+ new_bmvs[v] = bmv;
+ BM_elem_flag_enable(bmv, KEEP_FLAG);
+ any_change = true;
+ }
+ }
+
+ /* Initially mark all existing faces as "don't keep", except hidden faces.
+ * Also, save current BMFace pointers as creating faces will disturb the table.
+ */
+ Array<BMFace *> old_bmfs(bm->totface);
+ for (int f = 0; f < bm->totface; ++f) {
+ BMFace *bmf = BM_face_at_index(bm, f);
+ old_bmfs[f] = bmf;
+ if (BM_elem_flag_test(bmf, BM_ELEM_HIDDEN)) {
+ BM_elem_flag_enable(bmf, KEEP_FLAG);
}
- int maxflen = 0;
- for (Facep f : m_out.faces()) {
- maxflen = max_ii(maxflen, static_cast<int>(f->size()));
+ else {
+ BM_elem_flag_disable(bmf, KEEP_FLAG);
}
- Array<BMVert *> face_bmverts(maxflen);
- for (Facep f : m_out.faces()) {
- const Face &face = *f;
- int flen = static_cast<int>(face.size());
+ }
+
+ /* Reuse or make new BMFaces, as the faces are identical to old ones or not.
+ * If reusing, mark them as "keep". First find the maximum face length
+ * so we can declare some arrays outside of the face-creating loop.
+ */
+ int maxflen = 0;
+ for (Facep f : m_out.faces()) {
+ maxflen = max_ii(maxflen, static_cast<int>(f->size()));
+ }
+ Array<BMVert *> face_bmverts(maxflen);
+ Array<BMEdge *> face_bmedges(maxflen);
+ for (Facep f : m_out.faces()) {
+ const Face &face = *f;
+ int flen = static_cast<int>(face.size());
+ for (int i = 0; i < flen; ++i) {
+ Vertp v = face[i];
+ int v_index = m_out.lookup_vert(v);
+ BLI_assert(v_index < new_bmvs.size());
+ face_bmverts[i] = new_bmvs[v_index];
+ }
+ BMFace *bmf = BM_face_exists(face_bmverts.data(), flen);
+ if (bmf != NULL) {
+ BM_elem_flag_enable(bmf, KEEP_FLAG);
+ }
+ else {
+ int orig = face.orig;
+ // BLI_assert(orig != NO_INDEX && orig >= 0 && orig < bm->totface);
+ // BMFace *orig_face = old_bmfs[orig];
+ // TODO(howard): figure out why not all faces have an orig.
+ BMFace *orig_face;
+ if (orig != NO_INDEX) {
+ orig_face = old_bmfs[orig];
+ }
+ else {
+ orig_face = NULL;
+ }
+ /* Make or find BMEdges. */
for (int i = 0; i < flen; ++i) {
- Vertp v = face[i];
- int v_index = m_out.lookup_vert(v);
- BLI_assert(v_index < new_bmv.size());
- face_bmverts[i] = new_bmv[v_index];
+ BMVert *bmv1 = face_bmverts[i];
+ BMVert *bmv2 = face_bmverts[(i + 1) % flen];
+ BMEdge *bme = BM_edge_exists(bmv1, bmv2);
+ if (bme == NULL) {
+ /* TODO(howard): fetch face.edge_orig[i] and use it to fetch example BMEdge,
+ * but will have to store all the BMEdges somewhere before this whole loop.
+ */
+ bme = BM_edge_create(bm, bmv1, bmv2, NULL, BM_CREATE_NOP);
+ }
+ face_bmedges[i] = bme;
}
- BM_face_create_ngon_verts(bm, face_bmverts.begin(), flen, NULL, BM_CREATE_NOP, true, true);
+ BMFace *bmf = BM_face_create(
+ bm, face_bmverts.data(), face_bmedges.data(), flen, orig_face, BM_CREATE_NOP);
+ BM_elem_flag_enable(bmf, KEEP_FLAG);
+ any_change = true;
}
}
- return true;
+
+ /* Now kill the unused faces and verts, and clear flags for kept ones. */
+ /* BM_ITER_MESH_MUTABLE macro needs type casts for C++, so expand here.
+ * TODO(howard): make some nice C++ iterators for BMesh.
+ */
+ BMIter iter;
+ BMFace *bmf = static_cast<BMFace *>(BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL));
+ while (bmf != NULL) {
+#ifdef DEBUG
+ iter.count = BM_iter_mesh_count(BM_FACES_OF_MESH, bm);
+#endif
+ BMFace *bmf_next = static_cast<BMFace *>(BM_iter_step(&iter));
+ if (BM_elem_flag_test(bmf, KEEP_FLAG)) {
+ BM_elem_flag_disable(bmf, KEEP_FLAG);
+ }
+ else {
+ BM_face_kill(bm, bmf);
+ any_change = true;
+ }
+ bmf = bmf_next;
+ }
+ BMVert *bmv = static_cast<BMVert *>(BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL));
+ while (bmv != NULL) {
+#ifdef DEBUG
+ iter.count = BM_iter_mesh_count(BM_VERTS_OF_MESH, bm);
+#endif
+ BMVert *bmv_next = static_cast<BMVert *>(BM_iter_step(&iter));
+ if (BM_elem_flag_test(bmv, KEEP_FLAG)) {
+ BM_elem_flag_disable(bmv, KEEP_FLAG);
+ }
+ else {
+ BM_vert_kill(bm, bmv);
+ any_change = true;
+ }
+ bmv = bmv_next;
+ }
+
+ return any_change;
}
static bool bmesh_boolean(BMesh *bm,
More information about the Bf-blender-cvs
mailing list