From 2d252b6d26f90f81f2a2dc7a3031c407dc8a643c Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 11 Feb 2021 08:27:47 +1100 Subject: Fix T85508: UV select overlap fails on identical faces The triangle overlap test failed for exactly overlapping triangles. When none of the segments intersect, testing a if a single corner is inside the other triangle fails when the triangles share UV coordinates. Resolve by comparing the triangle centers. --- source/blender/editors/uvedit/uvedit_select.c | 64 +++++++++++++++++++-------- 1 file changed, 46 insertions(+), 18 deletions(-) (limited to 'source/blender/editors') diff --git a/source/blender/editors/uvedit/uvedit_select.c b/source/blender/editors/uvedit/uvedit_select.c index 0bc1943802a..88802e0d868 100644 --- a/source/blender/editors/uvedit/uvedit_select.c +++ b/source/blender/editors/uvedit/uvedit_select.c @@ -3546,6 +3546,51 @@ struct UVOverlapData { float tri[3][2]; }; +/** + * Specialized 2D triangle intersection for detecting UV overlap: + * + * \return + * - false when single corners or edges touch (common for UV coordinates). + * - true when all corners touch (an exactly overlapping triangle). + */ +static bool overlap_tri_tri_uv_test(const float t1[3][2], + const float t2[3][2], + const float endpoint_bias) +{ + float vi[2]; + + /* Don't use 'isect_tri_tri_v2' here + * because it's important to ignore overlap at end-points. */ + if (isect_seg_seg_v2_point_ex(t1[0], t1[1], t2[0], t2[1], endpoint_bias, vi) == 1 || + isect_seg_seg_v2_point_ex(t1[0], t1[1], t2[1], t2[2], endpoint_bias, vi) == 1 || + isect_seg_seg_v2_point_ex(t1[0], t1[1], t2[2], t2[0], endpoint_bias, vi) == 1 || + isect_seg_seg_v2_point_ex(t1[1], t1[2], t2[0], t2[1], endpoint_bias, vi) == 1 || + isect_seg_seg_v2_point_ex(t1[1], t1[2], t2[1], t2[2], endpoint_bias, vi) == 1 || + isect_seg_seg_v2_point_ex(t1[1], t1[2], t2[2], t2[0], endpoint_bias, vi) == 1 || + isect_seg_seg_v2_point_ex(t1[2], t1[0], t2[0], t2[1], endpoint_bias, vi) == 1 || + isect_seg_seg_v2_point_ex(t1[2], t1[0], t2[1], t2[2], endpoint_bias, vi) == 1) { + return true; + } + + /* When none of the segments intersect, checking if either of the triangles corners + * is inside the others is almost always sufficient to test if the two triangles intersect. + * + * However, the `endpoint_bias` on segment intersections causes _exact_ overlapping + * triangles not to be detected. + * + * Resolve this problem at the small cost of calculating the triangle center, see T85508. */ + mid_v2_v2v2v2(vi, UNPACK3(t1)); + if (isect_point_tri_v2(vi, UNPACK3(t2)) != 0) { + return true; + } + mid_v2_v2v2v2(vi, UNPACK3(t2)); + if (isect_point_tri_v2(vi, UNPACK3(t1)) != 0) { + return true; + } + + return false; +} + static int uv_select_overlap(bContext *C, const bool extend) { Depsgraph *depsgraph = CTX_data_ensure_evaluated_depsgraph(C); @@ -3689,24 +3734,7 @@ static int uv_select_overlap(bContext *C, const bool extend) /* Main tri-tri overlap test. */ const float endpoint_bias = -1e-4f; - const float(*t1)[2] = o_a->tri; - const float(*t2)[2] = o_b->tri; - float vi[2]; - bool result = ( - /* Don't use 'isect_tri_tri_v2' here - * because it's important to ignore overlap at end-points. */ - isect_seg_seg_v2_point_ex(t1[0], t1[1], t2[0], t2[1], endpoint_bias, vi) == 1 || - isect_seg_seg_v2_point_ex(t1[0], t1[1], t2[1], t2[2], endpoint_bias, vi) == 1 || - isect_seg_seg_v2_point_ex(t1[0], t1[1], t2[2], t2[0], endpoint_bias, vi) == 1 || - isect_seg_seg_v2_point_ex(t1[1], t1[2], t2[0], t2[1], endpoint_bias, vi) == 1 || - isect_seg_seg_v2_point_ex(t1[1], t1[2], t2[1], t2[2], endpoint_bias, vi) == 1 || - isect_seg_seg_v2_point_ex(t1[1], t1[2], t2[2], t2[0], endpoint_bias, vi) == 1 || - isect_seg_seg_v2_point_ex(t1[2], t1[0], t2[0], t2[1], endpoint_bias, vi) == 1 || - isect_seg_seg_v2_point_ex(t1[2], t1[0], t2[1], t2[2], endpoint_bias, vi) == 1 || - isect_point_tri_v2(t1[0], t2[0], t2[1], t2[2]) != 0 || - isect_point_tri_v2(t2[0], t1[0], t1[1], t1[2]) != 0); - - if (result) { + if (overlap_tri_tri_uv_test(o_a->tri, o_b->tri, endpoint_bias)) { uvedit_face_select_enable(scene, em_a, face_a, false, cd_loop_uv_offset_a); uvedit_face_select_enable(scene, em_b, face_b, false, cd_loop_uv_offset_b); } -- cgit v1.2.3