Triangulate Modifier changes - using scanfill
authorDalai Felinto <dfelinto@gmail.com>
Tue, 8 Oct 2013 19:28:11 +0000 (19:28 +0000)
committerDalai Felinto <dfelinto@gmail.com>
Tue, 8 Oct 2013 19:28:11 +0000 (19:28 +0000)
The ear loop method is potentially too slow (OˆN).

We are not using the 'beauty' option at the moment.
I'll incorporate that next.
(and later specific methods for quad splitting)

Patch done in collaboration (and reviewed by)  with Campbell Barton.

source/blender/bmesh/intern/bmesh_core.c
source/blender/bmesh/intern/bmesh_core.h
source/blender/bmesh/intern/bmesh_polygon.c
source/blender/bmesh/intern/bmesh_polygon.h
source/blender/bmesh/tools/bmesh_triangulate.c

index 164a92125cd0c921e197efb7edf569ce33e50a9a..0b14cf22276e20479b8488a54a5cc7fdbb27bf08 100644 (file)
@@ -2279,3 +2279,27 @@ BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep)
        BMLoop *l = BM_face_vert_share_loop(f_sep, v_sep);
        return bmesh_urmv_loop(bm, l);
 }
+
+/**
+ * Avoid calling this where possible,
+ * low level function for swapping faces.
+ */
+void bmesh_face_swap_data(BMesh *bm, BMFace *f_a, BMFace *f_b)
+{
+       BMLoop *l_iter, *l_first;
+
+       BLI_assert(f_a != f_b);
+
+       l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
+       do {
+               l_iter->f = f_b;
+       } while ((l_iter = l_iter->next) != l_first);
+
+       l_iter = l_first = BM_FACE_FIRST_LOOP(f_b);
+       do {
+               l_iter->f = f_a;
+       } while ((l_iter = l_iter->next) != l_first);
+
+       SWAP(BMFace, (*f_a), (*f_b));
+       bm->elem_index_dirty |= BM_FACE;
+}
index a18c2ebd32c746730a0922e882072ec9b3dc6e97..9e33509c2c831ec60d9029b2a6c3ee5506519743 100644 (file)
@@ -87,4 +87,6 @@ BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e);
 BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep);
 BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep);
 
+void    bmesh_face_swap_data(BMesh *bm, BMFace *f_a, BMFace *f_b);
+
 #endif /* __BMESH_CORE_H__ */
index 0978faee9e49532debc61d1704574952cdc0d05a..d11ae82b3d2e85d71467c4d331229515762861c1 100644 (file)
@@ -34,6 +34,7 @@
 
 #include "BLI_alloca.h"
 #include "BLI_math.h"
+#include "BLI_memarena.h"
 #include "BLI_scanfill.h"
 #include "BLI_listbase.h"
 
@@ -801,264 +802,127 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3])
        return crosses % 2 != 0;
 }
 
