From 6f935dbb38818e79006c2209821869d54bb1643f Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 12 Aug 2017 18:12:29 +1000 Subject: Math Lib: add isect_seg_seg_v2_point_ex This exposes end-point bias argument, needed in rare cases. --- source/blender/blenlib/BLI_math_geom.h | 10 ++++++-- source/blender/blenlib/intern/math_geom.c | 40 +++++++++++++++++++++++-------- 2 files changed, 38 insertions(+), 12 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) \ -- cgit v1.2.3