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<bool>` and `BLI_bitmap`.

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

2 files changed, 39 insertions, 43 deletions

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<MLoop> loops = mesh->loops_for_write();
   const Span<MPoly> 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);
 }