blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 745 Projects 19 Wiki Activity

Speedups for new boolean. Better hash function for verts. 

The existing hash function didn't work well with Set's method of
masking to the lower bits, because many verts have zeros in the
lower bits.
Also, replaced VectorSet with Set for Vert deduping.
This commit is contained in:
Howard Trickey 2020-11-23 19:30:40 -05:00
parent b0a9081883
commit 246c11634f
3 changed files with 49 additions and 40 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

53
source/blender/blenlib/intern/mesh_intersect.cc
View File

@ -39,6 +39,7 @@
# include "BLI_math_mpq.hh"
# include "BLI_mpq2.hh"
# include "BLI_mpq3.hh"
# include "BLI_set.hh"
# include "BLI_span.hh"
# include "BLI_task.h"
# include "BLI_threads.h"
@ -76,7 +77,13 @@ bool Vert::operator==(const Vert &other) const
uint64_t Vert::hash() const
{
return co_exact.hash();
uint64_t x = *reinterpret_cast<const uint64_t *>(&co.x);
uint64_t y = *reinterpret_cast<const uint64_t *>(&co.y);
uint64_t z = *reinterpret_cast<const uint64_t *>(&co.z);
x = (x >> 56) ^ (x >> 46) ^ x;
y = (y >> 55) ^ (y >> 45) ^ y;
z = (z >> 54) ^ (z >> 44) ^ z;
return x ^ y ^ z;
}
std::ostream &operator<<(std::ostream &os, const Vert *v)
@ -145,15 +152,15 @@ bool Plane::exact_populated() const
uint64_t Plane::hash() const
{
constexpr uint64_t h1 = 33;
constexpr uint64_t h2 = 37;
constexpr uint64_t h3 = 39;
uint64_t hashx = hash_mpq_class(this->norm_exact.x);
uint64_t hashy = hash_mpq_class(this->norm_exact.y);
uint64_t hashz = hash_mpq_class(this->norm_exact.z);
uint64_t hashd = hash_mpq_class(this->d_exact);
uint64_t ans = hashx ^ (hashy * h1) ^ (hashz * h1 * h2) ^ (hashd * h1 * h2 * h3);
return ans;
uint64_t x = *reinterpret_cast<const uint64_t *>(&this->norm.x);
uint64_t y = *reinterpret_cast<const uint64_t *>(&this->norm.y);
uint64_t z = *reinterpret_cast<const uint64_t *>(&this->norm.z);
uint64_t d = *reinterpret_cast<const uint64_t *>(&this->d);
x = (x >> 56) ^ (x >> 46) ^ x;
y = (y >> 55) ^ (y >> 45) ^ y;
z = (z >> 54) ^ (z >> 44) ^ z;
d = (d >> 53) ^ (d >> 43) ^ d;
return x ^ y ^ z ^ d;
}
std::ostream &operator<<(std::ostream &os, const Plane *plane)
@ -315,7 +322,7 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
{
}
uint32_t hash() const
uint64_t hash() const
{
return vert->hash();
}
@ -326,7 +333,7 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
}
};
VectorSet<VSetKey> vset_; /* TODO: replace with Set */
Set<VSetKey> vset_;
/**
* Ownership of the Vert memory is here, so destroying this reclaims that memory.
@ -434,8 +441,7 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
const Vert *find_vert(const mpq3 &co)
{
const Vert *ans;
Vert vtry(co, double3(), NO_INDEX, NO_INDEX);
Vert vtry(co, double3(co[0].get_d(), co[1].get_d(), co[2].get_d()), NO_INDEX, NO_INDEX);
VSetKey vskey(&vtry);
if (intersect_use_threading) {
# ifdef USE_SPINLOCK
@ -444,13 +450,7 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
BLI_mutex_lock(mutex_);
# endif
}
int i = vset_.index_of_try(vskey);
if (i == -1) {
ans = nullptr;
}
else {
ans = vset_[i].vert;
}
const VSetKey *lookup = vset_.lookup_key_ptr(vskey);
if (intersect_use_threading) {
# ifdef USE_SPINLOCK
BLI_spin_unlock(&lock_);
@ -458,7 +458,10 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
BLI_mutex_unlock(mutex_);
# endif
}
return ans;
if (!lookup) {
return nullptr;
}
return lookup->vert;
}
/**
@ -493,8 +496,8 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
BLI_mutex_lock(mutex_);
# endif
}
int i = vset_.index_of_try(vskey);
if (i == -1) {
const VSetKey *lookup = vset_.lookup_key_ptr(vskey);
if (!lookup) {
vskey.vert = new Vert(mco, dco, next_vert_id_++, orig);
vset_.add_new(vskey);
allocated_verts_.append(std::unique_ptr<Vert>(vskey.vert));
@ -506,7 +509,7 @@ class IMeshArena::IMeshArenaImpl : NonCopyable, NonMovable {
* This is the intended semantics: if the Vert already
* exists then we are merging verts and using the first-seen
* one as the canonical one. */
ans = vset_[i].vert;
ans = lookup->vert;
}
if (intersect_use_threading) {
# ifdef USE_SPINLOCK

34
source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
View File

@ -623,17 +623,21 @@ TEST(mesh_intersect, TetTet)
const Vert *v1 = mb.arena.find_vert(mpq3(2, 0, 0));
const Vert *v8 = mb.arena.find_vert(mpq3(0.5, 0.5, 1));
const Vert *v9 = mb.arena.find_vert(mpq3(1.5, 0.5, 1));
EXPECT_TRUE(v1 != nullptr && v8 != nullptr && v9 != nullptr);
const Face *f = mb.arena.find_face({v1, v8, v9});
EXPECT_NE(f, nullptr);
EXPECT_EQ(f->orig, 1);
int v1pos = f->vert[0] == v1 ? 0 : (f->vert[1] == v1 ? 1 : 2);
EXPECT_EQ(f->edge_orig[v1pos], NO_INDEX);
EXPECT_EQ(f->edge_orig[(v1pos + 1) % 3], NO_INDEX);
EXPECT_EQ(f->edge_orig[(v1pos + 2) % 3], 1001);
EXPECT_EQ(f->is_intersect[v1pos], false);
EXPECT_EQ(f->is_intersect[(v1pos + 1) % 3], true);
EXPECT_EQ(f->is_intersect[(v1pos + 2) % 3], false);
EXPECT_TRUE(v1 && v8 && v9);
if (v1 && v8 && v9) {
const Face *f = mb.arena.find_face({v1, v8, v9});
EXPECT_NE(f, nullptr);
if (f != nullptr) {
EXPECT_EQ(f->orig, 1);
int v1pos = f->vert[0] == v1 ? 0 : (f->vert[1] == v1 ? 1 : 2);
EXPECT_EQ(f->edge_orig[v1pos], NO_INDEX);
EXPECT_EQ(f->edge_orig[(v1pos + 1) % 3], NO_INDEX);
EXPECT_EQ(f->edge_orig[(v1pos + 2) % 3], 1001);
EXPECT_EQ(f->is_intersect[v1pos], false);
EXPECT_EQ(f->is_intersect[(v1pos + 1) % 3], true);
EXPECT_EQ(f->is_intersect[(v1pos + 2) % 3], false);
}
}
if (DO_OBJ) {
write_obj_mesh(out, "test_tc_3");
}
@ -908,7 +912,7 @@ static void spheresphere_test(int nrings, double y_offset, bool use_self)
int num_sphere_tris;
get_sphere_params(nrings, nsegs, true, &num_sphere_verts, &num_sphere_tris);
Array<Face *> tris(2 * num_sphere_tris);
arena.reserve(2 * num_sphere_verts, 2 * num_sphere_tris);
arena.reserve(6 * num_sphere_verts / 2, 8 * num_sphere_tris);
double3 center1(0.0, 0.0, 0.0);
fill_sphere_data(nrings,
nsegs,
@ -1052,7 +1056,8 @@ static void spheregrid_test(int nrings, int grid_level, double z_offset, bool us
get_sphere_params(nrings, nsegs, true, &num_sphere_verts, &num_sphere_tris);
get_grid_params(subdivs, subdivs, true, &num_grid_verts, &num_grid_tris);
Array<Face *> tris(num_sphere_tris + num_grid_tris);
arena.reserve(num_sphere_verts + num_grid_verts, num_sphere_tris + num_grid_tris);
arena.reserve(3 * (num_sphere_verts + num_grid_verts) / 2,
4 * (num_sphere_tris + num_grid_tris));
double3 center(0.0, 0.0, z_offset);
fill_sphere_data(nrings,
nsegs,
@ -1120,7 +1125,8 @@ static void gridgrid_test(int x_level_1,
get_grid_params(x_subdivs_1, y_subdivs_1, true, &num_grid_verts_1, &num_grid_tris_1);
get_grid_params(x_subdivs_2, y_subdivs_2, true, &num_grid_verts_2, &num_grid_tris_2);
Array<Face *> tris(num_grid_tris_1 + num_grid_tris_2);
arena.reserve(num_grid_verts_1 + num_grid_verts_2, num_grid_tris_1 + num_grid_tris_2);
arena.reserve(3 * (num_grid_verts_1 + num_grid_verts_2) / 2,
4 * (num_grid_tris_1 + num_grid_tris_2));
fill_grid_data(x_subdivs_1,
y_subdivs_1,
true,

2
source/blender/bmesh/tools/bmesh_boolean.cc
View File

@ -52,7 +52,7 @@ static IMesh mesh_from_bm(BMesh *bm,
BM_mesh_elem_index_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
BM_mesh_elem_table_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
/* Account for triangulation and intersects. */
const int estimate_num_outv = (3 * bm->totvert) / 2;
const int estimate_num_outv = 3 * bm->totvert;
const int estimate_num_outf = 4 * bm->totface;
arena->reserve(estimate_num_outv, estimate_num_outf);
Array<const Vert *> vert(bm->totvert);