-static bool bm_face_goodline(float const (*projectverts)[2], BMFace *f, int v1i, int v2i, int v3i)
-{
-       BMLoop *l_iter;
-       BMLoop *l_first;
-
-       float pv1[2];
-       const float *v1 = projectverts[v1i];
-       const float *v2 = projectverts[v2i];
-       const float *v3 = projectverts[v3i];
-       int i;
-
-       /* v3 must be on the left side of [v1, v2] line, else we know [v1, v3] is outside of f! */
-       if (testedgesidef(v1, v2, v3)) {
-               return false;
-       }
-
-       l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-       do {
-               i = BM_elem_index_get(l_iter->v);
-               copy_v2_v2(pv1, projectverts[i]);
-
-               if (ELEM3(i, v1i, v2i, v3i)) {
-#if 0
-                       printf("%d in (%d, %d, %d) tri (from indices!), continuing\n", i, v1i, v2i, v3i);
-#endif
-                       continue;
-               }
-
-               if (isect_point_tri_v2(pv1, v1, v2, v3) ||
-                   isect_point_tri_v2(pv1, v3, v2, v1))
-               {
-#if 0
-                       if (isect_point_tri_v2(pv1, v1, v2, v3))
-                               printf("%d in (%d, %d, %d)\n", v3i, i, v1i, v2i);
-                       else
-                               printf("%d in (%d, %d, %d)\n", v1i, i, v3i, v2i);
-#endif
-                       return false;
-               }
-       } while ((l_iter = l_iter->next) != l_first);
-       return true;
-}
-
 /**
- * \brief Find Ear
+ * \brief BMESH TRIANGULATE FACE
  *
- * Used by tessellator to find the next triangle to 'clip off' of a polygon while tessellating.
+ * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not
+ * produces a "remaining" face with too much wide/narrow angles
+ * (using cos (i.e. dot product of normalized vectors) of angles).
  *
- * \param f The face to search.
- * \param projectverts an array of face vert coords.
- * \param use_beauty Currently only applies to quads, can be extended later on.
- * \param abscoss Must be allocated by caller, and at least f->len length
- *        (allow to avoid allocating a new one for each tri!).
+ * \param r_faces_new if non-null, must be an array of BMFace pointers,
+ * with a length equal to (f->len - 2). It will be filled with the new
+ * triangles.
+ *
+ * \note use_tag tags new flags and edges.
  */
-static BMLoop *poly_find_ear(BMFace *f, float (*projectverts)[2], const bool use_beauty, float *abscoss)
+void BM_face_triangulate(BMesh *bm, BMFace *f,
+                         BMFace **r_faces_new,
+                         MemArena *sf_arena,
+                         const bool UNUSED(use_beauty), const bool use_tag)
 {
-       BMLoop *bestear = NULL;
+       int nf_i = 0;
+       BMLoop *l_iter, *l_first, *l_new;
+       BMFace *f_new;
 
-       BMLoop *l_iter;
-       BMLoop *l_first;
+       BLI_assert(BM_face_is_normal_valid(f));
 
-       const float cos_threshold = 0.9f;
-       const float bias = 1.0f + 1e-6f;
-
-       /* just triangulate degenerate faces */
-       if (UNLIKELY(is_zero_v3(f->no))) {
-               return BM_FACE_FIRST_LOOP(f);
-       }
 
        if (f->len == 4) {
-               BMLoop *larr[4];
-               int i = 0, i4;
-               float cos1, cos2;
-               l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-               do {
-                       larr[i] = l_iter;
-                       i++;
-               } while ((l_iter = l_iter->next) != l_first);
+               l_first = BM_FACE_FIRST_LOOP(f);
 
-               /* pick 0/1 based on best length */
-               /* XXX Can't only rely on such test, also must check we do not get (too much) degenerated triangles!!! */
-               i = (((len_squared_v3v3(larr[0]->v->co, larr[2]->v->co) >
-                      len_squared_v3v3(larr[1]->v->co, larr[3]->v->co) * bias)) != use_beauty);
-               i4 = (i + 3) % 4;
-               /* Check produced tris aren't too flat/narrow...
-                * Probably not the best test, but is quite efficient and should at least avoid null-area faces! */
-               cos1 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i]->v->co, larr[i + 1]->v->co));
-               cos2 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i + 2]->v->co, larr[i + 1]->v->co));
-#if 0
-               printf("%d, (%f, %f), (%f, %f)\n", i, cos1, cos2,
-                      fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)),
-                      fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)));
-#endif
-               if (cos1 < cos2)
-                       cos1 = cos2;
-
-               if (cos1 > cos_threshold) {
-                       if (cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)) &&
-                           cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)))
-                       {
-                               i = !i;
-                       }
+               f_new = BM_face_split(bm, f, l_first->v, l_first->next->next->v, &l_new, NULL, false);
+               copy_v3_v3(f_new->no, f->no);
+
+               if (UNLIKELY(!l_new || !f_new)) {
+                       fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
                }
