diff options
Diffstat (limited to 'source/blender/bmesh/tools/bmesh_beautify.c')
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_beautify.c | 123 |
1 files changed, 37 insertions, 86 deletions
diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c index 6639e767e77..990a2108bd7 100644 --- a/source/blender/bmesh/tools/bmesh_beautify.c +++ b/source/blender/bmesh/tools/bmesh_beautify.c @@ -37,6 +37,7 @@ #include "BLI_math.h" #include "BLI_heap.h" +#include "BLI_polyfill2d_beautify.h" #include "MEM_guardedalloc.h" @@ -96,7 +97,7 @@ static GSet *erot_gset_new(void) static void erot_state_ex(const BMEdge *e, int v_index[2], int f_index[2]) { - BLI_assert(BM_edge_is_manifold((BMEdge *)e)); + BLI_assert(BM_edge_is_manifold(e)); BLI_assert(BM_vert_in_edge(e, e->l->prev->v) == false); BLI_assert(BM_vert_in_edge(e, e->l->radial_next->prev->v) == false); @@ -125,22 +126,22 @@ static void erot_state_alternate(const BMEdge *e, EdRotState *e_state) /* -------------------------------------------------------------------- */ /* Calculate the improvement of rotating the edge */ -/** - * \return a negative value means the edge can be rotated. - */ static float bm_edge_calc_rotate_beauty__area( const float v1[3], const float v2[3], const float v3[3], const float v4[3]) { /* not a loop (only to be able to break out) */ do { float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2]; - bool is_zero_a, is_zero_b; /* first get the 2d values */ { + const float eps = 1e-5; float no_a[3], no_b[3]; float no[3]; float axis_mat[3][3]; + float no_scale; + cross_tri_v3(no_a, v2, v3, v4); + cross_tri_v3(no_b, v2, v4, v1); // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f); BLI_assert((ELEM(v1, v2, v3, v4) == false) && @@ -148,97 +149,40 @@ static float bm_edge_calc_rotate_beauty__area( (ELEM(v3, v1, v2, v4) == false) && (ELEM(v4, v1, v2, v3) == false)); - is_zero_a = (normal_tri_v3(no_a, v2, v3, v4) <= FLT_EPSILON); - is_zero_b = (normal_tri_v3(no_b, v2, v4, v1) <= FLT_EPSILON); - - if (LIKELY(is_zero_a == false && is_zero_b == false)) { - add_v3_v3v3(no, no_a, no_b); - if (UNLIKELY(normalize_v3(no) <= FLT_EPSILON)) { - break; - } - } - else if (is_zero_a == false) { - copy_v3_v3(no, no_a); - } - else if (is_zero_b == false) { - copy_v3_v3(no, no_b); - } - else { - /* both zero area, no useful normal can be calculated */ + add_v3_v3v3(no, no_a, no_b); + if (UNLIKELY((no_scale = normalize_v3(no)) <= FLT_EPSILON)) { break; } - // { float a = angle_normalized_v3v3(no_a, no_b); printf("~ %.7f\n", a); fflush(stdout);} - axis_dominant_v3_to_m3(axis_mat, no); mul_v2_m3v3(v1_xy, axis_mat, v1); mul_v2_m3v3(v2_xy, axis_mat, v2); mul_v2_m3v3(v3_xy, axis_mat, v3); mul_v2_m3v3(v4_xy, axis_mat, v4); - } - - // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f); - - if (is_zero_a == false && is_zero_b == false) { - /* both tri's are valid, check we make a concave quad */ - if (!is_quad_convex_v2(v1_xy, v2_xy, v3_xy, v4_xy)) { - break; - } - } - else { - /* one of the tri's was degenerate, chech we're not rotating - * into a different degenerate shape or flipping the face */ - float area_a, area_b; - - area_a = area_tri_signed_v2(v1_xy, v2_xy, v3_xy); - area_b = area_tri_signed_v2(v1_xy, v3_xy, v4_xy); - - if ((fabsf(area_a) <= FLT_EPSILON) || (fabsf(area_b) <= FLT_EPSILON)) { - /* one of the new rotations is degenerate */ - break; - } - if ((area_a >= 0.0f) != (area_b >= 0.0f)) { - /* rotation would cause flipping */ + /** + * Check if input faces are already flipped. + * Logic for 'signum_i' addition is: + * + * Accept: + * - (1, 1) or (-1, -1): same side (common case). + * - (-1/1, 0): one degenerate, OK since we may rotate into a valid state. + * + * Ignore: + * - (-1, 1): opposite winding, ignore. + * - ( 0, 0): both degenerate, ignore. + * + * \note The cross product is divided by 'no_scale' + * so the rotation calculation is scale independent. + */ + if (!(signum_i_ex(cross_tri_v2(v2_xy, v3_xy, v4_xy) / no_scale, eps) + + signum_i_ex(cross_tri_v2(v2_xy, v4_xy, v1_xy) / no_scale, eps))) + { break; } } - { - /* testing rule: the area divided by the perimeter, - * check if (1-3) beats the existing (2-4) edge rotation */ - float area_a, area_b; - float prim_a, prim_b; - float fac_24, fac_13; - - float len_12, len_23, len_34, len_41, len_24, len_13; - - /* edges around the quad */ - len_12 = len_v2v2(v1_xy, v2_xy); - len_23 = len_v2v2(v2_xy, v3_xy); - len_34 = len_v2v2(v3_xy, v4_xy); - len_41 = len_v2v2(v4_xy, v1_xy); - /* edges crossing the quad interior */ - len_13 = len_v2v2(v1_xy, v3_xy); - len_24 = len_v2v2(v2_xy, v4_xy); - - /* edge (2-4), current state */ - area_a = area_tri_v2(v2_xy, v3_xy, v4_xy); - area_b = area_tri_v2(v2_xy, v4_xy, v1_xy); - prim_a = len_23 + len_34 + len_24; - prim_b = len_24 + len_41 + len_12; - fac_24 = (area_a / prim_a) + (area_b / prim_b); - - /* edge (1-3), new state */ - area_a = area_tri_v2(v1_xy, v2_xy, v3_xy); - area_b = area_tri_v2(v1_xy, v3_xy, v4_xy); - prim_a = len_12 + len_23 + len_13; - prim_b = len_34 + len_41 + len_13; - fac_13 = (area_a / prim_a) + (area_b / prim_b); - - /* negative number if (1-3) is an improved state */ - return fac_24 - fac_13; - } + return BLI_polyfill_beautify_quad_rotate_calc(v1_xy, v2_xy, v3_xy, v4_xy); } while (false); return FLT_MAX; @@ -272,6 +216,12 @@ static float bm_edge_calc_rotate_beauty__angle( return FLT_MAX; } +/** + * Assuming we have 2 triangles sharing an edge (2 - 4), + * check if the edge running from (1 - 3) gives better results. + * + * \return (negative number means the edge can be rotated, lager == better). + */ float BM_verts_calc_rotate_beauty( const BMVert *v1, const BMVert *v2, const BMVert *v3, const BMVert *v4, const short flag, const short method) @@ -400,9 +350,10 @@ static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_ /** * \note This function sets the edge indices to invalid values. */ -void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_len, - const short flag, const short method, - const short oflag_edge, const short oflag_face) +void BM_mesh_beautify_fill( + BMesh *bm, BMEdge **edge_array, const int edge_array_len, + const short flag, const short method, + const short oflag_edge, const short oflag_face) { Heap *eheap; /* edge heap */ HeapNode **eheap_table; /* edge index aligned table pointing to the eheap */ |