From 967664d1ee2f40a85301b1a8ccdb0ba3fe811d5d Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Wed, 7 Sep 2022 13:15:34 +0200 Subject: BLI: new C++ BitVector data structure This adds a new `blender::BitVector` data structure that was requested a couple of times. It also replaces usages of `BLI_bitmap` in C++ code. See the comment in `BLI_bit_vector.hh` for more details about the advantages and disadvantages of using a bit-vector and how the new data structure compares to `std::vector` and `BLI_bitmap`. Differential Revision: https://developer.blender.org/D14006 --- source/blender/blenkernel/intern/mesh.cc | 27 ++++++------ source/blender/blenkernel/intern/mesh_normals.cc | 55 ++++++++++++------------ 2 files changed, 39 insertions(+), 43 deletions(-) (limited to 'source/blender/blenkernel') diff --git a/source/blender/blenkernel/intern/mesh.cc b/source/blender/blenkernel/intern/mesh.cc index 361eb9bcbbe..1bf068fcd45 100644 --- a/source/blender/blenkernel/intern/mesh.cc +++ b/source/blender/blenkernel/intern/mesh.cc @@ -17,7 +17,7 @@ #include "DNA_meshdata_types.h" #include "DNA_object_types.h" -#include "BLI_bitmap.h" +#include "BLI_bit_vector.hh" #include "BLI_edgehash.h" #include "BLI_endian_switch.h" #include "BLI_ghash.h" @@ -64,6 +64,7 @@ #include "BLO_read_write.h" +using blender::BitVector; using blender::float3; using blender::MutableSpan; using blender::Span; @@ -1892,8 +1893,8 @@ static int split_faces_prepare_new_verts(Mesh *mesh, BKE_mesh_vertex_normals_ensure(mesh); float(*vert_normals)[3] = BKE_mesh_vertex_normals_for_write(mesh); - BLI_bitmap *verts_used = BLI_BITMAP_NEW(verts_len, __func__); - BLI_bitmap *done_loops = BLI_BITMAP_NEW(loops_len, __func__); + BitVector<> verts_used(verts_len, false); + BitVector<> done_loops(loops_len, false); MLoop *ml = loops.data(); MLoopNorSpace **lnor_space = lnors_spacearr->lspacearr; @@ -1901,9 +1902,9 @@ static int split_faces_prepare_new_verts(Mesh *mesh, BLI_assert(lnors_spacearr->data_type == MLNOR_SPACEARR_LOOP_INDEX); for (int loop_idx = 0; loop_idx < loops_len; loop_idx++, ml++, lnor_space++) { - if (!BLI_BITMAP_TEST(done_loops, loop_idx)) { + if (!done_loops[loop_idx]) { const int vert_idx = ml->v; - const bool vert_used = BLI_BITMAP_TEST_BOOL(verts_used, vert_idx); + const bool vert_used = verts_used[vert_idx]; /* If vert is already used by another smooth fan, we need a new vert for this one. */ const int new_vert_idx = vert_used ? verts_len++ : vert_idx; @@ -1912,7 +1913,7 @@ static int split_faces_prepare_new_verts(Mesh *mesh, if ((*lnor_space)->flags & MLNOR_SPACE_IS_SINGLE) { /* Single loop in this fan... */ BLI_assert(POINTER_AS_INT((*lnor_space)->loops) == loop_idx); - BLI_BITMAP_ENABLE(done_loops, loop_idx); + done_loops[loop_idx].set(); if (vert_used) { ml->v = new_vert_idx; } @@ -1920,7 +1921,7 @@ static int split_faces_prepare_new_verts(Mesh *mesh, else { for (LinkNode *lnode = (*lnor_space)->loops; lnode; lnode = lnode->next) { const int ml_fan_idx = POINTER_AS_INT(lnode->link); - BLI_BITMAP_ENABLE(done_loops, ml_fan_idx); + done_loops[ml_fan_idx].set(); if (vert_used) { loops[ml_fan_idx].v = new_vert_idx; } @@ -1928,7 +1929,7 @@ static int split_faces_prepare_new_verts(Mesh *mesh, } if (!vert_used) { - BLI_BITMAP_ENABLE(verts_used, vert_idx); + verts_used[vert_idx].set(); /* We need to update that vertex's normal here, we won't go over it again. */ /* This is important! *DO NOT* set vnor to final computed lnor, * vnor should always be defined to 'automatic normal' value computed from its polys, @@ -1949,9 +1950,6 @@ static int split_faces_prepare_new_verts(Mesh *mesh, } } - MEM_freeN(done_loops); - MEM_freeN(verts_used); - return verts_len - mesh->totvert; } @@ -1967,7 +1965,7 @@ static int split_faces_prepare_new_edges(Mesh *mesh, MutableSpan loops = mesh->loops_for_write(); const Span polys = mesh->polys(); - BLI_bitmap *edges_used = BLI_BITMAP_NEW(num_edges, __func__); + BitVector<> edges_used(num_edges, false); EdgeHash *edges_hash = BLI_edgehash_new_ex(__func__, num_edges); const MPoly *mp = polys.data(); @@ -1980,7 +1978,7 @@ static int split_faces_prepare_new_edges(Mesh *mesh, const int edge_idx = ml_prev->e; /* That edge has not been encountered yet, define it. */ - if (BLI_BITMAP_TEST(edges_used, edge_idx)) { + if (edges_used[edge_idx]) { /* Original edge has already been used, we need to define a new one. */ const int new_edge_idx = num_edges++; *eval = POINTER_FROM_INT(new_edge_idx); @@ -2000,7 +1998,7 @@ static int split_faces_prepare_new_edges(Mesh *mesh, edges[edge_idx].v1 = ml_prev->v; edges[edge_idx].v2 = ml->v; *eval = POINTER_FROM_INT(edge_idx); - BLI_BITMAP_ENABLE(edges_used, edge_idx); + edges_used[edge_idx].set(); } } else { @@ -2012,7 +2010,6 @@ static int split_faces_prepare_new_edges(Mesh *mesh, } } - MEM_freeN(edges_used); BLI_edgehash_free(edges_hash, nullptr); return num_edges - mesh->totedge; diff --git a/source/blender/blenkernel/intern/mesh_normals.cc b/source/blender/blenkernel/intern/mesh_normals.cc index 706026f072b..a88ff4e9d90 100644 --- a/source/blender/blenkernel/intern/mesh_normals.cc +++ b/source/blender/blenkernel/intern/mesh_normals.cc @@ -17,8 +17,7 @@ #include "DNA_meshdata_types.h" #include "BLI_alloca.h" -#include "BLI_bitmap.h" - +#include "BLI_bit_vector.hh" #include "BLI_linklist.h" #include "BLI_linklist_stack.h" #include "BLI_math.h" @@ -37,6 +36,7 @@ #include "atomic_ops.h" +using blender::BitVector; using blender::MutableSpan; using blender::Span; @@ -856,7 +856,10 @@ static void mesh_edges_sharp_tag(LoopSplitTaskDataCommon *data, int(*edge_to_loops)[2] = data->edge_to_loops; int *loop_to_poly = data->loop_to_poly; - BLI_bitmap *sharp_edges = do_sharp_edges_tag ? BLI_BITMAP_NEW(numEdges, __func__) : nullptr; + BitVector sharp_edges; + if (do_sharp_edges_tag) { + sharp_edges.resize(numEdges, false); + } const MPoly *mp; int mp_index; @@ -908,7 +911,7 @@ static void mesh_edges_sharp_tag(LoopSplitTaskDataCommon *data, /* We want to avoid tagging edges as sharp when it is already defined as such by * other causes than angle threshold. */ if (do_sharp_edges_tag && is_angle_sharp) { - BLI_BITMAP_SET(sharp_edges, ml_curr->e, true); + sharp_edges[ml_curr->e].set(); } } else { @@ -922,7 +925,7 @@ static void mesh_edges_sharp_tag(LoopSplitTaskDataCommon *data, /* We want to avoid tagging edges as sharp when it is already defined as such by * other causes than angle threshold. */ if (do_sharp_edges_tag) { - BLI_BITMAP_SET(sharp_edges, ml_curr->e, false); + sharp_edges[ml_curr->e].reset(); } } /* Else, edge is already 'disqualified' (i.e. sharp)! */ @@ -934,12 +937,10 @@ static void mesh_edges_sharp_tag(LoopSplitTaskDataCommon *data, MEdge *me; int me_index; for (me = (MEdge *)medges, me_index = 0; me_index < numEdges; me++, me_index++) { - if (BLI_BITMAP_TEST(sharp_edges, me_index)) { + if (sharp_edges[me_index]) { me->flag |= ME_SHARP; } } - - MEM_freeN(sharp_edges); } } @@ -1361,7 +1362,7 @@ static bool loop_split_generator_check_cyclic_smooth_fan(const MLoop *mloops, const int (*edge_to_loops)[2], const int *loop_to_poly, const int *e2l_prev, - BLI_bitmap *skip_loops, + BitVector<> &skip_loops, const MLoop *ml_curr, const MLoop *ml_prev, const int ml_curr_index, @@ -1390,8 +1391,8 @@ static bool loop_split_generator_check_cyclic_smooth_fan(const MLoop *mloops, BLI_assert(mlfan_vert_index >= 0); BLI_assert(mpfan_curr_index >= 0); - BLI_assert(!BLI_BITMAP_TEST(skip_loops, mlfan_vert_index)); - BLI_BITMAP_ENABLE(skip_loops, mlfan_vert_index); + BLI_assert(!skip_loops[mlfan_vert_index]); + skip_loops[mlfan_vert_index].set(); while (true) { /* Find next loop of the smooth fan. */ @@ -1412,7 +1413,7 @@ static bool loop_split_generator_check_cyclic_smooth_fan(const MLoop *mloops, return false; } /* Smooth loop/edge. */ - if (BLI_BITMAP_TEST(skip_loops, mlfan_vert_index)) { + if (skip_loops[mlfan_vert_index]) { if (mlfan_vert_index == ml_curr_index) { /* We walked around a whole cyclic smooth fan without finding any already-processed loop, * means we can use initial `ml_curr` / `ml_prev` edge as start for this smooth fan. */ @@ -1423,7 +1424,7 @@ static bool loop_split_generator_check_cyclic_smooth_fan(const MLoop *mloops, } /* We can skip it in future, and keep checking the smooth fan. */ - BLI_BITMAP_ENABLE(skip_loops, mlfan_vert_index); + skip_loops[mlfan_vert_index].set(); } } @@ -1447,7 +1448,7 @@ static void loop_split_generator(TaskPool *pool, LoopSplitTaskDataCommon *common int ml_curr_index; int ml_prev_index; - BLI_bitmap *skip_loops = BLI_BITMAP_NEW(numLoops, __func__); + BitVector<> skip_loops(numLoops, false); LoopSplitTaskData *data_buff = nullptr; int data_idx = 0; @@ -1489,7 +1490,7 @@ static void loop_split_generator(TaskPool *pool, LoopSplitTaskDataCommon *common ml_curr->e, ml_curr->v, IS_EDGE_SHARP(e2l_curr), - BLI_BITMAP_TEST_BOOL(skip_loops, ml_curr_index)); + skip_loops[ml_curr_index]); #endif /* A smooth edge, we have to check for cyclic smooth fan case. @@ -1502,7 +1503,7 @@ static void loop_split_generator(TaskPool *pool, LoopSplitTaskDataCommon *common * However, this would complicate the code, add more memory usage, and despite its logical * complexity, #loop_manifold_fan_around_vert_next() is quite cheap in term of CPU cycles, * so really think it's not worth it. */ - if (!IS_EDGE_SHARP(e2l_curr) && (BLI_BITMAP_TEST(skip_loops, ml_curr_index) || + if (!IS_EDGE_SHARP(e2l_curr) && (skip_loops[ml_curr_index] || !loop_split_generator_check_cyclic_smooth_fan(mloops, mpolys, edge_to_loops, @@ -1597,7 +1598,6 @@ static void loop_split_generator(TaskPool *pool, LoopSplitTaskDataCommon *common if (edge_vectors) { BLI_stack_free(edge_vectors); } - MEM_freeN(skip_loops); #ifdef DEBUG_TIME TIMEIT_END_AVERAGED(loop_split_generator); @@ -1778,7 +1778,7 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, * (and perhaps from some editing tools later?). * So better to keep some simplicity here, and just call #BKE_mesh_normals_loop_split() twice! */ MLoopNorSpaceArray lnors_spacearr = {nullptr}; - BLI_bitmap *done_loops = BLI_BITMAP_NEW((size_t)numLoops, __func__); + BitVector<> done_loops(numLoops, false); float(*lnors)[3] = (float(*)[3])MEM_calloc_arrayN((size_t)numLoops, sizeof(*lnors), __func__); int *loop_to_poly = (int *)MEM_malloc_arrayN((size_t)numLoops, sizeof(int), __func__); /* In this case we always consider split nors as ON, @@ -1836,14 +1836,14 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, /* This should not happen in theory, but in some rare case (probably ugly geometry) * we can get some nullptr loopspacearr at this point. :/ * Maybe we should set those loops' edges as sharp? */ - BLI_BITMAP_ENABLE(done_loops, i); + done_loops[i].set(); if (G.debug & G_DEBUG) { printf("WARNING! Getting invalid nullptr loop space for loop %d!\n", i); } continue; } - if (!BLI_BITMAP_TEST(done_loops, i)) { + if (!done_loops[i]) { /* Notes: * - In case of mono-loop smooth fan, we have nothing to do. * - Loops in this linklist are ordered (in reversed order compared to how they were @@ -1854,7 +1854,7 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, * to avoid small differences adding up into a real big one in the end! */ if (lnors_spacearr.lspacearr[i]->flags & MLNOR_SPACE_IS_SINGLE) { - BLI_BITMAP_ENABLE(done_loops, i); + done_loops[i].set(); continue; } @@ -1886,7 +1886,7 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, prev_ml = ml; loops = loops->next; - BLI_BITMAP_ENABLE(done_loops, lidx); + done_loops[lidx].set(); } /* We also have to check between last and first loops, @@ -1930,14 +1930,14 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, loop_to_poly); } else { - BLI_bitmap_set_all(done_loops, true, (size_t)numLoops); + done_loops.fill(true); } /* And we just have to convert plain object-space custom normals to our * lnor space-encoded ones. */ for (int i = 0; i < numLoops; i++) { if (!lnors_spacearr.lspacearr[i]) { - BLI_BITMAP_DISABLE(done_loops, i); + done_loops[i].reset(); if (G.debug & G_DEBUG) { printf("WARNING! Still getting invalid nullptr loop space in second loop for loop %d!\n", i); @@ -1945,7 +1945,7 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, continue; } - if (BLI_BITMAP_TEST_BOOL(done_loops, i)) { + if (done_loops[i]) { /* Note we accumulate and average all custom normals in current smooth fan, * to avoid getting different clnors data (tiny differences in plain custom normals can * give rather huge differences in computed 2D factors). */ @@ -1956,7 +1956,7 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, float *nor = r_custom_loopnors[nidx]; BKE_lnor_space_custom_normal_to_data(lnors_spacearr.lspacearr[i], nor, r_clnors_data[i]); - BLI_BITMAP_DISABLE(done_loops, i); + done_loops[i].reset(); } else { int avg_nor_count = 0; @@ -1974,7 +1974,7 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, BLI_SMALLSTACK_PUSH(clnors_data, (short *)r_clnors_data[lidx]); loops = loops->next; - BLI_BITMAP_DISABLE(done_loops, lidx); + done_loops[lidx].reset(); } mul_v3_fl(avg_nor, 1.0f / (float)avg_nor_count); @@ -1990,7 +1990,6 @@ static void mesh_normals_loop_custom_set(const MVert *mverts, MEM_freeN(lnors); MEM_freeN(loop_to_poly); - MEM_freeN(done_loops); BKE_lnor_spacearr_free(&lnors_spacearr); } -- cgit v1.2.3