Merge branch 'master' into blender2.8
authorCampbell Barton <ideasman42@gmail.com>
Sat, 12 Aug 2017 09:08:49 +0000 (19:08 +1000)
committerCampbell Barton <ideasman42@gmail.com>
Sat, 12 Aug 2017 09:08:49 +0000 (19:08 +1000)
source/blender/blenlib/BLI_math_geom.h
source/blender/blenlib/intern/math_geom.c
source/blender/bmesh/intern/bmesh_polygon_edgenet.c
source/blender/editors/interface/interface_layout.c

index f1d9c9571f207fad40a7207a6c3daae6c5b43c22..0fef849c8fac7a865223cefc12f662734cfb37c6 100644 (file)
@@ -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]);
index bfe1aefcbbd9538f8da6f118be0fce63e81d4c8c..53fcf9c745ce6c2e1103d0046c92fd969ce4e0d2 100644 (file)
@@ -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) \
index e515f9af63ff5bb0cb03189ca3673626e419ce8c..1b35f049838470082bff598f4fd47ad63a562755 100644 (file)
@@ -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},
index b80b85d0c27e47f3e524b698fe3a1ac32c81c855..393692e51c140517648700671950e8214619c50d 100644 (file)
@@ -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);