Fix T74195: Solidify Complex Dissolve Crash.

I also added a few more comments to the code as I gone along.

Maniphest Tasks: T74195

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

1 files changed, 82 insertions, 34 deletions

diff --git a/source/blender/modifiers/intern/MOD_solidify_nonmanifold.c b/source/blender/modifiers/intern/MOD_solidify_nonmanifold.c
index 23053adfd5a..3cd045b73ae 100644
--- a/source/blender/modifiers/intern/MOD_solidify_nonmanifold.c
+++ b/source/blender/modifiers/intern/MOD_solidify_nonmanifold.c
@@ -243,6 +243,7 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
       if (mp->totloop > largest_ngon) {
         largest_ngon = (uint)mp->totloop;
       }
+      /* add to final mesh face count */
       if (do_shell) {
         numNewPolys += 2;
         numNewLoops += (uint)mp->totloop * 2;
@@ -272,7 +273,7 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
   /* Edge groups for every original vert. */
   EdgeGroup **orig_vert_groups_arr = MEM_calloc_arrayN(
       numVerts, sizeof(*orig_vert_groups_arr), "orig_vert_groups_arr in solidify");
-  /* Duplicate verts map. */
+  /* vertex map used to map duplicates. */
   uint *vm = MEM_malloc_arrayN(numVerts, sizeof(*vm), "orig_vert_map in solidify");
   for (uint i = 0; i < numVerts; i++) {
     vm[i] = i;
@@ -309,15 +310,15 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
             BLI_assert(len > 0);
             uint *adj_faces = MEM_malloc_arrayN(
                 len, sizeof(*adj_faces), "OldEdgeFaceRef::faces in solidify");
-            bool *adj_faces_loops_reversed = MEM_malloc_arrayN(
-                len, sizeof(*adj_faces_loops_reversed), "OldEdgeFaceRef::reversed in solidify");
+            bool *adj_faces_reversed = MEM_malloc_arrayN(
+                len, sizeof(*adj_faces_reversed), "OldEdgeFaceRef::reversed in solidify");
             adj_faces[0] = i;
             for (uint k = 1; k < len; k++) {
               adj_faces[k] = MOD_SOLIDIFY_EMPTY_TAG;
             }
-            adj_faces_loops_reversed[0] = reversed;
+            adj_faces_reversed[0] = reversed;
             OldEdgeFaceRef *ref = MEM_mallocN(sizeof(*ref), "OldEdgeFaceRef in solidify");
-            *ref = (OldEdgeFaceRef){adj_faces, len, adj_faces_loops_reversed, 1};
+            *ref = (OldEdgeFaceRef){adj_faces, len, adj_faces_reversed, 1};
             edge_adj_faces[edge] = ref;
           }
           else {
@@ -339,6 +340,7 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
     {
       bool *face_singularity = MEM_calloc_arrayN(
           numPolys, sizeof(*face_singularity), "face_sides_arr in solidify");
+      
       ed = orig_medge;
       for (uint i = 0; i < numEdges; i++, ed++) {
         if (edge_adj_faces_len[i] > 0) {
@@ -348,7 +350,7 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
             sub_v3_v3v3(edgedir, orig_mvert[v2].co, orig_mvert[v1].co);
             orig_edge_lengths[i] = len_squared_v3(edgedir);
           }
-          if (v1 == v2 || orig_edge_lengths[i] <= FLT_EPSILON) {
+          if (v1 != v2 && orig_edge_lengths[i] <= FLT_EPSILON) {
             if (v2 > v1) {
               for (uint j = v2; j < numVerts; j++) {
                 if (vm[j] == v2) {
@@ -370,40 +372,59 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
             if (do_shell) {
               numNewLoops -= edge_adj_faces_len[i] * 2;
             }
-            if (v1 == v2) {
-              /* Remove polys. */
-              for (uint j = 0; j < edge_adj_faces[i]->faces_len; j++) {
-                const uint face = edge_adj_faces[i]->faces[j];
-                if (!face_singularity[face]) {
-                  bool is_singularity = true;
-                  for (uint k = 0; k < orig_mpoly[face].totloop; k++) {
-                    if (vm[orig_mloop[((uint)orig_mpoly[face].loopstart) + k].v] != v1) {
-                      is_singularity = false;
-                      break;
-                    }
-                  }
-                  if (is_singularity) {
-                    face_singularity[face] = true;
-                    if (do_shell) {
-                      numNewPolys -= 2;
-                    }
-                  }
-                }
-              }
-            }
+            
             edge_adj_faces_len[i] = 0;
             MEM_freeN(edge_adj_faces[i]->faces);
             MEM_freeN(edge_adj_faces[i]->faces_reversed);
             MEM_freeN(edge_adj_faces[i]);
             edge_adj_faces[i] = NULL;
           }
-          else if (edge_adj_faces_len[i] > 0) {
+          else if (v1 != v2 && edge_adj_faces_len[i] > 0) {
             orig_edge_lengths[i] = sqrtf(orig_edge_lengths[i]);
             vert_adj_edges_len[v1]++;
             vert_adj_edges_len[v2]++;
           }
         }
       }
+      /* remove zero faces in a second pass */
+      ed = orig_medge;
+      for (uint i = 0; i < numEdges; i++, ed++) {
+        const uint v1 = vm[ed->v1];
+        const uint v2 = vm[ed->v2];
+        if (v1 == v2 && edge_adj_faces[i]) {
+          /* Remove polys. */
+          for (uint j = 0; j < edge_adj_faces[i]->faces_len; j++) {
+            const uint face = edge_adj_faces[i]->faces[j];
+            if (!face_singularity[face]) {
+              bool is_singularity = true;
+              for (uint k = 0; k < orig_mpoly[face].totloop; k++) {
+                if (vm[orig_mloop[((uint)orig_mpoly[face].loopstart) + k].v] != v1) {
+                  is_singularity = false;
+                  break;
+                }
+              }
+              if (is_singularity) {
+                face_singularity[face] = true;
+                /* remove from final mesh poly count */
+                if (do_shell) {
+                  numNewPolys -= 2;
+                }
+              }
+            }
+          }
+          
+          if (do_shell) {
+            numNewLoops -= edge_adj_faces_len[i] * 2;
+          }
+
+          edge_adj_faces_len[i] = 0;
+          MEM_freeN(edge_adj_faces[i]->faces);
+          MEM_freeN(edge_adj_faces[i]->faces_reversed);
+          MEM_freeN(edge_adj_faces[i]);
+          edge_adj_faces[i] = NULL;
+        }
+      }
+
       MEM_freeN(face_singularity);
     }
 
@@ -478,6 +499,7 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
                 }
               }
             }
+            /* remove from final face count */
             if (do_shell) {
               numNewPolys -= 2 * j;
               numNewLoops -= 4 * j;
@@ -779,6 +801,7 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
             /* TODO check where the null pointer come from,
              * because there should not be any... */
             if (new_edges) {
+              /* count the number of new edges around the original vert */
               while (*new_edges) {
                 unassigned_edges_len++;
                 new_edges++;
@@ -797,8 +820,10 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
             }
           }
 
+          /* an edge group will always contain min 2 edges so max edge group count can be calculated */
+          uint edge_groups_len = unassigned_edges_len / 2;
           edge_groups = MEM_calloc_arrayN(
-              (unassigned_edges_len / 2) + 1, sizeof(*edge_groups), "edge_groups in solidify");
+              edge_groups_len + 1, sizeof(*edge_groups), "edge_groups in solidify");
 
           uint assigned_edges_len = 0;
           NewEdgeRef *found_edge = NULL;
@@ -807,14 +832,15 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
           uint eg_capacity = 5;
           NewFaceRef *eg_track_faces[2] = {NULL, NULL};
           NewFaceRef *last_open_edge_track = NULL;
-          NewEdgeRef *edge = NULL;
 
           while (assigned_edges_len < unassigned_edges_len) {
             found_edge = NULL;
             insert_at_start = false;
             if (eg_index >= 0 && edge_groups[eg_index].edges_len == 0) {
+              /* called everytime a new group was started in the last iteration */
+              /* find an unused edge to start the next group and setup variables to start creating it */
               uint j = 0;
-              edge = NULL;
+              NewEdgeRef *edge = NULL;
               while (!edge && j < unassigned_edges_len) {
                 edge = unassigned_edges[j++];
                 if (edge && last_open_edge_track &&
@@ -856,7 +882,7 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
               for (found_edge_index = 0; found_edge_index < unassigned_edges_len;
                    found_edge_index++, edge_ptr++) {
                 if (*edge_ptr) {
-                  edge = *edge_ptr;
+                  NewEdgeRef *edge = *edge_ptr;
                   if (edge->faces[0] == eg_track_faces[1]) {
                     insert_at_start = false;
                     eg_track_faces[1] = edge->faces[1];
@@ -932,8 +958,10 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
               }
             }
             else {
+              /* called on first iteration to clean up the eg_index = -1 and start the first group,
+               * or when the current group is found to be complete (no new found_edge) */
               eg_index++;
-              BLI_assert(eg_index < (unassigned_edges_len / 2));
+              BLI_assert(eg_index < edge_groups_len);
               eg_capacity = 5;
               NewEdgeRef **edges = MEM_calloc_arrayN(
                   eg_capacity, sizeof(*edges), "edge_group in solidify");
@@ -959,7 +987,10 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
           eg_index++;
           /* #topo_groups is the number of topo groups from here on. */
           topo_groups++;
+
           MEM_freeN(unassigned_edges);
+
+          /* TODO reshape the edge_groups array to its actual size after writing is finished to save on memory */
         }
 
         /* Split of long self intersection groups */
@@ -1788,10 +1819,28 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
   /* DEBUG CODE FOR BUGFIXING (can not be removed because every bugfix needs this badly!). */
 #if 0
   {
+    /* this code will output the content of orig_vert_groups_arr.
+     * in orig_vert_groups_arr these conditions must be met for every vertex:
+     * - new_edge value should have no duplicates
+     * - every old_edge value should appear twice
+     * - every group should have at least two members (edges)
+     * Note: that there can be vertices that only have one group. They are called singularities.
+     * These vertices will only have one side (there is no way of telling apart front
+     * from back like on a mobius strip)
+     */
+
+    /* Debug output format:
+     * <original vertex id>:
+     * {
+     *   { <old edge id>/<new edge id>, } (tg:<topology group id>)(s:<is split group>,c:<is closed group (before splitting)>)
+     * }
+     */
     gs_ptr = orig_vert_groups_arr;
     for (uint i = 0; i < numVerts; i++, gs_ptr++) {
       EdgeGroup *gs = *gs_ptr;
+      /* check if the vertex is present (may be dissolved because of proximity) */
       if (gs) {
+        printf("%d:\n", i);
         for (EdgeGroup *g = gs; g->valid; g++) {
           NewEdgeRef **e = g->edges;
           for (uint j = 0; j < g->edges_len; j++, e++) {
@@ -1799,7 +1848,6 @@ Mesh *MOD_solidify_nonmanifold_applyModifier(ModifierData *md,
           }
           printf("(tg:%u)(s:%u,c:%d)\n", g->topo_group, g->split, g->is_orig_closed);
         }
-        printf("\n");
       }
     }
   }