BLI_math: add isect_tri_tri_v2, wrap via mathutils.geometry

3 files changed, 254 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h
index 5ac4ce8be0b..b1437dbe140 100644
--- a/source/blender/blenlib/BLI_math_geom.h
+++ b/source/blender/blenlib/BLI_math_geom.h
@@ -390,6 +390,13 @@ bool isect_tri_tri_epsilon_v3(const float t_a0[3],
                               float r_i2[3],
                               const float epsilon);
 
+bool isect_tri_tri_v2(const float p1[2],
+                      const float q1[2],
+                      const float r1[2],
+                      const float p2[2],
+                      const float q2[2],
+                      const float r2[2]);
+
 /* water-tight raycast (requires pre-calculation) */
 struct IsectRayPrecalc {
   /* Maximal dimension kz, and orthogonal dimensions. */
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index b4a96ff316a..bb3d2786ca6 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -2346,6 +2346,213 @@ bool isect_tri_tri_epsilon_v3(const float t_a0[3],
   return false;
 }
 
+/* -------------------------------------------------------------------- */
+/** \name Tri-Tri Intersect 2D
+ *
+ * "Fast and Robust Triangle-Triangle Overlap Test
+ * Using Orientation Predicates" P. Guigue - O. Devillers
+ * Journal of Graphics Tools, 8(1), 2003.
+ *
+ * \{ */
+
+static bool isect_tri_tri_v2_impl_vert(const float t_a0[2],
+                                       const float t_a1[2],
+                                       const float t_a2[2],
+                                       const float t_b0[2],
+                                       const float t_b1[2],
+                                       const float t_b2[2])
+{
+  if (line_point_side_v2(t_b2, t_b0, t_a1) >= 0.0f) {
+    if (line_point_side_v2(t_b2, t_b1, t_a1) <= 0.0f) {
+      if (line_point_side_v2(t_a0, t_b0, t_a1) > 0.0f) {
+        if (line_point_side_v2(t_a0, t_b1, t_a1) <= 0.0f) {
+          return 1;
+        }
+        else {
+          return 0;
+        }
+      }
+      else {
+        if (line_point_side_v2(t_a0, t_b0, t_a2) >= 0.0f) {
+          if (line_point_side_v2(t_a1, t_a2, t_b0) >= 0.0f) {
+            return 1;
+          }
+          else {
+            return 0;
+          }
+        }
+        else {
+          return 0;
+        }
+      }
+    }
+    else if (line_point_side_v2(t_a0, t_b1, t_a1) <= 0.0f) {
+      if (line_point_side_v2(t_b2, t_b1, t_a2) <= 0.0f) {
+        if (line_point_side_v2(t_a1, t_a2, t_b1) >= 0.0f) {
+          return 1;
+        }
+        else {
+          return 0;
+        }
+      }
+      else {
+        return 0;
+      }
+    }
+    else {
+      return 0;
+    }
+  }
+  else if (line_point_side_v2(t_b2, t_b0, t_a2) >= 0.0f) {
+    if (line_point_side_v2(t_a1, t_a2, t_b2) >= 0.0f) {
+      if (line_point_side_v2(t_a0, t_b0, t_a2) >= 0.0f) {
+        return 1;
+      }
+      else {
+        return 0;
+      }
+    }
+    else if (line_point_side_v2(t_a1, t_a2, t_b1) >= 0.0f) {
+      if (line_point_side_v2(t_b2, t_a2, t_b1) >= 0.0f) {
+        return 1;
+      }
+      else {
+        return 0;
+      }
+    }
+    else {
+      return 0;
+    }
+  }
+  else {
+    return 0;
+  }
+}
+
+static bool isect_tri_tri_v2_impl_edge(const float t_a0[2],
+                                       const float t_a1[2],
+                                       const float t_a2[2],
+                                       const float t_b0[2],
+                                       const float t_b1[2],
+                                       const float t_b2[2])
+{
+  UNUSED_VARS(t_b1);
+
+  if (line_point_side_v2(t_b2, t_b0, t_a1) >= 0.0f) {
+    if (line_point_side_v2(t_a0, t_b0, t_a1) >= 0.0f) {
+      if (line_point_side_v2(t_a0, t_a1, t_b2) >= 0.0f) {
+        return 1;
+      }
+      else {
+        return 0;
+      }
+    }
+    else {
+      if (line_point_side_v2(t_a1, t_a2, t_b0) >= 0.0f) {
+        if (line_point_side_v2(t_a2, t_a0, t_b0) >= 0.0f) {
+          return 1;
+        }
+        else {
+          return 0;
+        }
+      }
+      else {
+        return 0;
+      }
+    }
+  }
+  else {
+    if (line_point_side_v2(t_b2, t_b0, t_a2) >= 0.0f) {
+      if (line_point_side_v2(t_a0, t_b0, t_a2) >= 0.0f) {
+        if (line_point_side_v2(t_a0, t_a2, t_b2) >= 0.0f) {
+          return 1;
+        }
+        else {
+          if (line_point_side_v2(t_a1, t_a2, t_b2) >= 0.0f) {
+            return 1;
+          }
+          else {
+            return 0;
+          }
+        }
+      }
+      else {
+        return 0;
+      }
+    }
+    else {
+      return 0;
+    }
+  }
+}
+
+static int isect_tri_tri_impl_ccw_v2(const float t_a0[2],
+                                     const float t_a1[2],
+                                     const float t_a2[2],
+                                     const float t_b0[2],
+                                     const float t_b1[2],
+                                     const float t_b2[2])
+{
+  if (line_point_side_v2(t_b0, t_b1, t_a0) >= 0.0f) {
+    if (line_point_side_v2(t_b1, t_b2, t_a0) >= 0.0f) {
+      if (line_point_side_v2(t_b2, t_b0, t_a0) >= 0.0f) {
+        return 1;
+      }
+      else {
+        return isect_tri_tri_v2_impl_edge(t_a0, t_a1, t_a2, t_b0, t_b1, t_b2);
+      }
+    }
+    else {
+      if (line_point_side_v2(t_b2, t_b0, t_a0) >= 0.0f) {
+        return isect_tri_tri_v2_impl_edge(t_a0, t_a1, t_a2, t_b2, t_b0, t_b1);
+      }
+      else {
+        return isect_tri_tri_v2_impl_vert(t_a0, t_a1, t_a2, t_b0, t_b1, t_b2);
+      }
+    }
+  }
+  else {
+    if (line_point_side_v2(t_b1, t_b2, t_a0) >= 0.0f) {
+      if (line_point_side_v2(t_b2, t_b0, t_a0) >= 0.0f) {
+        return isect_tri_tri_v2_impl_edge(t_a0, t_a1, t_a2, t_b1, t_b2, t_b0);
+      }
+      else {
+        return isect_tri_tri_v2_impl_vert(t_a0, t_a1, t_a2, t_b1, t_b2, t_b0);
+      }
+    }
+    else {
+      return isect_tri_tri_v2_impl_vert(t_a0, t_a1, t_a2, t_b2, t_b0, t_b1);
+    }
+  }
+}
+
+bool isect_tri_tri_v2(const float t_a0[2],
+                      const float t_a1[2],
+                      const float t_a2[2],
+                      const float t_b0[2],
+                      const float t_b1[2],
+                      const float t_b2[2])
+{
+  if (line_point_side_v2(t_a0, t_a1, t_a2) < 0.0f) {
+    if (line_point_side_v2(t_b0, t_b1, t_b2) < 0.0f) {
+      return isect_tri_tri_impl_ccw_v2(t_a0, t_a2, t_a1, t_b0, t_b2, t_b1);
+    }
+    else {
+      return isect_tri_tri_impl_ccw_v2(t_a0, t_a2, t_a1, t_b0, t_b1, t_b2);
+    }
+  }
+  else {
+    if (line_point_side_v2(t_b0, t_b1, t_b2) < 0.0f) {
+      return isect_tri_tri_impl_ccw_v2(t_a0, t_a1, t_a2, t_b0, t_b2, t_b1);
+    }
+    else {
+      return isect_tri_tri_impl_ccw_v2(t_a0, t_a1, t_a2, t_b0, t_b1, t_b2);
+    }
+  }
+}
+
+/** \} */
+
 /* Adapted from the paper by Kasper Fauerby */
 
 /* "Improved Collision detection and Response" */
diff --git a/source/blender/python/mathutils/mathutils_geometry.c b/source/blender/python/mathutils/mathutils_geometry.c
index d4f56490627..32ce78f702d 100644
--- a/source/blender/python/mathutils/mathutils_geometry.c
+++ b/source/blender/python/mathutils/mathutils_geometry.c
@@ -283,6 +283,42 @@ static PyObject *M_Geometry_intersect_sphere_sphere_2d(PyObject *UNUSED(self), P
   return ret;
 }
 
+PyDoc_STRVAR(M_Geometry_intersect_tri_tri_2d_doc,
+             ".. function:: intersect_tri_tri_2d(tri_a1, tri_a2, tri_a3, tri_b1, tri_b2, tri_b3)\n"
+             "\n"
+             "   Check if two 2D triangles intersect.\n"
+             "\n"
+             "   :rtype: bool\n");
+static PyObject *M_Geometry_intersect_tri_tri_2d(PyObject *UNUSED(self), PyObject *args)
+{
+  const char *error_prefix = "intersect_tri_tri_2d";
+  PyObject *tri_pair_py[2][3];
+  float tri_pair[2][3][2];
+
+  if (!PyArg_ParseTuple(args,
+                        "OOOOOO:intersect_tri_tri_2d",
+                        &tri_pair_py[0][0],
+                        &tri_pair_py[0][1],
+                        &tri_pair_py[0][2],
+                        &tri_pair_py[1][0],
+                        &tri_pair_py[1][1],
+                        &tri_pair_py[1][2])) {
+    return NULL;
+  }
+
+  for (int i = 0; i < 2; i++) {
+    for (int j = 0; j < 3; j++) {
+      if (mathutils_array_parse(
+              tri_pair[i][j], 2, 2 | MU_ARRAY_SPILL, tri_pair_py[i][j], error_prefix) == -1) {
+        return NULL;
+      }
+    }
+  }
+
+  bool ret = isect_tri_tri_v2(UNPACK3(tri_pair[0]), UNPACK3(tri_pair[1]));
+  return PyBool_FromLong(ret);
+}
+
 PyDoc_STRVAR(M_Geometry_normal_doc,
              ".. function:: normal(vectors)\n"
              "\n"
@@ -1526,6 +1562,10 @@ static PyMethodDef M_Geometry_methods[] = {
      (PyCFunction)M_Geometry_intersect_sphere_sphere_2d,
      METH_VARARGS,
      M_Geometry_intersect_sphere_sphere_2d_doc},
+    {"intersect_tri_tri_2d",
+     (PyCFunction)M_Geometry_intersect_tri_tri_2d,
+     METH_VARARGS,
+     M_Geometry_intersect_tri_tri_2d_doc},
     {"area_tri", (PyCFunction)M_Geometry_area_tri, METH_VARARGS, M_Geometry_area_tri_doc},
     {"volume_tetrahedron",
      (PyCFunction)M_Geometry_volume_tetrahedron,