diff options
author | Campbell Barton <ideasman42@gmail.com> | 2014-03-27 04:48:18 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2014-03-27 04:48:18 +0400 |
commit | bec7c8c7aa951dd98ee4a7c14a434a4d0ac02688 (patch) | |
tree | f0e2f66ea384572440f87f25bf5d16007bb3b384 /source/blender | |
parent | 66671f1aaecdbab932cbdff8c5e527083f5d2bc1 (diff) |
BMesh: optimize BM_face_legal_splits for concave faces
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/BLI_math_geom.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 39 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 4 |
3 files changed, 43 insertions, 1 deletions
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index db71eeb8770..14357c06f78 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -73,6 +73,7 @@ float volume_tetrahedron_v3(const float v1[3], const float v2[3], const float v3 int is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3]); int is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2]); +int is_poly_convex_v2(const float verts[][2], unsigned int nr); /********************************* Distance **********************************/ diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 6a812814afe..ca9d3bb413f 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -3846,3 +3846,42 @@ int is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], c /* linetests, the 2 diagonals have to instersect to be convex */ return (isect_line_line_v2(v1, v3, v2, v4) > 0); } + +int is_poly_convex_v2(const float verts[][2], unsigned int nr) +{ + unsigned int sign_flag = 0; + unsigned int a; + const float *co_curr, *co_prev; + float dir_curr[2], dir_prev[2]; + + co_prev = verts[nr - 1]; + co_curr = verts[0]; + + sub_v2_v2v2(dir_prev, verts[nr - 2], co_prev); + + for (a = 0; a < nr; a++) { + float cross; + + sub_v2_v2v2(dir_curr, co_prev, co_curr); + + cross = cross_v2v2(dir_prev, dir_curr); + + if (cross < 0.0f) { + sign_flag |= 1; + } + else if (cross > 0.0f) { + sign_flag |= 2; + } + + if (sign_flag == (1 | 2)) { + return false; + } + + copy_v2_v2(dir_prev, dir_curr); + + co_prev = co_curr; + co_curr += 2; + } + + return true; +} diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 3093cba663f..867c54ad4b8 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -1064,7 +1064,9 @@ void BM_face_legal_splits(BMFace *f, BMLoop *(*loops)[2], int len) } /* first test for completely convex face */ - + if (is_poly_convex_v2((const float (*)[2])projverts, f->len)) { + return; + } for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) { out[0] = max_ff(out[0], projverts[i][0]); |