diff options
author | Campbell Barton <ideasman42@gmail.com> | 2014-12-17 13:31:33 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2014-12-17 13:34:16 +0300 |
commit | a56e31c89c8a539e8726f5060eff3445064114a8 (patch) | |
tree | fc834124eae11f5ff2afebac1c0fb5453c32da8a | |
parent | dc2617130b2e1d7d2b9892fbd7c6e7b60caafb66 (diff) |
Fix triangulating concave quads
Resulting triangles could be pointing in opposing directions.
-rw-r--r-- | source/blender/blenlib/BLI_math_geom.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 28 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 43 |
3 files changed, 51 insertions, 21 deletions
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index ba32b29becc..32678bdf680 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -77,6 +77,7 @@ float volume_tetrahedron_signed_v3(const float v1[3], const float v2[3], const f bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]); bool is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2]); bool is_poly_convex_v2(const float verts[][2], unsigned int nr); +int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]); /********************************* Distance **********************************/ diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 1c75a907a95..42aa24d284d 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -4016,3 +4016,31 @@ bool is_poly_convex_v2(const float verts[][2], unsigned int nr) return true; } + +/** + * Check if either of the diagonals along this quad create flipped triangles + * (normals pointing away from eachother). + * - (1 << 0): (v1-v3) is flipped. + * - (1 << 1): (v2-v4) is flipped. + */ +int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]) +{ + float d_12[3], d_23[3], d_34[3], d_41[3]; + float cross_a[3], cross_b[3]; + int ret = 0; + + sub_v3_v3v3(d_12, v1, v2); + sub_v3_v3v3(d_23, v2, v3); + sub_v3_v3v3(d_34, v3, v4); + sub_v3_v3v3(d_41, v4, v1); + + cross_v3_v3v3(cross_a, d_12, d_23); + cross_v3_v3v3(cross_b, d_34, d_41); + ret |= ((dot_v3v3(cross_a, cross_b) < 0.0f) << 0); + + cross_v3_v3v3(cross_a, d_23, d_34); + cross_v3_v3v3(cross_b, d_41, d_12); + ret |= ((dot_v3v3(cross_a, cross_b) < 0.0f) << 1); + + return ret; +} diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index a0f2f8c9b1a..f2c426133c2 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -783,38 +783,39 @@ void BM_face_triangulate( break; } case MOD_TRIANGULATE_QUAD_SHORTEDGE: - { - BMLoop *l_v3, *l_v4; - float d1, d2; - - l_v1 = l_first; - l_v2 = l_first->next->next; - l_v3 = l_first->next; - l_v4 = l_first->prev; - - d1 = len_squared_v3v3(l_v1->v->co, l_v2->v->co); - d2 = len_squared_v3v3(l_v3->v->co, l_v4->v->co); - - if (d2 < d1) { - l_v1 = l_v3; - l_v2 = l_v4; - } - break; - } case MOD_TRIANGULATE_QUAD_BEAUTY: default: { BMLoop *l_v3, *l_v4; - float cost; + bool split_24; l_v1 = l_first->next; l_v2 = l_first->next->next; l_v3 = l_first->prev; l_v4 = l_first; - cost = BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0); + if (quad_method == MOD_TRIANGULATE_QUAD_SHORTEDGE) { + float d1, d2; + d1 = len_squared_v3v3(l_v4->v->co, l_v2->v->co); + d2 = len_squared_v3v3(l_v1->v->co, l_v3->v->co); + split_24 = ((d2 - d1) > 0.0f); + } + else { + /* first check if the quad is concave on either diagonal */ + const int flip_flag = is_quad_flip_v3(l_v1->v->co, l_v2->v->co, l_v3->v->co, l_v4->v->co); + if (UNLIKELY(flip_flag & (1 << 0))) { + split_24 = true; + } + else if (UNLIKELY(flip_flag & (1 << 1))) { + split_24 = false; + } + else { + split_24 = (BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) > 0.0f); + } + } - if (cost > 0.0f) { + /* named confusingly, l_v1 is in fact the second vertex */ + if (split_24) { l_v1 = l_v4; //l_v2 = l_v2; } |