diff options
Diffstat (limited to 'source/blender/blenkernel')
-rw-r--r-- | source/blender/blenkernel/intern/pbvh.c | 14 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/pbvh_bmesh.c | 570 |
2 files changed, 554 insertions, 30 deletions
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c index 3140837ebac..a9ec91a39bc 100644 --- a/source/blender/blenkernel/intern/pbvh.c +++ b/source/blender/blenkernel/intern/pbvh.c @@ -1364,7 +1364,8 @@ static void pbvh_update_draw_buffer_cb(void *__restrict userdata, node->bm_faces, node->bm_unique_verts, node->bm_other_verts, - update_flags); + update_flags, + pbvh->cd_vert_node_offset); break; case PBVH_TRIMESH: GPU_pbvh_trimesh_buffers_update(node->draw_buffers, @@ -1388,7 +1389,7 @@ static void pbvh_update_draw_buffers(PBVH *pbvh, PBVHNode **nodes, int totnode, PBVHNode *node = nodes[n]; if (node->flag & PBVH_Delete) { - printf("corrupted node! %p\n", node); + printf("corrupted node! %p %d\n", node, node->flag); return; } @@ -2441,7 +2442,7 @@ bool BKE_pbvh_node_raycast(PBVH *pbvh, face_normal); break; case PBVH_BMESH: - //BM_mesh_elem_index_ensure(pbvh->bm, BM_VERT); + // BM_mesh_elem_index_ensure(pbvh->bm, BM_VERT); hit = pbvh_bmesh_node_raycast(node, ray_start, ray_normal, @@ -3027,7 +3028,6 @@ void BKE_pbvh_gather_proxies(PBVH *pbvh, PBVHNode ***r_array, int *r_tot) for (int n = 0; n < pbvh->totnode; n++) { PBVHNode *node = pbvh->nodes + n; - if (node->proxy_count > 0) { if (tot == space) { /* resize array if needed */ @@ -3424,10 +3424,12 @@ void BKE_pbvh_ensure_proxyarray(SculptSession *ss, if (vd.no) { copy_v3_v3_short(p->no[i], vd.no); normal_short_to_float_v3(p->fno[i], vd.no); - } else if (vd.fno) { + } + else if (vd.fno) { copy_v3_v3(p->fno[i], vd.fno); normal_float_to_short_v3(p->no[i], p->fno[i]); - } else { + } + else { zero_v3(p->fno[i]); p->fno[i][2] = 1.0f; normal_float_to_short_v3(p->no[i], p->fno[i]); diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c index 0d31494daa8..05d1d2c3e2b 100644 --- a/source/blender/blenkernel/intern/pbvh_bmesh.c +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -20,11 +20,13 @@ #include "MEM_guardedalloc.h" +#include "BLI_array.h" #include "BLI_buffer.h" #include "BLI_ghash.h" #include "BLI_heap_simple.h" #include "BLI_math.h" #include "BLI_memarena.h" +#include "BLI_rand.h" #include "BLI_utildefines.h" #include "PIL_time.h" @@ -40,17 +42,36 @@ #define DYNTOPO_TIME_LIMIT 0.015 #define DYNTOPO_RUN_INTERVAL 0.01 +#define DYNTOPO_USE_HEAP + +#ifndef DYNTOPO_USE_HEAP +/* don't add edges into the queue multiple times */ +# define USE_EDGEQUEUE_TAG +#endif + /* Avoid skinny faces */ #define USE_EDGEQUEUE_EVEN_SUBDIV + #ifdef USE_EDGEQUEUE_EVEN_SUBDIV # include "BKE_global.h" #endif +#ifdef WIN32 +# include "crtdbg.h" +#endif + +static void check_heap() +{ +#ifdef WIN32 + if (!_CrtCheckMemory()) { + printf("Memory corruption!"); + _CrtDbgBreak(); + } +#endif +} /* Support for only operating on front-faces */ #define USE_EDGEQUEUE_FRONTFACE -/* don't add edges into the queue multiple times */ -#define USE_EDGEQUEUE_TAG /** * Ensure we don't have dirty tags for the edge queue, and that they are left cleared. * (slow, even for debug mode, so leave disabled for now). @@ -204,7 +225,8 @@ static BMVert *bm_vert_hash_lookup_chain(GHash *deleted_verts, BMVert *v) static void pbvh_bmesh_node_finalize(PBVH *pbvh, const int node_index, const int cd_vert_node_offset, - const int cd_face_node_offset) + const int cd_face_node_offset, + bool add_orco) { GSetIterator gs_iter; PBVHNode *n = &pbvh->nodes[node_index]; @@ -255,19 +277,24 @@ static void pbvh_bmesh_node_finalize(PBVH *pbvh, BKE_pbvh_node_mark_rebuild_draw(n); BKE_pbvh_node_fully_hidden_set(n, !has_visible); - n->flag |= PBVH_UpdateNormals; + n->flag |= PBVH_UpdateNormals | PBVH_UpdateTopology; + + if (add_orco) { + BKE_pbvh_bmesh_node_save_orig(pbvh->bm, n); + } } /* Recursively split the node if it exceeds the leaf_limit */ -static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_index) +static void pbvh_bmesh_node_split( + PBVH *pbvh, const BBC *bbc_array, int node_index, bool add_orco, int depth) { const int cd_vert_node_offset = pbvh->cd_vert_node_offset; const int cd_face_node_offset = pbvh->cd_face_node_offset; PBVHNode *n = &pbvh->nodes[node_index]; - if (BLI_gset_len(n->bm_faces) <= pbvh->leaf_limit) { + if (depth > 6 || BLI_gset_len(n->bm_faces) <= pbvh->leaf_limit) { /* Node limit not exceeded */ - pbvh_bmesh_node_finalize(pbvh, node_index, cd_vert_node_offset, cd_face_node_offset); + pbvh_bmesh_node_finalize(pbvh, node_index, cd_vert_node_offset, cd_face_node_offset, add_orco); return; } @@ -286,6 +313,10 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind const int axis = BB_widest_axis(&cb); const float mid = (cb.bmax[axis] + cb.bmin[axis]) * 0.5f; + if (isnan(mid)) { + printf("NAN ERROR! %s\n", __func__); + } + /* Add two new child nodes */ const int children = pbvh->totnode; n->children_offset = children; @@ -313,7 +344,7 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind BLI_gset_insert(c2->bm_faces, f); } } - +#if 0 /* Enforce at least one primitive in each node */ GSet *empty = NULL, *other; if (BLI_gset_len(c1->bm_faces) == 0) { @@ -324,6 +355,7 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind empty = c2->bm_faces; other = c1->bm_faces; } + if (empty) { GSET_ITER (gs_iter, other) { void *key = BLI_gsetIterator_getKey(&gs_iter); @@ -332,7 +364,7 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind break; } } - +#endif /* Clear this node */ /* Mark this node's unique verts as unclaimed */ @@ -371,8 +403,8 @@ static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_ind n->flag &= ~PBVH_Leaf; /* Recurse */ - pbvh_bmesh_node_split(pbvh, bbc_array, children); - pbvh_bmesh_node_split(pbvh, bbc_array, children + 1); + pbvh_bmesh_node_split(pbvh, bbc_array, children, add_orco, depth + 1); + pbvh_bmesh_node_split(pbvh, bbc_array, children + 1, add_orco, depth + 1); /* Array maybe reallocated, update current node pointer */ n = &pbvh->nodes[node_index]; @@ -389,6 +421,7 @@ static bool pbvh_bmesh_node_limit_ensure(PBVH *pbvh, int node_index) { GSet *bm_faces = pbvh->nodes[node_index].bm_faces; const int bm_faces_size = BLI_gset_len(bm_faces); + if (bm_faces_size <= pbvh->leaf_limit) { /* Node limit not exceeded */ return false; @@ -417,7 +450,7 @@ static bool pbvh_bmesh_node_limit_ensure(PBVH *pbvh, int node_index) /* Likely this is already dirty. */ pbvh->bm->elem_index_dirty |= BM_FACE; - pbvh_bmesh_node_split(pbvh, bbc_array, node_index); + pbvh_bmesh_node_split(pbvh, bbc_array, node_index, pbvh->nodes[node_index].bm_ortri != NULL, 0); MEM_freeN(bbc_array); @@ -480,12 +513,18 @@ BLI_INLINE int pbvh_bmesh_node_index_from_face(PBVH *pbvh, const BMFace *key) BLI_INLINE PBVHNode *pbvh_bmesh_node_from_vert(PBVH *pbvh, const BMVert *key) { - return &pbvh->nodes[pbvh_bmesh_node_index_from_vert(pbvh, key)]; + int ni = pbvh_bmesh_node_index_from_vert(pbvh, key); + + return ni >= 0 ? pbvh->nodes + ni : NULL; + // return &pbvh->nodes[pbvh_bmesh_node_index_from_vert(pbvh, key)]; } BLI_INLINE PBVHNode *pbvh_bmesh_node_from_face(PBVH *pbvh, const BMFace *key) { - return &pbvh->nodes[pbvh_bmesh_node_index_from_face(pbvh, key)]; + int ni = pbvh_bmesh_node_index_from_face(pbvh, key); + + return ni >= 0 ? pbvh->nodes + ni : NULL; + // return &pbvh->nodes[pbvh_bmesh_node_index_from_face(pbvh, key)]; } static BMVert *pbvh_bmesh_vert_create(PBVH *pbvh, @@ -640,6 +679,10 @@ static void pbvh_bmesh_vert_remove(PBVH *pbvh, BMVert *v) BM_FACES_OF_VERT_ITER_BEGIN (f, v) { const int f_node_index = pbvh_bmesh_node_index_from_face(pbvh, f); + if (f_node_index == DYNTOPO_NODE_NONE) { + continue; + } + /* faces often share the same node, * quick check to avoid redundant #BLI_gset_remove calls */ if (f_node_index_prev != f_node_index) { @@ -662,6 +705,11 @@ static void pbvh_bmesh_face_remove(PBVH *pbvh, BMFace *f) { PBVHNode *f_node = pbvh_bmesh_node_from_face(pbvh, f); + if (!f_node) { + 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); @@ -733,6 +781,10 @@ struct EdgeQueue; typedef struct EdgeQueue { HeapSimple *heap; + + void **elems; + int totelems; + const float *center; float center_proj[3]; /* for when we use projected coords. */ float radius_squared; @@ -742,6 +794,7 @@ typedef struct EdgeQueue { #endif bool (*edge_queue_tri_in_range)(const struct EdgeQueue *q, BMFace *f); + bool (*edge_queue_vert_in_range)(const struct EdgeQueue *q, BMVert *v); const float *view_normal; #ifdef USE_EDGEQUEUE_FRONTFACE @@ -758,6 +811,17 @@ typedef struct { int cd_face_node_offset; } EdgeQueueContext; +static float calc_weighted_edge(EdgeQueueContext *eq_ctx, BMEdge *e) +{ + float l = BM_edge_calc_length_squared(e); + float n; + + n = (float)(BM_vert_edge_count(e->v1) + BM_vert_edge_count(e->v2)) * 0.5f; + n = MAX2(n - 5.0f, 1.0f); + + return l * powf(n, 5.0f); +} + /* only tag'd edges are in the queue */ #ifdef USE_EDGEQUEUE_TAG # define EDGE_QUEUE_TEST(e) (BM_elem_flag_test((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG)) @@ -797,6 +861,12 @@ static void pbvh_bmesh_edge_tag_verify(PBVH *pbvh) } #endif +static bool edge_queue_vert_in_sphere(const EdgeQueue *q, BMVert *v) +{ + /* Check if triangle intersects the sphere */ + return len_squared_v3v3(q->center, v->co) <= q->radius_squared; +} + static bool edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f) { BMVert *v_tri[3]; @@ -830,6 +900,15 @@ static bool edge_queue_tri_in_circle(const EdgeQueue *q, BMFace *f) return len_squared_v3v3(q->center_proj, c) <= q->radius_squared; } +static bool edge_queue_vert_in_circle(const EdgeQueue *q, BMVert *v) +{ + float c[3]; + + project_plane_normalized_v3_v3v3(c, v->co, q->view_normal); + + return len_squared_v3v3(q->center_proj, c) <= q->radius_squared; +} + /* Return true if the vertex mask is less than 1.0, false otherwise */ static bool check_mask(EdgeQueueContext *eq_ctx, BMVert *v) { @@ -838,6 +917,10 @@ static bool check_mask(EdgeQueueContext *eq_ctx, BMVert *v) static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e, float priority) { + void **elems = eq_ctx->q->elems; + BLI_array_declare(elems); + BLI_array_len_set(elems, eq_ctx->q->totelems); + /* Don't let topology update affect fully masked vertices. This used to * have a 50% mask cutoff, with the reasoning that you can't do a 50% * topology update. But this gives an ugly border in the mesh. The mask @@ -851,7 +934,14 @@ static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e, float priorit BMVert **pair = BLI_mempool_alloc(eq_ctx->pool); pair[0] = e->v1; pair[1] = e->v2; +#ifdef DYNTOPO_USE_HEAP BLI_heapsimple_insert(eq_ctx->q->heap, priority, pair); +#endif + + BLI_array_append(elems, pair); + eq_ctx->q->elems = elems; + eq_ctx->q->totelems = BLI_array_len(elems); + #ifdef USE_EDGEQUEUE_TAG BLI_assert(EDGE_QUEUE_TEST(e) == false); EDGE_QUEUE_ENABLE(e); @@ -936,7 +1026,7 @@ static void short_edge_queue_edge_add(EdgeQueueContext *eq_ctx, BMEdge *e) if (EDGE_QUEUE_TEST(e) == false) #endif { - const float len_sq = BM_edge_calc_length_squared(e); + const float len_sq = calc_weighted_edge(eq_ctx, e); if (len_sq < eq_ctx->q->limit_len_squared) { edge_queue_insert(eq_ctx, e, len_sq); } @@ -1011,6 +1101,8 @@ static void long_edge_queue_create(EdgeQueueContext *eq_ctx, const bool use_projected) { eq_ctx->q->heap = BLI_heapsimple_new(); + eq_ctx->q->elems = NULL; + eq_ctx->q->totelems = 0; eq_ctx->q->center = center; eq_ctx->q->radius_squared = radius * radius; eq_ctx->q->limit_len_squared = pbvh->bm_max_edge_len * pbvh->bm_max_edge_len; @@ -1028,10 +1120,12 @@ static void long_edge_queue_create(EdgeQueueContext *eq_ctx, if (use_projected) { eq_ctx->q->edge_queue_tri_in_range = edge_queue_tri_in_circle; + eq_ctx->q->edge_queue_vert_in_range = edge_queue_vert_in_circle; project_plane_normalized_v3_v3v3(eq_ctx->q->center_proj, center, view_normal); } else { eq_ctx->q->edge_queue_tri_in_range = edge_queue_tri_in_sphere; + eq_ctx->q->edge_queue_vert_in_range = edge_queue_vert_in_sphere; } #ifdef USE_EDGEQUEUE_TAG_VERIFY @@ -1074,6 +1168,8 @@ static void short_edge_queue_create(EdgeQueueContext *eq_ctx, const bool use_projected) { eq_ctx->q->heap = BLI_heapsimple_new(); + eq_ctx->q->elems = NULL; + eq_ctx->q->totelems = 0; eq_ctx->q->center = center; eq_ctx->q->radius_squared = radius * radius; eq_ctx->q->limit_len_squared = pbvh->bm_min_edge_len * pbvh->bm_min_edge_len; @@ -1091,10 +1187,12 @@ static void short_edge_queue_create(EdgeQueueContext *eq_ctx, if (use_projected) { eq_ctx->q->edge_queue_tri_in_range = edge_queue_tri_in_circle; + eq_ctx->q->edge_queue_vert_in_range = edge_queue_vert_in_circle; project_plane_normalized_v3_v3v3(eq_ctx->q->center_proj, center, view_normal); } else { eq_ctx->q->edge_queue_tri_in_range = edge_queue_tri_in_sphere; + eq_ctx->q->edge_queue_vert_in_range = edge_queue_vert_in_sphere; } for (int n = 0; n < pbvh->totnode; n++) { @@ -1221,15 +1319,23 @@ static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx, if (!BLI_gset_haskey(pbvh->nodes[ni].bm_unique_verts, v_new)) { BLI_gset_add(pbvh->nodes[ni].bm_other_verts, v_new); } - + //* if (BM_vert_edge_count_is_over(v_opp, 8)) { BMIter bm_iter; BMEdge *e2; BM_ITER_ELEM (e2, &bm_iter, v_opp, BM_EDGES_OF_VERT) { - long_edge_queue_edge_add(eq_ctx, e2); + BMVert *v2 = BM_edge_other_vert(e2, v_opp); + bool add = eq_ctx->q->edge_queue_vert_in_range(eq_ctx->q, v2); + + add = add && BM_edge_calc_length_squared(e2) > eq_ctx->q->limit_len_squared; + + if (add) { + long_edge_queue_edge_add(eq_ctx, e2); + } } } + //*/ } BM_edge_kill(pbvh->bm, e); @@ -1242,12 +1348,26 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, bool any_subdivided = false; double time = PIL_check_seconds_timer(); + RNG *rng = BLI_rng_new((int)(time * 1000.0f)); + while (!BLI_heapsimple_is_empty(eq_ctx->q->heap)) { if (PIL_check_seconds_timer() - time > DYNTOPO_TIME_LIMIT) { break; } +#ifndef DYNTOPO_USE_HEAP + if (eq_ctx->q->totelems == 0) { + break; + } + + int ri = BLI_rng_get_int(rng) % eq_ctx->q->totelems; + + BMVert **pair = eq_ctx->q->elems[ri]; + eq_ctx->q->elems[ri] = eq_ctx->q->elems[eq_ctx->q->totelems - 1]; + eq_ctx->q->totelems--; +#else BMVert **pair = BLI_heapsimple_pop_min(eq_ctx->q->heap); +#endif BMVert *v1 = pair[0], *v2 = pair[1]; BMEdge *e; @@ -1286,10 +1406,25 @@ static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, pbvh_bmesh_split_edge(eq_ctx, pbvh, e, edge_loops); } +#if !defined(DYNTOPO_USE_HEAP) && defined(USE_EDGEQUEUE_TAG) + for (int i = 0; i < eq_ctx->q->totelems; i++) { + BMVert **pair = eq_ctx->q->elems[i]; + BMVert *v1 = pair[0], *v2 = pair[1]; + + BMEdge *e = BM_edge_exists(v1, v2); + + if (e) { + EDGE_QUEUE_DISABLE(e); + } + } +#endif + #ifdef USE_EDGEQUEUE_TAG_VERIFY pbvh_bmesh_edge_tag_verify(pbvh); #endif + BLI_rng_free(rng); + return any_subdivided; } @@ -1481,13 +1616,25 @@ static bool pbvh_bmesh_collapse_short_edges(EdgeQueueContext *eq_ctx, GHash *deleted_verts = BLI_ghash_ptr_new("deleted_verts"); double time = PIL_check_seconds_timer(); + RNG *rng = BLI_rng_new(time * 1000.0); while (!BLI_heapsimple_is_empty(eq_ctx->q->heap)) { if (PIL_check_seconds_timer() - time > DYNTOPO_TIME_LIMIT) { break; } +#ifndef DYNTOPO_USE_HEAP + if (eq_ctx->q->totelems == 0) { + break; + } + + int ri = BLI_rng_get_int(rng) % eq_ctx->q->totelems; + BMVert **pair = eq_ctx->q->elems[ri]; + eq_ctx->q->elems[ri] = eq_ctx->q->elems[eq_ctx->q->totelems - 1]; + eq_ctx->q->totelems--; +#else BMVert **pair = BLI_heapsimple_pop_min(eq_ctx->q->heap); +#endif BMVert *v1 = pair[0], *v2 = pair[1]; BLI_mempool_free(eq_ctx->pool, pair); pair = NULL; @@ -1525,6 +1672,24 @@ static bool pbvh_bmesh_collapse_short_edges(EdgeQueueContext *eq_ctx, pbvh_bmesh_collapse_edge(pbvh, e, v1, v2, deleted_verts, deleted_faces, eq_ctx); } +#if !defined(DYNTOPO_USE_HEAP) && defined(USE_EDGEQUEUE_TAG) + for (int i = 0; i < eq_ctx->q->totelems; i++) { + BMVert **pair = eq_ctx->q->elems[i]; + BMVert *v1 = pair[0], *v2 = pair[1]; + + /* Check the verts still exist */ + if (!(v1 = bm_vert_hash_lookup_chain(deleted_verts, v1)) || + !(v2 = bm_vert_hash_lookup_chain(deleted_verts, v2)) || (v1 == v2)) { + continue; + } + + BMEdge *e = BM_edge_exists(v1, v2); + if (e) { + EDGE_QUEUE_DISABLE(e); + } + } +#endif + BLI_rng_free(rng); BLI_ghash_free(deleted_verts, NULL, NULL); return any_collapsed; @@ -1924,7 +2089,7 @@ void BKE_pbvh_build_bmesh(PBVH *pbvh, pbvh->bm_log = log; /* TODO: choose leaf limit better */ - pbvh->leaf_limit = 2000; + pbvh->leaf_limit = 3000; if (smooth_shading) { pbvh->flags |= PBVH_DYNTOPO_SMOOTH_SHADING; @@ -2001,7 +2166,6 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh, if (sym_axis >= 0 && PIL_check_seconds_timer() - last_update_time[sym_axis] < DYNTOPO_RUN_INTERVAL) { return false; - // return false; } if (sym_axis >= 0) { @@ -2037,6 +2201,9 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh, &eq_ctx, pbvh, center, view_normal, radius, use_frontface, use_projected); modified |= pbvh_bmesh_collapse_short_edges(&eq_ctx, pbvh, &deleted_faces); BLI_heapsimple_free(q.heap, NULL); + if (q.elems) { + MEM_freeN(q.elems); + } BLI_mempool_destroy(queue_pool); } @@ -2055,6 +2222,9 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh, long_edge_queue_create( &eq_ctx, pbvh, center, view_normal, radius, use_frontface, use_projected); modified |= pbvh_bmesh_subdivide_long_edges(&eq_ctx, pbvh, &edge_loops); + if (q.elems) { + MEM_freeN(q.elems); + } BLI_heapsimple_free(q.heap, NULL); BLI_mempool_destroy(queue_pool); } @@ -2065,14 +2235,12 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh, if ((node->flag & PBVH_Leaf) && (node->flag & PBVH_UpdateTopology) && !(node->flag & PBVH_FullyHidden)) { + node->flag &= ~PBVH_UpdateTopology; + /* Recursively split nodes that have gotten too many * elements */ pbvh_bmesh_node_limit_ensure(pbvh, i); } - - if ((node->flag & PBVH_Leaf) && (node->flag & PBVH_UpdateTopology)) { - node->flag &= ~PBVH_UpdateTopology; - } } } else { // still unmark nodes @@ -2156,10 +2324,362 @@ void BKE_pbvh_bmesh_node_save_orig(BMesh *bm, PBVHNode *node) node->bm_tot_ortri = i; } +static int pbvh_count_subtree_verts(PBVH *pbvh, PBVHNode *n) +{ + if (n->flag & PBVH_Leaf) { + n->tm_subtree_tottri = BLI_gset_len( + n->bm_faces); // n->tm_unique_verts->length + n->tm_other_verts->length; + return n->tm_subtree_tottri; + } + + int ni = n->children_offset; + + int ret = pbvh_count_subtree_verts(pbvh, pbvh->nodes + ni); + ret += pbvh_count_subtree_verts(pbvh, pbvh->nodes + ni + 1); + + n->tm_subtree_tottri = ret; + + return ret; +} + +static void pbvh_bmesh_join_subnodes(PBVH *pbvh, PBVHNode *node, PBVHNode *parent) +{ + if (!(node->flag & PBVH_Leaf)) { + int ni = node->children_offset; + + if (ni > 0 && ni < pbvh->totnode - 1) { + pbvh_bmesh_join_subnodes(pbvh, pbvh->nodes + ni, parent); + pbvh_bmesh_join_subnodes(pbvh, pbvh->nodes + ni + 1, parent); + } + else { + printf("node corruption: %d\n", ni); + return; + } + if (node != parent) { + node->flag |= PBVH_Delete; // mark for deletion + } + + return; + } + + if (node != parent) { + node->flag |= PBVH_Delete; // mark for deletion + } + + BMVert *v; + GSetIterator gsiter; + + GSET_ITER (gsiter, node->bm_unique_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gsiter); + BLI_gset_add(parent->bm_unique_verts, v); + + BM_ELEM_CD_SET_INT(v, pbvh->cd_vert_node_offset, DYNTOPO_NODE_NONE); + } + + // printf(" subtotface: %d\n", BLI_gset_len(node->bm_faces)); + + GSET_ITER (gsiter, node->bm_faces) { + BMFace *f = BLI_gsetIterator_getKey(&gsiter); + + BLI_gset_add(parent->bm_faces, f); + BM_ELEM_CD_SET_INT(f, pbvh->cd_face_node_offset, DYNTOPO_NODE_NONE); + } +} + +static void BKE_pbvh_bmesh_corect_tree(PBVH *pbvh, PBVHNode *node, PBVHNode *parent) +{ + const int size_lower = pbvh->leaf_limit - (pbvh->leaf_limit >> 1); + const int size_higher = pbvh->leaf_limit + (pbvh->leaf_limit >> 1); + + if (node->flag & PBVH_Leaf) { + // pbvh_trimesh_node_limit_ensure(pbvh, (int)(node - pbvh->nodes)); + return; + + // join nodes if subtree lacks verts, unless node is root + } + + if (node->tm_subtree_tottri < size_lower && node != pbvh->nodes) { + node->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts"); + node->bm_other_verts = BLI_gset_ptr_new("bm_other_verts"); + node->bm_faces = BLI_gset_ptr_new("bm_faces"); + + pbvh_bmesh_join_subnodes(pbvh, pbvh->nodes + node->children_offset, node); + pbvh_bmesh_join_subnodes(pbvh, pbvh->nodes + node->children_offset + 1, node); + + node->children_offset = 0; + node->flag |= PBVH_Leaf | PBVH_UpdateRedraw | PBVH_UpdateBB | PBVH_UpdateDrawBuffers | + PBVH_RebuildDrawBuffers | PBVH_UpdateOriginalBB | PBVH_UpdateMask | + PBVH_UpdateVisibility | PBVH_UpdateColor | PBVH_UpdateTopology | + PBVH_UpdateNormals; + + GSet *other = BLI_gset_ptr_new(__func__); + GSetIterator gsiter; + BMVert *v; + + node->children_offset = 0; + node->draw_buffers = NULL; + + // make sure other list isn't overlapping with unique + GSET_ITER (gsiter, node->bm_other_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gsiter); + + if (!BLI_gset_haskey(node->bm_unique_verts, v)) { + // BLI_gset_add(other, v); + } + } + + GSET_ITER (gsiter, node->bm_faces) { + BMFace *f = BLI_gsetIterator_getKey(&gsiter); + BMLoop *l = f->l_first; + + BM_ELEM_CD_SET_INT(f, pbvh->cd_face_node_offset, DYNTOPO_NODE_NONE); + + do { + if (!BLI_gset_haskey(node->bm_unique_verts, l->v)) { + BLI_gset_add(other, l->v); + } + l = l->next; + } while (l != f->l_first); + } + + BLI_gset_free(node->bm_other_verts, NULL); + node->bm_other_verts = other; + + BB_reset(&node->vb); + //* + GSET_ITER (gsiter, node->bm_unique_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gsiter); + BB_expand(&node->vb, v->co); + } + GSET_ITER (gsiter, node->bm_other_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gsiter); + BB_expand(&node->vb, v->co); + } //*/ + + // printf("totface: %d\n", BLI_gset_len(node->bm_faces)); + node->orig_vb = node->vb; + + return; + } + + int ni = node->children_offset; + + for (int i = 0; i < 2; i++, ni++) { + PBVHNode *child = pbvh->nodes + ni; + BKE_pbvh_bmesh_corect_tree(pbvh, child, node); + } +} + +static void pbvh_bmesh_join_nodes(PBVH *bvh) +{ + pbvh_count_subtree_verts(bvh, bvh->nodes); + BKE_pbvh_bmesh_corect_tree(bvh, bvh->nodes, NULL); + + // compact nodes + int totnode = 0; + for (int i = 0; i < bvh->totnode; i++) { + PBVHNode *n = bvh->nodes + i; + + if (!(n->flag & PBVH_Delete)) { + if (!(n->flag & PBVH_Leaf)) { + PBVHNode *n1 = bvh->nodes + n->children_offset; + PBVHNode *n2 = bvh->nodes + n->children_offset + 1; + + if ((n1->flag & PBVH_Delete) != (n2->flag & PBVH_Delete)) { + printf("un-deleting an empty node\n"); + PBVHNode *n3 = n1->flag & PBVH_Delete ? n1 : n2; + + n3->flag = PBVH_Leaf; + n3->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts"); + n3->bm_other_verts = BLI_gset_ptr_new("bm_other_verts"); + n3->bm_faces = BLI_gset_ptr_new("bm_faces"); + } + else if ((n1->flag & PBVH_Delete) && (n2->flag & PBVH_Delete)) { + n->children_offset = 0; + n->flag |= PBVH_Leaf; + + if (!n->bm_unique_verts) { + // should not happen + n->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts"); + n->bm_other_verts = BLI_gset_ptr_new("bm_other_verts"); + n->bm_faces = BLI_gset_ptr_new("bm_faces"); + } + } + } + + totnode++; + } + } + + int *map = MEM_callocN(sizeof(int) * bvh->totnode, "bmesh map temp"); + + // build idx map for child offsets + int j = 0; + for (int i = 0; i < bvh->totnode; i++) { + PBVHNode *n = bvh->nodes + i; + + if (!(n->flag & PBVH_Delete)) { + map[i] = j++; + } + else if (1) { + if (n->layer_disp) { + MEM_freeN(n->layer_disp); + n->layer_disp = NULL; + } + if (n->draw_buffers) { + GPU_pbvh_buffers_free(n->draw_buffers); + n->draw_buffers = NULL; + } + if (n->vert_indices) { + MEM_freeN((void *)n->vert_indices); + n->vert_indices = NULL; + } + if (n->face_vert_indices) { + MEM_freeN((void *)n->face_vert_indices); + n->face_vert_indices = NULL; + } + + if (n->bm_orco) { + MEM_freeN(n->bm_orco); + n->bm_orco = NULL; + } + + if (n->bm_ortri) { + MEM_freeN(n->bm_ortri); + n->bm_ortri = NULL; + } + + if (n->bm_unique_verts) { + BLI_gset_free(n->bm_unique_verts, NULL); + n->bm_unique_verts = NULL; + } + + if (n->bm_other_verts) { + BLI_gset_free(n->bm_other_verts, NULL); + n->bm_other_verts = NULL; + } + + if (n->bm_faces) { + BLI_gset_free(n->bm_faces, NULL); + n->bm_faces = NULL; + } + } + } + + // compact node array + j = 0; + for (int i = 0; i < bvh->totnode; i++) { + if (!(bvh->nodes[i].flag & PBVH_Delete)) { + int i1 = map[bvh->nodes[i].children_offset]; + int i2 = map[bvh->nodes[i].children_offset + 1]; + + if (bvh->nodes[i].children_offset >= bvh->totnode) { + printf("bad child node reference %d->%d, totnode: %d\n", + i, + bvh->nodes[i].children_offset, + bvh->totnode); + continue; + } + + if (bvh->nodes[i].children_offset && i2 != i1 + 1) { + printf(" pbvh corruption during node join %d %d\n", i1, i2); + } + + bvh->nodes[j] = bvh->nodes[i]; + bvh->nodes[j].children_offset = i1; + + j++; + } + } + + if (j != totnode) { + printf("eek!"); + } + + if (bvh->totnode != j) { + memset(bvh->nodes + j, 0, sizeof(*bvh->nodes) * (bvh->totnode - j)); + bvh->node_mem_count = j; + } + + bvh->totnode = j; + + GSetIterator gsiter; + BMVert *v; + + // set vert/face node indices again + for (int i = 0; i < bvh->totnode; i++) { + PBVHNode *n = bvh->nodes + i; + + if (!(n->flag & PBVH_Leaf)) { + continue; + } + + if (!n->bm_unique_verts) { + printf("ERROR!\n"); + n->bm_unique_verts = BLI_gset_ptr_new("bleh"); + n->bm_other_verts = BLI_gset_ptr_new("bleh"); + n->bm_faces = BLI_gset_ptr_new("bleh"); + } + + GSET_ITER (gsiter, n->bm_unique_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gsiter); + + BM_ELEM_CD_SET_INT(v, bvh->cd_vert_node_offset, i); + } + + GSET_ITER (gsiter, n->bm_faces) { + BMFace *f = BLI_gsetIterator_getKey(&gsiter); + BM_ELEM_CD_SET_INT(f, bvh->cd_face_node_offset, i); + } + } + + BMVert **scratch = NULL; + BLI_array_declare(scratch); + + for (int i = 0; i < bvh->totnode; i++) { + PBVHNode *n = bvh->nodes + i; + + if (!(n->flag & PBVH_Leaf)) { + continue; + } + + BLI_array_clear(scratch); + + GSET_ITER (gsiter, n->bm_other_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gsiter); + + int ni = BM_ELEM_CD_GET_INT(v, bvh->cd_vert_node_offset); + if (ni == DYNTOPO_NODE_NONE) { + BLI_array_append(scratch, v); + } + // BM_ELEM_CD_SET_INT(v, bvh->cd_vert_node_offset, i); + } + + int slen = BLI_array_len(scratch); + for (int j = 0; j < slen; j++) { + BMVert *v = scratch[j]; + + BLI_gset_remove(n->bm_other_verts, v, NULL); + BLI_gset_add(n->bm_unique_verts, v); + BM_ELEM_CD_SET_INT(v, bvh->cd_vert_node_offset, i); + } + } + + BLI_array_free(scratch); + MEM_freeN(map); +} + void BKE_pbvh_bmesh_after_stroke(PBVH *pbvh) { + check_heap(); + + pbvh_bmesh_join_nodes(pbvh); + + check_heap(); + for (int i = 0; i < pbvh->totnode; i++) { - PBVHNode *n = &pbvh->nodes[i]; + PBVHNode *n = pbvh->nodes + i; + if (n->flag & PBVH_Leaf) { /* Free orco/ortri data */ pbvh_bmesh_node_drop_orig(n); @@ -2169,6 +2689,8 @@ void BKE_pbvh_bmesh_after_stroke(PBVH *pbvh) pbvh_bmesh_node_limit_ensure(pbvh, i); } } + + BKE_pbvh_update_bounds(pbvh, (PBVH_UpdateBB | PBVH_UpdateOriginalBB | PBVH_UpdateRedraw)); } void BKE_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size) |