Could you submit the performance improvement of the default (Full) Weld Modifier in another patch?
Once the other patch is reviewed and accepted, it can be committed and this one can be updated.

Thanks for the patch.
Seeing the code, I have some ideas on how to improve readability/style (mainly of the _ctx_alloc and _ctx_setup functions).
I will work on that later.

These are the warnings raised when compiling:

'v_mask_act': unreferenced formal parameter
'medge': local variable is initialized but not referenced
'totedge': local variable is initialized but not referenced

I'm not sure I understand the "chain merging" problem.
So I decided to test this patch removing all the changes that at first sight don't seem to be necessary.
Here is the resulting patch:

It worked very well in my tests and is certainly more efficient.
Can you provide a file that shows the problem mentioned?

Oh right I missed to mention one thing. Solidify used the original vertex positions back then (and now the ones from this new array), so the problem was much worse in that case, as it always merged to the last vertex. In case of the weld modifier it's a bit better because it merges to the center of the merged verts, so it's not order dependend. I mean removing those array would make it faster, but just look at the difference.

Steps to reproduce the problem:
(apply P1649 and run blender)

1. Open the file in T75032 (F8369236).
2. Disable the Solidify Modifier. And add a Weld Modifier.
3. Increase parameter "Resolution Preview U" from 1 to 5 or more and watch.
4. Now enable solidify again and disable weld (make sure they have the same merge threshold).
5. repeat step 3. and watch the difference. My current patch has the same behavior as solidify there.

Another way to clearly see the difference is to apply 5 subsurf levels on a cube and then add a weld modifier and slowly turn up the merge threshold.

EDIT:
Hold on, I was just testing it a bit more and it doesn't immediatly seem to show the issue that I though would definitly happen. So I will take some time and investigate further... maybe there is a good way to get rid of something here.

Ok I investigated a bit further. First of all, just removing those two arrays from my implementation does not seem to change the result too much (in the image below, you would not immediatly see the quality difference). It's just a bit more unpredictable and in some special cases really bad (what I call chain merging, observable in F8369236).

But your proposed patch still used overlaps and therefore creates significantly different results. Look at this comparison (same settings and everything):

using overlap	using vert_dest_map directly and the helper arrays

Also note that I could increase the merge distance, but then we would be looking at an empty image on the left and a still very good image at the right.

I also checked the performance by adding a wave modifier and observing the fps. My results were:

1. There is no obvious difference whether those additional array are used or not. (at least in my testing)
2. Your patch is in this case 30% faster, but mostly because there are much less vertices in the result that need to get calculated.

I understand that the solution on the right seems to be better. But you are using an unconventional method to get an order-dependent result.
Unnecessarily complicating the code to make the "connected" method behave quite differently from "full".
Merging chain of vertices that overlap in a single point was by design.
If this behavior has to change, it has to affect both methods (full and connected).
And it has to be done preferably in a separate patch.

Ok but then I still need to make that patch, because I need that to get rid of solidifys merge.

I want to give an overview over the current implementation here.

Connected Mode uses edge connections to merge vertices.
This can be done in three basic ways.

1. Tag too short edges and then collapse all of them.
   • Order independent
   • Even very big usual meshes can collapse to a single vert if the individual edges are too short (heavy infinite chain merging)
   • result looks much like the BVH Tree solution and is similar in implementation
   • probably the fastest of all (not by much though)
2. Merge short edges one by one in edge order.
   • edge order dependent as a merged edge will always change the length of adjacent edges of at least one of the merged verts.
   • result looks like the current KD Tree solution and is somewhat similar in implementation.
   • There are multiple ways to merge the too short edges with different results.
     1. Always merge to vertex with lowest index (simplest/fastest implementation) -> heavy infinite chain merging for text objects and curves.
     2. Always merge to the mean of the resulting cluster (current) -> only infinite chain merging for a crafted leaning tower of lire (very very rare and not severe)
     3. Always merge to the mean of the resulting cluster and enlarge the radius of the cluster to contain all merged verts, only merge when the resulting radius is less than the merge threshold -> no infinite chain merging possible (tested)
     4. Always merge to the first merged vertex in the clusters (on first merge, merge to the vert with lower index, new single verts will be merged to that one as well, when two clusters merge, merge to the first created cluster) -> infinite chain merging for edges with less than half the merge length for some edge orders, not for usual text/curves. (theory at this point, will maybe test and add a paste)
   • Loose edges and stray (non-manifold) triangles appear on very high merge thresholds even when starting from smooth manifold surfaces. This happens because sometimes the edge order collapses a loop before ever encountering the inner verts. If the collapsed loop has a far distance to the inside verts, they will stay behind. This happens with all the strategies A-D. Additional filtering would be required to remove these artifacts (I could add a TODO in the code).
3. Do Incremental Decimation like in http://graphics.stanford.edu/courses/cs468-10-fall/LectureSlides/08_Simplification.pdf
   • like the Decimate Modifier in Collapse Mode but with merge distance instead of a percentage. Would be simpler to do it there I guess.
   • quite heavy, requires sorting of the edges and sorted manipulation (needs fitting data structure)
   • will automatically keep topological shape

