From e6d947f037d341fc1f84fb422b2cada8bd6f5d0a Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Wed, 29 Jun 2016 16:09:58 +1000 Subject: 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. --- source/blender/bmesh/intern/bmesh_private.h | 3 +- source/blender/bmesh/tools/bmesh_intersect.c | 167 +++++++++++++-------------- 2 files changed, 83 insertions(+), 87 deletions(-) (limited to 'source/blender/bmesh') 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 -- cgit v1.2.3