From 01c04333f5226703178fa027e8ce0de02dff982b Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 27 Dec 2014 16:47:42 +1100 Subject: Fix T43034: beautify-fill leaves zero area tri's --- source/blender/blenlib/BLI_math_base.h | 2 + source/blender/blenlib/BLI_math_geom.h | 1 + source/blender/blenlib/BLI_polyfill2d_beautify.h | 3 + source/blender/blenlib/intern/math_base_inline.c | 13 +++ source/blender/blenlib/intern/math_geom.c | 15 +++ source/blender/blenlib/intern/polyfill2d.c | 4 +- .../blender/blenlib/intern/polyfill2d_beautify.c | 28 ++---- source/blender/bmesh/tools/bmesh_beautify.c | 108 +++++---------------- 8 files changed, 72 insertions(+), 102 deletions(-) (limited to 'source/blender') diff --git a/source/blender/blenlib/BLI_math_base.h b/source/blender/blenlib/BLI_math_base.h index 13718e83621..2bc23c8a72d 100644 --- a/source/blender/blenlib/BLI_math_base.h +++ b/source/blender/blenlib/BLI_math_base.h @@ -194,6 +194,8 @@ MINLINE int min_iiii(int a, int b, int c, int d); MINLINE int max_iiii(int a, int b, int c, int d); MINLINE float signf(float f); +MINLINE int signum_i_ex(float a, float eps); +MINLINE int signum_i(float a); MINLINE float power_of_2(float f); diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 32678bdf680..95ab3185d1f 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -60,6 +60,7 @@ float area_poly_v3(const float verts[][3], unsigned int nr); float area_poly_v2(const float verts[][2], unsigned int nr); float cotangent_tri_weight_v3(const float v1[3], const float v2[3], const float v3[3]); +void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3]); MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2]); float cross_poly_v2(const float verts[][2], unsigned int nr); diff --git a/source/blender/blenlib/BLI_polyfill2d_beautify.h b/source/blender/blenlib/BLI_polyfill2d_beautify.h index c3bb29af21e..20e53b080fe 100644 --- a/source/blender/blenlib/BLI_polyfill2d_beautify.h +++ b/source/blender/blenlib/BLI_polyfill2d_beautify.h @@ -33,6 +33,9 @@ void BLI_polyfill_beautify( /* structs for reuse */ struct MemArena *arena, struct Heap *eheap, struct EdgeHash *eh); +float BLI_polyfill_beautify_quad_rotate_calc( + const float v1[2], const float v2[2], const float v3[2], const float v4[2]); + /* avoid realloc's when creating new structures for polyfill ngons */ #define BLI_POLYFILL_ALLOC_NGON_RESERVE 64 diff --git a/source/blender/blenlib/intern/math_base_inline.c b/source/blender/blenlib/intern/math_base_inline.c index 39116d6f30f..f5713824296 100644 --- a/source/blender/blenlib/intern/math_base_inline.c +++ b/source/blender/blenlib/intern/math_base_inline.c @@ -276,5 +276,18 @@ MINLINE float signf(float f) return (f < 0.f) ? -1.f : 1.f; } +MINLINE int signum_i_ex(float a, float eps) +{ + if (a > eps) return 1; + if (a < -eps) return -1; + else return 0; +} + +MINLINE int signum_i(float a) +{ + if (a > 0.0f) return 1; + if (a < 0.0f) return -1; + else return 0; +} #endif /* __MATH_BASE_INLINE_C__ */ diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 3a0187584ff..a360148182d 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -50,6 +50,21 @@ void cent_quad_v3(float cent[3], const float v1[3], const float v2[3], const flo cent[2] = 0.25f * (v1[2] + v2[2] + v3[2] + v4[2]); } +void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3]) +{ + float n1[3], n2[3]; + + n1[0] = v1[0] - v2[0]; + n2[0] = v2[0] - v3[0]; + n1[1] = v1[1] - v2[1]; + n2[1] = v2[1] - v3[1]; + n1[2] = v1[2] - v2[2]; + n2[2] = v2[2] - v3[2]; + n[0] = n1[1] * n2[2] - n1[2] * n2[1]; + n[1] = n1[2] * n2[0] - n1[0] * n2[2]; + n[2] = n1[0] * n2[1] - n1[1] * n2[0]; +} + float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3]) { float n1[3], n2[3]; diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c index 16cf7ff960b..3aadbe5f1df 100644 --- a/source/blender/blenlib/intern/polyfill2d.c +++ b/source/blender/blenlib/intern/polyfill2d.c @@ -165,7 +165,7 @@ static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip); static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip); -BLI_INLINE eSign signum_i(float a) +BLI_INLINE eSign signum_enum(float a) { if (UNLIKELY(a == 0.0f)) return 0; @@ -191,7 +191,7 @@ BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2]) { - return signum_i(area_tri_signed_v2_alt_2x(v3, v2, v1)); + return signum_enum(area_tri_signed_v2_alt_2x(v3, v2, v1)); } diff --git a/source/blender/blenlib/intern/polyfill2d_beautify.c b/source/blender/blenlib/intern/polyfill2d_beautify.c index b8922ef6cb2..7914b7cb39b 100644 --- a/source/blender/blenlib/intern/polyfill2d_beautify.c +++ b/source/blender/blenlib/intern/polyfill2d_beautify.c @@ -123,7 +123,7 @@ BLI_INLINE bool is_boundary_edge(unsigned int i_a, unsigned int i_b, const unsig * * \return (negative number means the edge can be rotated, lager == better). */ -static float quad_v2_rotate_beauty_calc( +float BLI_polyfill_beautify_quad_rotate_calc( const float v1[2], const float v2[2], const float v3[2], const float v4[2]) { /* not a loop (only to be able to break out) */ @@ -150,24 +150,16 @@ static float quad_v2_rotate_beauty_calc( } } - 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, v2, v3, v4)) { - break; - } + /* one of the tri's was degenerate, check we're not rotating + * into a different degenerate shape or flipping the face */ + if ((fabsf(area_2x_123) <= FLT_EPSILON) || (fabsf(area_2x_134) <= FLT_EPSILON)) { + /* one of the new rotations is degenerate */ + break; } - else { - /* one of the tri's was degenerate, chech we're not rotating - * into a different degenerate shape or flipping the face */ - if ((fabsf(area_2x_123) <= FLT_EPSILON) || (fabsf(area_2x_134) <= FLT_EPSILON)) { - /* one of the new rotations is degenerate */ - break; - } - if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) { - /* rotation would cause flipping */ - break; - } + if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) { + /* rotation would cause flipping */ + break; } { @@ -225,7 +217,7 @@ static float polyedge_rotate_beauty_calc( v2 = coords[e->verts[0]]; v4 = coords[e->verts[1]]; - return quad_v2_rotate_beauty_calc(v1, v2, v3, v4); + return BLI_polyfill_beautify_quad_rotate_calc(v1, v2, v3, v4); } static void polyedge_beauty_cost_update_single( diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c index 6fb7f7cb4be..e531db1d02d 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" @@ -131,13 +132,16 @@ static float bm_edge_calc_rotate_beauty__area( /* 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) && @@ -145,100 +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)) { + /** + * 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; } } - 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 = cross_tri_v2(v1_xy, v2_xy, v3_xy); - area_b = cross_tri_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 */ - 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); - - /* note, area is in fact (area * 2), - * but in this case its OK, since we're comparing ratios */ - - /* edge (2-4), current state */ - area_a = fabsf(cross_tri_v2(v2_xy, v3_xy, v4_xy)); - area_b = fabsf(cross_tri_v2(v2_xy, v4_xy, v1_xy)); - prim_a = len_23 + len_34 + len_24; - prim_b = len_41 + len_12 + len_24; - fac_24 = (area_a / prim_a) + (area_b / prim_b); - - /* edge (1-3), new state */ - area_a = fabsf(cross_tri_v2(v1_xy, v2_xy, v3_xy)); - area_b = fabsf(cross_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; -- cgit v1.2.3