diff options
author | Campbell Barton <ideasman42@gmail.com> | 2017-08-12 12:08:49 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2017-08-12 12:08:49 +0300 |
commit | 673c9dce0850f2e6a13570ade132024c34bdb11c (patch) | |
tree | c86bfd2b4189b487f29ed91b0630e9a214c5b5b3 /source/blender | |
parent | ac17f29b2fc6dabd182613f89974b9e262ed30e5 (diff) | |
parent | a4bcdf5fb1a7afc85b464c35b359e627907db2e0 (diff) |
Merge branch 'master' into blender2.8
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/BLI_math_geom.h | 10 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 40 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon_edgenet.c | 69 | ||||
-rw-r--r-- | source/blender/editors/interface/interface_layout.c | 3 |
4 files changed, 88 insertions, 34 deletions
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index f1d9c9571f2..0fef849c8fa 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -166,8 +166,14 @@ void limit_dist_v3(float v1[3], float v2[3], const float dist); int isect_seg_seg_v2(const float a1[2], const float a2[2], const float b1[2], const float b2[2]); int isect_seg_seg_v2_int(const int a1[2], const int a2[2], const int b1[2], const int b2[2]); -int isect_seg_seg_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float vi[2]); -bool isect_seg_seg_v2_simple(const float v1[2], const float v2[2], const float v3[2], const float v4[2]); +int isect_seg_seg_v2_point_ex( + const float v0[2], const float v1[2], const float v2[2], const float v3[2], const float endpoint_bias, + float vi[2]); +int isect_seg_seg_v2_point( + const float v0[2], const float v1[2], const float v2[2], const float v3[2], + float vi[2]); +bool isect_seg_seg_v2_simple( + const float v1[2], const float v2[2], const float v3[2], const float v4[2]); int isect_line_sphere_v3(const float l1[3], const float l2[3], const float sp[3], const float r, float r_p1[3], float r_p2[3]); int isect_line_sphere_v2(const float l1[2], const float l2[2], const float sp[2], const float r, float r_p1[2], float r_p2[2]); diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index bfe1aefcbbd..53fcf9c745c 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -765,18 +765,29 @@ int isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], co return ISECT_LINE_LINE_NONE; } -/* get intersection point of two 2D segments and return intersection type: - * -1: collinear - * 1: intersection +/** + * Get intersection point of two 2D segments. + * + * \param endpoint_bias: Bias to use when testing for end-point overlap. + * A positive value considers intersections that extend past the endpoints, + * negative values contract the endpoints. + * Note the bias is applied to a 0-1 factor, not scaled to the length of segments. + * + * \returns intersection type: + * - -1: collinear. + * - 1: intersection. + * - 0: no intersection. */ -int isect_seg_seg_v2_point( +int isect_seg_seg_v2_point_ex( const float v0[2], const float v1[2], const float v2[2], const float v3[2], + const float endpoint_bias, float r_vi[2]) { float s10[2], s32[2], s30[2], d; const float eps = 1e-6f; - const float eps_sq = eps * eps; + const float endpoint_min = -endpoint_bias; + const float endpoint_max = endpoint_bias + 1.0f; sub_v2_v2v2(s10, v1, v0); sub_v2_v2v2(s32, v3, v2); @@ -790,8 +801,8 @@ int isect_seg_seg_v2_point( u = cross_v2v2(s30, s32) / d; v = cross_v2v2(s10, s30) / d; - if ((u >= -eps && u <= 1.0f + eps) && - (v >= -eps && v <= 1.0f + eps)) + if ((u >= endpoint_min && u <= endpoint_max) && + (v >= endpoint_min && v <= endpoint_max)) { /* intersection */ float vi_test[2]; @@ -810,7 +821,7 @@ int isect_seg_seg_v2_point( sub_v2_v2v2(s_vi_v2, vi_test, v2); v = (dot_v2v2(s32, s_vi_v2) / dot_v2v2(s32, s32)); #endif - if (v >= -eps && v <= 1.0f + eps) { + if (v >= endpoint_min && v <= endpoint_max) { copy_v2_v2(r_vi, vi_test); return 1; } @@ -828,7 +839,7 @@ int isect_seg_seg_v2_point( float u_a, u_b; if (equals_v2v2(v0, v1)) { - if (len_squared_v2v2(v2, v3) > eps_sq) { + if (len_squared_v2v2(v2, v3) > SQUARE(eps)) { /* use non-point segment as basis */ SWAP(const float *, v0, v2); SWAP(const float *, v1, v3); @@ -855,7 +866,7 @@ int isect_seg_seg_v2_point( if (u_a > u_b) SWAP(float, u_a, u_b); - if (u_a > 1.0f + eps || u_b < -eps) { + if (u_a > endpoint_max || u_b < endpoint_min) { /* non-overlapping segments */ return -1; } @@ -871,6 +882,15 @@ int isect_seg_seg_v2_point( } } +int isect_seg_seg_v2_point( + const float v0[2], const float v1[2], + const float v2[2], const float v3[2], + float r_vi[2]) +{ + const float endpoint_bias = 1e-6f; + return isect_seg_seg_v2_point_ex(v0, v1, v2, v3, endpoint_bias, r_vi); +} + bool isect_seg_seg_v2_simple(const float v1[2], const float v2[2], const float v3[2], const float v4[2]) { #define CCW(A, B, C) \ diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c index e515f9af63f..1b35f049838 100644 --- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c +++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c @@ -725,10 +725,30 @@ BLI_INLINE bool edge_isect_verts_point_2d( const BMEdge *e, const BMVert *v_a, const BMVert *v_b, float r_isect[2]) { - return ((isect_seg_seg_v2_point(v_a->co, v_b->co, e->v1->co, e->v2->co, r_isect) == 1) && + /* This bias seems like it could be too large, + * mostly its not needed, see T52329 for example where it is. */ + const float endpoint_bias = 1e-4f; + return ((isect_seg_seg_v2_point_ex(v_a->co, v_b->co, e->v1->co, e->v2->co, endpoint_bias, r_isect) == 1) && ((e->v1 != v_a) && (e->v2 != v_a) && (e->v1 != v_b) && (e->v2 != v_b))); } +BLI_INLINE int axis_pt_cmp(const float pt_a[2], const float pt_b[2]) +{ + if (pt_a[0] < pt_b[0]) { + return -1; + } + if (pt_a[0] > pt_b[0]) { + return 1; + } + if (pt_a[1] < pt_b[1]) { + return -1; + } + if (pt_a[1] > pt_b[1]) { + return 1; + } + return 0; +} + /** * Represents isolated edge-links, * each island owns contiguous slices of the vert array. @@ -749,7 +769,8 @@ struct EdgeGroupIsland { struct { BMVert *min, *max; /* used for sorting only */ - float min_axis; + float min_axis[2]; + float max_axis[2]; } vert_span; }; @@ -758,12 +779,11 @@ static int group_min_cmp_fn(const void *p1, const void *p2) const struct EdgeGroupIsland *g1 = *(struct EdgeGroupIsland **)p1; const struct EdgeGroupIsland *g2 = *(struct EdgeGroupIsland **)p2; /* min->co[SORT_AXIS] hasn't been applied yet */ - const float f1 = g1->vert_span.min_axis; - const float f2 = g2->vert_span.min_axis; - - if (f1 < f2) return -1; - if (f1 > f2) return 1; - else return 0; + int test = axis_pt_cmp(g1->vert_span.min_axis, g2->vert_span.min_axis); + if (UNLIKELY(test == 0)) { + test = axis_pt_cmp(g1->vert_span.max_axis, g2->vert_span.max_axis); + } + return test; } struct Edges_VertVert_BVHTreeTest { @@ -993,8 +1013,8 @@ static int bm_face_split_edgenet_find_connection( for (int j = 0; j < 2; j++) { BMVert *v_iter = v_pair[j]; if (BM_elem_flag_test(v_iter, VERT_IS_VALID)) { - if (direction_sign ? (v_iter->co[SORT_AXIS] >= v_origin->co[SORT_AXIS]) : - (v_iter->co[SORT_AXIS] <= v_origin->co[SORT_AXIS])) + if (direction_sign ? (v_iter->co[SORT_AXIS] > v_origin->co[SORT_AXIS]) : + (v_iter->co[SORT_AXIS] < v_origin->co[SORT_AXIS])) { BLI_SMALLSTACK_PUSH(vert_search, v_iter); BLI_SMALLSTACK_PUSH(vert_blacklist, v_iter); @@ -1360,8 +1380,8 @@ bool BM_face_split_edgenet_connect_islands( /* init with *any* different verts */ g->vert_span.min = ((BMEdge *)edge_links->link)->v1; g->vert_span.max = ((BMEdge *)edge_links->link)->v2; - float min_axis = FLT_MAX; - float max_axis = -FLT_MAX; + float min_axis[2] = {FLT_MAX, FLT_MAX}; + float max_axis[2] = {-FLT_MAX, -FLT_MAX}; do { BMEdge *e = edge_links->link; @@ -1372,24 +1392,29 @@ bool BM_face_split_edgenet_connect_islands( BLI_assert(v_iter->head.htype == BM_VERT); /* ideally we could use 'v_iter->co[SORT_AXIS]' here, * but we need to sort the groups before setting the vertex array order */ + const float axis_value[2] = { #if SORT_AXIS == 0 - const float axis_value = dot_m3_v3_row_x(axis_mat, v_iter->co); + dot_m3_v3_row_x(axis_mat, v_iter->co), + dot_m3_v3_row_y(axis_mat, v_iter->co), #else - const float axis_value = dot_m3_v3_row_y(axis_mat, v_iter->co); + dot_m3_v3_row_y(axis_mat, v_iter->co), + dot_m3_v3_row_x(axis_mat, v_iter->co), #endif + }; - if (axis_value < min_axis) { + if (axis_pt_cmp(axis_value, min_axis) == -1) { g->vert_span.min = v_iter; - min_axis = axis_value; + copy_v2_v2(min_axis, axis_value); } - if (axis_value > max_axis ) { + if (axis_pt_cmp(axis_value, max_axis) == 1) { g->vert_span.max = v_iter; - max_axis = axis_value; + copy_v2_v2(max_axis, axis_value); } } } while ((edge_links = edge_links->next)); - g->vert_span.min_axis = min_axis; + copy_v2_v2(g->vert_span.min_axis, min_axis); + copy_v2_v2(g->vert_span.max_axis, max_axis); g->has_prev_edge = false; @@ -1449,8 +1474,10 @@ bool BM_face_split_edgenet_connect_islands( bm->elem_index_dirty |= BM_VERT; - /* Now create bvh tree*/ - BVHTree *bvhtree = BLI_bvhtree_new(edge_arr_len, 0.0f, 8, 8); + /* Now create bvh tree + * + * Note that a large epsilon is used because meshes with dimensions of around 100+ need it. see T52329. */ + BVHTree *bvhtree = BLI_bvhtree_new(edge_arr_len, 1e-4f, 8, 8); for (uint i = 0; i < edge_arr_len; i++) { const float e_cos[2][3] = { {UNPACK2(edge_arr[i]->v1->co), 0.0f}, diff --git a/source/blender/editors/interface/interface_layout.c b/source/blender/editors/interface/interface_layout.c index b80b85d0c27..393692e51c1 100644 --- a/source/blender/editors/interface/interface_layout.c +++ b/source/blender/editors/interface/interface_layout.c @@ -3328,8 +3328,9 @@ void ui_layout_add_but(uiLayout *layout, uiBut *but) ui_item_size((uiItem *)bitem, &w, &h); /* XXX uiBut hasn't scaled yet * we can flag the button as not expandable, depending on its size */ - if (w <= 2 * UI_UNIT_X) + if (w <= 2 * UI_UNIT_X && (!but->str || but->str[0] == '\0')) { bitem->item.flag |= UI_ITEM_MIN; + } BLI_addtail(&layout->items, bitem); |