Fix T65568: sewing and self collision issue

As explained in T65568 by @LucaRood, the self collision system should exclude triangles that are connected by sewing springs.

Differential Revision: https://developer.blender.org/D6911

5 files changed, 106 insertions, 15 deletions

diff --git a/source/blender/blenkernel/BKE_cloth.h b/source/blender/blenkernel/BKE_cloth.h
index 039104cf377..883f4a137e7 100644
--- a/source/blender/blenkernel/BKE_cloth.h
+++ b/source/blender/blenkernel/BKE_cloth.h
@@ -32,6 +32,7 @@ struct Depsgraph;
 struct Mesh;
 struct Object;
 struct Scene;
+struct GHash;
 
 #define DO_INLINE MALWAYS_INLINE
 
@@ -44,8 +45,8 @@ struct Scene;
 
 /* Bits to or into the ClothVertex.flags. */
 typedef enum eClothVertexFlag {
-  CLOTH_VERT_FLAG_PINNED = 1,
-  CLOTH_VERT_FLAG_NOSELFCOLL = 2, /* vertex NOT used for self collisions */
+  CLOTH_VERT_FLAG_PINNED = (1 << 0),
+  CLOTH_VERT_FLAG_NOSELFCOLL = (1 << 1), /* vertex NOT used for self collisions */
 } eClothVertexFlag;
 
 typedef struct ClothHairData {
@@ -88,8 +89,9 @@ typedef struct Cloth {
   struct Implicit_Data *implicit; /* our implicit solver connects to this pointer */
   struct EdgeSet *edgeset;        /* used for selfcollisions */
   int last_frame;
-  float initial_mesh_volume; /* Initial volume of the mesh. Used for pressure */
-  struct MEdge *edges;       /* Used for hair collisions. */
+  float initial_mesh_volume;    /* Initial volume of the mesh. Used for pressure */
+  struct MEdge *edges;          /* Used for hair collisions. */
+  struct GHash *sew_edge_graph; /* Sewing edges represented using a GHash */
 } Cloth;
 
 /**
diff --git a/source/blender/blenkernel/intern/cloth.c b/source/blender/blenkernel/intern/cloth.c
index 45b3148c656..cd849f89f53 100644
--- a/source/blender/blenkernel/intern/cloth.c
+++ b/source/blender/blenkernel/intern/cloth.c
@@ -34,6 +34,7 @@
 #include "BLI_rand.h"
 #include "BLI_edgehash.h"
 #include "BLI_linklist.h"
+#include "BLI_ghash.h"
 
 #include "DEG_depsgraph.h"
 #include "DEG_depsgraph_query.h"
@@ -583,6 +584,11 @@ void cloth_free_modifier(ClothModifierData *clmd)
       BLI_edgeset_free(cloth->edgeset);
     }
 
+    if (cloth->sew_edge_graph) {
+      BLI_ghash_free(cloth->sew_edge_graph, MEM_freeN, NULL);
+      cloth->sew_edge_graph = NULL;
+    }
+
 #if 0
     if (clmd->clothObject->facemarks) {
       MEM_freeN(clmd->clothObject->facemarks);
@@ -660,6 +666,11 @@ void cloth_free_modifier_extern(ClothModifierData *clmd)
       BLI_edgeset_free(cloth->edgeset);
     }
 
+    if (cloth->sew_edge_graph) {
+      BLI_ghash_free(cloth->sew_edge_graph, MEM_freeN, NULL);
+      cloth->sew_edge_graph = NULL;
+    }
+
 #if 0
     if (clmd->clothObject->facemarks) {
       MEM_freeN(clmd->clothObject->facemarks);
@@ -845,6 +856,8 @@ static int cloth_from_object(
   clmd->clothObject->springs = NULL;
   clmd->clothObject->numsprings = -1;
 
+  clmd->clothObject->sew_edge_graph = NULL;
+
   if (clmd->sim_parms->shapekey_rest &&
       !(clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_DYNAMIC_BASEMESH)) {
     shapekey_rest = CustomData_get_layer(&mesh->vdata, CD_CLOTH_ORCO);
@@ -1644,6 +1657,13 @@ static int cloth_build_springs(ClothModifierData *clmd, Mesh *mesh)
     cloth->verts[i].avg_spring_len = 0.0f;
   }
 
+  if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW) {
+    /* cloth->sew_edge_graph should not exist before this */
+    BLI_assert(cloth->sew_edge_graph == NULL);
+    cloth->sew_edge_graph = BLI_ghash_new(
+        BLI_ghashutil_inthash_v2_p, BLI_ghashutil_inthash_v2_cmp, "cloth_sewing_edges_graph");
+  }
+
   /* Structural springs. */
   for (int i = 0; i < numedges; i++) {
     spring = (ClothSpring *)MEM_callocN(sizeof(ClothSpring), "cloth spring");
@@ -1655,6 +1675,19 @@ static int cloth_build_springs(ClothModifierData *clmd, Mesh *mesh)
         spring->restlen = 0.0f;
         spring->lin_stiffness = 1.0f;
         spring->type = CLOTH_SPRING_TYPE_SEWING;
+
+        /* set indices of verts of the sewing edge symmetrically in sew_edge_graph */
+        unsigned int *vertex_index_pair = MEM_mallocN(sizeof(unsigned int) * 2,
+                                                      "sewing_edge_index_pair_01");
+        if (medge[i].v1 < medge[i].v2) {
+          vertex_index_pair[0] = medge[i].v1;
+          vertex_index_pair[1] = medge[i].v2;
+        }
+        else {
+          vertex_index_pair[0] = medge[i].v2;
+          vertex_index_pair[1] = medge[i].v1;
+        }
+        BLI_ghash_insert(cloth->sew_edge_graph, vertex_index_pair, NULL);
       }
       else {
         shrink_factor = cloth_shrink_factor(clmd, cloth->verts, spring->ij, spring->kl);
diff --git a/source/blender/blenkernel/intern/collision.c b/source/blender/blenkernel/intern/collision.c
index 5d4753e7ef1..987791db101 100644
--- a/source/blender/blenkernel/intern/collision.c
+++ b/source/blender/blenkernel/intern/collision.c
@@ -37,6 +37,7 @@
 #include "BLI_math.h"
 #include "BLI_task.h"
 #include "BLI_threads.h"
+#include "BLI_ghash.h"
 
 #include "BKE_cloth.h"
 #include "BKE_collection.h"
@@ -1138,16 +1139,34 @@ static void cloth_collision(void *__restrict userdata,
   }
 }
 
