[Bf-blender-cvs] [97c3e5944c9] temp_bmesh_multires: Sculpt dyntopo: Finished bmesh cache coherency tester
Joseph Eagar
noreply at git.blender.org
Sun Aug 22 05:44:27 CEST 2021
Commit: 97c3e5944c90597edc3c775df5847adecbce1b3c
Author: Joseph Eagar
Date: Sat Aug 21 20:40:22 2021 -0700
Branches: temp_bmesh_multires
https://developer.blender.org/rB97c3e5944c90597edc3c775df5847adecbce1b3c
Sculpt dyntopo: Finished bmesh cache coherency tester
To run, in the python console enter:
bpy.msgbus.pbvh_bmesh_do_cache_test()
The output will be in the regular console. The test
build a half-million vert cube and smooths it. It runs
several passes (all of which perform the same smoothing
operation):
1; Randomized order pass
2. Ordered pass (by vertex clustering)
3. Same as 2 but with a purely data-oriented version
of the bmesh structs.
4. Same as 2, but using a version of the bmesh structs
with all pointers replaced by integer indices.
At least on my laptop #3 and #2 are about a third faster
then #1, and #2 tends to be around 15%.
===================================================================
M source/blender/blenkernel/intern/pbvh_bmesh.c
M source/blender/bmesh/intern/bmesh_mesh.c
M source/blender/modifiers/intern/MOD_correctivesmooth.c
===================================================================
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index 85ed314e370..13d322dbec7 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -1078,6 +1078,7 @@ static void pbvh_bmesh_normals_update_old(PBVHNode **nodes, int totnode)
struct FastNodeBuildInfo {
int totface; /* number of faces */
int start; /* start of faces in array */
+ int depth;
struct FastNodeBuildInfo *child1;
struct FastNodeBuildInfo *child2;
};
@@ -1092,7 +1093,7 @@ static void pbvh_bmesh_node_limit_ensure_fast(
{
struct FastNodeBuildInfo *child1, *child2;
- if (node->totface <= pbvh->leaf_limit) {
+ if (node->totface <= pbvh->leaf_limit || node->depth >= pbvh->depth_limit) {
return;
}
@@ -1174,8 +1175,12 @@ static void pbvh_bmesh_node_limit_ensure_fast(
child1->totface = num_child1;
child1->start = node->start;
+ child1->depth = node->depth + 1;
+
child2->totface = num_child2;
child2->start = node->start + num_child1;
+ child2->depth = node->depth + 2;
+
child1->child1 = child1->child2 = child2->child1 = child2->child2 = NULL;
pbvh_bmesh_node_limit_ensure_fast(pbvh, nodeinfo, bbc_array, child1, arena);
@@ -1186,6 +1191,7 @@ static void pbvh_bmesh_create_nodes_fast_recursive(
PBVH *pbvh, BMFace **nodeinfo, BBC *bbc_array, struct FastNodeBuildInfo *node, int node_index)
{
PBVHNode *n = pbvh->nodes + node_index;
+
/* two cases, node does not have children or does have children */
if (node->child1) {
int children_offset = pbvh->totnode;
@@ -2651,7 +2657,7 @@ typedef struct ReVertNode {
BMVert *verts[];
} ReVertNode;
-ATTR_NO_OPT BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
+BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
{
/*try to compute size of verts per node*/
int vsize = sizeof(BMVert);
@@ -2674,7 +2680,7 @@ ATTR_NO_OPT BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
int i = 0;
BM_ITER_MESH (v, &iter, pbvh->bm, BM_VERTS_OF_MESH) {
- BM_elem_flag_disable(v, flag);
+ v->head.hflag &= ~flag;
v->head.index = i++;
}
@@ -2682,7 +2688,7 @@ ATTR_NO_OPT BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
BLI_array_declare(stack);
BM_ITER_MESH (v, &iter, pbvh->bm, BM_VERTS_OF_MESH) {
- if (BM_elem_flag_test(v, flag)) {
+ if (v->head.hflag & flag) {
continue;
}
@@ -2691,7 +2697,7 @@ ATTR_NO_OPT BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
BLI_array_clear(stack);
BLI_array_append(stack, v);
- BM_elem_flag_enable(v, flag);
+ v->head.hflag |= flag;
vnodemap[v->head.index] = node;
node->verts[node->totvert++] = v;
@@ -2715,7 +2721,8 @@ ATTR_NO_OPT BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
BMVert *v3 = BM_edge_other_vert(e, v2);
if (!BM_elem_flag_test(v3, flag) && len < leaf_limit) {
- BM_elem_flag_enable(v3, flag);
+ v3->head.hflag |= flag;
+
vnodemap[v3->head.index] = node;
node->verts[node->totvert++] = v3;
@@ -2760,6 +2767,8 @@ ATTR_NO_OPT BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
ReVertNode *node2 = vnodemap[v2->head.index];
bool ok = node != node2 && !node2->parent;
+ ok = ok && parent->totchild < MAX_RE_CHILD;
+
for (int j = 0; j < parent->totchild; j++) {
if (parent->children[j] == node2) {
ok = false;
@@ -2769,17 +2778,13 @@ ATTR_NO_OPT BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
if (ok) {
parent->children[parent->totchild++] = node2;
+ node2->parent = parent;
break;
}
e = e->v1 == v ? e->v1_disk_link.next : e->v2_disk_link.next;
} while (e != v->e);
- if (parent->totchild == 1) {
- BLI_mempool_free(pool, parent);
- continue;
- }
-
if (last_step) {
BLI_array_append(roots, parent);
}
@@ -2935,10 +2940,10 @@ ATTR_NO_OPT BMesh *BKE_pbvh_reorder_bmesh(PBVH *pbvh)
lidx[i] = (uint)l->head.index;
}
- BM_mesh_remap(pbvh->bm, vidx, eidx, fidx, lidx);
-
printf("roots: %d\n", BLI_array_len(roots));
+ BM_mesh_remap(pbvh->bm, vidx, eidx, fidx, lidx);
+
MEM_SAFE_FREE(vidx);
MEM_SAFE_FREE(eidx);
MEM_SAFE_FREE(lidx);
@@ -3439,10 +3444,470 @@ static void *hashco(float fx, float fy, float fz, float fdimen)
return (void *)((intptr_t)(z * dimen * dimen + y * dimen + x));
}
+typedef struct MeshTest {
+ float (*v_co)[3];
+ float (*v_no)[3];
+ int *v_e;
+ int *v_index;
+ int *v_flag;
+
+ int *e_v1;
+ int *e_v2;
+ int *e_v1_next;
+ int *e_v2_next;
+ int *e_l;
+ int *e_flag;
+ int *e_index;
+
+ int *l_v;
+ int *l_e;
+ int *l_f;
+ int *l_next;
+ int *l_prev;
+ int *l_radial_next;
+ int *l_radial_prev;
+
+ int *f_l;
+ int *f_index;
+ int *f_flag;
+
+ int totvert, totedge, totloop, totface;
+ MemArena *arena;
+} MeshTest;
+
+typedef struct ElemHeader {
+ short type, hflag;
+ int index;
+ void *data;
+} ElemHeader;
+
+typedef struct MeshVert2 {
+ ElemHeader head;
+ float co[3];
+ float no[3];
+ int e;
+} MeshVert2;
+
+typedef struct MeshEdge2 {
+ ElemHeader head;
+ int v1, v2;
+ int v1_next, v2_next;
+ int l;
+} MeshEdge2;
+
+typedef struct MeshLoop2 {
+ ElemHeader head;
+ int v, e, f, next, prev;
+ int radial_next, radial_prev;
+} MeshLoop2;
+
+typedef struct MeshFace2 {
+ ElemHeader head;
+ int l, len;
+ float no[3];
+} MeshFace2;
+
+typedef struct MeshTest2 {
+ MeshVert2 *verts;
+ MeshEdge2 *edges;
+ MeshLoop2 *loops;
+ MeshFace2 *faces;
+
+ int totvert, totedge, totloop, totface;
+ MemArena *arena;
+} MeshTest2;
+
+static MeshTest2 *meshtest2_from_bm(BMesh *bm)
+{
+ MeshTest2 *m2 = MEM_callocN(sizeof(MeshTest2), "MeshTest2");
+ m2->arena = BLI_memarena_new(1024 * 32, "MeshTest2 arena");
+
+ m2->totvert = bm->totvert;
+ m2->totedge = bm->totedge;
+ m2->totloop = bm->totloop;
+ m2->totface = bm->totface;
+
+ BMVert *v;
+ BMEdge *e;
+ BMLoop *l;
+ BMFace *f;
+ BMIter iter;
+
+ int lindex = 0;
+
+ BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+ BMLoop *l = f->l_first;
+ do {
+ l->head.index = lindex++;
+ } while ((l = l->next) != f->l_first);
+ }
+
+ m2->totloop = lindex;
+
+ m2->verts = MEM_calloc_arrayN(bm->totvert, sizeof(MeshVert2), "MeshVert2s");
+ m2->edges = MEM_calloc_arrayN(bm->totedge, sizeof(MeshEdge2), "MeshEdge2s");
+ m2->loops = MEM_calloc_arrayN(m2->totloop, sizeof(MeshLoop2), "MeshLoop2s");
+ m2->faces = MEM_calloc_arrayN(bm->totface, sizeof(MeshFace2), "MeshFace2s");
+
+ bm->elem_index_dirty |= BM_VERT | BM_EDGE | BM_FACE;
+ BM_mesh_elem_index_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
+
+ BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
+ const int vi = v->head.index;
+
+ copy_v3_v3(m2->verts[vi].co, v->co);
+ copy_v3_v3(m2->verts[vi].no, v->no);
+
+ m2->verts[vi].e = v->e ? v->e->head.index : -1;
+ }
+
+ BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+ const ei = e->head.index;
+
+ m2->edges[ei].v1 = e->v1->head.index;
+ m2->edges[ei].v2 = e->v2->head.index;
+ m2->edges[ei].l = e->l ? e->l->head.index : -1;
+
+ m2->edges[ei].v1_next = e->v1_disk_link.next->head.index;
+ m2->edges[ei].v2_next = e->v2_disk_link.next->head.index;
+ }
+
+ BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+ int fi = f->head.index;
+
+ m2->faces[fi].len = f->len;
+ copy_v3_v3(m2->faces[fi].no, f->no);
+
+ BMLoop *l = f->l_first;
+ do {
+ int li = l->head.index;
+
+ m2->loops[li].v = l->v->head.index;
+ m2->loops[li].e = l->e->head.index;
+ m2->loops[li].f = l->f->head.index;
+
+ m2->loops[li].radial_next = l->radial_next->head.index;
+ m2->loops[li].radial_prev = l->radial_prev->head.index;
+
+ m2->loops[li].next = l->next->head.index;
+ m2->loops[li].prev = l->prev->head.index;
+ } while ((l = l->next) != f->l_first);
+ }
+
+ return m2;
+}
+
+static void free_meshtest2(MeshTest2 *m2)
+{
+ BLI_memarena_free(m2->arena);
+ MEM_freeN(m2);
+}
+
+static MeshTest *meshtest_from_bm(BMesh *bm)
+{
+ MeshTest *m = MEM_callocN(sizeof(MeshTest), "MeshTest");
+ m->arena = BLI_memarena_new(1024 * 32, "m->arena");
+
+ m->v_co = BLI_memarena_alloc(m->arena, bm->totvert * sizeof(*m->v_co));
+ m->v_no = BLI_memarena_alloc(m->arena, bm->totvert * sizeof(*m->v_no));
+ m->v_e = BLI_memarena_alloc(m->arena, bm->totvert * sizeof(*m->v_e));
+ m->v_flag = BLI_memarena_alloc(m->arena, bm->totvert * sizeof(*m->v_flag));
+ m->v_index = BLI_memarena_alloc(m->arena, bm->totvert * sizeof(*m->v_index));
+
+ m->e_v1 = BLI_memarena_alloc(m->arena, bm->totedge * sizeof(*m->e_v1));
+ m->e_v1_next = BLI_memarena_alloc(m->arena, bm->totedge * sizeof(*m->e_v1));
+ m->e_v2 = BLI_memarena_alloc(m->arena, bm->totedge * sizeof(*m->e_v1));
+ m->e_v2_next = BLI_memarena_alloc(m->arena, bm->totedge * sizeof(*m->e_v1));
+ m->e_l = BLI_memarena_alloc(m->arena, bm->totedge * sizeof(*m->e_v1));
+ m->e_index = BLI_memarena_alloc(m->arena, bm->totedge * sizeof(*m->e_v1));
+ m->e_flag = BLI_memarena_alloc(m->arena, bm->totedge * sizeof(*m->e_v1));
+
+ m->l_v = BLI_memarena_alloc(m->arena, bm->totloop * sizeof(*m->l_e));
+ m->l_e = BLI_memarena_alloc(m->arena, bm->totloop * sizeof(*m->l_e));
+ m->l_f = BLI_memarena_alloc(m->arena, bm->totloop * sizeof(*m->l_e));
+ m->l_next = BLI_memarena_alloc(m->arena, bm->totloop * sizeof(*m->l_e));
+ m->l_prev = BLI_memarena_alloc(m->arena, bm->totloop * sizeof(*m->l_e));
+ m->l_radial_next = BLI_memarena_alloc(m->arena, bm->totloop * sizeof(*m->l_e));
+ m->l_radial_prev = BLI_memarena_alloc(m->arena, bm->totloop * sizeof(*m->l_e));
+
+ m->f_l = BLI_memarena_alloc(m->arena, bm->totface * sizeof(*m->f_l));
+
+ m->totvert = bm->totvert;
+ m->totedge = bm->totedge;
+ m->totface = bm->totface;
+ m->totloop = bm->totloop;
+
+ BMVert *v;
+ BMEdge *e;
+ BMLoop *l;
+ BMFace *f;
+ BMIter iter;
+
+ int lindex = 0;
+
+ BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+ BMLoop *l = f->l_first;
+ do {
+ l->head.index = lindex++;
+ } while ((l = l->next) != f->l_first);
+ }
+
+ bm->elem_index_dirty |= BM_VERT | BM_EDGE | BM_FACE;
+ BM_mesh_elem_index_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
+
+ BM_IT
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list