[Bf-blender-cvs] [7fca310f25e] temp_bmesh_multires: Dyntopo now updates the existing pbvh on undo instead of building a new one from scratch, an operation that can be slow despite being threaded.
Joseph Eagar
noreply at git.blender.org
Sun May 16 06:28:10 CEST 2021
Commit: 7fca310f25e3ac2c434dd05a2eaf55b6c82f3922
Author: Joseph Eagar
Date: Sat May 15 21:19:20 2021 -0700
Branches: temp_bmesh_multires
https://developer.blender.org/rB7fca310f25e3ac2c434dd05a2eaf55b6c82f3922
Dyntopo now updates the existing pbvh on undo instead of building
a new one from scratch, an operation that can be slow despite being
threaded.
PBVH building is a memory bound operation (not just on the CPU side
either, remember the draw buffers have to be fully regenerated too).
Incrementally updating it this way is enormously faster (about as fast
as non-dyntopo undo).
The downside is we don't have the convienience of users regularly
building the pbvh from scratch anymore. Dyntopo does try to
join empty PBVH nodes (which happens after every stroke), but
that's not a complete substitute for a decent tree balancer.
That's on the todo list.
===================================================================
M source/blender/blenkernel/BKE_pbvh.h
M source/blender/blenkernel/intern/pbvh_bmesh.c
M source/blender/bmesh/intern/bmesh_log.c
M source/blender/bmesh/intern/bmesh_log.h
M source/blender/draw/intern/draw_manager_data.c
M source/blender/editors/sculpt_paint/sculpt_dyntopo.c
M source/blender/editors/sculpt_paint/sculpt_face_set.c
M source/blender/editors/sculpt_paint/sculpt_undo.c
M source/blender/gpu/GPU_buffers.h
M source/blender/gpu/intern/gpu_buffers.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index f75f1491d68..f2c8cb1eade 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -68,6 +68,7 @@ typedef struct PBVHTriBuf {
// private field
intptr_t *loops;
int totloop;
+ float min[3], max[3];
} PBVHTriBuf;
struct BMLog;
@@ -702,7 +703,10 @@ void BKE_pbvh_bmesh_free_tris(PBVH *pbvh, PBVHNode *node);
/*recalculates boundary flags for *all* vertices. used by
symmetrize.*/
void BKE_pbvh_recalc_bmesh_boundary(PBVH *pbvh);
-void BKE_pbvh_bmesh_face_kill(PBVH *pbvh, struct BMFace *f);
+
+void BKE_pbvh_bmesh_remove_face(PBVH *pbvh, struct BMFace *f, bool log_face);
+void BKE_pbvh_bmesh_remove_vertex(PBVH *pbvh, struct BMVert *v, bool log_vert);
+void BKE_pbvh_bmesh_add_face(PBVH *pbvh, struct BMFace *f, bool log_face, bool force_tree_walk);
// note that e_tri and f_example are allowed to be NULL
struct BMFace *BKE_pbvh_face_create_bmesh(PBVH *pbvh,
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index 0b812bdaa99..7758a84e9e8 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -1021,11 +1021,14 @@ static void pbvh_bmesh_vert_remove(PBVH *pbvh, BMVert *v)
{
/* never match for first time */
int f_node_index_prev = DYNTOPO_NODE_NONE;
+ const int updateflag = PBVH_UpdateDrawBuffers | PBVH_UpdateBB | PBVH_UpdateTris |
+ PBVH_UpdateNormals;
PBVHNode *v_node = pbvh_bmesh_node_from_vert(pbvh, v);
if (v_node) {
BLI_table_gset_remove(v_node->bm_unique_verts, v, NULL);
+ v_node->flag |= updateflag;
}
BM_ELEM_CD_SET_INT(v, pbvh->cd_vert_node_offset, DYNTOPO_NODE_NONE);
@@ -1045,7 +1048,7 @@ static void pbvh_bmesh_vert_remove(PBVH *pbvh, BMVert *v)
f_node_index_prev = f_node_index;
PBVHNode *f_node = &pbvh->nodes[f_node_index];
- f_node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB | PBVH_UpdateTris;
+ f_node->flag |= updateflag;
/* Remove current ownership */
BLI_table_gset_remove(f_node->bm_other_verts, v, NULL);
@@ -1057,15 +1060,16 @@ static void pbvh_bmesh_vert_remove(PBVH *pbvh, BMVert *v)
BM_FACES_OF_VERT_ITER_END;
}
-static void pbvh_bmesh_face_remove(PBVH *pbvh, BMFace *f)
+static void pbvh_bmesh_face_remove(PBVH *pbvh, BMFace *f, bool log_face)
{
PBVHNode *f_node = pbvh_bmesh_node_from_face(pbvh, f);
- if (!f_node) {
+ if (!f_node || !(f_node->flag & PBVH_Leaf)) {
printf("pbvh corruption\n");
fflush(stdout);
return;
}
+
/* Check if any of this face's vertices need to be removed
* from the node */
BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
@@ -1083,6 +1087,10 @@ static void pbvh_bmesh_face_remove(PBVH *pbvh, BMFace *f)
if (new_node) {
pbvh_bmesh_vert_ownership_transfer(pbvh, new_node, v);
}
+ else {
+ BM_ELEM_CD_SET_INT(v, pbvh->cd_vert_node_offset, DYNTOPO_NODE_NONE);
+ BLI_table_gset_remove(f_node->bm_unique_verts, v, NULL);
+ }
}
else {
/* Remove from other verts */
@@ -1096,16 +1104,204 @@ static void pbvh_bmesh_face_remove(PBVH *pbvh, BMFace *f)
BM_ELEM_CD_SET_INT(f, pbvh->cd_face_node_offset, DYNTOPO_NODE_NONE);
/* Log removed face */
- BM_log_face_removed(pbvh->bm_log, f);
+ if (log_face) {
+ BM_log_face_removed(pbvh->bm_log, f);
+ }
/* mark node for update */
f_node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateNormals | PBVH_UpdateTris;
}
-void BKE_pbvh_bmesh_face_kill(PBVH *pbvh, BMFace *f)
+void BKE_pbvh_bmesh_remove_face(PBVH *pbvh, BMFace *f, bool log_face)
+{
+ pbvh_bmesh_face_remove(pbvh, f, log_face);
+}
+
+void BKE_pbvh_bmesh_remove_vertex(PBVH *pbvh, BMVert *v, bool log_vert)
+{
+ pbvh_bmesh_vert_remove(pbvh, v);
+
+ if (log_vert) {
+ BM_log_vert_removed(pbvh->bm_log, v, pbvh->cd_vert_mask_offset);
+ }
+}
+
+static bool point_in_node(const PBVHNode *node, const float co[3])
+{
+ return co[0] >= node->vb.bmin[0] && co[0] <= node->vb.bmax[0] && co[1] >= node->vb.bmin[1] &&
+ co[1] <= node->vb.bmax[1] && co[2] >= node->vb.bmin[2] && co[2] <= node->vb.bmax[2];
+}
+
+static void bke_pbvh_insert_face_finalize(PBVH *pbvh, BMFace *f, const int ni)
{
- pbvh_bmesh_face_remove(pbvh, f);
- BM_face_kill(pbvh->bm, f);
+ PBVHNode *node = pbvh->nodes + ni;
+ BM_ELEM_CD_SET_INT(f, pbvh->cd_face_node_offset, ni);
+
+ BLI_table_gset_add(node->bm_faces, f);
+
+ int updateflag = PBVH_UpdateTris | PBVH_UpdateBB | PBVH_UpdateDrawBuffers |
+ PBVH_UpdateCurvatureDir;
+ updateflag |= PBVH_UpdateColor | PBVH_UpdateMask | PBVH_UpdateNormals | PBVH_UpdateOriginalBB;
+ updateflag |= PBVH_UpdateVisibility | PBVH_UpdateRedraw;
+
+ node->flag |= updateflag;
+
+ // ensure verts are in pbvh
+ BMLoop *l = f->l_first;
+ do {
+ const int ni2 = BM_ELEM_CD_GET_INT(l->v, pbvh->cd_vert_node_offset);
+ MDynTopoVert *mv = BKE_PBVH_DYNVERT(pbvh->cd_dyn_vert, l->v);
+
+ BB_expand(&node->vb, l->v->co);
+ BB_expand(&node->orig_vb, mv->origco);
+
+ if (ni2 == DYNTOPO_NODE_NONE) {
+ BM_ELEM_CD_SET_INT(l->v, pbvh->cd_vert_node_offset, ni);
+ BLI_table_gset_add(node->bm_unique_verts, l->v);
+ }
+ else {
+ PBVHNode *node2 = pbvh->nodes + ni2;
+
+ BLI_table_gset_add(node->bm_other_verts, l->v);
+
+ node2->flag |= updateflag;
+
+ BB_expand(&node2->vb, l->v->co);
+ BB_expand(&node2->orig_vb, mv->origco);
+ }
+ l = l->next;
+ } while (l != f->l_first);
+}
+
+static void bke_pbvh_insert_face(PBVH *pbvh, struct BMFace *f)
+{
+ int i = 0;
+ bool ok = false;
+ int ni = -1;
+
+#if 1
+ while (i < pbvh->totnode) {
+ PBVHNode *node = pbvh->nodes + i;
+ bool ok2 = false;
+
+ if (node->flag & PBVH_Leaf) {
+ ok = true;
+ ni = i;
+ break;
+ }
+
+ if (node->children_offset == 0) {
+ continue;
+ }
+
+ for (int j = 0; j < 2; j++) {
+ int ni2 = node->children_offset + j;
+ if (ni2 == 0) {
+ continue;
+ }
+
+ PBVHNode *node2 = pbvh->nodes + ni2;
+ BMLoop *l = f->l_first;
+
+ do {
+ if (point_in_node(node2, l->v->co)) {
+ i = ni2;
+ ok2 = true;
+ break;
+ }
+
+ l = l->next;
+ } while (l != f->l_first);
+
+ if (ok2) {
+ break;
+ }
+ }
+
+ if (!ok2) {
+ break;
+ }
+ }
+#endif
+
+ if (!ok) {
+ // find closest node
+ float co[3];
+ int tot = 0;
+ BMLoop *l = f->l_first;
+
+ zero_v3(co);
+
+ do {
+ add_v3_v3(co, l->v->co);
+ l = l->next;
+ tot++;
+ } while (l != f->l_first);
+
+ mul_v3_fl(co, 1.0f / (float)tot);
+ float mindis = 1e17;
+
+ for (int i = 0; i < pbvh->totnode; i++) {
+ PBVHNode *node = pbvh->nodes + i;
+
+ if (!(node->flag & PBVH_Leaf)) {
+ continue;
+ }
+
+ float cent[3];
+ add_v3_v3v3(cent, node->vb.bmin, node->vb.bmax);
+ mul_v3_fl(cent, 0.5f);
+
+ float dis = len_squared_v3v3(co, cent);
+ if (dis < mindis) {
+ mindis = dis;
+ ni = i;
+ }
+ }
+ }
+
+ if (ni < 0) {
+ fprintf(stderr, "pbvh error!\n");
+ fflush(stderr);
+ return;
+ }
+
+ bke_pbvh_insert_face_finalize(pbvh, f, ni);
+}
+
+void BKE_pbvh_bmesh_add_face(PBVH *pbvh, struct BMFace *f, bool log_face, bool force_tree_walk)
+{
+ int ni = -1;
+
+ // look for node in surrounding geometry
+ BMLoop *l = f->l_first;
+ do {
+ ni = BM_ELEM_CD_GET_INT(l->radial_next->f, pbvh->cd_face_node_offset);
+
+ if (ni >= 0 && (!(pbvh->nodes[ni].flag & PBVH_Leaf) || ni >= pbvh->totnode)) {
+ printf("EEK! ni: %d totnode: %d\n", ni, pbvh->totnode);
+ l = l->next;
+ continue;
+ }
+
+ if (ni >= 0 && (pbvh->nodes[ni].flag & PBVH_Leaf)) {
+ break;
+ }
+
+ l = l->next;
+ } while (l != f->l_first);
+
+ if (ni < 0 || force_tree_walk) {
+ bke_pbvh_insert_face(pbvh, f);
+ }
+ else {
+ BM_ELEM_CD_SET_INT(f, pbvh->cd_face_node_offset, ni);
+ bke_pbvh_insert_face_finalize(pbvh, f, ni);
+ }
+
+ if (log_face) {
+ BM_log_face_added(pbvh->bm_log, f);
+ }
}
static void pbvh_bmesh_edge_loops(BLI_Buffer *buf, BMEdge *e)
@@ -1770,7 +1966,7 @@ static void long_edge_queue_edge_add_recursive(EdgeQueueContext *eq_ctx,
BMLoop *l_iter = l_edge;
do {
BMLoop *l_adjacent[2] = {l_iter->next, l_iter->prev};
- for (int i = 0; i < ARRAY_SIZE(l_adjacent); i++) {
+ for (int i = 0; i < (int)ARRAY_SIZE(l_adjacent); i++) {
float len_sq_other = BM_edge_calc_length_squared(l_adjacent[i]->e);
if (len_sq_other > max_ff(len_sq_cmp, limit_len_sq)) {
// edge_queue_insert(eq_ctx, l_adjacent[i]->e, -len_sq_other);
@@ -1892,7 +2088,7 @@ static void short_edge_queue_edge_add_recursive_2(EdgeQueueThreadData *tdata,
BMLoop *l_iter = l_edge;
do {
BMLoop *l_adjacent[2] = {l_iter->next, l_iter->prev};
- for (int i = 0; i < ARRAY_SIZE(l_adjacent); i++) {
+ for (int i = 0; i < (int)ARRAY_SIZE(l_adjacent); i++) {
float len_sq_other = calc_weighted_edge_collapse(
tdata->eq_ctx, l_adjacent[i]->e->v1, l_adjacent[i]->e->v2);
@@ -1948,7 +2144,7 @@ static void long_edge_queue_edge_add_recursive_2(EdgeQueueThreadData *tdata,
BMLoop *l_iter = l_edge;
do {
BMLoop *l_adjacent[2] = {l_iter->next, l_iter->prev};
- for (int i = 0; i < ARRAY_SIZE(l_adjacent); i++) {
+ for (int i = 0; i < (int)ARRAY_SIZE(l_adjacent); i++) {
float len_sq_other = calc_weighted_edge_split(
tdata->eq_ctx, l_adjacent[i]->e->v1, l_adjacent[i]->e->v2);
@@ -2337,7 +2533,7 @@ static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx,
}
/* For each face, add two new triangles and delete the original */
- for (int i = 0; i < edge_loops->count; i++) {
+ for (int i = 0; i < (int)edge_loops->count; i++) {
BMLoop *l_adj = BLI_buffer_at(edge_loops, BMLoop *, i);
BMFace *f_adj = l_adj->f;
BMFace *f_new;
@@ -2464,7 +2660,7 @@ static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx,
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list