-               /* Last check we do not get overlapping triangles
-                * (as much as possible, there are some cases with no good solution!) */
-               i4 = (i + 3) % 4;
-               if (!bm_face_goodline((float const (*)[2])projectverts, f,
-                                     BM_elem_index_get(larr[i4]->v),
-                                     BM_elem_index_get(larr[i]->v),
-                                     BM_elem_index_get(larr[i + 1]->v)))
-               {
-                       i = !i;
+
+               if (use_tag) {
+                       BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
+                       BM_elem_flag_enable(f, BM_ELEM_TAG);
                }
-/*             printf("%d\n", i);*/
-               bestear = larr[i];
 
+               if (r_faces_new) {
+                       r_faces_new[nf_i++] = f_new;
+               }
        }
-       else {
-               /* float angle, bestangle = 180.0f; */
-               const int len = f->len;
-               float cos, cos_best = 1.0f;
-               int i, j;
+       else if (f->len > 4) {
+               /* scanfill */
+               ScanFillContext sf_ctx;
+               ScanFillVert *sf_vert, *sf_vert_prev = NULL;
+               ScanFillFace *sf_tri;
+               int totfilltri;
 
-               /* Compute cos of all corners! */
-               i = 0;
+               /* populate scanfill */
+               BLI_scanfill_begin_arena(&sf_ctx, sf_arena);
                l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-               do {
-                       const BMVert *v1 = l_iter->prev->v;
-                       const BMVert *v2 = l_iter->v;
-                       const BMVert *v3 = l_iter->next->v;
 
-                       abscoss[i] = fabsf(cos_v3v3v3(v1->co, v2->co, v3->co));
-/*                     printf("tcoss: %f\n", *tcoss);*/
-                       i++;
-               } while ((l_iter = l_iter->next) != l_first);
+               /* step once before entering the loop */
+               sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+               sf_vert->tmp.p = l_iter;
+               sf_vert_prev = sf_vert;
+               l_iter = l_iter->next;
 
-               i = 0;
-               l_iter = l_first;
                do {
-                       const BMVert *v1 = l_iter->prev->v;
-                       const BMVert *v2 = l_iter->v;
-                       const BMVert *v3 = l_iter->next->v;
-
-                       /* Compute highest cos (i.e. narrowest angle) of this tri. */
-                       cos = max_fff(abscoss[i],
-                                     fabsf(cos_v3v3v3(v2->co, v3->co, v1->co)),
-                                     fabsf(cos_v3v3v3(v3->co, v1->co, v2->co)));
-
-                       /* Compare to prev best (i.e. lowest) cos. */
-                       if (cos < cos_best) {
-                               if (bm_face_goodline((float const (*)[2])projectverts, f,
-                                                    BM_elem_index_get(v1),
-                                                    BM_elem_index_get(v2),
-                                                    BM_elem_index_get(v3)))
-                               {
-                                       /* We must check this tri would not leave a (too much) degenerated remaining face! */
-                                       /* For now just assume if the average of cos of all
-                                        * "remaining face"'s corners is below a given threshold, it's OK. */
-                                       float cos_mean = fabsf(cos_v3v3v3(v1->co, v3->co, l_iter->next->next->v->co));
-                                       const int i_limit = (i - 1 + len) % len;
-                                       cos_mean += fabsf(cos_v3v3v3(l_iter->prev->prev->v->co, v1->co, v3->co));
-                                       j = (i + 2) % len;
-                                       do {
-                                               cos_mean += abscoss[j];
-                                       } while ((j = (j + 1) % len) != i_limit);
-                                       cos_mean /= len - 1;
-
-                                       /* We need a best ear in any case... */
-                                       if (cos_mean < cos_threshold || (!bestear && cos_mean < 1.0f)) {
-                                               /* OKI, keep this ear (corner...) as a potential best one! */
-                                               bestear = l_iter;
-                                               cos_best = cos;
-                                       }
-#if 0
-                                       else
-                                               printf("Had a nice tri (higest cos of %f, current cos_best is %f), "
-                                                      "but average cos of all \"remaining face\"'s corners is too high (%f)!\n",
-                                                      cos, cos_best, cos_mean);
-#endif
-                               }
-                       }
-                       i++;
+                       sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co);
+                       BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_vert);
+
+                       sf_vert->tmp.p = l_iter;
+                       sf_vert_prev = sf_vert;
                } while ((l_iter = l_iter->next) != l_first);
