blender
/
blender
129
397
Fork 571
Code Issues 6.2k Pull Requests 754 Projects 19 Wiki Activity

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
This commit is contained in:
Kévin Dietrich 2022-07-23 06:01:34 +02:00
parent d26c29d8e4
commit f7d5aaa365
1 changed files with 13 additions and 16 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

29
source/blender/io/alembic/intern/abc_reader_mesh.cc
View File

@ -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;
}