Fix T52291: Boolean fails w/ co-linear edged ngons
authorCampbell Barton <ideasman42@gmail.com>
Thu, 14 Sep 2017 06:00:27 +0000 (16:00 +1000)
committerCampbell Barton <ideasman42@gmail.com>
Thu, 14 Sep 2017 06:08:03 +0000 (16:08 +1000)
This means boolean tessellation wont match viewport tessellation
however it's needed to avoid zero area triangles causing problems.

source/blender/bmesh/intern/bmesh_polygon.c
source/blender/bmesh/intern/bmesh_polygon.h
source/blender/modifiers/intern/MOD_boolean.c

index a4621b45fe61e2df94060056caa5fdb85eb1bdc5..a839f92b9e945b92bc8788fe40f48e3ebae9aa4c 100644 (file)
@@ -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);
+
+}
index d944f3a8bc54892851173885a0b9910bfe808200..313caac12431ca5ed7c4b385e8eba38a79b4f82a 100644 (file)
@@ -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,
index f86d8b99f3c20bced672086539712878248c7a63..a5ce18b9668edba3c7ab66aaf4c73e245cc0bd90 100644 (file)
@@ -246,7 +246,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 */