[Bf-blender-cvs] [4d58e68565e] newboolean: First test with dissolve of triangulation edges is passing.
Howard Trickey
noreply at git.blender.org
Mon Jun 29 00:48:13 CEST 2020
Commit: 4d58e68565ef92069a0a302af2a57111dca9bd85
Author: Howard Trickey
Date: Sun Jun 28 18:47:08 2020 -0400
Branches: newboolean
https://developer.blender.org/rB4d58e68565ef92069a0a302af2a57111dca9bd85
First test with dissolve of triangulation edges is passing.
Still lots to do. And this includes a horribly inefficient way
of finding which edges are dissolvable -- to be fixed later.
===================================================================
M source/blender/blenlib/intern/boolean.cc
===================================================================
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index c091b5900ff..33f164e1e94 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -15,8 +15,8 @@
*/
#include <algorithm>
-#include <iostream>
#include <fstream>
+#include <iostream>
#include "gmpxx.h"
@@ -33,6 +33,7 @@
#include "BLI_span.hh"
#include "BLI_stack.hh"
#include "BLI_vector.hh"
+#include "BLI_vector_set.hh"
#include "BLI_boolean.h"
@@ -453,7 +454,8 @@ static PatchesInfo find_patches(const TriMesh &tm, const TriMeshTopology &tmtopo
while (!cur_patch_grow.is_empty()) {
int tcand = cur_patch_grow.pop();
if (dbg_level > 1) {
- std::cout << "pop tcand = " << tcand << "; assigned = " << pinfo.tri_is_assigned(tcand) << "\n";
+ std::cout << "pop tcand = " << tcand << "; assigned = " << pinfo.tri_is_assigned(tcand)
+ << "\n";
}
if (pinfo.tri_is_assigned(tcand)) {
continue;
@@ -1207,7 +1209,7 @@ static TriMesh nary_boolean(const TriMesh &tm_in,
int nshapes,
std::function<int(int)> shape_fn)
{
- constexpr int dbg_level = 2;
+ constexpr int dbg_level = 0;
if (dbg_level > 0) {
std::cout << "BOOLEAN of " << nshapes << " operand" << (nshapes == 1 ? "" : "s")
<< " op=" << bool_optype_name(bool_optype) << "\n";
@@ -1223,6 +1225,7 @@ static TriMesh nary_boolean(const TriMesh &tm_in,
auto si_shape_fn = [shape_fn, tm_si](int t) { return shape_fn(tm_si.tri[t].orig()); };
if (dbg_level > 1) {
write_obj_trimesh(tm_si.vert, tm_si.tri, "boolean_tm_input");
+ std::cout << "boolean tm input:\n";
for (int t = 0; t < static_cast<int>(tm_si.tri.size()); ++t) {
std::cout << "tri " << t << " = " << tm_si.tri[t] << " shape " << si_shape_fn(t) << "\n";
}
@@ -1261,20 +1264,21 @@ 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 void triangulate_polymesh(PolyMesh &pm) {
+static void triangulate_polymesh(PolyMesh &pm)
+{
int face_tot = static_cast<int>(pm.face.size());
Array<Array<IndexedTriangle>> face_tris(face_tot);
for (int f = 0; f < face_tot; ++f) {
/* Tesselate face f, following plan similar to BM_face_calc_tesselation. */
int flen = static_cast<int>(pm.face[f].size());
if (flen == 3) {
- face_tris[f] = Array<IndexedTriangle>{ IndexedTriangle(pm.face[f][0], pm.face[f][1], pm.face[f][2], f) };
+ face_tris[f] = Array<IndexedTriangle>{
+ IndexedTriangle(pm.face[f][0], pm.face[f][1], pm.face[f][2], f)};
}
else if (flen == 4) {
face_tris[f] = Array<IndexedTriangle>{
- IndexedTriangle(pm.face[f][0], pm.face[f][1], pm.face[f][2], f),
- IndexedTriangle(pm.face[f][0], pm.face[f][2], pm.face[f][3], f)
- };
+ IndexedTriangle(pm.face[f][0], pm.face[f][1], pm.face[f][2], f),
+ 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 */
@@ -1310,7 +1314,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)
+static 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) {
@@ -1342,24 +1348,340 @@ static void write_obj_polymesh(const Array<mpq3> &vert, const Array<Array<int>>
f.close();
}
-static Vector<Vector<int>> merge_tris_for_face(Vector<int> tris, const TriMesh &tm)
+/* If tri1 and tri2 have a common edge (in opposite orientation), return the indices into tri1 and
+ * tri2 where that common edge starts. Else return (-1,-1).
+ */
+static std::pair<int, int> find_tris_common_edge(const IndexedTriangle &tri1,
+ const IndexedTriangle &tri2)
+{
+ for (int i = 0; i < 3; ++i) {
+ for (int j = 0; j < 3; ++j) {
+ if (tri1[(i + 1) % 3] == tri2[j] && tri1[i] == tri2[(j + 1) % 3]) {
+ return std::pair<int, int>(i, j);
+ }
+ }
+ }
+ return std::pair<int, int>(-1, -1);
+}
+
+struct MergeEdge {
+ /* left_face and right_face are indices into FaceMergeState->face. */
+ int left_face = -1;
+ int right_face = -1;
+ int v1 = -1;
+ int v2 = -1;
+ double len_squared = 0.0;
+ bool dissolvable = false;
+
+ MergeEdge() = default;
+
+ MergeEdge(int va, int vb)
+ {
+ if (va < vb) {
+ this->v1 = va;
+ this->v2 = vb;
+ }
+ else {
+ this->v1 = vb;
+ this->v2 = va;
+ }
+ };
+};
+
+struct MergeFace {
+ /* vert contents are vertex indices in underlying TriMesh. */
+ Vector<int> vert;
+ /* edge contents are edge indices in FaceMergeState, paralleling vert array. */
+ Vector<int> edge;
+ /* If not -1, merge_to gives an index in FaceMergeState that this is merged to. */
+ int merge_to = -1;
+};
+struct FaceMergeState {
+ Vector<MergeFace> face;
+ Vector<MergeEdge> edge;
+ Map<std::pair<int, int>, int> edge_map;
+};
+
+static std::ostream &operator<<(std::ostream &os, const FaceMergeState &fms)
+{
+ os << "faces:\n";
+ for (uint f = 0; f < fms.face.size(); ++f) {
+ std::cout << f << ": verts " << fms.face[f].vert << "\n";
+ std::cout << " edges " << fms.face[f].edge << "\n";
+ std::cout << " merge_to = " << fms.face[f].merge_to << "\n";
+ }
+ os << "\nedges:\n";
+ for (uint e = 0; e < fms.edge.size(); ++e) {
+ std::cout << e << ": (" << fms.edge[e].v1 << "," << fms.edge[e].v2
+ << ") left=" << fms.edge[e].left_face << " right=" << fms.edge[e].right_face
+ << " dis=" << fms.edge[e].dissolvable << "\n";
+ }
+ return os;
+}
+
+/* Does (av1,av2) overlap (bv1,bv2) at more than a single point? */
+static bool segs_overlap(const mpq3 av1, const mpq3 av2, const mpq3 bv1, const mpq3 bv2)
+{
+ mpq3 a = av2 - av1;
+ mpq3 b = bv2 - bv1;
+ mpq3 ab = mpq3::cross(a, b);
+ if (ab.x == 0 && ab.y == 0 && ab.z == 0) {
+ /*
+ * Lines containing a and b are collinear.
+ * Find r and s such that bv1 = av1 + r a and bv2 = av1 + s a.
+ * We can do this in 1D, projected onto any axis where a is not zero.
+ */
+ int axis = mpq3::dominant_axis(a);
+ if (a[axis] == 0 || (b.x == 0 && b.y == 0 && b.z == 0)) {
+ /* One or both segs is a point --> cannot intersect in more than a point. */
+ return false;
+ }
+ mpq_class s = (bv1[axis] - av1[axis]) / a[axis];
+ mpq_class r = (bv2[axis] - av1[axis]) / a[axis];
+ /* Do intervals [0, 1] and [r,s] overlap nontrivially? First make r < s. */
+ if (s < r) {
+ SWAP(mpq_class, r, s);
+ }
+ if (r >= 1 || s <= 0) {
+ return false;
+ }
+ else {
+ /* We know intersection interval starts strictly before av2 and ends strictly after av1. */
+ return r != s;
+ }
+ }
+ return false;
+}
+
+/* Any edge in fms that does not overlap an edge in pm_in is dissolvable.
+ * TODO: implement a much more efficient way of doing this O(n^2) algorithm!
+ * Probably eventually will just plumb through edge representatives from beginning
+ * to tm and can dump this altogether.
+ * We set len_squared here, which we only need for dissolvable edges.
+ */
+static void find_dissolvable_edges(FaceMergeState *fms, const TriMesh &tm, const PolyMesh &pm_in)
+{
+ for (uint me_index = 0; me_index < fms->edge.size(); ++me_index) {
+ MergeEdge &me = fms->edge[me_index];
+ const mpq3 &me_v1 = tm.vert[me.v1];
+ const mpq3 &me_v2 = tm.vert[me.v2];
+ bool me_dis = true;
+ for (uint pm_f_index = 0; pm_f_index < pm_in.face.size() && me_dis; ++pm_f_index) {
+ const Array<int> &pm_f = pm_in.face[pm_f_index];
+ int f_size = static_cast<int>(pm_f.size());
+ for (int i = 0; i < f_size && me_dis; ++i) {
+ int inext = (i + 1) % f_size;
+ const mpq3 &pm_v1 = pm_in.vert[pm_f[i]];
+ const mpq3 &pm_v2 = pm_in.vert[pm_f[inext]];
+ if (segs_overlap(me_v1, me_v2, pm_v1, pm_v2)) {
+ me_dis = false;
+ }
+ }
+ }
+ me.dissolvable = me_dis;
+ if (me_dis) {
+ mpq3 evec = me_v2 - me_v1;
+ me.len_squared = evec.length_squared().get_d();
+ }
+ }
+}
+
+static void init_face_merge_state(FaceMergeState *fms,
+ const Vector<int> &tris,
+ const TriMesh &tm,
+ const PolyMesh &pm_in)
+{
+ const int dbg_level = 0;
+ /* Reserve enough faces and edges so that neither will have to resize. */
+ fms->face.reserve(tris.size() + 1);
+ fms->edge.reserve((3 * tris.size()));
+ fms->edge_map.reserve(3 * tris.size());
+ if (dbg_level > 0) {
+ std::cout << "\nINIT_FACE_MERGE_STATE\n";
+ }
+ for (uint t = 0; t < tris.size(); ++t) {
+ MergeFace mf;
+ const IndexedTriangle &tri = tm.tri[tris[t]];
+ mf.vert.append(tri.v0());
+ mf.vert.append(tri.v1());
+ mf.vert.append(tri.v2());
+ int f = static_cast<int>(fms->face.append_and_get_index(mf));
+ for (int i = 0; i < 3; ++i) {
+ int inext = (i + 1) % 3;
+ MergeEdge new_me(mf.vert[i], mf.vert[inext]);
+ std::pair<int, int> canon_vs(new_me.v1, new_me.v2);
+ int me_index = fms->edge_map.lookup_default(canon_vs, -1);
+ if (me_index == -1) {
+ fms->edge.append(new_me);
+ me_index = static_cast<int>(fms->edge.size()) - 1;
+ fms->edge_map.add_new(canon_vs, me_index);
+ }
+ MergeEdge &me = fms->edge[me_index];
+ /* This face is left or right depending on orientation of edge. */
+ if (me.v1 == mf.vert[i]) {
+ BLI_assert(me.left_face == -1);
+ fms->edge[me_index].left_face = f;
+ }
+ else {
+ BLI_assert(me.right_face == -1);
+ fms->edge[me_index].right_face = f;
+ }
+ fms->face[f].edge.append(me_index);
+ }
+ }
+ find_dissolvable_edges(fms, tm, pm_in);
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list