BKE: parallelize BKE_mesh_calc_edges

`BKE_mesh_calc_edges` was the main performance bottleneck in D9141.
While openvdb only needed ~115ms, calculating the edges afterwards
took ~960ms. Now with some parallelization this is reduced to ~210ms.

Parallelizing `BKE_mesh_calc_edges` is not entirely trivial, because it
has to perform deduplication and some other things that have to happen
in a certain order. Even though the multithreading improves performance
with more threads, there are diminishing returns when too many threads
are used in this function.

The speedup is mainly achieved by having multiple hash tables that are
filled in parallel. The distribution of the edges to hash tables is based on
a hash (that is different from the hash used in the actual hash tables).

I moved the function to C++, because that made it easier for me to
optimize it. Furthermore, I added `BLI_task.hh` which contains some
light tbb wrappers for parallelization.

Reviewers: campbellbarton

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

1 files changed, 0 insertions, 105 deletions

diff --git a/source/blender/blenkernel/intern/mesh_validate.c b/source/blender/blenkernel/intern/mesh_validate.c
index af09ef6dae0..5f11476574e 100644
--- a/source/blender/blenkernel/intern/mesh_validate.c
+++ b/source/blender/blenkernel/intern/mesh_validate.c
@@ -1526,111 +1526,6 @@ void BKE_mesh_calc_edges_legacy(Mesh *me, const bool use_old)
   BKE_mesh_strip_loose_faces(me);
 }
 
-/**
- * Calculate edges from polygons
- *
- * \param mesh: The mesh to add edges into
- * \param update: When true create new edges co-exist
- */
-void BKE_mesh_calc_edges(Mesh *mesh, bool update, const bool select)
-{
-  MEdge *med;
-  int i, totpoly = mesh->totpoly;
-  /* Select for newly created meshes which are selected T25595. */
-  const short ed_flag = (ME_EDGEDRAW | ME_EDGERENDER) | (select ? SELECT : 0);
-
-  if (mesh->totedge == 0) {
-    update = false;
-  }
-
-  const unsigned int eh_reserve = max_ii(update ? mesh->totedge : 0,
-                                         BLI_EDGEHASH_SIZE_GUESS_FROM_POLYS(totpoly));
-  EdgeHash *eh = BLI_edgehash_new_ex(__func__, eh_reserve);
-
-  if (update) {
-    /* assume existing edges are valid
-     * useful when adding more faces and generating edges from them */
-    med = mesh->medge;
-    for (i = 0; i < mesh->totedge; i++, med++) {
-      BLI_edgehash_insert(eh, med->v1, med->v2, med);
-    }
-  }
-
-  /* mesh loops (bmesh only) */
-  MPoly *mp;
-  for (mp = mesh->mpoly, i = 0; i < totpoly; mp++, i++) {
-    MLoop *l = &mesh->mloop[mp->loopstart];
-    int j, v_prev = (l + (mp->totloop - 1))->v;
-    for (j = 0; j < mp->totloop; j++, l++) {
-      if (v_prev != l->v) {
-        void **val_p;
-        if (!BLI_edgehash_ensure_p(eh, v_prev, l->v, &val_p)) {
-          *val_p = NULL;
-        }
-      }
-      v_prev = l->v;
-    }
-  }
-
-  const int totedge = BLI_edgehash_len(eh);
-
-  /* write new edges into a temporary CustomData */
-  CustomData edata;
-  CustomData_reset(&edata);
-  CustomData_add_layer(&edata, CD_MEDGE, CD_CALLOC, NULL, totedge);
-
-  med = CustomData_get_layer(&edata, CD_MEDGE);
-  EdgeHashIterator *ehi;
-  for (ehi = BLI_edgehashIterator_new(eh), i = 0; BLI_edgehashIterator_isDone(ehi) == false;
-       BLI_edgehashIterator_step(ehi), ++i, ++med) {
-    MEdge *med_orig;
-    if (update && (med_orig = BLI_edgehashIterator_getValue(ehi))) {
-      *med = *med_orig; /* copy from the original */
-    }
-    else {
-      BLI_edgehashIterator_getKey(ehi, &med->v1, &med->v2);
-      med->flag = ed_flag;
-    }
-
-    /* store the new edge index in the hash value */
-    BLI_edgehashIterator_setValue(ehi, POINTER_FROM_INT(i));
-  }
-  BLI_edgehashIterator_free(ehi);
-
-  if (mesh->totpoly) {
-    /* second pass, iterate through all loops again and assign
-     * the newly created edges to them. */
-    for (mp = mesh->mpoly, i = 0; i < mesh->totpoly; mp++, i++) {
-      MLoop *l = &mesh->mloop[mp->loopstart];
-      MLoop *l_prev = (l + (mp->totloop - 1));
-      int j;
-      for (j = 0; j < mp->totloop; j++, l++) {
-        /* Lookup hashed edge index, if it's valid. */
-        int med_index;
-        if (l_prev->v != l->v) {
-          med_index = POINTER_AS_INT(BLI_edgehash_lookup(eh, l_prev->v, l->v));
-        }
-        else {
-          /* This is an invalid edge; normally this does not happen in Blender, but it can be part
-           * of an imported mesh with invalid geometry. See T76514. */
-          med_index = 0;
-        }
-        l_prev->e = med_index;
-        l_prev = l;
-      }
-    }
-  }
-
-  /* free old CustomData and assign new one */
-  CustomData_free(&mesh->edata, mesh->totedge);
-  mesh->edata = edata;
-  mesh->totedge = totedge;
-
-  mesh->medge = CustomData_get_layer(&mesh->edata, CD_MEDGE);
-
-  BLI_edgehash_free(eh, NULL);
-}
-
 void BKE_mesh_calc_edges_loose(Mesh *mesh)
 {
   MEdge *med = mesh->medge;