Commit: ebe8f8ce719729eef402119f4d0edd29e746abf3 Author: Hans Goudey Date: Fri Feb 3 10:19:19 2023 -0500 Branches: master https://developer.blender.org/rBebe8f8ce719729eef402119f4d0edd29e746abf3
BMesh: Parallelize BMesh to evaluated Mesh conversion Currently this conversion (which happens when using modifiers in edit mode, for example) is completely single threaded. It's harder than some other areas to multithread because BMesh elements don't always know their indices (and vise versa), and because the dynamic AoS format used by BMesh makes some typical solutions not helpful. This patch proposes to split the operation into two steps. The first updates the indices of BMesh elements and builds tables for easy iteration later. It also checks if some optional mesh attributes should be added. The second uses parallel loops over all elements, copying attribute values and building the Mesh topology. Both steps process different domains in separate threads (though the first has to combine faces and loops). Though this isn't proper data parallelism, it's quite helpful because each domain doesn't affect the others. **Timings** I tested this on a Ryzen 7950x with a 1 million face grid, with no extra attributes and then with several color attributes and vertex groups. | File | Before | After | | Simple | 101.6 ms | 59.6 ms | | More Attributes | 149.2 ms | 65.6 ms | The optimization scales better with more attributes on the BMesh. The speedup isn't as linear as multithreading other operations, indicating added overhead. I think this is worth it though, because the user is usually actively interacting with a mesh in edit mode. See the differential revision for more timing information. Differential Revision: https://developer.blender.org/D16249 =================================================================== M source/blender/bmesh/intern/bmesh_construct.c M source/blender/bmesh/intern/bmesh_construct.h M source/blender/bmesh/intern/bmesh_mesh_convert.cc =================================================================== diff --git a/source/blender/bmesh/intern/bmesh_construct.c b/source/blender/bmesh/intern/bmesh_construct.c index 0c05e7bb83d..b549580f354 100644 --- a/source/blender/bmesh/intern/bmesh_construct.c +++ b/source/blender/bmesh/intern/bmesh_construct.c @@ -715,25 +715,3 @@ BMesh *BM_mesh_copy(BMesh *bm_old) return bm_new; } - -char BM_edge_flag_from_mflag(const short mflag) -{ - return (((mflag & ME_SEAM) ? BM_ELEM_SEAM : 0) | ((mflag & ME_EDGEDRAW) ? BM_ELEM_DRAW : 0)); -} -char BM_face_flag_from_mflag(const char mflag) -{ - return ((mflag & ME_SMOOTH) ? BM_ELEM_SMOOTH : 0); -} - -short BM_edge_flag_to_mflag(BMEdge *e) -{ - const char hflag = e->head.hflag; - - return (((hflag & BM_ELEM_SEAM) ? ME_SEAM : 0) | ((hflag & BM_ELEM_DRAW) ? ME_EDGEDRAW : 0)); -} -char BM_face_flag_to_mflag(BMFace *f) -{ - const char hflag = f->head.hflag; - - return ((hflag & BM_ELEM_SMOOTH) ? ME_SMOOTH : 0); -} diff --git a/source/blender/bmesh/intern/bmesh_construct.h b/source/blender/bmesh/intern/bmesh_construct.h index 635198b9346..0b85abdaa92 100644 --- a/source/blender/bmesh/intern/bmesh_construct.h +++ b/source/blender/bmesh/intern/bmesh_construct.h @@ -170,11 +170,6 @@ void BM_mesh_copy_init_customdata_all_layers(BMesh *bm_dst, const struct BMAllocTemplate *allocsize); BMesh *BM_mesh_copy(BMesh *bm_old); -char BM_face_flag_from_mflag(char mflag); -char BM_edge_flag_from_mflag(short mflag); -/* ME -> BM */ -char BM_face_flag_to_mflag(BMFace *f); -short BM_edge_flag_to_mflag(BMEdge *e); #ifdef __cplusplus } diff --git a/source/blender/bmesh/intern/bmesh_mesh_convert.cc b/source/blender/bmesh/intern/bmesh_mesh_convert.cc index c795fd1138a..7fd8dbe44bf 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_convert.cc +++ b/source/blender/bmesh/intern/bmesh_mesh_convert.cc @@ -111,6 +111,28 @@ using blender::MutableSpan; using blender::Span; using blender::StringRef; +static char bm_edge_flag_from_mflag(const short mflag) +{ + return ((mflag & ME_SEAM) ? BM_ELEM_SEAM : 0) | ((mflag & ME_EDGEDRAW) ? BM_ELEM_DRAW : 0); +} +static char bm_face_flag_from_mflag(const char mflag) +{ + return ((mflag & ME_SMOOTH) ? BM_ELEM_SMOOTH : 0); +} + +static short bm_edge_flag_to_mflag(const BMEdge *e) +{ + const char hflag = e->head.hflag; + + return ((hflag & BM_ELEM_SEAM) ? ME_SEAM : 0) | ((hflag & BM_ELEM_DRAW) ? ME_EDGEDRAW : 0); +} +static char bm_face_flag_to_mflag(const BMFace *f) +{ + const char hflag = f->head.hflag; + + return ((hflag & BM_ELEM_SMOOTH) ? ME_SMOOTH : 0); +} + /* Static function for alloc (duplicate in modifiers_bmesh.c) */ static BMFace *bm_face_create_from_mpoly(BMesh &bm, Span<MLoop> loops, @@ -385,7 +407,7 @@ void BM_mesh_bm_from_me(BMesh *bm, const Mesh *me, const struct BMeshFromMeshPar BM_elem_index_set(e, i); /* set_ok */ /* Transfer flags. */ - e->head.hflag = BM_edge_flag_from_mflag(medge[i].flag); + e->head.hflag = bm_edge_flag_from_mflag(medge[i].flag); if (hide_edge && hide_edge[i]) { BM_elem_flag_enable(e, BM_ELEM_HIDDEN); } @@ -435,7 +457,7 @@ void BM_mesh_bm_from_me(BMesh *bm, const Mesh *me, const struct BMeshFromMeshPar BM_elem_index_set(f, bm->totface - 1); /* set_ok */ /* Transfer flag. */ - f->head.hflag = BM_face_flag_from_mflag(mpoly[i].flag); + f->head.hflag = bm_face_flag_from_mflag(mpoly[i].flag); if (hide_poly && hide_poly[i]) { BM_elem_flag_enable(f, BM_ELEM_HIDDEN); } @@ -1097,7 +1119,7 @@ void BM_mesh_bm_to_me(Main *bmain, BMesh *bm, Mesh *me, const struct BMeshToMesh medge[i].v1 = BM_elem_index_get(e->v1); medge[i].v2 = BM_elem_index_get(e->v2); - medge[i].flag = BM_edge_flag_to_mflag(e); + medge[i].flag = bm_edge_flag_to_mflag(e); if (BM_elem_flag_test(e, BM_ELEM_HIDDEN)) { need_hide_edge = true; } @@ -1127,7 +1149,7 @@ void BM_mesh_bm_to_me(Main *bmain, BMesh *bm, Mesh *me, const struct BMeshToMesh if (f->mat_nr != 0) { need_material_index = true; } - mpoly[i].flag = BM_face_flag_to_mflag(f); + mpoly[i].flag = bm_face_flag_to_mflag(f); if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) { need_hide_poly = true; } @@ -1287,6 +1309,197 @@ void BM_mesh_bm_to_me(Main *bmain, BMesh *bm, Mesh *me, const struct BMeshToMesh multires_topology_changed(me); } +namespace blender { + +static void bm_vert_table_build(BMesh &bm, + MutableSpan<const BMVert *> table, + bool &need_select_vert, + bool &need_hide_vert) +{ + char hflag = 0; + BMIter iter; + int i; + BMVert *vert; + BM_ITER_MESH_INDEX (vert, &iter, &bm, BM_VERTS_OF_MESH, i) { + BM_elem_index_set(vert, i); /* set_inline */ + table[i] = vert; + hflag |= vert->head.hflag; + } + need_select_vert |= (hflag & BM_ELEM_SELECT); + need_hide_vert |= (hflag & BM_ELEM_HIDDEN); +} + +static void bm_edge_table_build(BMesh &bm, + MutableSpan<const BMEdge *> table, + bool &need_select_edge, + bool &need_hide_edge, + bool &need_sharp_edge) +{ + char hflag = 0; + BMIter iter; + int i; + BMEdge *edge; + BM_ITER_MESH_INDEX (edge, &iter, &bm, BM_EDGES_OF_MESH, i) { + BM_elem_index_set(edge, i); /* set_inline */ + table[i] = edge; + hflag |= edge->head.hflag; + } + need_select_edge |= (hflag & BM_ELEM_SELECT); + need_hide_edge |= (hflag & BM_ELEM_HIDDEN); + need_sharp_edge |= (hflag & BM_ELEM_SMOOTH); +} + +static void bm_face_loop_table_build(BMesh &bm, + MutableSpan<const BMFace *> face_table, + MutableSpan<const BMLoop *> loop_table, + bool &need_select_poly, + bool &need_hide_poly, + bool &need_material_index) +{ + char hflag = 0; + BMIter iter; + int face_i = 0; + int loop_i = 0; + BMFace *face; + BM_ITER_MESH_INDEX (face, &iter, &bm, BM_FACES_OF_MESH, face_i) { + BM_elem_index_set(face, face_i); /* set_inline */ + face_table[face_i] = face; + hflag |= face->head.hflag; + need_material_index |= face->mat_nr != 0; + + BMLoop *loop = BM_FACE_FIRST_LOOP(face); + for ([[maybe_unused]] const int i : IndexRange(face->len)) { + BM_elem_index_set(loop, loop_i); /* set_inline */ + loop_table[loop_i] = loop; + loop = loop->next; + loop_i++; + } + } + need_select_poly |= (hflag & BM_ELEM_SELECT); + need_hide_poly |= (hflag & BM_ELEM_HIDDEN); +} + +static void bm_to_mesh_verts(const BMesh &bm, + const Span<const BMVert *> bm_verts, + Mesh &mesh, + MutableSpan<bool> select_vert, + MutableSpan<bool> hide_vert) +{ + MutableSpan<float3> dst_vert_positions = mesh.vert_positions_for_write(); + threading::parallel_for(dst_vert_positions.index_range(), 1024, [&](const IndexRange range) { + for (const int vert_i : range) { + const BMVert &src_vert = *bm_verts[vert_i]; + copy_v3_v3(dst_vert_positions[vert_i], src_vert.co); + CustomData_from_bmesh_block(&bm.vdata, &mesh.vdata, src_vert.head.data, vert_i); + } + if (!select_vert.is_empty()) { + for (const int vert_i : range) { + select_vert[vert_i] = BM_elem_flag_test(bm_verts[vert_i], BM_ELEM_SELECT); + } + } + if (!hide_vert.is_empty()) { + for (const int vert_i : range) { + hide_vert[vert_i] = BM_elem_flag_test(bm_verts[vert_i], BM_ELEM_HIDDEN); + } + } + }); +} + +static void bm_to_mesh_edges(const BMesh &bm, + const Span<const BMEdge *> bm_edges, + Mesh &mesh, + MutableSpan<bool> select_edge, + MutableSpan<bool> hide_edge, + MutableSpan<bool> sharp_edge) +{ + MutableSpan<MEdge> dst_edges = mesh.edges_for_write(); + threading::parallel_for(dst_edges.index_range(), 512, [&](const IndexRange range) { + for (const int edge_i : range) { + const BMEdge &src_edge = *bm_edges[edge_i]; + MEdge &dst_edge = dst_edges[edge_i]; + dst_edge.v1 = BM_elem_index_get(src_edge.v1); + dst_edge.v2 = BM_elem_index_get(src_edge.v2); + dst_edge.flag = bm_edge_flag_to_mflag(&src_edge); + + /* Handle this differently to editmode switching; only enable draw for single user + * edges rather than calculating angle. */ + if ((dst_edge.flag & ME_EDGEDRAW) == 0) { + if (src_edge.l && src_edge.l == src_edge.l->radial_next) { + dst_edge.flag |= ME_EDGEDRAW; + } + } + + CustomData_from_bmesh_block(&bm.edata, &mesh.edata, src_edge.head.data, edge_i); + } + if (!select_edge.is_empty()) { + for (const int edge_i : range) { + select_edge[edge_i] = BM_elem_flag_test(bm_edges[edge_i], BM_ELEM_SELECT); + } + } + if (!hide_edge.is_empty()) { + for (const int edge_i : range) { + hide_edge[edge_i] = BM_elem_flag_test(bm_edges[edge_i], BM_ELEM_HIDDEN); + } + } + if (!sharp_edge.is_empty()) { + for (const int edge_i : range) { + sharp_edge[edge_i] = !BM_elem_flag_test(bm_edges[edge_i], BM_ELEM_SMOOTH); + } + } + }); +} + +static void bm_to_mesh_faces(const BMesh &bm, + const Span<const BMFace *> bm_faces, + Mesh &mesh, + MutableSpan<bool> select_poly, + MutableSpan<bool> hide_poly, + MutableSpan<int> material_indices) +{ + MutableSpan<MPoly> dst_polys = mesh.polys_for_write(); + threading::parallel_for(dst_polys.index_range(), 1024, [&](const IndexRange range) { + for (const int face_i : range) { + const BMFace &src_face = *bm_faces[face_i]; + MPoly &dst_poly = dst_polys[face_i]; + dst_poly.totloop = src_face.len; + dst_poly.loopstart = BM_elem_index_get(BM_FACE @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list [email protected] List details, subscription details or unsubscribe: https://lists.blender.org/mailman/listinfo/bf-blender-cvs
