[Bf-blender-cvs] [2d252b6d26f] blender-v2.92-release: Fix T85508: UV select overlap fails on identical faces

[Campbell Barton]

Commit: 2d252b6d26f90f81f2a2dc7a3031c407dc8a643c
Author: Campbell Barton
Date:   Thu Feb 11 08:27:47 2021 +1100
Branches: blender-v2.92-release
https://developer.blender.org/rB2d252b6d26f90f81f2a2dc7a3031c407dc8a643c

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.

===================================================================

M	source/blender/editors/uvedit/uvedit_select.c

===================================================================

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);
       }