[Bf-blender-cvs] [967664d1ee2] master: BLI: new C++ BitVector data structure
Jacques Lucke
noreply at git.blender.org
Wed Sep 7 13:16:05 CEST 2022
Commit: 967664d1ee2f40a85301b1a8ccdb0ba3fe811d5d
Author: Jacques Lucke
Date: Wed Sep 7 13:15:34 2022 +0200
Branches: master
https://developer.blender.org/rB967664d1ee2f40a85301b1a8ccdb0ba3fe811d5d
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
===================================================================
M source/blender/blenkernel/intern/mesh.cc
M source/blender/blenkernel/intern/mesh_normals.cc
A source/blender/blenlib/BLI_bit_vector.hh
M source/blender/blenlib/BLI_index_range.hh
M source/blender/blenlib/CMakeLists.txt
M source/blender/blenlib/intern/BLI_index_range.cc
A source/blender/blenlib/tests/BLI_bit_vector_test.cc
M source/blender/blenlib/tests/BLI_index_range_test.cc
===================================================================
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,
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list