Commit: 57cff46cec9599e5897de72f45ce735da79db0ff
Author: Campbell Barton
Date: Thu Jun 16 04:27:48 2016 +1000
Branches: master
https://developer.blender.org/rB57cff46cec9599e5897de72f45ce735da79db0ff
BMesh Decimate: support ngons
===================================================================
M source/blender/bmesh/tools/bmesh_decimate_collapse.c
===================================================================
diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c
b/source/blender/bmesh/tools/bmesh_decimate_collapse.c
index 589b6d4..fe8b132 100644
--- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c
+++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c
@@ -34,6 +34,14 @@
#include "BLI_math.h"
#include "BLI_quadric.h"
#include "BLI_heap.h"
+#include "BLI_linklist.h"
+#include "BLI_alloca.h"
+#include "BLI_memarena.h"
+#include "BLI_edgehash.h"
+#include "BLI_polyfill2d.h"
+#include "BLI_polyfill2d_beautify.h"
+#include "BLI_stackdefines.h"
+
#include "BKE_customdata.h"
@@ -59,9 +67,6 @@
# define TOPOLOGY_FALLBACK_EPS 1e-12f
#endif
-/* these checks are for rare cases that we can't avoid since they are valid
meshes still */
-#define USE_SAFETY_CHECKS
-
#define BOUNDARY_PRESERVE_WEIGHT 100.0f
#define OPTIMIZE_EPS 0.01f /* FLT_EPSILON is too small, see [#33106] */
#define COST_INVALID FLT_MAX
@@ -473,12 +478,58 @@ static int *bm_edge_symmetry_map(BMesh *bm, unsigned int
symmetry_axis, float li
*
* \return true if any faces were triangulated.
*/
+static bool bm_face_triangulate(
+ BMesh *bm, BMFace *f_base, LinkNode **r_faces_double, int
*r_edges_tri_tot,
-static bool bm_decim_triangulate_begin(BMesh *bm)
+ MemArena *pf_arena,
+ /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
+ struct Heap *pf_heap, struct EdgeHash *pf_ehash)
+{
+ const int f_base_len = f_base->len;
+ int faces_array_tot = f_base_len - 3;
+ int edges_array_tot = f_base_len - 3;
+ BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
+ BMEdge **edges_array = BLI_array_alloca(edges_array, edges_array_tot);
+ const int quad_method = 0, ngon_method = 0; /* beauty */
+
+ bool has_cut = false;
+
+ const int f_index = BM_elem_index_get(f_base);
+
+ BM_face_triangulate(
+ bm, f_base,
+ faces_array, &faces_array_tot,
+ edges_array, &edges_array_tot,
+ r_faces_double,
+ quad_method, ngon_method, false,
+ pf_arena,
+ pf_heap, pf_ehash);
+
+ for (int i = 0; i < edges_array_tot; i++) {
+ BMLoop *l_iter, *l_first;
+ l_iter = l_first = edges_array[i]->l;
+ do {
+ BM_elem_index_set(l_iter, f_index); /* set_dirty */
+ has_cut = true;
+ } while ((l_iter = l_iter->radial_next) != l_first);
+ }
+
+ for (int i = 0; i < faces_array_tot; i++) {
+ BM_face_normal_update(faces_array[i]);
+ }
+
+ *r_edges_tri_tot += edges_array_tot;
+
+ return has_cut;
+}
+
+
+static bool bm_decim_triangulate_begin(BMesh *bm, int *r_edges_tri_tot)
{
BMIter iter;
BMFace *f;
- // bool has_quad; // could optimize this a little
+ bool has_quad;
+ bool has_ngon;
bool has_cut = false;
BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
@@ -493,98 +544,103 @@ static bool bm_decim_triangulate_begin(BMesh *bm)
BM_elem_index_set(l_iter, -1); /* set_dirty */
} while ((l_iter = l_iter->next) != l_first);
- // has_quad |= (f->len == 4)
+ has_quad |= (f->len > 3);
+ has_ngon |= (f->len > 4);
}
bm->elem_index_dirty |= BM_LOOP;
- /* adding new faces as we loop over faces
- * is normally best avoided, however in this case its not so bad
because any face touched twice
- * will already be triangulated*/
- BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
- if (f->len == 4) {
- BMLoop *f_l[4];
- BMLoop *l_a, *l_b;
+ {
+ MemArena *pf_arena;
+ Heap *pf_heap;
+ EdgeHash *pf_ehash;
- {
- BMLoop *l_iter = BM_FACE_FIRST_LOOP(f);
+ LinkNode *faces_double = NULL;
- f_l[0] = l_iter; l_iter = l_iter->next;
- f_l[1] = l_iter; l_iter = l_iter->next;
- f_l[2] = l_iter; l_iter = l_iter->next;
- f_l[3] = l_iter;
- }
+ if (has_ngon) {
+ pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE,
__func__);
+ pf_heap =
BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
+ pf_ehash = BLI_edgehash_new_ex(__func__,
BLI_POLYFILL_ALLOC_NGON_RESERVE);
+ }
+ else {
+ pf_arena = NULL;
+ pf_heap = NULL;
+ pf_ehash = NULL;
+ }
- if (len_squared_v3v3(f_l[0]->v->co, f_l[2]->v->co) <
- len_squared_v3v3(f_l[1]->v->co, f_l[3]->v->co))
- {
- l_a = f_l[0];
- l_b = f_l[2];
+ /* adding new faces as we loop over faces
+ * is normally best avoided, however in this case its not so
bad because any face touched twice
+ * will already be triangulated*/
+ BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+ if (f->len > 3) {
+ has_cut |= bm_face_triangulate(
+ bm, f, &faces_double,
+ r_edges_tri_tot,
+
+ pf_arena,
+ pf_heap, pf_ehash);
}
- else {
- l_a = f_l[1];
- l_b = f_l[3];
- }
-
-#ifdef USE_SAFETY_CHECKS
- if (BM_edge_exists(l_a->v, l_b->v) == NULL)
-#endif
- {
- BMFace *f_new;
- BMLoop *l_new;
-
- /* warning, NO_DOUBLE option here isn't handled
as nice as it could be
- * - if there is a quad that has a free
standing edge joining it along
- * where we want to split the face, there isnt
a good way we can handle this.
- * currently that edge will get removed when
joining the tris back into a quad. */
- f_new = BM_face_split(bm, f, l_a, l_b, &l_new,
NULL, false);
-
- if (f_new) {
- /* the value of this doesn't matter,
only that the 2 loops match and have unique values */
- const int f_index =
BM_elem_index_get(f);
-
- /* since we just split theres only ever
2 loops */
-
BLI_assert(BM_edge_is_manifold(l_new->e));
+ }
- BM_elem_index_set(l_new, f_index); /*
set_dirty */
- BM_elem_index_set(l_new->radial_next,
f_index); /* set_dirty */
+ while (faces_double) {
+ LinkNode *next = faces_double->next;
+ BM_face_kill(bm, faces_double->link);
+ MEM_freeN(faces_double);
+ faces_double = next;
+ }
- BM_face_normal_update(f);
- BM_face_normal_update(f_new);
+ BLI_memarena_free(pf_arena);
- has_cut = true;
- }
- }
+ if (has_ngon) {
+ BLI_heap_free(pf_heap, NULL);
+ BLI_edgehash_free(pf_ehash, NULL);
}
- }
- BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
+ BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
- if (has_cut) {
- /* now triangulation is done we need to correct index values */
- BM_mesh_elem_index_ensure(bm, BM_EDGE | BM_FACE);
+ if (has_cut) {
+ /* now triangulation is done we need to correct index
values */
+ BM_mesh_elem_index_ensure(bm, BM_EDGE | BM_FACE);
+ }
}
return has_cut;
}
-static void bm_decim_triangulate_end(BMesh *bm)
+
+static void bm_decim_triangulate_end(BMesh *bm, const int edges_tri_tot)
{
/* decimation finished, now re-join */
BMIter iter;
- BMEdge *e, *e_next;
+ BMEdge *e;
+
+ /* we need to collect before merging for ngons since the loops indices
will be lost */
+ BMEdge **edges_tri = MEM_mallocN(MIN2(edges_tri_tot, bm->totedge) *
sizeof(*edges_tri), __func__);
+ STACK_DECLARE(edges_tri);
/* boundary edges */
- BM_ITER_MESH_MUTABLE (e, e_next, &iter, bm, BM_EDGES_OF_MESH) {
+ BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
BMLoop *l_a, *l_b;
if (BM_edge_loop_pair(e, &l_a, &l_b)) {
const int l_a_index = BM_elem_index_get(l_a);
if (l_a_index != -1) {
const int l_b_index = BM_elem_index_get(l_b);
if (l_a_index == l_b_index) {
- if (LIKELY(l_a->f->len == 3 &&
l_b->f->len == 3)) {
- if (l_a->v != l_b->v) { /* if
this is the case, faces have become flipped */
- /* check we are not
making a degenerate quad */
+ if (l_a->v != l_b->v) { /* if this is
the case, faces have become flipped */
+ /* check we are not making a
degenerate quad */
+
+#define CAN_LOOP_MERGE(l) \
+ (BM_loop_is_manifold(l) && \
+ ((l)->v != (l)->radial_next->v) && \
+ (l_a_index == BM_elem_index_get(l)) && \
+ (l_a_index == BM_elem_index_get((l)->radial_next)))
+
+ if ((l_a->f->len == 3 &&
l_b->f->len == 3) &&
+
(!CAN_LOOP_MERGE(l_a->next)) &&
+
(!CAN_LOOP_MERGE(l_a->prev)) &&
+
(!CAN_LOOP_MERGE(l_b->next)) &&
+
(!CAN_LOOP_MERGE(l_b->prev)))
+ {
BMVert *vquad[4] = {
e->v1,
BM_vert_in_edge(e, l_a->next->v) ? l_a->prev->v : l_a->next->v,
@@ -597,17 +653,32 @@ static void bm_decim_triangulate_end(BMesh *bm)
BLI_assert(ELEM(vquad[2], vquad[1], vquad[0], vquad[3]) == false);
BLI_assert(ELEM(vquad[3], vquad[1], vquad[2], vquad[0]) == false);
- if
(is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
- /* highly
unlikely to fail, but prevents possible double-ups */
- BMFace *f[2] =
{l_a->f, l_b->f};
-
BM_faces_join(bm, f, 2, true);
+ if
(!is_quad_convex_v3(vquad[0]->co, vquad[1]->co, vquad[2]->co, vquad[3]->co)) {
+ continue;
}
}
+#undef CAN_LOOP_MERGE
+
+ /* highly unlikely to fail, but
prevents possible double-ups */
+ STACK_PUSH(edges_tri, e);
}
}
}
}
}
+
+ for (int i = 0; i < STACK_SIZE(edges_tri); i++) {
+ BMLoop *l_a, *l_b;
+ e = edges_tri[i];
+ if (BM_edge_loop_pair(e, &l_a, &l_b)) {
+ BMFace *f_array[2] = {l_a->f, l_b->f};
+ BM_faces_join(bm, f_array, 2, false);
+ if (e->l == NULL) {
+ BM_edge_kill(bm, e);
+ }
+ }
+ }
+ MEM_freeN(edges_tri);
}
#endif /* USE_TRIANGULATE */
@@ -1220,7 +1291,6 @@ void BM_mesh_decimate_collapse(
Quadric *vquadrics; /* vert index aligned quadrics */
int tot_edge_orig;
int face_tot_target;
- bool use_triangulate;
CD_UseFlag customdata_flag = 0;
@@ -1230,8 +1300,11 @@ void BM_mesh_decimate_collapse(
#endif
#ifdef USE_TRIANGULATE
+ int edges_tri_tot = 0;
/* temp convert quads to triangles */
- use_triangulate = bm_decim_triangulate_begin(bm);
+ bool use_triangulate = bm_decim_triangulate_begin(bm, &edges_tri_tot);
+#else
+ UNUSED_VARS(do_triangulate);
#endif
@@ -1416,7 +1489,7 @@ invalidate:
/* its possible we only had triangles, skip this step in that
case */
if (LIKELY(use_triangulate)) {
/* temp convert quads to triangles */
- bm_decim_triangulate_end(bm);
+ bm_decim_triangulate_end(bm, edges_tri_tot);
}
}
#endif
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
