[Bf-blender-cvs] [e9092110ff1] master: Fix T94144: Duplicate edges in dual mesh node

[Wannes Malfait]

Commit: e9092110ff1c647bd9d7b2d92dfaef44ba0b9b96
Author: Wannes Malfait
Date:   Mon Dec 20 13:08:05 2021 -0600
Branches: master
https://developer.blender.org/rBe9092110ff1c647bd9d7b2d92dfaef44ba0b9b96

Fix T94144: Duplicate edges in dual mesh node

The duplicated edges were caused by 'oversubdivided' edges, i.e. edges
where some of the vertices on them are only connected to two polygons.
The fix finds these vertices and 'dissolves' them so that only one edge
is created.

For most 'normal' meshes this shouldn't occurr, or only very little, so
the performance impact of this change should be neglegible. In practice
this is also avoidable by triangulating the mesh first.

Differential Revision: https://developer.blender.org/D13445

===================================================================

M	source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc

===================================================================

diff --git a/source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc b/source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
index a3bbeca7af3..d1cbaa540d7 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
@@ -537,6 +537,77 @@ static void add_edge(const Mesh &mesh,
   loop_edges.append(new_edge_i);
 }
 
+/* Returns true if the vertex is connected only to the two polygons and is not on the boundary. */
+static bool vertex_needs_dissolving(const int vertex,
+                                    const int first_poly_index,
+                                    const int second_poly_index,
+                                    const Span<VertexType> vertex_types,
+                                    const Span<Vector<int>> vertex_poly_indices)
+{
+  /* Order is guaranteed to be the same because 2poly verts that are not on the boundary are
+   * ignored in `sort_vertex_polys`. */
+  return (vertex_types[vertex] != VertexType::Boundary &&
+          vertex_poly_indices[vertex].size() == 2 &&
+          vertex_poly_indices[vertex][0] == first_poly_index &&
+          vertex_poly_indices[vertex][1] == second_poly_index);
+}
+
+/**
+ * Finds 'normal' vertices which are connected to only two polygons and marks them to not be
+ * used in the datastructures derived from the mesh. For each pair of polygons which has such a
+ * vertex, an edge is created for the dual mesh between the centers of those two polygons. All
+ * edges in the input mesh which contain such a vertex are marked as 'done' to prevent duplicate
+ * edges being created. (See T94144)
+ */
+static void dissolve_redundant_verts(const Mesh &mesh,
+                                     const Span<Vector<int>> vertex_poly_indices,
+                                     MutableSpan<VertexType> vertex_types,
+                                     MutableSpan<int> old_to_new_edges_map,
+                                     Vector<MEdge> &new_edges,
+                                     Vector<int> &new_to_old_edges_map)
+{
+  for (const int vert_i : IndexRange(mesh.totvert)) {
+    if (vertex_poly_indices[vert_i].size() != 2 || vertex_types[vert_i] != VertexType::Normal) {
+      continue;
+    }
+    const int first_poly_index = vertex_poly_indices[vert_i][0];
+    const int second_poly_index = vertex_poly_indices[vert_i][1];
+    const int new_edge_index = new_edges.size();
+    bool edge_created = false;
+    const MPoly &poly = mesh.mpoly[first_poly_index];
+    for (const MLoop &loop : Span<MLoop>(&mesh.mloop[poly.loopstart], poly.totloop)) {
+      const MEdge &edge = mesh.medge[loop.e];
+      const int v1 = edge.v1;
+      const int v2 = edge.v2;
+      bool mark_edge = false;
+      if (vertex_needs_dissolving(
+              v1, first_poly_index, second_poly_index, vertex_types, vertex_poly_indices)) {
+        /* This vertex is now 'removed' and should be ignored elsewhere. */
+        vertex_types[v1] = VertexType::Loose;
+        mark_edge = true;
+      }
+      if (vertex_needs_dissolving(
+              v2, first_poly_index, second_poly_index, vertex_types, vertex_poly_indices)) {
+        /* This vertex is now 'removed' and should be ignored elsewhere. */
+        vertex_types[v2] = VertexType::Loose;
+        mark_edge = true;
+      }
+      if (mark_edge) {
+        if (!edge_created) {
+          MEdge new_edge = MEdge(edge);
+          /* The vertex indices in the dual mesh are the polygon indices of the input mesh. */
+          new_edge.v1 = first_poly_index;
+          new_edge.v2 = second_poly_index;
+          new_to_old_edges_map.append(loop.e);
+          new_edges.append(new_edge);
+          edge_created = true;
+        }
+        old_to_new_edges_map[loop.e] = new_edge_index;
+      }
+    }
+  }
+}
+
 /**
  * Calculate the barycentric dual of a mesh. The dual is only "dual" in terms of connectivity,
  * i.e. applying the function twice will give the same vertices, edges, and faces, but not the
@@ -564,6 +635,9 @@ static void calc_dual_mesh(GeometrySet &geometry_set,
   Array<VertexType> vertex_types(mesh_in.totvert);
   Array<EdgeType> edge_types(mesh_in.totedge);
   calc_boundaries(mesh_in, vertex_types, edge_types);
+  /* Stores the indices of the polygons connected to the vertex. Because the polygons are looped
+   * over in order of their indices, the polygon's indices will be sorted in ascending order.
+   (This can change once they are sorted using `sort_vertex_polys`). */
   Array<Vector<int>> vertex_poly_indices(mesh_in.totvert);
   Array<Array<int>> vertex_shared_edges(mesh_in.totvert);
   Array<Array<int>> vertex_corners(mesh_in.totvert);
@@ -632,6 +706,16 @@ static void calc_dual_mesh(GeometrySet &geometry_set,
    * don't need a hashmap for that. */
   Array<int> old_to_new_edges_map(mesh_in.totedge);
   old_to_new_edges_map.fill(-1);
+
+  /* This is necessary to prevent duplicate edges from being created, but will likely not do
+   * anything for most meshes. */
+  dissolve_redundant_verts(mesh_in,
+                           vertex_poly_indices,
+                           vertex_types,
+                           old_to_new_edges_map,
+                           new_edges,
+                           new_to_old_edges_map);
+
   for (const int i : IndexRange(mesh_in.totvert)) {
     if (vertex_types[i] == VertexType::Loose || vertex_types[i] >= VertexType::NonManifold ||
         (!keep_boundaries && vertex_types[i] == VertexType::Boundary)) {