BMesh Intersect: use flags to keep track of verts

For simple cases bitmasks were OK, but didnt work for vert/edge, vert/edge tests.

Tag verts instead, makes logic easier to follow and gives minor speedup.

2 files changed, 83 insertions, 87 deletions

diff --git a/source/blender/bmesh/intern/bmesh_private.h b/source/blender/bmesh/intern/bmesh_private.h
index 9b3a147301d..d8d297c9298 100644
--- a/source/blender/bmesh/intern/bmesh_private.h
+++ b/source/blender/bmesh/intern/bmesh_private.h
@@ -67,12 +67,13 @@ enum {
 	_FLAG_MV       = (1 << 1),  /* make face, vertex */
 	_FLAG_OVERLAP  = (1 << 2),  /* general overlap flag  */
 	_FLAG_WALK     = (1 << 3),  /* general walk flag (keep clean) */
+	_FLAG_WALK_ALT = (1 << 4),  /* same as _FLAG_WALK, for when a second tag is needed */
 
 	_FLAG_ELEM_CHECK = (1 << 7),  /* reserved for bmesh_elem_check */
 };
 
 #define BM_ELEM_API_FLAG_ENABLE(element, f)  { ((element)->head.api_flag |=  (f)); } (void)0
-#define BM_ELEM_API_FLAG_DISABLE(element, f) { ((element)->head.api_flag &= ~(f)); } (void)0
+#define BM_ELEM_API_FLAG_DISABLE(element, f) { ((element)->head.api_flag &= (unsigned char)~(f)); } (void)0
 #define BM_ELEM_API_FLAG_TEST(element, f)      ((element)->head.api_flag &   (f))
 #define BM_ELEM_API_FLAG_CLEAR(element)      { ((element)->head.api_flag = 0); } (void)0
 
diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c
index bd6a68faabb..58234ddf3bd 100644
--- a/source/blender/bmesh/tools/bmesh_intersect.c
+++ b/source/blender/bmesh/tools/bmesh_intersect.c
@@ -53,6 +53,8 @@
 #include "BLI_buffer.h"
 
 #include "bmesh.h"
+#include "intern/bmesh_private.h"
+
 #include "bmesh_intersect.h"  /* own include */
 
 #include "tools/bmesh_edgesplit.h"
@@ -87,18 +89,6 @@
 
 // #define USE_DUMP
 
-/* use only for small arrays */
-BLI_INLINE bool array_contains_pointer(const void **arr, unsigned int arr_len, const void *item)
-{
-	BLI_assert(arr_len < 3);
-	for (unsigned int i = 0; i < arr_len; i++) {
-		if (arr[i] == item) {
-			return true;
-		}
-	}
-	return false;
-}
-
 static void tri_v3_scale(
         float v1[3], float v2[3], float v3[3],
         const float t)
@@ -547,9 +537,6 @@ static void bm_isect_tri_tri(
 	const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)};
 	float f_a_nor[3];
 	float f_b_nor[3];
-	/* track vertices which have been added to 'iv_ls_a' & 'iv_ls_b' */
-	int a_mask = 0;
-	int b_mask = 0;
 	unsigned int i;
 
 
@@ -569,24 +556,22 @@ static void bm_isect_tri_tri(
 	STACK_INIT(iv_ls_a, ARRAY_SIZE(iv_ls_a));
 	STACK_INIT(iv_ls_b, ARRAY_SIZE(iv_ls_b));
 
-	/* don't test, but we must be sure not to add doubles (assert instead). */
-#ifndef NDEBUG
-#  define STACK_PUSH_NOTEST(arr, ele) \
-	{ \
-		BLI_assert(BLI_array_findindex(arr, STACK_SIZE(arr), &(ele)) == -1); \
-		STACK_PUSH(arr, ele); \
+#define VERT_VISIT_A _FLAG_WALK
+#define VERT_VISIT_B _FLAG_WALK_ALT
+
+#define STACK_PUSH_TEST_A(ele) \
+	if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_A) == 0) { \
+		BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_A); \
+		STACK_PUSH(iv_ls_a, ele); \
 	} ((void)0)
-#else
-#  define STACK_PUSH_NOTEST STACK_PUSH
-#endif
 
-	/* warning, this seems like it might be inefficent,
-	 * however there will be <3 items in this case. */
-#  define STACK_PUSH_TEST(arr, ele, arr_offset) \
-	if (!array_contains_pointer((const void **)(&(arr)[arr_offset]), STACK_SIZE(arr) - (arr_offset), (void *)ele)) { \
-		STACK_PUSH(arr, ele); \
+#define STACK_PUSH_TEST_B(ele) \
+	if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_B) == 0) { \
+		BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_B); \
+		STACK_PUSH(iv_ls_b, ele); \
 	} ((void)0)
 
