[Bf-blender-cvs] [66f511018eb] newboolean: Dissolving triangulation edges and verts passes first test.
Howard Trickey
noreply at git.blender.org
Tue Jun 30 20:47:02 CEST 2020
Commit: 66f511018ebf47bf2165acfca4de397d1ed03fe9
Author: Howard Trickey
Date: Tue Jun 30 14:46:08 2020 -0400
Branches: newboolean
https://developer.blender.org/rB66f511018ebf47bf2165acfca4de397d1ed03fe9
Dissolving triangulation edges and verts passes first test.
===================================================================
M source/blender/blenlib/BLI_boolean.h
M source/blender/blenlib/BLI_mpq3.hh
M source/blender/blenlib/intern/boolean.cc
M source/blender/blenlib/intern/math_vec.cc
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 080804dd643..87b778c94e6 100644
--- a/source/blender/blenlib/BLI_boolean.h
+++ b/source/blender/blenlib/BLI_boolean.h
@@ -80,6 +80,10 @@ struct PolyMesh {
PolyMesh boolean(PolyMesh &pm, int bool_optype, int nshapes, std::function<int(int)> shape_fn);
+void write_obj_polymesh(const Array<mpq3> &vert,
+ const Array<Array<int>> &face,
+ const std::string &objname);
+
} // namespace meshintersect
} // namespace blender
diff --git a/source/blender/blenlib/BLI_mpq3.hh b/source/blender/blenlib/BLI_mpq3.hh
index af510e9f849..1efa8c9ad7b 100644
--- a/source/blender/blenlib/BLI_mpq3.hh
+++ b/source/blender/blenlib/BLI_mpq3.hh
@@ -249,6 +249,8 @@ struct mpq3 {
return ((x > y) ? ((x > z) ? 0 : 2) : ((y > z) ? 1 : 2));
}
+ static mpq3 cross_poly(const mpq3 *poly, int n);
+
static int orient3d(const mpq3 &a, const mpq3 &b, const mpq3 &c, const mpq3 &d);
/* There is a sensible use for hashing on exact arithmetic types. */
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index 33f164e1e94..7fa946870ce 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -1264,6 +1264,54 @@ static TriMesh binary_boolean(const TriMesh &tm_in_a, const TriMesh &tm_in_b, in
return nary_boolean(tm_in, bool_optype, 2, shape_fn);
}
+static Array<IndexedTriangle> triangulate_poly(int orig_face,
+ const Array<int> &face,
+ const Array<mpq3> &vert)
+{
+ int flen = static_cast<int>(face.size());
+ CDT_input<mpq_class> cdt_in;
+ cdt_in.vert = Array<mpq2>(flen);
+ cdt_in.face = Array<Vector<int>>(1);
+ cdt_in.face[0].reserve(flen);
+ Array<mpq3> face_verts(flen);
+ for (int i = 0; i < flen; ++i) {
+ cdt_in.face[0].append(i);
+ face_verts[i] = vert[face[i]];
+ }
+ /* Project poly along dominant axis of normal to get 2d coords. */
+ mpq3 poly_normal = mpq3::cross_poly(face_verts.begin(), flen);
+ int axis = mpq3::dominant_axis(poly_normal);
+ /* If project down y axis as opposed to x or z, the orientation
+ * of the polygon will be reversed.
+ */
+ bool rev = (axis == 1);
+ for (int i = 0; i < flen; ++i) {
+ int ii = rev ? flen - i - 1 : i;
+ mpq2 &p2d = cdt_in.vert[ii];
+ int k = 0;
+ for (int j = 0; j < 3; ++j) {
+ if (j != axis) {
+ p2d[k++] = face_verts[ii][j];
+ }
+ }
+ }
+ CDT_result<mpq_class> cdt_out = delaunay_2d_calc(cdt_in, CDT_INSIDE);
+ int n_tris = static_cast<int>(cdt_out.face.size());
+ Array<IndexedTriangle> ans(n_tris);
+ for (int t = 0; t < n_tris; ++t) {
+ /* Assume no input verts to CDT were merged. Not necessarily true. FIXME. */
+ BLI_assert(cdt_out.vert.size() == cdt_in.vert.size());
+ int v0_out = cdt_out.face[t][0];
+ int v1_out = cdt_out.face[t][1];
+ int v2_out = cdt_out.face[t][2];
+ int v0 = face[v0_out];
+ int v1 = face[v1_out];
+ int v2 = face[v2_out];
+ ans[t] = IndexedTriangle(v0, v1, v2, orig_face);
+ }
+ return ans;
+}
+
static void triangulate_polymesh(PolyMesh &pm)
{
int face_tot = static_cast<int>(pm.face.size());
@@ -1281,9 +1329,7 @@ static void triangulate_polymesh(PolyMesh &pm)
IndexedTriangle(pm.face[f][0], pm.face[f][2], pm.face[f][3], f)};
}
else {
- /* TODO: use CDT to do this. cf do_cdt in mesh_intersect.cc */
- std::cout << "IMPLEMENT ME - TESSELATE FACES OF SIZE > 4\n";
- BLI_assert(false);
+ face_tris[f] = triangulate_poly(f, pm.face[f], pm.vert);
}
}
pm.triangulation.set(face_tris);
@@ -1314,9 +1360,9 @@ static TriMesh trimesh_from_polymesh(PolyMesh &pm)
}
/* For Debugging. */
-static void write_obj_polymesh(const Array<mpq3> &vert,
- const Array<Array<int>> &face,
- const std::string &objname)
+void write_obj_polymesh(const Array<mpq3> &vert,
+ const Array<Array<int>> &face,
+ const std::string &objname)
{
constexpr const char *objdir = "/tmp/";
if (face.size() == 0) {
@@ -1540,12 +1586,42 @@ static void init_face_merge_state(FaceMergeState *fms,
* (which will happen if there's another edge sharing the same two faces);
* or (b) it would create a face with a repeated vertex.
*/
-static bool dissolve_leaves_valid_bmesh(FaceMergeState *UNUSED(fms),
- const MergeEdge &UNUSED(me),
- const MergeFace &UNUSED(mf_left),
- const MergeFace &UNUSED(mf_right))
+static bool dissolve_leaves_valid_bmesh(FaceMergeState *fms,
+ const MergeEdge &me,
+ int me_index,
+ const MergeFace &mf_left,
+ const MergeFace &mf_right)
{
- return true; /* TODO: IMPLEMENT ME! */
+ int a_edge_start = mf_left.edge.first_index_of_try(me_index);
+ int b_edge_start = mf_right.edge.first_index_of_try(me_index);
+ BLI_assert(a_edge_start != -1 && b_edge_start != -1);
+ int alen = static_cast<int>(mf_left.vert.size());
+ int blen = static_cast<int>(mf_right.vert.size());
+ int b_left_face = me.right_face;
+ bool ok = true;
+ /* Is there another edge, not me, in A's face, whose right face is B's left? */
+ for (int a_e_index = (a_edge_start + 1) % alen; ok && a_e_index != a_edge_start;
+ a_e_index = (a_e_index + 1) % alen) {
+ const MergeEdge &a_me_cur = fms->edge[mf_left.edge[a_e_index]];
+ if (a_me_cur.right_face == b_left_face) {
+ ok = false;
+ }
+ }
+ /* Is there a vert in A, not me.v1 or me.v2, that is also in B?
+ * One could avoid this O(n^2) algorithm if had a structure saying which faces a vertex touches.
+ */
+ for (int a_v_index = 0; ok && a_v_index < alen; ++a_v_index) {
+ int a_v = mf_left.vert[a_v_index];
+ if (a_v != me.v1 && a_v != me.v2) {
+ for (int b_v_index = 0; b_v_index < blen; ++b_v_index) {
+ int b_v = mf_right.vert[b_v_index];
+ if (a_v == b_v) {
+ ok = false;
+ }
+ }
+ }
+ }
+ return ok;
}
/* mf_left and mf_right should share a MergeEdge me, having index me_index.
@@ -1603,6 +1679,12 @@ static void splice_faces(
me.right_face = -1;
}
+/* Given that fms has been properly initialized to contain a set of faces that
+ * together form a face or part of a face of the original PolyMesh, and that
+ * it has properly recorded with faces are dissolvable, dissolve as many edges as possible.
+ * We try to dissolve in decreasing order of edge length, so that it is more likely
+ * that the final output doesn't have awkward looking long edges with extreme angles.
+ */
static void do_dissolve(FaceMergeState *fms)
{
const int dbg_level = 0;
@@ -1618,9 +1700,10 @@ static void do_dissolve(FaceMergeState *fms)
if (dissolve_edges.size() == 0) {
return;
}
+ /* Things look nicer if we dissolve the longer edges first. */
std::sort(
dissolve_edges.begin(), dissolve_edges.end(), [fms](const int &a, const int &b) -> bool {
- return (fms->edge[a].len_squared < fms->edge[b].len_squared);
+ return (fms->edge[a].len_squared > fms->edge[b].len_squared);
});
if (dbg_level > 0) {
std::cout << "Sorted dissolvable edges: " << dissolve_edges << "\n";
@@ -1632,7 +1715,7 @@ static void do_dissolve(FaceMergeState *fms)
}
MergeFace &mf_left = fms->face[me.left_face];
MergeFace &mf_right = fms->face[me.right_face];
- if (!dissolve_leaves_valid_bmesh(fms, me, mf_left, mf_right)) {
+ if (!dissolve_leaves_valid_bmesh(fms, me, me_index, mf_left, mf_right)) {
continue;
}
if (dbg_level > 0) {
@@ -1646,6 +1729,11 @@ static void do_dissolve(FaceMergeState *fms)
}
}
+/* Given that tris form a triangulation of a face or part of a face that was in pm_in,
+ * merge as many of the triangles together as possible, by dissolving the edges between them.
+ * We can only dissolve triangulation edges that don't overlap real input edges, and we
+ * can only dissolve them if doing so leaves the remaining faces able to create valid BMesh.
+ */
static Vector<Vector<int>> merge_tris_for_face(Vector<int> tris,
const TriMesh &tm,
const PolyMesh &pm_in)
@@ -1654,7 +1742,10 @@ static Vector<Vector<int>> merge_tris_for_face(Vector<int> tris,
Vector<Vector<int>> ans;
if (tris.size() == 2) {
/* Is this a case where quad with one diagonal remained unchanged? */
- /* TODO: could be diagonal is not dissolvable if this isn't whole original face. FIXME. */
+ /* TODO: could be diagonal is not dissolvable if this isn't whole original face. FIXME.
+ * We could just use the code below for this case too, but this seems likely to be
+ * such a common case that it is worth trying to handle specially, with less work.
+ */
const IndexedTriangle &tri1 = tm.tri[tris[0]];
const IndexedTriangle &tri2 = tm.tri[tris[1]];
std::pair<int, int> estarts = find_tris_common_edge(tri1, tri2);
@@ -1681,18 +1772,151 @@ static Vector<Vector<int>> merge_tris_for_face(Vector<int> tris,
ans[ans.size() - 1] = mf.vert;
}
}
-#if 0
- for (uint i = 0; i < tris.size(); ++i) {
- ans.append(Vector<int>());
- const IndexedTriangle &tri = tm.tri[tris[i]];
- ans[i].append(tri.v0());
- ans[i].append(tri.v1());
- ans[i].append(tri.v2());
- }
-#endif
return ans;
}
+/* Return an array, paralleling pm_out.vert, saying which vertices can be dissolved.
+ * A vertex v can be dissolved if (a) it is not an input vertex; (b) it has valence 2;
+ * and (c) if v's two neighboring vertices are u and w, then (u,v,w) forms a straight line.
+ * Return the number of dissolvable vertices in r_count_dissolve.
+ */
+static Array<bool> find_dissolve_verts(const PolyMesh &pm_out,
+ const PolyMesh
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list