[Bf-blender-cvs] [bee0c75] bmesh-boolean-experiment: temporarily convert the geometry to 2d coords

Campbell Barton noreply at git.blender.org
Wed Dec 9 07:06:21 CET 2015


Commit: bee0c750c76009ca7e63fefd93af03564f6aa370
Author: Campbell Barton
Date:   Wed Dec 9 16:57:28 2015 +1100
Branches: bmesh-boolean-experiment
https://developer.blender.org/rBbee0c750c76009ca7e63fefd93af03564f6aa370

temporarily convert the geometry to 2d coords

I wanted to avoid this, but its becoming too impractical to perform 2d calculations on 3d geometry.

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

M	source/blender/bmesh/intern/bmesh_polygon_edgenet.c

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

diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
index 787a8a4..c78971f 100644
--- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
+++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
@@ -595,6 +595,9 @@ bool BM_face_split_edgenet(
  *
  * \{ */
 
+/* can be X or Y */
+#define SORT_AXIS 0
+
 /* Represents isolated edge-links,
  * each island owns contiguous slices of a vert & edge array. */
 struct GeomIsland {
@@ -614,13 +617,12 @@ struct GeomIsland {
 	} vert_span;
 };
 
-static int group_min_cmp_fn(const void *p1, const void *p2, void *user_data)
+static int group_min_cmp_fn(const void *p1, const void *p2)
 {
-	struct { unsigned int axis; } *data = user_data;
 	const struct GeomIsland *g1 = *(struct GeomIsland **)p1;
 	const struct GeomIsland *g2 = *(struct GeomIsland **)p2;
-	const float f1 = g1->vert_span.min->co[data->axis];
-	const float f2 = g2->vert_span.min->co[data->axis];
+	const float f1 = g1->vert_span.min->co[SORT_AXIS];
+	const float f2 = g2->vert_span.min->co[SORT_AXIS];
 
 	if (f1 < f2) return -1;
 	if (f1 > f2) return  1;
@@ -630,10 +632,9 @@ static int group_min_cmp_fn(const void *p1, const void *p2, void *user_data)
 struct GeomIsland_KDTreeTest {
 	unsigned int vert_range[2];
 	BMVert **vert_arr;
-	unsigned int axis;
 
 	/* for each search */
-	float axis_value;
+	float value;
 };
 
 static int kdtree_find_exclude_range_prev_cb(void *user_data, int index, const float co[3], float dist_sq)
@@ -642,7 +643,7 @@ static int kdtree_find_exclude_range_prev_cb(void *user_data, int index, const f
 	struct GeomIsland_KDTreeTest *group_test = user_data;
 	return ((index < (int)group_test->vert_range[0] || index >= (int)group_test->vert_range[1]) &&
 	        /* allow equality to support degenerate cases (when they're equal) */
-	        (group_test->vert_arr[index]->co[group_test->axis] <= group_test->axis_value));
+	        (group_test->vert_arr[index]->co[SORT_AXIS] <= group_test->value));
 }
 
 static int kdtree_find_exclude_range_next_cb(void *user_data, int index, const float co[3], float dist_sq)
@@ -651,7 +652,7 @@ static int kdtree_find_exclude_range_next_cb(void *user_data, int index, const f
 	struct GeomIsland_KDTreeTest *group_test = user_data;
 	return ((index < (int)group_test->vert_range[0] || index >= (int)group_test->vert_range[1]) &&
 	        /* allow equality to support degenerate cases (when they're equal) */
-	        (group_test->vert_arr[index]->co[group_test->axis] >= group_test->axis_value));
+	        (group_test->vert_arr[index]->co[SORT_AXIS] >= group_test->value));
 }
 
 /**
@@ -773,7 +774,6 @@ bool BM_face_split_edgenet_connect_islands(
 #define VERT_IN_KDTREE BM_ELEM_INTERNAL_TAG
 
 	struct GeomIsland **group_arr = BLI_array_alloca(group_arr, group_arr_len);
-	const unsigned int axis = (unsigned int)axis_dominant_v3_ortho_single(f->no);
 	unsigned int vert_arr_len = 0;
 	/* sort groups by lowest value vertex */
 	{
@@ -794,12 +794,12 @@ bool BM_face_split_edgenet_connect_islands(
 				for (int j = 0; j < 2; j++) {
 					BMVert *v_iter = (&e->v1)[j];
 					BLI_assert(v_iter->head.htype == BM_VERT);
-					const float axis_value = v_iter->co[axis];
+					const float axis_value = v_iter->co[SORT_AXIS];
 
-					if (axis_value < g->vert_span.min->co[axis]) {
+					if (axis_value < g->vert_span.min->co[SORT_AXIS]) {
 						g->vert_span.min = v_iter;
 					}
-					if (axis_value > g->vert_span.max->co[axis]) {
+					if (axis_value > g->vert_span.max->co[SORT_AXIS]) {
 						g->vert_span.max = v_iter;
 					}
 				}
@@ -813,19 +813,23 @@ bool BM_face_split_edgenet_connect_islands(
 		}
 	}
 
-	{
-		struct { unsigned int axis; } data = {axis};
-		BLI_qsort_r(group_arr, group_arr_len, sizeof(*group_arr), group_min_cmp_fn, &data);
-	}
+	qsort(group_arr, group_arr_len, sizeof(*group_arr), group_min_cmp_fn);
 
 	/* we don't know how many unique verts there are connecting the edges, so over-alloc */
 	BMVert **vert_arr = BLI_array_alloca(vert_arr, vert_arr_len);
 	/* map vertex -> group index */
 	unsigned int *verts_group_table = BLI_array_alloca(verts_group_table, vert_arr_len);
 
+	float (*vert_coords_backup)[3] = BLI_array_alloca(vert_coords_backup, vert_arr_len);
+
 	KDTree *tree = BLI_kdtree_new(vert_arr_len);
 
 	{
+		float axis_mat[3][3];
+		axis_dominant_v3_to_m3(axis_mat, f->no);
+		/* relative location, for higher precision calculations */
+		const float f_co_ref[3] = {UNPACK3(BM_FACE_FIRST_LOOP(f)->v->co)};
+
 		int v_index = 0;  /* global vert index */
 		for (unsigned int g_index = 0; g_index < group_arr_len; g_index++) {
 			/* fill the kdtree */
@@ -836,6 +840,21 @@ bool BM_face_split_edgenet_connect_islands(
 					BMVert *v_iter = (&e->v1)[j];
 					if (!BM_elem_flag_test(v_iter, VERT_IN_KDTREE)) {
 						BM_elem_flag_enable(v_iter, VERT_IN_KDTREE);
+
+						/* not nice, but alternatives arent much better :S */
+						{
+							copy_v3_v3(vert_coords_backup[v_index], v_iter->co);
+
+							/* for higher precision */
+							sub_v3_v3(v_iter->co, f_co_ref);
+
+							float co_2d[2];
+							mul_v2_m3v3(co_2d, axis_mat, v_iter->co);
+							v_iter->co[0] = co_2d[0];
+							v_iter->co[1] = co_2d[1];
+							v_iter->co[2] = 0.0f;
+						}
+
 						BLI_kdtree_insert(tree, v_index, v_iter->co);
 						vert_arr[v_index] = v_iter;
 						verts_group_table[v_index] = g_index;
@@ -864,7 +883,6 @@ bool BM_face_split_edgenet_connect_islands(
 		group_test.vert_range[0] = 0;
 		group_test.vert_range[1] = group_arr[0]->vert_len;
 		group_test.vert_arr = vert_arr;
-		group_test.axis = axis;
 
 		for (unsigned int g_index = 1; g_index < group_arr_len; g_index++) {
 			struct GeomIsland *g = group_arr[g_index];
@@ -876,7 +894,7 @@ bool BM_face_split_edgenet_connect_islands(
 			if (g->has_prev_edge == false) {
 				BMVert *v_start = g->vert_span.min;
 
-				group_test.axis_value = v_start->co[axis];
+				group_test.value = v_start->co[SORT_AXIS];
 				const int index_other = BLI_kdtree_find_nearest_cb(
 				        tree, v_start->co,
 				        kdtree_find_exclude_range_prev_cb, &group_test,
@@ -894,7 +912,7 @@ bool BM_face_split_edgenet_connect_islands(
 			{
 				BMVert *v_start = g->vert_span.max;
 
-				group_test.axis_value = v_start->co[axis];
+				group_test.value = v_start->co[SORT_AXIS];
 				const int index_other = BLI_kdtree_find_nearest_cb(
 				        tree, v_start->co,
 				        kdtree_find_exclude_range_next_cb, &group_test,
@@ -923,6 +941,10 @@ bool BM_face_split_edgenet_connect_islands(
 	*r_edge_net_new_len = edge_net_new_len;
 	ok = true;
 
+	for (unsigned int i = 0; i < vert_arr_len; i++) {
+		copy_v3_v3(vert_arr[i]->co, vert_coords_backup[i]);
+	}
+
 finally:
 	for (unsigned int i = 0; i < edge_arr_len; i++) {
 		BM_elem_flag_disable(edge_arr[i], EDGE_NOT_IN_STACK);
@@ -937,4 +959,6 @@ finally:
 	return ok;
 }
 
+#undef SORT_AXIS
+
 /** \} */




More information about the Bf-blender-cvs mailing list