From 9c35a5a5241b6db465e07d9b7548a2d462c76d5e Mon Sep 17 00:00:00 2001 From: Hans Goudey Date: Fri, 16 Sep 2022 14:31:01 -0500 Subject: Sculpt: Improve performance when initializing face sets Avoid conversion to `BMesh` for basic topology operations and data access. Instead use a mesh map to retrieve the faces connected to each edge. I observed performance improvements of 5x (600ms to 100ms) to 10x (15s to 1s), with bigger changes for large meshes with more data layers Switching to `std::queue` over Blender's `GSQueue` gave another 25% improvement. Differential Revision: https://developer.blender.org/D15988 --- .../editors/sculpt_paint/sculpt_face_set.cc | 261 +++++++++------------ 1 file changed, 114 insertions(+), 147 deletions(-) (limited to 'source/blender/editors') diff --git a/source/blender/editors/sculpt_paint/sculpt_face_set.cc b/source/blender/editors/sculpt_paint/sculpt_face_set.cc index 447972d74c2..7002ae7b358 100644 --- a/source/blender/editors/sculpt_paint/sculpt_face_set.cc +++ b/source/blender/editors/sculpt_paint/sculpt_face_set.cc @@ -7,12 +7,16 @@ #include #include +#include #include "MEM_guardedalloc.h" -#include "BLI_blenlib.h" +#include "BLI_bit_vector.hh" +#include "BLI_function_ref.hh" #include "BLI_hash.h" #include "BLI_math.h" +#include "BLI_math_vector.hh" +#include "BLI_span.hh" #include "BLI_task.h" #include "DNA_brush_types.h" @@ -22,6 +26,7 @@ #include "DNA_object_types.h" #include "DNA_scene_types.h" +#include "BKE_attribute.hh" #include "BKE_brush.h" #include "BKE_ccg.h" #include "BKE_colortools.h" @@ -510,178 +515,100 @@ static EnumPropertyItem prop_sculpt_face_sets_init_types[] = { {0, nullptr, 0, nullptr, nullptr}, }; -typedef bool (*face_sets_flood_fill_test)( - BMesh *bm, BMFace *from_f, BMEdge *from_e, BMFace *to_f, const float threshold); +using FaceSetsFloodFillFn = blender::FunctionRef; -static bool sculpt_face_sets_init_loose_parts_test(BMesh *UNUSED(bm), - BMFace *from_f, - BMEdge *UNUSED(from_e), - BMFace *to_f, - const float UNUSED(threshold)) -{ - return BM_elem_flag_test(from_f, BM_ELEM_HIDDEN) == BM_elem_flag_test(to_f, BM_ELEM_HIDDEN); -} - -static bool sculpt_face_sets_init_normals_test( - BMesh *UNUSED(bm), BMFace *from_f, BMEdge *UNUSED(from_e), BMFace *to_f, const float threshold) -{ - return fabsf(dot_v3v3(from_f->no, to_f->no)) > threshold; -} - -static bool sculpt_face_sets_init_uv_seams_test(BMesh *UNUSED(bm), - BMFace *UNUSED(from_f), - BMEdge *from_e, - BMFace *UNUSED(to_f), - const float UNUSED(threshold)) -{ - return !BM_elem_flag_test(from_e, BM_ELEM_SEAM); -} - -static bool sculpt_face_sets_init_crease_test( - BMesh *bm, BMFace *UNUSED(from_f), BMEdge *from_e, BMFace *UNUSED(to_f), const float threshold) -{ - return BM_elem_float_data_get(&bm->edata, from_e, CD_CREASE) < threshold; -} - -static bool sculpt_face_sets_init_bevel_weight_test( - BMesh *bm, BMFace *UNUSED(from_f), BMEdge *from_e, BMFace *UNUSED(to_f), const float threshold) -{ - return BM_elem_float_data_get(&bm->edata, from_e, CD_BWEIGHT) < threshold; -} - -static bool sculpt_face_sets_init_sharp_edges_test(BMesh *UNUSED(bm), - BMFace *UNUSED(from_f), - BMEdge *from_e, - BMFace *UNUSED(to_f), - const float UNUSED(threshold)) -{ - return BM_elem_flag_test(from_e, BM_ELEM_SMOOTH); -} - -static bool sculpt_face_sets_init_face_set_boundary_test( - BMesh *bm, BMFace *from_f, BMEdge *UNUSED(from_e), BMFace *to_f, const float UNUSED(threshold)) -{ - const int cd_face_sets_offset = CustomData_get_offset(&bm->pdata, CD_SCULPT_FACE_SETS); - return BM_ELEM_CD_GET_INT(from_f, cd_face_sets_offset) == - BM_ELEM_CD_GET_INT(to_f, cd_face_sets_offset); -} - -static void sculpt_face_sets_init_flood_fill(Object *ob, - face_sets_flood_fill_test test, - const float threshold) +static void sculpt_face_sets_init_flood_fill(Object *ob, const FaceSetsFloodFillFn &test_fn) { + using namespace blender; SculptSession *ss = ob->sculpt; Mesh *mesh = static_cast(ob->data); - BMesh *bm; - const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(mesh); - BMeshCreateParams create_params{}; - create_params.use_toolflags = true; - bm = BM_mesh_create(&allocsize, &create_params); - - BMeshFromMeshParams convert_params{}; - convert_params.calc_vert_normal = true; - convert_params.calc_face_normal = true; - BM_mesh_bm_from_me(bm, mesh, &convert_params); - BLI_bitmap *visited_faces = BLI_BITMAP_NEW(mesh->totpoly, "visited faces"); - const int totfaces = mesh->totpoly; + BitVector<> visited_faces(mesh->totpoly, false); int *face_sets = ss->face_sets; - BM_mesh_elem_table_init(bm, BM_FACE); - BM_mesh_elem_table_ensure(bm, BM_FACE); + const Span edges = mesh->edges(); + const Span polys = mesh->polys(); + const Span loops = mesh->loops(); + + if (!ss->epmap) { + BKE_mesh_edge_poly_map_create(&ss->epmap, + &ss->epmap_mem, + edges.data(), + edges.size(), + polys.data(), + polys.size(), + loops.data(), + loops.size()); + } int next_face_set = 1; - for (int i = 0; i < totfaces; i++) { - if (BLI_BITMAP_TEST(visited_faces, i)) { + for (const int i : polys.index_range()) { + if (visited_faces[i]) { continue; } - GSQueue *queue; - queue = BLI_gsqueue_new(sizeof(int)); + std::queue queue; face_sets[i] = next_face_set; - BLI_BITMAP_ENABLE(visited_faces, i); - BLI_gsqueue_push(queue, &i); - - while (!BLI_gsqueue_is_empty(queue)) { - int from_f; - BLI_gsqueue_pop(queue, &from_f); - - BMFace *f, *f_neighbor; - BMEdge *ed; - BMIter iter_a, iter_b; - - f = BM_face_at_index(bm, from_f); - - BM_ITER_ELEM (ed, &iter_a, f, BM_EDGES_OF_FACE) { - BM_ITER_ELEM (f_neighbor, &iter_b, ed, BM_FACES_OF_EDGE) { - if (f_neighbor == f) { + visited_faces[i].set(true); + queue.push(i); + + while (!queue.empty()) { + const int poly_i = queue.front(); + const MPoly &poly = polys[poly_i]; + queue.pop(); + + for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) { + const int edge_i = loop.e; + const Span neighbor_polys(ss->epmap[edge_i].indices, ss->epmap[edge_i].count); + for (const int neighbor_i : neighbor_polys) { + if (neighbor_i == poly_i) { continue; } - int neighbor_face_index = BM_elem_index_get(f_neighbor); - if (BLI_BITMAP_TEST(visited_faces, neighbor_face_index)) { + if (visited_faces[neighbor_i]) { continue; } - if (!test(bm, f, ed, f_neighbor, threshold)) { + if (!test_fn(poly_i, edge_i, neighbor_i)) { continue; } - face_sets[neighbor_face_index] = next_face_set; - BLI_BITMAP_ENABLE(visited_faces, neighbor_face_index); - BLI_gsqueue_push(queue, &neighbor_face_index); + face_sets[neighbor_i] = next_face_set; + visited_faces[neighbor_i].set(true); + queue.push(neighbor_i); } } } next_face_set += 1; - - BLI_gsqueue_free(queue); } - - MEM_SAFE_FREE(visited_faces); - - BM_mesh_free(bm); } static void sculpt_face_sets_init_loop(Object *ob, const int mode) { + using namespace blender; Mesh *mesh = static_cast(ob->data); SculptSession *ss = ob->sculpt; - BMesh *bm; - const BMAllocTemplate allocsize = BMALLOC_TEMPLATE_FROM_ME(mesh); - BMeshCreateParams create_params{}; - create_params.use_toolflags = true; - bm = BM_mesh_create(&allocsize, &create_params); - - BMeshFromMeshParams convert_params{}; - convert_params.calc_vert_normal = true; - convert_params.calc_face_normal = true; - BM_mesh_bm_from_me(bm, mesh, &convert_params); - BMIter iter; - BMFace *f; - - const int cd_fmaps_offset = CustomData_get_offset(&bm->pdata, CD_FACEMAP); - - BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { - if (mode == SCULPT_FACE_SETS_FROM_MATERIALS) { - ss->face_sets[BM_elem_index_get(f)] = (int)(f->mat_nr + 1); + if (mode == SCULPT_FACE_SETS_FROM_MATERIALS) { + const bke::AttributeAccessor attributes = mesh->attributes(); + const VArraySpan material_indices = attributes.lookup_or_default( + "material_index", ATTR_DOMAIN_FACE, 0); + for (const int i : IndexRange(mesh->totpoly)) { + ss->face_sets[i] = material_indices[i] + 1; } - else if (mode == SCULPT_FACE_SETS_FROM_FACE_MAPS) { - if (cd_fmaps_offset != -1) { - ss->face_sets[BM_elem_index_get(f)] = BM_ELEM_CD_GET_INT(f, cd_fmaps_offset) + 2; - } - else { - ss->face_sets[BM_elem_index_get(f)] = 1; - } + } + else if (mode == SCULPT_FACE_SETS_FROM_FACE_MAPS) { + const int *face_maps = static_cast(CustomData_get_layer(&mesh->pdata, CD_FACEMAP)); + for (const int i : IndexRange(mesh->totpoly)) { + ss->face_sets[i] = face_maps ? face_maps[i] : 1; } } - BM_mesh_free(bm); } static int sculpt_face_set_init_exec(bContext *C, wmOperator *op) { + using namespace blender; Object *ob = CTX_data_active_object(C); SculptSession *ss = ob->sculpt; Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C); @@ -711,36 +638,76 @@ static int sculpt_face_set_init_exec(bContext *C, wmOperator *op) Mesh *mesh = static_cast(ob->data); ss->face_sets = BKE_sculpt_face_sets_ensure(mesh); + const bke::AttributeAccessor attributes = mesh->attributes(); switch (mode) { - case SCULPT_FACE_SETS_FROM_LOOSE_PARTS: - sculpt_face_sets_init_flood_fill(ob, sculpt_face_sets_init_loose_parts_test, threshold); + case SCULPT_FACE_SETS_FROM_LOOSE_PARTS: { + const VArray hide_poly = attributes.lookup_or_default( + ".hide_poly", ATTR_DOMAIN_FACE, false); + sculpt_face_sets_init_flood_fill( + ob, [&](const int from_face, const int /*edge*/, const int to_face) { + return hide_poly[from_face] == hide_poly[to_face]; + }); break; - case SCULPT_FACE_SETS_FROM_MATERIALS: + } + case SCULPT_FACE_SETS_FROM_MATERIALS: { sculpt_face_sets_init_loop(ob, SCULPT_FACE_SETS_FROM_MATERIALS); break; - case SCULPT_FACE_SETS_FROM_NORMALS: - sculpt_face_sets_init_flood_fill(ob, sculpt_face_sets_init_normals_test, threshold); + } + case SCULPT_FACE_SETS_FROM_NORMALS: { + const Span poly_normals( + reinterpret_cast(BKE_mesh_poly_normals_ensure(mesh)), mesh->totpoly); + sculpt_face_sets_init_flood_fill( + ob, [&](const int from_face, const int /*edge*/, const int to_face) -> bool { + return std::abs(math::dot(poly_normals[from_face], poly_normals[to_face])) > threshold; + }); break; - case SCULPT_FACE_SETS_FROM_UV_SEAMS: - sculpt_face_sets_init_flood_fill(ob, sculpt_face_sets_init_uv_seams_test, threshold); + } + case SCULPT_FACE_SETS_FROM_UV_SEAMS: { + const Span edges = mesh->edges(); + sculpt_face_sets_init_flood_fill( + ob, [&](const int /*from_face*/, const int edge, const int /*to_face*/) -> bool { + return (edges[edge].flag & ME_SEAM) == 0; + }); break; - case SCULPT_FACE_SETS_FROM_CREASES: - sculpt_face_sets_init_flood_fill(ob, sculpt_face_sets_init_crease_test, threshold); + } + case SCULPT_FACE_SETS_FROM_CREASES: { + const Span edges = mesh->edges(); + sculpt_face_sets_init_flood_fill( + ob, [&](const int /*from_face*/, const int edge, const int /*to_face*/) -> bool { + return edges[edge].crease / 255.0f < threshold; + }); break; - case SCULPT_FACE_SETS_FROM_SHARP_EDGES: - sculpt_face_sets_init_flood_fill(ob, sculpt_face_sets_init_sharp_edges_test, threshold); + } + case SCULPT_FACE_SETS_FROM_SHARP_EDGES: { + const Span edges = mesh->edges(); + sculpt_face_sets_init_flood_fill( + ob, [&](const int /*from_face*/, const int edge, const int /*to_face*/) -> bool { + return (edges[edge].flag & ME_SHARP) == 0; + }); break; - case SCULPT_FACE_SETS_FROM_BEVEL_WEIGHT: - sculpt_face_sets_init_flood_fill(ob, sculpt_face_sets_init_bevel_weight_test, threshold); + } + case SCULPT_FACE_SETS_FROM_BEVEL_WEIGHT: { + const float *bevel_weights = static_cast( + CustomData_get_layer(&mesh->edata, CD_BWEIGHT)); + sculpt_face_sets_init_flood_fill( + ob, [&](const int /*from_face*/, const int edge, const int /*to_face*/) -> bool { + return bevel_weights ? bevel_weights[edge] / 255.0f < threshold : true; + }); break; - case SCULPT_FACE_SETS_FROM_FACE_SET_BOUNDARIES: + } + case SCULPT_FACE_SETS_FROM_FACE_SET_BOUNDARIES: { + Array face_sets_copy(Span(ss->face_sets, mesh->totpoly)); sculpt_face_sets_init_flood_fill( - ob, sculpt_face_sets_init_face_set_boundary_test, threshold); + ob, [&](const int from_face, const int /*edge*/, const int to_face) -> bool { + return face_sets_copy[from_face] == face_sets_copy[to_face]; + }); break; - case SCULPT_FACE_SETS_FROM_FACE_MAPS: + } + case SCULPT_FACE_SETS_FROM_FACE_MAPS: { sculpt_face_sets_init_loop(ob, SCULPT_FACE_SETS_FROM_FACE_MAPS); break; + } } SCULPT_undo_push_end(ob); -- cgit v1.2.3