[Bf-blender-cvs] [227a40e] bmesh-boolean-experiment: Improved starting point when calculating island joining paths

[Campbell Barton]

Commit: 227a40ebaec553fe3f24d7166708a309f7a04888
Author: Campbell Barton
Date:   Mon Dec 7 22:54:09 2015 +1100
Branches: bmesh-boolean-experiment
https://developer.blender.org/rB227a40ebaec553fe3f24d7166708a309f7a04888

Improved starting point when calculating island joining paths

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

M	source/blender/bmesh/tools/bmesh_intersect.c

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

diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c
index 11e84a3..3ac6d6b 100644
--- a/source/blender/bmesh/tools/bmesh_intersect.c
+++ b/source/blender/bmesh/tools/bmesh_intersect.c
@@ -240,16 +240,21 @@ static bool  bm_face_split_edgenet_prepare_holes(
 		LinkNode node;
 		unsigned int edge_len, vert_len;
 	} *group_base, **groups_arr = BLI_array_alloca(groups_arr, groups_len);
-	KDTree *tree = BLI_kdtree_new(edge_arr_len * 2);
+	/* we don't know how many unique verts there are connecting the edges, so over-alloc */
 	BMVert **verts_arr = BLI_array_alloca(verts_arr, edge_arr_len * 2);
+	float (*verts_center)[3] = BLI_array_alloca(verts_center, edge_arr_len * 2);
 	unsigned int verts_len = 0;
 
+	KDTree *tree = BLI_kdtree_new(edge_arr_len * 2);
+
 	{
 		group_base = (void *)groups;
 		for (unsigned int i = 0; i < groups_len; i++, group_base = (void *)group_base->node.next) {
-			/* fill the kdtree */
 
+			/* unrelated to the kdtree, but find the center at the same time */
+			zero_v3(verts_center[i]);
 
+			/* fill the kdtree */
 			LinkNode *g = group_base->node.link;
 			do {
 				BMEdge *e = g->link;
@@ -263,12 +268,16 @@ static bool  bm_face_split_edgenet_prepare_holes(
 						BLI_kdtree_insert(tree, (int)verts_len, v_iter->co);
 						verts_arr[verts_len] = v_iter;
 
+						add_v3_v3(verts_center[i], v_iter->co);
+
 						verts_len++;
 						group_base->vert_len++;
 					}
 				}
 			} while ((g = g->next));
 
+			mul_v3_fl(verts_center[i], 1.0f / (float)group_base->vert_len);
+
 			groups_arr[i] = group_base;
 		}
 	}
@@ -287,18 +296,23 @@ static bool  bm_face_split_edgenet_prepare_holes(
 		/* start-end of the verts in the current group */
 		unsigned int group_vert_range[2] = {0, groups_arr[0]->vert_len};
 		for (unsigned int group_index = 1; group_index < groups_len; group_index++) {
-			BMVert *v_start;
-			/* left most vert of left most edge */
-			{
-				BMEdge *e = groups_arr[group_index]->node.link;
-				v_start = (dot_v3v3(f_ortho_dir, e->v1->co) <
-				           dot_v3v3(f_ortho_dir, e->v2->co)) ? e->v1 : e->v2;
-			}
 
 			/* the range of verts this group uses in 'verts_arr' (not uncluding the last index) */
 			group_vert_range[0]  = group_vert_range[1];
 			group_vert_range[1] += groups_arr[group_index]->vert_len;
 
+			/* find the closest point all all previous to this edge-groups center,
+			 * gives a 'reasonably' good starting point from which to refine a close pair */
+			BMVert *v_start;
+			{
+				const int index = BLI_kdtree_find_nearest_cb(
+				        tree, verts_center[group_index],
+				        kdtree_find_v_prev_range_cb, group_vert_range,
+				        NULL);
+				BLI_assert(index >= 0 && index < (int)verts_len);
+				v_start = verts_arr[index];
+			}
+
 			BMVert *vpair_best[2] = {v_start, NULL};
 			for (unsigned int i = 0; i < refine; i++) {
 				unsigned int src_side, dst_side;
@@ -317,8 +331,7 @@ static bool  bm_face_split_edgenet_prepare_holes(
 				        src_side ? kdtree_find_v_prev_range_cb : kdtree_find_v_in_range_cb, group_vert_range,
 				        NULL);
 
-				BLI_assert(index >= 0);
-				BLI_assert(index < (int)verts_len);
+				BLI_assert(index >= 0 && index < (int)verts_len);
 				vpair_best[dst_side] = verts_arr[index];
 			}