+
 	/* vert-vert
 	 * --------- */
 	{
@@ -598,22 +583,18 @@ static void bm_isect_tri_tri(
 			unsigned int i_b;
 			for (i_b = 0; i_b < 3; i_b++) {
 				if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
-					if (!((1 << i_a) & a_mask)) {
-						STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
-						a_mask |= (1 << i_a);
 #ifdef USE_DUMP
+					if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT) == 0) {
 						printf("  ('VERT-VERT-A') %d, %d),\n",
 						       i_a, BM_elem_index_get(fv_a[i_a]));
-#endif
 					}
-					if (!((1 << i_b) & b_mask)) {
-						STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
-						b_mask |= (1 << i_b);
-#ifdef USE_DUMP
+					if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT) == 0) {
 						printf("  ('VERT-VERT-B') %d, %d),\n",
 						       i_b, BM_elem_index_get(fv_b[i_b]));
-#endif
 					}
+#endif
+					STACK_PUSH_TEST_A(fv_a[i_a]);
+					STACK_PUSH_TEST_B(fv_b[i_b]);
 				}
 			}
 		}
@@ -624,22 +605,25 @@ static void bm_isect_tri_tri(
 	{
 		unsigned int i_a;
 		for (i_a = 0; i_a < 3; i_a++) {
-			if (!((1 << i_a) & a_mask)) {
+			if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) {
 				unsigned int i_b_e0;
 				for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
 					unsigned int i_b_e1 = (i_b_e0 + 1) % 3;
-					float fac;
-					if (((1 << i_b_e0) | (1 << i_b_e1)) & b_mask)
+
+					if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) ||
+					    BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B))
+					{
 						continue;
-					fac = line_point_factor_v3(fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co);
+					}
+
+					const float fac = line_point_factor_v3(fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co);
 					if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
 						float ix[3];
 						interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac);
 						if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
 							BMEdge *e;
-							STACK_PUSH_NOTEST(iv_ls_b, fv_a[i_a]);
-							// STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
-							a_mask |= (1 << i_a);
+							STACK_PUSH_TEST_B(fv_a[i_a]);
+							// STACK_PUSH_TEST_A(fv_a[i_a]);
 							e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]);
 #ifdef USE_DUMP
 							printf("  ('VERT-EDGE-A', %d, %d),\n",
@@ -662,22 +646,25 @@ static void bm_isect_tri_tri(
 	{
 		unsigned int i_b;
 		for (i_b = 0; i_b < 3; i_b++) {
-			if (!((1 << i_b) & b_mask)) {
+			if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) {
 				unsigned int i_a_e0;
 				for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
 					unsigned int i_a_e1 = (i_a_e0 + 1) % 3;
-					float fac;
-					if (((1 << i_a_e0) | (1 << i_a_e1)) & a_mask)
+
+					if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) ||
+					    BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A))
+					{
 						continue;
-					fac = line_point_factor_v3(fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co);
+					}
+
+					const float fac = line_point_factor_v3(fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co);
 					if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
 						float ix[3];
 						interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac);
 						if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
 							BMEdge *e;
-							STACK_PUSH_NOTEST(iv_ls_a, fv_b[i_b]);
+							STACK_PUSH_TEST_A(fv_b[i_b]);
 							// STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
-							b_mask |= (1 << i_b);
 							e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]);
 #ifdef USE_DUMP
 							printf("  ('VERT-EDGE-B', %d, %d),\n",
@@ -711,14 +698,15 @@ static void bm_isect_tri_tri(
 
 		// second check for verts intersecting the triangle
 		for (i_a = 0; i_a < 3; i_a++) {
-			float ix[3];
-			if ((1 << i_a) & a_mask)
+			if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A)) {
 				continue;
+			}
+
+			float ix[3];
 			if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) {
 				if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
-					STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
-					STACK_PUSH_NOTEST(iv_ls_b, fv_a[i_a]);
-					a_mask |= (1 << i_a);
+					STACK_PUSH_TEST_A(fv_a[i_a]);
+					STACK_PUSH_TEST_B(fv_a[i_a]);
 #ifdef USE_DUMP
 					printf("  'VERT TRI-A',\n");
 #endif
@@ -737,15 +725,15 @@ static void bm_isect_tri_tri(
 		tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);
 
 		for (i_b = 0; i_b < 3; i_b++) {
-			float ix[3];
-			if ((1 << i_b) & b_mask)
+			if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B)) {
 				continue;
+			}
 