2.B. is the currently implemented solution.

Thanks for the info,
But I still feel that this code can be simplified.
I do not see the need to make a solution that seeks order independence and in which the center of each cluster has to be computed in advance.
Kdtree does not do this, so this new solution just needs to be differentiated by performance.

But I tried a different and simplified solution and did not get a satisfactory result.

So there must be a lot more involved.

Can you show the results of profiling, for us to see how much advantage this patch brings?

I tried your patch. It's as you said not satisfactory, but I did the profiling nevertheless.
Turns out your patch runs on average roughly (surprise) half as fast as the current solution of this patch.
(obviously that only applies for my test object and not for any object, see below)
The reason for that is, that the geometry created by your merge algorithm is more (and more complicated?),
so more time is spent in the second stage of the weld modifier.

This goes to show, that as long as the algorithm is in linear execution time and cares for quality, performance will not be the issue.

I didn't find the code of the KD Tree yet, because there was some trickery in the files which made it hard to find.
Nevertheless I think the KD Tree does not need the average positions to avoid chain merging, because it is evaluated
over all vertices. Therefore it can disperse the vertices into clusters of bounded size. When only working with edges
it is necessary to keep track of the cluster size in some other way. Especially because edges may also merge whole clusters.

I also want to add a screenshot of the loose edges and stray triangles that I was talking about.
This screenshot shows the current patch. It is also the object on which I tested the performance difference.

I also gained more confidence in the current patch while writing the summary. I think it should be fine (the best solution)
and these artifacts can be fixed later if needed as they will not be a problem in most common cases AFAICT.

I think we can accept these loose edges for now.
But I still don't see the need for these struct WeldVertexCluster *vert_clusters.
I made a comparison without it and the result didn't seem to be that different.

I don't see much of the benefit of calculating the center of the clusters, the result is not perfect in both cases.

diff --git a/source/blender/modifiers/intern/MOD_weld.c b/source/blender/modifiers/intern/MOD_weld.c
index 7e4897dd3bc..7372f440514 100644
--- a/source/blender/modifiers/intern/MOD_weld.c
+++ b/source/blender/modifiers/intern/MOD_weld.c
@@ -1567,11 +1567,6 @@ static bool bvhtree_weld_overlap_cb(void *userdata, int index_a, int index_b, in
 }
 #endif
 
-struct WeldVertexCluster {
-  float co[3];
-  uint merged_verts;
-};
-
 static Mesh *weldModifier_doWeld(WeldModifierData *wmd, const ModifierEvalContext *ctx, Mesh *mesh)
 {
   Mesh *result = mesh;
@@ -1717,13 +1712,7 @@ static Mesh *weldModifier_doWeld(WeldModifierData *wmd, const ModifierEvalContex
     totvert = mesh->totvert;
     totedge = mesh->totedge;
 
-    struct WeldVertexCluster *vert_clusters = MEM_calloc_arrayN(
-        totvert, sizeof(*vert_clusters), __func__);
-    struct WeldVertexCluster *vc = &vert_clusters[0];
-    for (uint i = 0; i < totvert; i++, vc++) {
-      copy_v3_v3(vc->co, mvert[i].co);
-    }
-    float merge_dist_sq = square_f(wmd->merge_dist);
+    float merge_dist = wmd->merge_dist;
 
     range_vn_u(vert_dest_map, totvert, 0);
 
@@ -1748,24 +1737,13 @@ static Mesh *weldModifier_doWeld(WeldModifierData *wmd, const ModifierEvalContex
       if (v1 > v2) {
         SWAP(uint, v1, v2);
       }
-      struct WeldVertexCluster *v1_cluster = &vert_clusters[v1];
-      struct WeldVertexCluster *v2_cluster = &vert_clusters[v2];
 
-      sub_v3_v3v3(edgedir, v2_cluster->co, v1_cluster->co);
-      const float dist_sq = len_squared_v3(edgedir);
-      if (dist_sq <= merge_dist_sq) {
-        float influence = (v2_cluster->merged_verts + 1) /
-                          (float)(v1_cluster->merged_verts + v2_cluster->merged_verts + 2);
-        madd_v3_v3fl(v1_cluster->co, edgedir, influence);
-
-        v1_cluster->merged_verts += v2_cluster->merged_verts + 1;
+      if (compare_v3v3(mvert[v1].co, mvert[v2].co, merge_dist)) {
         vert_dest_map[v2] = v1;
         vert_kill_len++;
       }
     }
 
-    MEM_freeN(vert_clusters);
-
     for (uint i = 0; i < totvert; i++) {
       if (i == vert_dest_map[i]) {
         vert_dest_map[i] = OUT_OF_CONTEXT;

Here is a comparison for with and without using mean position (with your paste). You can see minor differences in the mesh in the lower part of the video (less streched triangles on the left), but for text objects the difference is really clear.
The reason text objects show this effect of chain merging entire regions when the edges are short, is the element order. It is completely sorted.

This Testfile contains the usual cases where some algorithms break down. I didn't do the leaning tower of lire example, because it is a lot of work to craft it with the right element order.

In fact with text objects the result is better.
The code in general is fine in my opinion.