From 98b1a716d65f187a2499eba2475e4d456f8ed107 Mon Sep 17 00:00:00 2001
From: Germano Cavalcante <germano.costa@ig.com.br>
Date: Tue, 14 Jul 2020 15:18:03 -0300
Subject: Cleanup: simplify Weld Modifier logic

The original code to rearrange the weld vertices map was confusing.

It traverses the overlap result multiple times within a loop.

This part of the code has therefore been rethought, simplified and commented.

This also results in a slight improvement in the performance of the modifier.
---
 source/blender/modifiers/intern/MOD_weld.c | 87 +++++++++++++++---------------
 1 file changed, 44 insertions(+), 43 deletions(-)

diff --git a/source/blender/modifiers/intern/MOD_weld.c b/source/blender/modifiers/intern/MOD_weld.c
index cf92da1b0e6..ec5d7feba41 100644
--- a/source/blender/modifiers/intern/MOD_weld.c
+++ b/source/blender/modifiers/intern/MOD_weld.c
@@ -395,55 +395,51 @@ static void weld_vert_ctx_alloc_and_setup(const uint mvert_len,
     *v_dest_iter = OUT_OF_CONTEXT;
   }
 
-  uint vert_kill_len = 0;
-  const BVHTreeOverlap *overlap_iter = &overlap[0];
-  for (uint i = 0; i < overlap_len; i++, overlap_iter++) {
+  const BVHTreeOverlap *overlap_iter, *overlap_end;
+  overlap_iter = &overlap[0];
+  overlap_end = overlap + overlap_len;
+  for (; overlap_iter < overlap_end; overlap_iter++) {
     uint indexA = overlap_iter->indexA;
     uint indexB = overlap_iter->indexB;
 
     BLI_assert(indexA < indexB);
+    r_vert_dest_map[indexA] = indexB;
+  }
 
-    uint va_dst = r_vert_dest_map[indexA];
-    uint vb_dst = r_vert_dest_map[indexB];
-    if (va_dst == OUT_OF_CONTEXT) {
-      if (vb_dst == OUT_OF_CONTEXT) {
-        vb_dst = indexA;
-        r_vert_dest_map[indexB] = vb_dst;
-      }
-      r_vert_dest_map[indexA] = vb_dst;
-      vert_kill_len++;
+  /**
+   * Point all groups of merged vertices to the same vertex.
+   * That is, if the pairs of vertices are:
+   *   [1, 2], [2, 3] and [3, 4],
+   * Adjust they to:
+   *   [1, 4], [2, 4] and [3, 4].
+   */
+  v_dest_iter = &r_vert_dest_map[0];
+  for (uint i = 0; i < mvert_len; i++, v_dest_iter++) {
+    uint v_dest = *v_dest_iter;
+    uint v_dest_final = v_dest;
+
+    /* ELEM_MERGED or OUT_OF_CONTEXT. */
+    if ((int)v_dest_final < 0) {
+      continue;
     }
-    else if (vb_dst == OUT_OF_CONTEXT) {
-      r_vert_dest_map[indexB] = va_dst;
-      vert_kill_len++;
+
+    uint index_test;
+    while ((int)(index_test = r_vert_dest_map[v_dest_final]) >= 0) {
+      v_dest_final = index_test;
     }
-    else if (va_dst != vb_dst) {
-      uint v_new, v_old;
-      if (va_dst < vb_dst) {
-        v_new = va_dst;
-        v_old = vb_dst;
-      }
-      else {
-        v_new = vb_dst;
-        v_old = va_dst;
-      }
-      BLI_assert(r_vert_dest_map[v_old] == v_old);
-      BLI_assert(r_vert_dest_map[v_new] == v_new);
-      vert_kill_len++;
-
-      const BVHTreeOverlap *overlap_iter_b = &overlap[0];
-      for (uint j = i + 1; j--; overlap_iter_b++) {
-        indexA = overlap_iter_b->indexA;
-        indexB = overlap_iter_b->indexB;
-        va_dst = r_vert_dest_map[indexA];
-        vb_dst = r_vert_dest_map[indexB];
-        if (ELEM(v_old, vb_dst, va_dst)) {
-          r_vert_dest_map[indexA] = v_new;
-          r_vert_dest_map[indexB] = v_new;
-        }
+
+    if (v_dest_final != v_dest) {
+      r_vert_dest_map[i] = v_dest_final;
+
+      /* Since we have found the final destination vertex,
+       * it is better to update the entire path at once. */
+      while ((int)(index_test = r_vert_dest_map[v_dest]) >= 0) {
+        r_vert_dest_map[v_dest] = v_dest_final;
+        v_dest = index_test;
       }
-      BLI_assert(r_vert_dest_map[v_old] == v_new);
     }
+
+    r_vert_dest_map[v_dest_final] = ELEM_MERGED;
   }
 
   /* Vert Context. */
@@ -455,8 +451,13 @@ static void weld_vert_ctx_alloc_and_setup(const uint mvert_len,
 
   v_dest_iter = &r_vert_dest_map[0];
   for (uint i = 0; i < mvert_len; i++, v_dest_iter++) {
-    if (*v_dest_iter != OUT_OF_CONTEXT) {
-      wv->vert_dest = *v_dest_iter;
+    uint v_dest = *v_dest_iter;
+    if (v_dest != OUT_OF_CONTEXT) {
+      if (v_dest == ELEM_MERGED) {
+        /* Point to itself. Useful for finding groups. */
+        *v_dest_iter = v_dest = i;
+      }
+      wv->vert_dest = v_dest;
       wv->vert_orig = i;
       wv++;
       wvert_len++;
@@ -469,7 +470,7 @@ static void weld_vert_ctx_alloc_and_setup(const uint mvert_len,
 
   *r_wvert = MEM_reallocN(wvert, sizeof(*wvert) * wvert_len);
   *r_wvert_len = wvert_len;
-  *r_vert_kill_len = vert_kill_len;
+  *r_vert_kill_len = overlap_len;
 }
 
 static void weld_vert_groups_setup(const uint mvert_len,
-- 
cgit v1.2.3