+			float ix[3];
 			if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) {
 				if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
-					STACK_PUSH_NOTEST(iv_ls_a, fv_b[i_b]);
-					STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
-					b_mask |= (1 << i_b);
+					STACK_PUSH_TEST_A(fv_b[i_b]);
+					STACK_PUSH_TEST_B(fv_b[i_b]);
 #ifdef USE_DUMP
 					printf("  'VERT TRI-B',\n");
 #endif
@@ -760,7 +748,7 @@ static void bm_isect_tri_tri(
 #ifdef USE_DUMP
 		printf("# OVERLAP\n");
 #endif
-		return;
+		goto finally;
 	}
 
 	normal_tri_v3(f_a_nor, UNPACK3(f_a_cos));
@@ -769,44 +757,42 @@ static void bm_isect_tri_tri(
 	/* edge-tri & edge-edge
 	 * -------------------- */
 	{
-		/**
-		 * Note that its possible to add the same vertex multiple times
-		 * with near degenerate faces (or a large epsilon).
-		 *
-		 * For this reason we have #STACK_PUSH_TEST macro which only adds vertices that aren't already added.
-		 * Since we know none of the vertices from #bm_isect_edge_tri, the check can be offset.
-		 */
-
-		const unsigned int iv_ls_a_offset = STACK_SIZE(iv_ls_a);
-		const unsigned int iv_ls_b_offset = STACK_SIZE(iv_ls_b);
-
-		unsigned int i_e0;
-		for (i_e0 = 0; i_e0 < 3; i_e0++) {
-			unsigned int i_e1 = (i_e0 + 1) % 3;
+		for (unsigned int i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
+			unsigned int i_a_e1 = (i_a_e0 + 1) % 3;
 			enum ISectType side;
 			BMVert *iv;
-			if (((1 << i_e0) | (1 << i_e1)) & a_mask)
+
+			if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) ||
+			    BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A))
+			{
 				continue;
-			iv = bm_isect_edge_tri(s, fv_a[i_e0], fv_a[i_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
+			}
+
+			iv = bm_isect_edge_tri(s, fv_a[i_a_e0], fv_a[i_a_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
 			if (iv) {
-				STACK_PUSH_TEST(iv_ls_a, iv, iv_ls_a_offset);
-				STACK_PUSH_TEST(iv_ls_b, iv, iv_ls_b_offset);
+				STACK_PUSH_TEST_A(iv);
+				STACK_PUSH_TEST_B(iv);
 #ifdef USE_DUMP
 				printf("  ('EDGE-TRI-A', %d),\n", side);
 #endif
 			}
 		}
 
-		for (i_e0 = 0; i_e0 < 3; i_e0++) {
-			unsigned int i_e1 = (i_e0 + 1) % 3;
+		for (unsigned int i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
+			unsigned int i_b_e1 = (i_b_e0 + 1) % 3;
 			enum ISectType side;
 			BMVert *iv;
-			if (((1 << i_e0) | (1 << i_e1)) & b_mask)
+
+			if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) ||
+			    BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B))
+			{
 				continue;
-			iv = bm_isect_edge_tri(s, fv_b[i_e0], fv_b[i_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);
+			}
+
+			iv = bm_isect_edge_tri(s, fv_b[i_b_e0], fv_b[i_b_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);
 			if (iv) {
-				STACK_PUSH_TEST(iv_ls_a, iv, iv_ls_a_offset);
-				STACK_PUSH_TEST(iv_ls_b, iv, iv_ls_b_offset);
+				STACK_PUSH_TEST_A(iv);
+				STACK_PUSH_TEST_B(iv);
 #ifdef USE_DUMP
 				printf("  ('EDGE-TRI-B', %d),\n", side);
 #endif
@@ -859,6 +845,15 @@ static void bm_isect_tri_tri(
 			// BLI_assert(len(ie_vs) <= 2)
 		}
 	}
+
+finally:
+	for (i = 0; i < STACK_SIZE(iv_ls_a); i++) {
+		BM_ELEM_API_FLAG_DISABLE(iv_ls_a[i], VERT_VISIT_A); \
+	}
+	for (i = 0; i < STACK_SIZE(iv_ls_b); i++) {
+		BM_ELEM_API_FLAG_DISABLE(iv_ls_b[i], VERT_VISIT_B); \
+	}
+
 }
 
 #ifdef USE_BVH