diff options
author | Kévin Dietrich <kevin.dietrich@mailoo.org> | 2022-07-23 07:01:34 +0300 |
---|---|---|
committer | Kévin Dietrich <kevin.dietrich@mailoo.org> | 2022-07-24 22:18:11 +0300 |
commit | f7d5aaa3656cf5b839d86bc6d5ad57960d540202 (patch) | |
tree | bf35d6b90a9a6435d546666866c6c0cc5fd5c473 | |
parent | d26c29d8e46c284b27cc6d3bcde8fde7ff678ae4 (diff) |
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
-rw-r--r-- | source/blender/io/alembic/intern/abc_reader_mesh.cc | 29 |
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; } |