diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-09-14 09:00:27 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2018-01-03 14:49:48 +0300 |
commit | 78cc3c828f79bc561aa5bc87de5ceda7d07184e1 (patch) | |
tree | 11ab038fab1b7ab343ab058450d48a925c002adc | |
parent | 04125d8a9cbd1272486c327e65445b77f3335460 (diff) |
Fix T52291: Boolean fails w/ co-linear edged ngons
This means boolean tessellation wont match viewport tessellation
however it's needed to avoid zero area triangles causing problems.
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 128 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 1 | ||||
-rw-r--r-- | source/blender/modifiers/intern/MOD_boolean.c | 2 |
3 files changed, 130 insertions, 1 deletions
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index a4621b45fe6..a839f92b9e9 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -39,6 +39,8 @@ #include "BLI_polyfill2d.h" #include "BLI_polyfill2d_beautify.h" #include "BLI_linklist.h" +#include "BLI_edgehash.h" +#include "BLI_heap.h" #include "bmesh.h" #include "bmesh_tools.h" @@ -1474,3 +1476,129 @@ void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptri #undef USE_TESSFACE_SPEEDUP } + + +/** + * A version of #BM_mesh_calc_tessellation that avoids degenerate triangles. + */ +void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot) +{ + /* this assumes all faces can be scan-filled, which isn't always true, + * worst case we over alloc a little which is acceptable */ +#ifndef NDEBUG + const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); +#endif + + BMIter iter; + BMFace *efa; + int i = 0; + + MemArena *pf_arena = NULL; + + /* use_beauty */ + Heap *pf_heap = NULL; + EdgeHash *pf_ehash = NULL; + + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + /* don't consider two-edged faces */ + if (UNLIKELY(efa->len < 3)) { + /* do nothing */ + } + else if (efa->len == 3) { + BMLoop *l; + BMLoop **l_ptr = looptris[i++]; + l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa); + l_ptr[1] = l = l->next; + l_ptr[2] = l->next; + } + else if (efa->len == 4) { + BMLoop *l_v1 = BM_FACE_FIRST_LOOP(efa); + BMLoop *l_v2 = l_v1->next; + BMLoop *l_v3 = l_v2->next; + BMLoop *l_v4 = l_v1->prev; + + const bool split_24 = (BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) > 0.0f); + + BMLoop **l_ptr_a = looptris[i++]; + BMLoop **l_ptr_b = looptris[i++]; + if (split_24 == 0) { + l_ptr_a[0] = l_v1; + l_ptr_a[1] = l_v2; + l_ptr_a[2] = l_v3; + + l_ptr_b[0] = l_v1; + l_ptr_b[1] = l_v3; + l_ptr_b[2] = l_v4; + } + else { + l_ptr_a[0] = l_v1; + l_ptr_a[1] = l_v2; + l_ptr_a[2] = l_v4; + + l_ptr_b[0] = l_v2; + l_ptr_b[1] = l_v3; + l_ptr_b[2] = l_v4; + } + } + else { + int j; + + BMLoop *l_iter; + BMLoop *l_first; + BMLoop **l_arr; + + float axis_mat[3][3]; + float (*projverts)[2]; + unsigned int (*tris)[3]; + + const int totfilltri = efa->len - 2; + + if (UNLIKELY(pf_arena == NULL)) { + pf_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); + pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE); + } + + tris = BLI_memarena_alloc(pf_arena, sizeof(*tris) * totfilltri); + l_arr = BLI_memarena_alloc(pf_arena, sizeof(*l_arr) * efa->len); + projverts = BLI_memarena_alloc(pf_arena, sizeof(*projverts) * efa->len); + + axis_dominant_v3_to_m3_negate(axis_mat, efa->no); + + j = 0; + l_iter = l_first = BM_FACE_FIRST_LOOP(efa); + do { + l_arr[j] = l_iter; + mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co); + j++; + } while ((l_iter = l_iter->next) != l_first); + + BLI_polyfill_calc_arena((const float (*)[2])projverts, efa->len, 1, tris, pf_arena); + + BLI_polyfill_beautify((const float (*)[2])projverts, efa->len, tris, pf_arena, pf_heap, pf_ehash); + + for (j = 0; j < totfilltri; j++) { + BMLoop **l_ptr = looptris[i++]; + unsigned int *tri = tris[j]; + + l_ptr[0] = l_arr[tri[0]]; + l_ptr[1] = l_arr[tri[1]]; + l_ptr[2] = l_arr[tri[2]]; + } + + BLI_memarena_clear(pf_arena); + } + } + + if (pf_arena) { + BLI_memarena_free(pf_arena); + + BLI_heap_free(pf_heap, NULL); + BLI_edgehash_free(pf_ehash, NULL); + } + + *r_looptris_tot = i; + + BLI_assert(i <= looptris_tot); + +} diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index d944f3a8bc5..313caac1243 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -33,6 +33,7 @@ struct Heap; #include "BLI_compiler_attrs.h" void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot); +void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot); void BM_face_calc_tessellation( const BMFace *f, const bool use_fixed_quad, diff --git a/source/blender/modifiers/intern/MOD_boolean.c b/source/blender/modifiers/intern/MOD_boolean.c index 91b07ed49bb..f94ab777eb4 100644 --- a/source/blender/modifiers/intern/MOD_boolean.c +++ b/source/blender/modifiers/intern/MOD_boolean.c @@ -258,7 +258,7 @@ static DerivedMesh *applyModifier_bmesh( looptris = MEM_mallocN(sizeof(*looptris) * looptris_tot, __func__); - BM_mesh_calc_tessellation(bm, looptris, &tottri); + BM_mesh_calc_tessellation_beauty(bm, looptris, &tottri); /* postpone this until after tessellating * so we can use the original normals before the vertex are moved */ |