-       }
 
-       return bestear;
-}
+               BLI_scanfill_edge_add(&sf_ctx, sf_vert_prev, sf_ctx.fillvertbase.first);
 
-/**
- * \brief BMESH TRIANGULATE FACE
- *
- * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not
- * produces a "remaining" face with too much wide/narrow angles
- * (using cos (i.e. dot product of normalized vectors) of angles).
- *
- * \param r_faces_new if non-null, must be an array of BMFace pointers,
- * with a length equal to (f->len - 2). It will be filled with the new
- * triangles.
- *
- * \note use_tag tags new flags and edges.
- */
-void BM_face_triangulate(BMesh *bm, BMFace *f,
-                         BMFace **r_faces_new,
-                         const bool use_beauty, const bool use_tag)
-{
-       const float f_len_orig = f->len;
-       int i, nf_i = 0;
-       BMLoop *l_new;
-       BMLoop *l_iter;
-       BMLoop *l_first;
-       /* BM_face_triangulate: temp absolute cosines of face corners */
-       float (*projectverts)[2] = BLI_array_alloca(projectverts, f_len_orig);
-       float *abscoss = BLI_array_alloca(abscoss, f_len_orig);
-       float mat[3][3];
+               /* calculate filled triangles */
+               totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, f->no);
+               BLI_assert(totfilltri <= f->len - 2);
 
-       BLI_assert(BM_face_is_normal_valid(f));
 
-       axis_dominant_v3_to_m3(mat, f->no);
+               /* loop over calculated triangles and create new geometry */
+               for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
+                       /* the order is reverse, otherwise the normal is flipped */
+                       BMLoop *l_tri[3] = {
+                           sf_tri->v3->tmp.p,
+                           sf_tri->v2->tmp.p,
+                           sf_tri->v1->tmp.p};
 
-       /* copy vertex coordinates to vertspace area */
-       i = 0;
-       l_iter = l_first = BM_FACE_FIRST_LOOP(f);
-       do {
-               mul_v2_m3v3(projectverts[i], mat, l_iter->v->co);
-               BM_elem_index_set(l_iter->v, i++); /* set dirty! */
-       } while ((l_iter = l_iter->next) != l_first);
+                       BMVert *v_tri[3] = {
+                           l_tri[0]->v,
+                           l_tri[1]->v,
+                           l_tri[2]->v};
 
-       bm->elem_index_dirty |= BM_VERT; /* see above */
+                       f_new = BM_face_create_verts(bm, v_tri, 3, f, false, true);
+                       l_new = BM_FACE_FIRST_LOOP(f_new);
 
-       while (f->len > 3) {
-               l_iter = poly_find_ear(f, projectverts, use_beauty, abscoss);
+                       BLI_assert(v_tri[0] == l_new->v);
 
-               /* force triangulation - if we can't find an ear the face is degenerate */
-               if (l_iter == NULL) {
-                       l_iter = BM_FACE_FIRST_LOOP(f);
-               }
+                       /* copy CD data */
+                       BM_elem_attrs_copy(bm, bm, l_tri[0], l_new);
+                       BM_elem_attrs_copy(bm, bm, l_tri[1], l_new->next);
+                       BM_elem_attrs_copy(bm, bm, l_tri[2], l_new->prev);
 
-/*             printf("Subdividing face...\n");*/
-               f = BM_face_split(bm, l_iter->f, l_iter->prev->v, l_iter->next->v, &l_new, NULL, true);
+                       if (use_tag) {
+                               BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
+                       }
 
-               if (UNLIKELY(!f)) {
-                       fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__);
-                       break;
+                       if (r_faces_new && sf_tri->prev) {
+                               r_faces_new[nf_i++] = f_new;
+                       }
                }
 
