Commit: c0340ec89393055bbb0ba0432b9edb5d70b3711c Author: Germano Cavalcante Date: Mon Aug 10 12:05:37 2020 -0300 Branches: blender-v2.90-release https://developer.blender.org/rBc0340ec89393055bbb0ba0432b9edb5d70b3711c
Fix T78113: Random explosions of cloth with self collision The problem is caused by a lack of prediction in the `isect_line_segment_tri_v3` that incorrectly confirms some intersections of coplanar segments to the triangle. The solution is to use another algorithm to detect intersections. This also resulted in a slight improvement in the performance: - 1min 17sec to 1min 6sec in my test file Differential Revision: https://developer.blender.org/D8500 =================================================================== M source/blender/blenkernel/intern/collision.c M source/blender/blenkernel/intern/editmesh_bvh.c M source/blender/blenlib/BLI_math_geom.h M source/blender/blenlib/intern/math_geom.c M source/blender/draw/intern/draw_cache_extract_mesh.c M source/blender/python/mathutils/mathutils_bvhtree.c =================================================================== diff --git a/source/blender/blenkernel/intern/collision.c b/source/blender/blenkernel/intern/collision.c index 31d49dd4508..f358355912b 100644 --- a/source/blender/blenkernel/intern/collision.c +++ b/source/blender/blenkernel/intern/collision.c @@ -212,7 +212,6 @@ static float compute_collision_point_tri_tri(const float a1[3], float dist = FLT_MAX; float tmp_co1[3], tmp_co2[3]; float isect_a[3], isect_b[3]; - int isect_count = 0; float tmp, tmp_vec[3]; float normal[3], cent[3]; bool backside = false; @@ -226,38 +225,16 @@ static float compute_collision_point_tri_tri(const float a1[3], copy_v3_v3(b[2], b3); /* Find intersections. */ - for (int i = 0; i < 3; i++) { - if (isect_line_segment_tri_v3(a[i], a[next_ind(i)], b[0], b[1], b[2], &tmp, NULL)) { - interp_v3_v3v3(isect_a, a[i], a[next_ind(i)], tmp); - isect_count++; - } - } - - if (isect_count == 0) { - for (int i = 0; i < 3; i++) { - if (isect_line_segment_tri_v3(b[i], b[next_ind(i)], a[0], a[1], a[2], &tmp, NULL)) { - isect_count++; - } - } - } - else if (isect_count == 1) { - for (int i = 0; i < 3; i++) { - if (isect_line_segment_tri_v3(b[i], b[next_ind(i)], a[0], a[1], a[2], &tmp, NULL)) { - interp_v3_v3v3(isect_b, b[i], b[next_ind(i)], tmp); - break; - } - } - } + int tri_a_edge_isect_count; + const bool is_intersecting = isect_tri_tri_v3_ex( + a, b, isect_a, isect_b, &tri_a_edge_isect_count); /* Determine collision side. */ if (culling) { normal_tri_v3(normal, b[0], b[1], b[2]); mid_v3_v3v3v3(cent, b[0], b[1], b[2]); - if (isect_count == 2) { - backside = true; - } - else if (isect_count == 0) { + if (!is_intersecting) { for (int i = 0; i < 3; i++) { sub_v3_v3v3(tmp_vec, a[i], cent); if (dot_v3v3(tmp_vec, normal) < 0.0f) { @@ -266,12 +243,16 @@ static float compute_collision_point_tri_tri(const float a1[3], } } } + else if (tri_a_edge_isect_count != 1) { + /* It is not Edge intersection. */ + backside = true; + } } else if (use_normal) { normal_tri_v3(normal, b[0], b[1], b[2]); } - if (isect_count == 1) { + if (tri_a_edge_isect_count == 1) { /* Edge intersection. */ copy_v3_v3(r_a, isect_a); copy_v3_v3(r_b, isect_b); @@ -383,7 +364,7 @@ static float compute_collision_point_tri_tri(const float a1[3], } /* Closest edge. */ - if (isect_count == 0) { + if (!is_intersecting) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { isect_seg_seg_v3(a[i], a[next_ind(i)], b[j], b[next_ind(j)], tmp_co1, tmp_co2); @@ -398,7 +379,7 @@ static float compute_collision_point_tri_tri(const float a1[3], } } - if (isect_count == 0) { + if (!is_intersecting) { sub_v3_v3v3(r_vec, r_a, r_b); dist = sqrtf(dist); } diff --git a/source/blender/blenkernel/intern/editmesh_bvh.c b/source/blender/blenkernel/intern/editmesh_bvh.c index 72793919570..dc194f0077c 100644 --- a/source/blender/blenkernel/intern/editmesh_bvh.c +++ b/source/blender/blenkernel/intern/editmesh_bvh.c @@ -563,8 +563,7 @@ static bool bmbvh_overlap_cb(void *userdata, int index_a, int index_b, int UNUSE } } - return (isect_tri_tri_epsilon_v3( - UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1], data->epsilon) && + return (isect_tri_tri_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1]) && /* if we share a vertex, check the intersection isn't a 'point' */ ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon))); } diff --git a/source/blender/blenlib/BLI_math_geom.h b/source/blender/blenlib/BLI_math_geom.h index 3d1edb9c3b1..213f5a029b0 100644 --- a/source/blender/blenlib/BLI_math_geom.h +++ b/source/blender/blenlib/BLI_math_geom.h @@ -402,15 +402,19 @@ bool isect_ray_tri_epsilon_v3(const float ray_origin[3], float *r_lambda, float r_uv[2], const float epsilon); -bool isect_tri_tri_epsilon_v3(const float t_a0[3], - const float t_a1[3], - const float t_a2[3], - const float t_b0[3], - const float t_b1[3], - const float t_b2[3], - float r_i1[3], - float r_i2[3], - const float epsilon); +bool isect_tri_tri_v3_ex(const float tri_a[3][3], + const float tri_b[3][3], + float r_i1[3], + float r_i2[3], + int *r_tri_a_edge_isect_count); +bool isect_tri_tri_v3(const float t_a0[3], + const float t_a1[3], + const float t_a2[3], + const float t_b0[3], + const float t_b1[3], + const float t_b2[3], + float r_i1[3], + float r_i2[3]); bool isect_tri_tri_v2(const float p1[2], const float q1[2], diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 7c187679ad1..83750277bf6 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -2311,109 +2311,171 @@ bool isect_plane_plane_v3(const float plane_a[4], /** * Intersect two triangles. * - * \param r_i1, r_i2: Optional arguments to retrieve the overlapping edge between the 2 triangles. + * \param r_i1, r_i2: Retrieve the overlapping edge between the 2 triangles. + * \param r_tri_a_edge_isect_count: Indicates how many edges in the first triangle are intersected. * \return true when the triangles intersect. * + * \note If it exists, \a r_i1 will be a point on the edge of the 1st triangle. * \note intersections between coplanar triangles are currently undetected. */ -bool isect_tri_tri_epsilon_v3(const float t_a0[3], - const float t_a1[3], - const float t_a2[3], - const float t_b0[3], - const float t_b1[3], - const float t_b2[3], - float r_i1[3], - float r_i2[3], - const float epsilon) -{ - const float *tri_pair[2][3] = {{t_a0, t_a1, t_a2}, {t_b0, t_b1, t_b2}}; - float plane_a[4], plane_b[4]; - float plane_co[3], plane_no[3]; - - BLI_assert((r_i1 != NULL) == (r_i2 != NULL)); +bool isect_tri_tri_v3_ex(const float tri_a[3][3], + const float tri_b[3][3], + float r_i1[3], + float r_i2[3], + int *r_tri_a_edge_isect_count) +{ + struct { + /* Factor that indicates the position of the intersection point on the line + * that intersects the planes of the triangles. */ + float min, max; + /* Intersection point location. */ + float loc[2][3]; + } range[2]; + + float side[2][3]; + float ba[3], bc[3], plane_a[4], plane_b[4]; + *r_tri_a_edge_isect_count = 0; + + sub_v3_v3v3(ba, tri_a[0], tri_a[1]); + sub_v3_v3v3(bc, tri_a[2], tri_a[1]); + cross_v3_v3v3(plane_a, ba, bc); + plane_a[3] = -dot_v3v3(tri_a[1], plane_a); + side[1][0] = plane_point_side_v3(plane_a, tri_b[0]); + side[1][1] = plane_point_side_v3(plane_a, tri_b[1]); + side[1][2] = plane_point_side_v3(plane_a, tri_b[2]); + + if (!side[1][0] && !side[1][1] && !side[1][2]) { + /* Coplanar case is not supported. */ + return false; + } - /* normalizing is needed for small triangles T46007 */ - normal_tri_v3(plane_a, UNPACK3(tri_pair[0])); - normal_tri_v3(plane_b, UNPACK3(tri_pair[1])); + if ((side[1][0] && side[1][1] && side[1][2]) && (side[1][0] < 0.0f) == (side[1][1] < 0.0f) && + (side[1][0] < 0.0f) == (side[1][2] < 0.0f)) { + /* All vertices of the 2nd triangle are positioned on the same side to the + * plane defined by the 1st triangle. */ + return false; + } - plane_a[3] = -dot_v3v3(plane_a, t_a0); - plane_b[3] = -dot_v3v3(plane_b, t_b0); + sub_v3_v3v3(ba, tri_b[0], tri_b[1]); + sub_v3_v3v3(bc, tri_b[2], tri_b[1]); + cross_v3_v3v3(plane_b, ba, bc); + plane_b[3] = -dot_v3v3(tri_b[1], plane_b); + side[0][0] = plane_point_side_v3(plane_b, tri_a[0]); + side[0][1] = plane_point_side_v3(plane_b, tri_a[1]); + side[0][2] = plane_point_side_v3(plane_b, tri_a[2]); + if ((side[0][0] && side[0][1] && side[0][2]) && (side[0][0] < 0.0f) == (side[0][1] < 0.0f) && + (side[0][0] < 0.0f) == (side[0][2] < 0.0f)) { + /* All vertices of the 1st triangle are positioned on the same side to the + * plane defined by the 2nd triangle. */ + return false; + } - if (isect_plane_plane_v3(plane_a, plane_b, plane_co, plane_no) && - (normalize_v3(plane_no) > epsilon)) { - /** - * Implementation note: its simpler to project the triangles onto the intersection plane - * before intersecting their edges with the ray, defined by 'isect_plane_plane_v3'. - * This way we can use 'line_point_factor_v3_ex' to see if an edge crosses 'co_proj', - * then use the factor to calculate the world-space point. - */ - struct { - float min, max; - } range[2] = {{FLT_MAX, -FLT_MAX}, {FLT_MAX, -FLT_MAX}}; - int t; - float co_proj[3]; - - closest_to_plane3_normalized_v3(co_proj, plane_no, plane_co); - - /* For both triangles, find the overlap with the line defined by the ray [co_proj, plane_no]. - * When the ranges overlap we know the triangles do too. */ - for (t = 0; t < 2; t++) { - int j, j_prev; - float tri_proj[3][3]; - - closest_to_plane3_normalized_v3(tri_proj[0], plane_no, tri_pair[t][0]); - closest_to_plane3_normalized_v3(tri_proj[1], plane_no, tri_pair[t][1]); - closest_to_plane3_normalized_v3(tri_proj[2], plane_no, tri_pair[t][2]); - - for (j = 0, j_prev = 2; j < 3; j_prev = j++) { - /* note that its important to have a very small nonze @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list [email protected] https://lists.blender.org/mailman/listinfo/bf-blender-cvs