-static bool cloth_bvh_selfcollision_is_active(const ClothVertex *verts,
+static bool cloth_bvh_selfcollision_is_active(const Cloth *cloth,
                                               const MVertTri *tri_a,
-                                              const MVertTri *tri_b)
+                                              const MVertTri *tri_b,
+                                              bool sewing_active)
 {
-  /* Ignore overlap of neighboring triangles. */
+  const ClothVertex *verts = cloth->verts;
+  /* Ignore overlap of neighboring triangles and triangles connected by a sewing edge. */
   for (uint i = 0; i < 3; i++) {
     for (uint j = 0; j < 3; j++) {
       if (tri_a->tri[i] == tri_b->tri[j]) {
         return false;
       }
+
+      if (sewing_active) {
+        unsigned int vertex_index_pair[2];
+        /* The indices pair are ordered, thus must ensure the same here as well */
+        if (tri_a->tri[i] < tri_b->tri[j]) {
+          vertex_index_pair[0] = tri_a->tri[i];
+          vertex_index_pair[1] = tri_b->tri[j];
+        }
+        else {
+          vertex_index_pair[0] = tri_b->tri[j];
+          vertex_index_pair[1] = tri_a->tri[i];
+        }
+        if (BLI_ghash_haskey(cloth->sew_edge_graph, vertex_index_pair)) {
+          return false;
+        }
+      }
     }
   }
 
@@ -1177,7 +1196,10 @@ static void cloth_selfcollision(void *__restrict userdata,
   tri_a = &clmd->clothObject->tri[data->overlap[index].indexA];
   tri_b = &clmd->clothObject->tri[data->overlap[index].indexB];
 
-  BLI_assert(cloth_bvh_selfcollision_is_active(verts1, tri_a, tri_b));
+#ifdef DEBUG
+  bool sewing_active = (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW);
+  BLI_assert(cloth_bvh_selfcollision_is_active(clmd->clothObject, tri_a, tri_b, sewing_active));
+#endif
 
   /* Compute distance and normal. */
   distance = compute_collision_point_tri_tri(verts1[tri_a->tri[0]].tx,
@@ -1580,12 +1602,15 @@ static bool cloth_bvh_self_overlap_cb(void *userdata, int index_a, int index_b,
 {
   /* No need for equal combinations (eg. (0,1) & (1,0)). */
   if (index_a < index_b) {
-    struct Cloth *clothObject = userdata;
+    ClothModifierData *clmd = (ClothModifierData *)userdata;
+    struct Cloth *clothObject = clmd->clothObject;
     const MVertTri *tri_a, *tri_b;
     tri_a = &clothObject->tri[index_a];
     tri_b = &clothObject->tri[index_b];
 
-    if (cloth_bvh_selfcollision_is_active(clothObject->verts, tri_a, tri_b)) {
+    bool sewing_active = (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW);
+
+    if (cloth_bvh_selfcollision_is_active(clothObject, tri_a, tri_b, sewing_active)) {
       return true;
     }
   }
@@ -1652,11 +1677,8 @@ int cloth_bvh_collision(
   if (clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_SELF) {
     bvhtree_update_from_cloth(clmd, false, true);
 
-    overlap_self = BLI_bvhtree_overlap(cloth->bvhselftree,
-                                       cloth->bvhselftree,
-                                       &coll_count_self,
-                                       cloth_bvh_self_overlap_cb,
-                                       clmd->clothObject);
+    overlap_self = BLI_bvhtree_overlap(
+        cloth->bvhselftree, cloth->bvhselftree, &coll_count_self, cloth_bvh_self_overlap_cb, clmd);
   }
 
   do {
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index eb926c51ba9..f59d9ea99d0 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -370,6 +370,20 @@ unsigned int BLI_ghashutil_uinthash_v4_murmur(const unsigned int key[4]);
 bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b);
 #define BLI_ghashutil_inthash_v4_cmp BLI_ghashutil_uinthash_v4_cmp
 
+unsigned int BLI_ghashutil_uinthash_v2(const unsigned int key[2]);
+#define BLI_ghashutil_inthash_v2(key) \
+  (CHECK_TYPE_ANY(key, int *, const int *), BLI_ghashutil_uinthash_v2((const unsigned int *)key))
+#define BLI_ghashutil_inthash_v2_p ((GSetHashFP)BLI_ghashutil_uinthash_v2)
+#define BLI_ghashutil_uinthash_v2_p ((GSetHashFP)BLI_ghashutil_uinthash_v2)
+unsigned int BLI_ghashutil_uinthash_v2_murmur(const unsigned int key[2]);
+#define BLI_ghashutil_inthash_v2_murmur(key) \
+  (CHECK_TYPE_ANY(key, int *, const int *), \
+   BLI_ghashutil_uinthash_v2_murmur((const unsigned int *)key))
+#define BLI_ghashutil_inthash_v2_p_murmur ((GSetHashFP)BLI_ghashutil_uinthash_v2_murmur)
+#define BLI_ghashutil_uinthash_v2_p_murmur ((GSetHashFP)BLI_ghashutil_uinthash_v2_murmur)
+bool BLI_ghashutil_uinthash_v2_cmp(const void *a, const void *b);
+#define BLI_ghashutil_inthash_v2_cmp BLI_ghashutil_uinthash_v2_cmp
+
 typedef struct GHashPair {
   const void *first;
   const void *second;
diff --git a/source/blender/blenlib/intern/BLI_ghash_utils.c b/source/blender/blenlib/intern/BLI_ghash_utils.c
index 63559da5bd7..abe5970b9a6 100644
--- a/source/blender/blenlib/intern/BLI_ghash_utils.c
+++ b/source/blender/blenlib/intern/BLI_ghash_utils.c
@@ -75,6 +75,7 @@ uint BLI_ghashutil_uinthash_v4(const uint key[4])
   hash += key[3];
   return hash;
 }
+
 uint BLI_ghashutil_uinthash_v4_murmur(const uint key[4])
 {
   return BLI_hash_mm2((const unsigned char *)key, sizeof(int) * 4 /* sizeof(key) */, 0);
@@ -85,6 +86,25 @@ bool BLI_ghashutil_uinthash_v4_cmp(const void *a, const void *b)
   return (memcmp(a, b, sizeof(uint[4])) != 0);
 }
 
+uint BLI_ghashutil_uinthash_v2(const uint key[2])
+{
+  uint hash;
+  hash = key[0];
+  hash *= 37;
+  hash += key[1];
+  return hash;
+}
+
+uint BLI_ghashutil_uinthash_v2_murmur(const uint key[2])
+{
+  return BLI_hash_mm2((const unsigned char *)key, sizeof(int) * 2 /* sizeof(key) */, 0);
+}
+
+bool BLI_ghashutil_uinthash_v2_cmp(const void *a, const void *b)
+{
+  return (memcmp(a, b, sizeof(uint[2])) != 0);
+}
+
 uint BLI_ghashutil_uinthash(uint key)
 {
   key += ~(key << 16);