Alembic: speed up edge crease import

The Alembic importer uses a linear search over the mesh edges to find
the right edge when setting edge creases. Although the complexity is
`O(m * n)`, with `m` being the number of creased edges, and `n` being
the number of edges, this can lead to a quadratic complexity as `m`
approches `n`.

This patch uses `EdgeHash` to store and retrieve the edges, which
should bring complexity closer to `O(n)`, provided that lookup is
`O(1)`.

See differential for some timings. In most files, this is expected
to give at least a 2-3x speedup for this operation, but can lead
orders of magnitude speed increase for dense meshes with a significant
number of edge creases.

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

1 files changed, 13 insertions, 16 deletions

diff --git a/source/blender/io/alembic/intern/abc_reader_mesh.cc b/source/blender/io/alembic/intern/abc_reader_mesh.cc
index df3559c108c..bacc1f06599 100644
--- a/source/blender/io/alembic/intern/abc_reader_mesh.cc
+++ b/source/blender/io/alembic/intern/abc_reader_mesh.cc
@@ -20,6 +20,7 @@
 #include "DNA_object_types.h"
 
 #include "BLI_compiler_compat.h"
+#include "BLI_edgehash.h"
 #include "BLI_index_range.hh"
 #include "BLI_listbase.h"
 #include "BLI_math_geom.h"
@@ -830,19 +831,6 @@ void AbcMeshReader::readFaceSetsSample(Main *bmain, Mesh *mesh, const ISampleSel
 
 /* ************************************************************************** */
 
-BLI_INLINE MEdge *find_edge(MEdge *edges, int totedge, int v1, int v2)
-{
-  for (int i = 0, e = totedge; i < e; i++) {
-    MEdge &edge = edges[i];
-
-    if (edge.v1 == v1 && edge.v2 == v2) {
-      return &edge;
-    }
-  }
-
-  return nullptr;
-}
-
 static void read_subd_sample(const std::string &iobject_full_name,
                              ImportSettings *settings,
                              const ISubDSchema &schema,
@@ -927,7 +915,14 @@ static void read_edge_creases(Mesh *mesh,
   }
 
   MEdge *edges = mesh->medge;
-  int totedge = mesh->totedge;
+  const int totedge = mesh->totedge;
+
+  EdgeHash *edge_hash = BLI_edgehash_new_ex(__func__, mesh->totedge);
+
+  for (int i = 0; i < totedge; i++) {
+    MEdge *edge = &edges[i];
+    BLI_edgehash_insert(edge_hash, edge->v1, edge->v2, edge);
+  }
 
   for (int i = 0, s = 0, e = indices->size(); i < e; i += 2, s++) {
     int v1 = (*indices)[i];
@@ -939,9 +934,9 @@ static void read_edge_creases(Mesh *mesh,
       std::swap(v1, v2);
     }
 
-    MEdge *edge = find_edge(edges, totedge, v1, v2);
+    MEdge *edge = static_cast<MEdge *>(BLI_edgehash_lookup(edge_hash, v1, v2));
     if (edge == nullptr) {
-      edge = find_edge(edges, totedge, v2, v1);
+      edge = static_cast<MEdge *>(BLI_edgehash_lookup(edge_hash, v2, v1));
     }
 
     if (edge) {
@@ -949,6 +944,8 @@ static void read_edge_creases(Mesh *mesh,
     }
   }
 
+  BLI_edgehash_free(edge_hash, nullptr);
+
   mesh->cd_flag |= ME_CDFLAG_EDGE_CREASE;
 }