Commit: 9cc8a5c673a5303907df47d20d2572986486fffd
Author: Campbell Barton
Date: Sat Dec 27 16:47:42 2014 +1100
Branches: blender-v2.73-release
https://developer.blender.org/rB9cc8a5c673a5303907df47d20d2572986486fffd
Fix T43034: beautify-fill leaves zero area tri's
===================================================================
M source/blender/blenlib/BLI_math_base.h
M source/blender/blenlib/BLI_math_geom.h
M source/blender/blenlib/BLI_polyfill2d_beautify.h
M source/blender/blenlib/intern/math_base_inline.c
M source/blender/blenlib/intern/math_geom.c
M source/blender/blenlib/intern/polyfill2d.c
M source/blender/blenlib/intern/polyfill2d_beautify.c
M source/blender/bmesh/tools/bmesh_beautify.c
===================================================================
diff --git a/source/blender/blenlib/BLI_math_base.h
b/source/blender/blenlib/BLI_math_base.h
index 13718e8..2bc23c8 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 32678bd..95ab318 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 c3bb29a..20e53b0 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 39116d6..f571382 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 bcf2147..5dcd4c9 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 16cf7ff..3aadbe5 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 b8922ef..7914b7c 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 6fb7f7c..e531db1 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
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
