diff options
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_math_geom.h | 18 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 60 | ||||
-rw-r--r-- | source/blender/blenlib/intern/scanfill.c | 6 |
3 files changed, 81 insertions, 3 deletions
diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 9e65093a05f..5c1b6c8d774 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -329,6 +329,24 @@ float closest_to_line_segment_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2]); + +/** + * Finds the points where two line segments are closest to each other. + * + * `lambda_*` is a value between 0 and 1 for each segment that indicates where `r_closest_*` is on + * the corresponding segment. + * + * \return Squared distance between both segments. + */ +float closest_seg_seg_v2(float r_closest_a[2], + float r_closest_b[2], + float *r_lambda_a, + float *r_lambda_b, + const float a1[2], + const float a2[2], + const float b1[2], + const float b2[2]); + /** * Point closest to v1 on line v2-v3 in 3D. * diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 1b13493e00c..e7ccdeab80a 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -294,6 +294,66 @@ float dist_to_line_segment_v2(const float p[2], const float l1[2], const float l return sqrtf(dist_squared_to_line_segment_v2(p, l1, l2)); } +float closest_seg_seg_v2(float r_closest_a[2], + float r_closest_b[2], + float *r_lambda_a, + float *r_lambda_b, + const float a1[2], + const float a2[2], + const float b1[2], + const float b2[2]) +{ + if (isect_seg_seg_v2_simple(a1, a2, b1, b2)) { + float intersection[2]; + isect_line_line_v2_point(a1, a2, b1, b2, intersection); + copy_v2_v2(r_closest_a, intersection); + copy_v2_v2(r_closest_b, intersection); + float tmp[2]; + *r_lambda_a = closest_to_line_v2(tmp, intersection, a1, a2); + *r_lambda_b = closest_to_line_v2(tmp, intersection, b1, b2); + const float min_dist_sq = len_squared_v2v2(r_closest_a, r_closest_b); + return min_dist_sq; + } + + float p1[2], p2[2], p3[2], p4[2]; + const float lambda1 = closest_to_line_segment_v2(p1, a1, b1, b2); + const float lambda2 = closest_to_line_segment_v2(p2, a2, b1, b2); + const float lambda3 = closest_to_line_segment_v2(p3, b1, a1, a2); + const float lambda4 = closest_to_line_segment_v2(p4, b2, a1, a2); + const float dist_sq1 = len_squared_v2v2(p1, a1); + const float dist_sq2 = len_squared_v2v2(p2, a2); + const float dist_sq3 = len_squared_v2v2(p3, b1); + const float dist_sq4 = len_squared_v2v2(p4, b2); + + const float min_dist_sq = min_ffff(dist_sq1, dist_sq2, dist_sq3, dist_sq4); + if (min_dist_sq == dist_sq1) { + copy_v2_v2(r_closest_a, a1); + copy_v2_v2(r_closest_b, p1); + *r_lambda_a = 0.0f; + *r_lambda_b = lambda1; + } + else if (min_dist_sq == dist_sq2) { + copy_v2_v2(r_closest_a, a2); + copy_v2_v2(r_closest_b, p2); + *r_lambda_a = 1.0f; + *r_lambda_b = lambda2; + } + else if (min_dist_sq == dist_sq3) { + copy_v2_v2(r_closest_a, p3); + copy_v2_v2(r_closest_b, b1); + *r_lambda_a = lambda3; + *r_lambda_b = 0.0f; + } + else { + BLI_assert(min_dist_sq == dist_sq4); + copy_v2_v2(r_closest_a, p4); + copy_v2_v2(r_closest_b, b2); + *r_lambda_a = lambda4; + *r_lambda_b = 1.0f; + } + return min_dist_sq; +} + float closest_to_line_segment_v2(float r_close[2], const float p[2], const float l1[2], diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c index 32932c3dee1..bc07669687e 100644 --- a/source/blender/blenlib/intern/scanfill.c +++ b/source/blender/blenlib/intern/scanfill.c @@ -49,19 +49,19 @@ typedef struct ScanFillVertLink { #define SF_EPSILON 0.00003f #define SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON) -/* ScanFillVert.status */ +/** #ScanFillVert.status */ #define SF_VERT_NEW 0 /* all new verts have this flag set */ #define SF_VERT_AVAILABLE 1 /* available - in an edge */ #define SF_VERT_ZERO_LEN 2 -/* ScanFillEdge.status */ +/** #ScanFillEdge.status */ /* Optionally set ScanFillEdge f to this to mark original boundary edges. * Only needed if there are internal diagonal edges passed to BLI_scanfill_calc. */ #define SF_EDGE_NEW 0 /* all new edges have this flag set */ // #define SF_EDGE_BOUNDARY 1 /* UNUSED */ #define SF_EDGE_INTERNAL 2 /* edge is created while scan-filling */ -/* PolyFill.status */ +/** #PolyFill.status */ #define SF_POLY_NEW 0 /* all polys initialized to this */ #define SF_POLY_VALID 1 /* has at least 3 verts */ |