diff options
| -rw-r--r-- | source/blender/blenkernel/BKE_cloth.h | 10 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/cloth.c | 33 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/collision.c | 44 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_ghash.h | 14 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_ghash_utils.c | 20 | ||||
| -rw-r--r-- | tests/gtests/blenlib/BLI_ghash_performance_test.cc | 107 |
6 files changed, 213 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); diff --git a/tests/gtests/blenlib/BLI_ghash_performance_test.cc b/tests/gtests/blenlib/BLI_ghash_performance_test.cc index 58dd9998733..631adfc7a6b 100644 --- a/tests/gtests/blenlib/BLI_ghash_performance_test.cc +++ b/tests/gtests/blenlib/BLI_ghash_performance_test.cc @@ -464,6 +464,113 @@ TEST(ghash, Int4Murmur2a20000000) } #endif +/* GHash inthash_v2 tests */ +TEST(ghash, Int2NoHash12000) +{ + GHash *ghash = BLI_ghash_new(ghashutil_tests_nohash_p, ghashutil_tests_cmp_p, __func__); + + randint_ghash_tests(ghash, "RandIntGHash - No Hash - 12000", 12000); +} + +#ifdef GHASH_RUN_BIG +TEST(ghash, Int2NoHash50000000) +{ + GHash *ghash = BLI_ghash_new(ghashutil_tests_nohash_p, ghashutil_tests_cmp_p, __func__); + + randint_ghash_tests(ghash, "RandIntGHash - No Hash - 50000000", 50000000); +} +#endif + +/* Int_v2: 20M of randomly-generated integer vectors. */ + +static void int2_ghash_tests(GHash *ghash, const char *id, const unsigned int nbr) +{ + printf("\n========== STARTING %s ==========\n", id); + + void *data_v = MEM_mallocN(sizeof(unsigned int[2]) * (size_t)nbr, __func__); + unsigned int(*data)[2] = (unsigned int(*)[2])data_v; + unsigned int(*dt)[2]; + unsigned int i, j; + + { + RNG *rng = BLI_rng_new(0); + for (i = nbr, dt = data; i--; dt++) { + for (j = 2; j--;) { + (*dt)[j] = BLI_rng_get_uint(rng); + } + } + BLI_rng_free(rng); + } + + { + TIMEIT_START(int_v2_insert); + +#ifdef GHASH_RESERVE + BLI_ghash_reserve(ghash, nbr); +#endif + + for (i = nbr, dt = data; i--; dt++) { + BLI_ghash_insert(ghash, *dt, POINTER_FROM_UINT(i)); + } + + TIMEIT_END(int_v2_insert); + } + + PRINTF_GHASH_STATS(ghash); + + { + TIMEIT_START(int_v2_lookup); + + for (i = nbr, dt = data; i--; dt++) { + void *v = BLI_ghash_lookup(ghash, (void *)(*dt)); + EXPECT_EQ(POINTER_AS_UINT(v), i); + } + + TIMEIT_END(int_v2_lookup); + } + + BLI_ghash_free(ghash, NULL, NULL); + MEM_freeN(data); + + printf("========== ENDED %s ==========\n\n", id); +} + +TEST(ghash, Int2GHash2000) +{ + GHash *ghash = BLI_ghash_new( + BLI_ghashutil_uinthash_v2_p, BLI_ghashutil_uinthash_v2_cmp, __func__); + + int2_ghash_tests(ghash, "Int2GHash - GHash - 2000", 2000); +} + +#ifdef GHASH_RUN_BIG +TEST(ghash, Int2GHash20000000) +{ + GHash *ghash = BLI_ghash_new( + BLI_ghashutil_uinthash_v2_p, BLI_ghashutil_uinthash_v2_cmp, __func__); + + int2_ghash_tests(ghash, "Int2GHash - GHash - 20000000", 20000000); +} +#endif + +TEST(ghash, Int2Murmur2a2000) +{ + GHash *ghash = BLI_ghash_new( + BLI_ghashutil_uinthash_v2_p_murmur, BLI_ghashutil_uinthash_v2_cmp, __func__); + + int2_ghash_tests(ghash, "Int2GHash - Murmur - 2000", 2000); +} + +#ifdef GHASH_RUN_BIG +TEST(ghash, Int2Murmur2a20000000) +{ + GHash *ghash = BLI_ghash_new( + BLI_ghashutil_uinthash_v2_p_murmur, BLI_ghashutil_uinthash_v2_cmp, __func__); + + int2_ghash_tests(ghash, "Int2GHash - Murmur - 20000000", 20000000); +} +#endif + /* MultiSmall: create and manipulate a lot of very small ghashes * (90% < 10 items, 9% < 100 items, 1% < 1000 items). */ |