diff options
author | Campbell Barton <ideasman42@gmail.com> | 2019-08-09 22:34:30 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2019-08-11 14:50:48 +0300 |
commit | 1cd65b274b69990c36187148f873497f282cf5a9 (patch) | |
tree | 91c0ddeeef74ab3177a0c2fcf58e9c3ec70ed770 /source/blender/blenlib/intern/math_geom.c | |
parent | c3a9fc5efb4a81f6efb28d0c787e17503deaee46 (diff) |
BLI_math: add isect_tri_tri_v2, wrap via mathutils.geometry
Diffstat (limited to 'source/blender/blenlib/intern/math_geom.c')
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 207 |
1 files changed, 207 insertions, 0 deletions
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" */ |