[Bf-blender-cvs] [1cd65b274b6] master: BLI_math: add isect_tri_tri_v2, wrap via mathutils.geometry
Campbell Barton
noreply at git.blender.org
Sun Aug 11 13:57:02 CEST 2019
Commit: 1cd65b274b69990c36187148f873497f282cf5a9
Author: Campbell Barton
Date: Sat Aug 10 05:34:30 2019 +1000
Branches: master
https://developer.blender.org/rB1cd65b274b69990c36187148f873497f282cf5a9
BLI_math: add isect_tri_tri_v2, wrap via mathutils.geometry
===================================================================
M source/blender/blenlib/BLI_math_geom.h
M source/blender/blenlib/intern/math_geom.c
M source/blender/python/mathutils/mathutils_geometry.c
===================================================================
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,
More information about the Bf-blender-cvs
mailing list