-               copy_v3_v3(f->no, l_iter->f->no);
+               if (sf_ctx.fillfacebase.first) {
+                       /* we can't delete the real face, so swap data and delete */
+                       bmesh_face_swap_data(bm, f, f_new);
+                       BM_face_kill(bm, f_new);
 
-               if (use_tag) {
-                       BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
-                       BM_elem_flag_enable(f, BM_ELEM_TAG);
+                       if (use_tag) {
+                               BM_elem_flag_enable(f, BM_ELEM_TAG);
+                       }
                }
 
-               if (r_faces_new) {
-                       r_faces_new[nf_i++] = f;
-               }
+               /* garbage collection */
+               BLI_scanfill_end_arena(&sf_ctx, sf_arena);
        }
-
-       BLI_assert(f->len == 3);
 }
 
 /**
index 14fe1e763601b1f359f805c85c4506c794cf4374..b71176212736007ae08c4e6631d7330edf187543 100644 (file)
@@ -53,6 +53,7 @@ void  BM_face_normal_flip(BMesh *bm, BMFace *f) ATTR_NONNULL();
 bool  BM_face_point_inside_test(BMFace *f, const float co[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
 
 void  BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **newfaces,
+                          struct MemArena *sf_arena,
                           const bool use_beauty, const bool use_tag) ATTR_NONNULL(1, 2);
 
 void  BM_face_legal_splits(BMFace *f, BMLoop *(*loops)[2], int len) ATTR_NONNULL();
index 2eacf62d68ab5bf563b590d4721dde4382131cf2..34ff493a026ec782cda17a6b0852c5df9f81b96e 100644 (file)
@@ -31,6 +31,9 @@
 
 #include "BLI_utildefines.h"
 #include "BLI_alloca.h"
+#include "BLI_memarena.h"
+#include "BLI_listbase.h"
+#include "BLI_scanfill.h"
 
 #include "bmesh.h"
 
 /**
  * a version of #BM_face_triangulate that maps to #BMOpSlot
  */
-static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, const bool use_beauty, const bool use_tag,
+static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, MemArena *sf_arena, const bool use_beauty, const bool use_tag,
                                         BMOperator *op, BMOpSlot *slot_facemap_out)
 {
        const int faces_array_tot = face->len - 3;
        BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
        BLI_assert(face->len > 3);
 
-       BM_face_triangulate(bm, face, faces_array, use_beauty, use_tag);
+       BM_face_triangulate(bm, face, faces_array, sf_arena, use_beauty, use_tag);
 
        if (faces_array) {
                int i;
@@ -63,13 +66,16 @@ void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only,
 {
        BMIter iter;
        BMFace *face;
+       MemArena *sf_arena;
+
+       sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__);
 
        if (slot_facemap_out) {
                /* same as below but call: bm_face_triangulate_mapping() */
                BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
                        if (face->len > 3) {
                                if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
-                                       bm_face_triangulate_mapping(bm, face, use_beauty, tag_only,
+                                       bm_face_triangulate_mapping(bm, face, sf_arena, use_beauty, tag_only,
                                                                    op, slot_facemap_out);
                                }
                        }
@@ -79,9 +85,11 @@ void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only,
                BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) {
                        if (face->len > 3) {
                                if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) {
-                                       BM_face_triangulate(bm, face, NULL, use_beauty, tag_only);
+                                       BM_face_triangulate(bm, face, NULL, sf_arena, use_beauty, tag_only);
                                }
                        }
                }
        }
+
+       BLI_memarena_free(sf_arena);
 }