diff options
author | Campbell Barton <ideasman42@gmail.com> | 2016-06-23 14:44:22 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2016-06-23 15:20:40 +0300 |
commit | d9a01a1d04f87e46fadbee268cdea2dbf14993fc (patch) | |
tree | 235205710e2a1c10c444e2b58423c6a2a061ff96 /source/blender/bmesh | |
parent | 57744df38fef172edf7781f1e1bb48319f5ef066 (diff) |
Fix T48707: Edit-mesh intersect crash
In rare cases intersect would attempt to add edges with the same vertex twice
from edge-vert / edge-edge intersections.
Solve by checking for duplicates when creating vertex-array for these types of intersections
(always under 3x comparisons, so not much overhead).
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/tools/bmesh_intersect.c | 80 |
1 files changed, 56 insertions, 24 deletions
diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c index 7496af1d64c..bd6a68faabb 100644 --- a/source/blender/bmesh/tools/bmesh_intersect.c +++ b/source/blender/bmesh/tools/bmesh_intersect.c @@ -87,6 +87,18 @@ // #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) @@ -535,6 +547,7 @@ 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; @@ -556,6 +569,24 @@ 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); \ + } ((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); \ + } ((void)0) + /* vert-vert * --------- */ { @@ -568,7 +599,7 @@ static void bm_isect_tri_tri( 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(iv_ls_a, fv_a[i_a]); + STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]); a_mask |= (1 << i_a); #ifdef USE_DUMP printf(" ('VERT-VERT-A') %d, %d),\n", @@ -576,7 +607,7 @@ static void bm_isect_tri_tri( #endif } if (!((1 << i_b) & b_mask)) { - STACK_PUSH(iv_ls_b, fv_b[i_b]); + STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]); b_mask |= (1 << i_b); #ifdef USE_DUMP printf(" ('VERT-VERT-B') %d, %d),\n", @@ -606,8 +637,8 @@ static void bm_isect_tri_tri( 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(iv_ls_b, fv_a[i_a]); - // STACK_PUSH(iv_ls_a, fv_a[i_a]); + 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); e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]); #ifdef USE_DUMP @@ -644,8 +675,8 @@ static void bm_isect_tri_tri( 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(iv_ls_a, fv_b[i_b]); - // STACK_PUSH(iv_ls_b, fv_b[i_b]); + 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); e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]); #ifdef USE_DUMP @@ -685,11 +716,8 @@ static void bm_isect_tri_tri( continue; 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) { - BLI_assert(BLI_array_findindex(iv_ls_a, STACK_SIZE(iv_ls_a), &fv_a[i_a]) == -1); - BLI_assert(BLI_array_findindex(iv_ls_b, STACK_SIZE(iv_ls_b), &fv_a[i_a]) == -1); - - STACK_PUSH(iv_ls_a, fv_a[i_a]); - STACK_PUSH(iv_ls_b, fv_a[i_a]); + 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); #ifdef USE_DUMP printf(" 'VERT TRI-A',\n"); @@ -715,11 +743,8 @@ static void bm_isect_tri_tri( 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) { - BLI_assert(BLI_array_findindex(iv_ls_a, STACK_SIZE(iv_ls_a), &fv_b[i_b]) == -1); - BLI_assert(BLI_array_findindex(iv_ls_b, STACK_SIZE(iv_ls_b), &fv_b[i_b]) == -1); - - STACK_PUSH(iv_ls_a, fv_b[i_b]); - STACK_PUSH(iv_ls_b, fv_b[i_b]); + 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); #ifdef USE_DUMP printf(" 'VERT TRI-B',\n"); @@ -744,6 +769,17 @@ 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; @@ -753,10 +789,8 @@ static void bm_isect_tri_tri( 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); if (iv) { - BLI_assert(BLI_array_findindex(iv_ls_a, STACK_SIZE(iv_ls_a), &iv) == -1); - BLI_assert(BLI_array_findindex(iv_ls_b, STACK_SIZE(iv_ls_b), &iv) == -1); - STACK_PUSH(iv_ls_a, iv); - STACK_PUSH(iv_ls_b, iv); + STACK_PUSH_TEST(iv_ls_a, iv, iv_ls_a_offset); + STACK_PUSH_TEST(iv_ls_b, iv, iv_ls_b_offset); #ifdef USE_DUMP printf(" ('EDGE-TRI-A', %d),\n", side); #endif @@ -771,10 +805,8 @@ static void bm_isect_tri_tri( 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); if (iv) { - BLI_assert(BLI_array_findindex(iv_ls_a, STACK_SIZE(iv_ls_a), &iv) == -1); - BLI_assert(BLI_array_findindex(iv_ls_b, STACK_SIZE(iv_ls_b), &iv) == -1); - STACK_PUSH(iv_ls_a, iv); - STACK_PUSH(iv_ls_b, iv); + STACK_PUSH_TEST(iv_ls_a, iv, iv_ls_a_offset); + STACK_PUSH_TEST(iv_ls_b, iv, iv_ls_b_offset); #ifdef USE_DUMP printf(" ('EDGE-TRI-B', %d),\n", side); #endif |