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.

3 files changed, 49 insertions, 40 deletions

diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 4eff3c52e63..64ea25ccc90 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -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
diff --git a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
index fef4a52d9c9..769cadd2f47 100644
--- a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
+++ b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
@@ -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,
diff --git a/source/blender/bmesh/tools/bmesh_boolean.cc b/source/blender/bmesh/tools/bmesh_boolean.cc
index 39b425a41df..6031e160c8c 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.cc
+++ b/source/blender/bmesh/tools/bmesh_boolean.cc
@@ -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);