diff options
Diffstat (limited to 'source/blender/blenkernel')
| -rw-r--r-- | source/blender/blenkernel/BKE_pbvh.h | 6 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/pbvh_bmesh.c | 913 |
2 files changed, 875 insertions, 44 deletions
diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h index c8c693fc342..81e7ce1cdbe 100644 --- a/source/blender/blenkernel/BKE_pbvh.h +++ b/source/blender/blenkernel/BKE_pbvh.h @@ -141,9 +141,11 @@ struct BMesh *BKE_pbvh_get_bmesh(PBVH *pbvh); void BKE_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size); typedef enum { - PBVH_Subdivide = 1, - PBVH_Collapse = 2, + PBVH_Subdivide = (1 << 0), + PBVH_Collapse = (1 << 1), + PBVH_TopologyGenus = (1 << 2), } PBVHTopologyUpdateMode; + bool BKE_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode, const float center[3], float radius); diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c index 9e18d54614b..e0cf9eeeae1 100644 --- a/source/blender/blenkernel/intern/pbvh_bmesh.c +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -25,10 +25,13 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" +#include "BLI_alloca.h" +#include "BLI_array.h" #include "BLI_buffer.h" #include "BLI_ghash.h" #include "BLI_heap.h" #include "BLI_math.h" +#include "BLI_listbase.h" #include "BKE_ccg.h" #include "BKE_DerivedMesh.h" @@ -41,6 +44,9 @@ #include <assert.h> +/* removes skinny areas after making holes (is rather ugly without this) */ +#define USE_HOLE_VOLUME_CLEAN + /****************************** Building ******************************/ /* Update node data after splitting */ @@ -627,6 +633,80 @@ static void long_edge_queue_face_add(EdgeQueueContext *eq_ctx, } } +#ifdef USE_HOLE_VOLUME_CLEAN + +#define SHARP_THRESHOLD 0.5f + +/** + * 1.0 == sharp, 0.0 == flat + */ +static float bm_edge_calc_sharpness(BMEdge *e) +{ + if (BM_edge_is_manifold(e)) { + float axis[3], ang; + sub_v3_v3v3(axis, e->v1->co, e->v2->co); + ang = angle_on_axis_v3v3v3_v3( + e->l->prev->v->co, + e->v1->co, + e->l->radial_next->prev->v->co, + axis); + return 1.0f - (ang / M_PI); + } + else { + return 1.0f; + } +} + +/** + * volume weighted by sharpness + */ +static float bm_edge_calc_volume_weighted(BMEdge *e) +{ + BMLoop *l_a, *l_b; + + if (BM_edge_loop_pair(e, &l_a, &l_b)) { + BMVert *v1_alt = l_a->prev->v; + BMVert *v2_alt = l_b->prev->v; + float sharp; + + sharp = bm_edge_calc_sharpness(e); + + if (sharp > SHARP_THRESHOLD) { + /* remap from the threshold back to 0-1 */ + sharp = (sharp - SHARP_THRESHOLD) / (1.0 - SHARP_THRESHOLD); + return volume_tetrahedron_v3(e->v1->co, e->v2->co, v1_alt->co, v2_alt->co) / (FLT_EPSILON + (sharp)); + } + } + + return FLT_MAX; +} + +static void tetrahedron_edge_queue_edge_add(EdgeQueueContext *eq_ctx, + BMEdge *e) +{ + const float volume = bm_edge_calc_volume_weighted(e); + if (volume != FLT_MAX) { + edge_queue_insert(eq_ctx, e, volume); + } +} + +static void tetrahedron_edge_queue_face_add(EdgeQueueContext *eq_ctx, + BMFace *f) +{ + if (edge_queue_tri_in_sphere(eq_ctx->q, f)) { + BMLoop *l_iter; + BMLoop *l_first; + + /* Check each edge of the face */ + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + tetrahedron_edge_queue_edge_add(eq_ctx, l_iter->e); + } while ((l_iter = l_iter->next) != l_first); + } +} + +#endif /* USE_HOLE_VOLUME_CLEAN */ + static void short_edge_queue_face_add(EdgeQueueContext *eq_ctx, BMFace *f) { @@ -722,6 +802,224 @@ static void short_edge_queue_create(EdgeQueueContext *eq_ctx, } } +#ifdef USE_HOLE_VOLUME_CLEAN +static void tetrahedron_edge_queue_create( + EdgeQueueContext *eq_ctx, + PBVH *bvh, const float center[3], + float radius) +{ + int n; + + eq_ctx->q->heap = BLI_heap_new(); + eq_ctx->q->center = center; + eq_ctx->q->radius_squared = radius * radius; + eq_ctx->q->limit_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len; + + for (n = 0; n < bvh->totnode; n++) { + PBVHNode *node = &bvh->nodes[n]; + + /* Check leaf nodes marked for topology update */ + if ((node->flag & PBVH_Leaf) && + (node->flag & PBVH_UpdateTopology) && + !(node->flag & PBVH_FullyHidden)) + { + GSetIterator gs_iter; + + /* Check each face */ + GSET_ITER (gs_iter, node->bm_faces) { + BMFace *f = BLI_gsetIterator_getKey(&gs_iter); + + tetrahedron_edge_queue_face_add(eq_ctx, f); + } + } + } +} +#endif /* USE_HOLE_VOLUME_CLEAN */ + +static void pbvh_bmesh_delete_vert_face(PBVH *bvh, BMVert *v, BMFace *f_del, GSet *deleted_verts, EdgeQueueContext *eq_ctx) +{ + BMLoop *l_iter; + BMVert *v_tri[3]; + BMEdge *e_tri[3]; + int j; + + /* Get vertices and edges of face */ + BLI_assert(f_del->len == 3); + l_iter = BM_FACE_FIRST_LOOP(f_del); + v_tri[0] = l_iter->v; e_tri[0] = l_iter->e; l_iter = l_iter->next; + v_tri[1] = l_iter->v; e_tri[1] = l_iter->e; l_iter = l_iter->next; + v_tri[2] = l_iter->v; e_tri[2] = l_iter->e; + + /* Check if any of the face's vertices are now unused, if so + * remove them from the PBVH */ + for (j = 0; j < 3; j++) { + if (v_tri[j] != v && BM_vert_face_count(v_tri[j]) == 1) { + BLI_gset_insert(deleted_verts, v_tri[j]); + pbvh_bmesh_vert_remove(bvh, v_tri[j]); + } + else { + v_tri[j] = NULL; + } + } + + /* Remove the face */ + pbvh_bmesh_face_remove(bvh, f_del); + BM_face_kill(bvh->bm, f_del); + + /* Check if any of the face's edges are now unused by any + * face, if so delete them */ + for (j = 0; j < 3; j++) { + if (BM_edge_is_wire(e_tri[j])) + BM_edge_kill(bvh->bm, e_tri[j]); + } + + /* Delete unused vertices */ + for (j = 0; j < 3; j++) { + if (v_tri[j]) { + BM_log_vert_removed(bvh->bm_log, v_tri[j], eq_ctx->cd_vert_mask_offset); + BM_vert_kill(bvh->bm, v_tri[j]); + } + } +} + + +/** + * Same as #pbvh_bmesh_delete_vert_face but keeps verts + */ +static void pbvh_bmesh_delete_edge_face(PBVH *bvh, BMFace *f_del) +{ + BMLoop *l_iter; + BMEdge *e_tri[3]; + int j; + + /* Get vertices and edges of face */ + BLI_assert(f_del->len == 3); + l_iter = BM_FACE_FIRST_LOOP(f_del); + e_tri[0] = l_iter->e; l_iter = l_iter->next; + e_tri[1] = l_iter->e; l_iter = l_iter->next; + e_tri[2] = l_iter->e; + + /* Remove the face */ + pbvh_bmesh_face_remove(bvh, f_del); + BM_face_kill(bvh->bm, f_del); + + /* Check if any of the face's edges are now unused by any + * face, if so delete them */ + for (j = 0; j < 3; j++) { + if (BM_edge_is_wire(e_tri[j])) + BM_edge_kill(bvh->bm, e_tri[j]); + } +} + +/* Create a priority queue containing vertex pairs not connected by an + * edge, but close enough as defined by PBVH.bm_min_edge_len. + * + * Only nodes marked for topology update are checked, and in those + * nodes only edges used by a face intersecting the (center, radius) + * sphere are checked. + * + * The highest priority (lowest number) is given to the pair of vertices with + * the shortest distance. + */ +static void close_vert_queue_create(EdgeQueueContext *eq_ctx, + PBVH *bvh, const float center[3], + float radius) +{ + int n; + Heap *distheap = BLI_heap_new(); + BMVert *vprev, *vcur; + int num_close_verts; + /* list of verts for faster traversing */ + ListBase vlist = {0}; + LinkData *curnode; + LinkData *prevnode; + + eq_ctx->q->heap = BLI_heap_new(); + eq_ctx->q->center = center; + eq_ctx->q->radius_squared = radius * radius; + eq_ctx->q->limit_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len; + + for (n = 0; n < bvh->totnode; n++) { + PBVHNode *node = &bvh->nodes[n]; + + /* Check leaf nodes marked for topology update */ + if ((node->flag & PBVH_Leaf) && + (node->flag & PBVH_UpdateTopology) && + !(node->flag & PBVH_FullyHidden)) + { + GSetIterator gs_iter; + + /* Insert vertices in a distance heap */ + GSET_ITER (gs_iter, node->bm_unique_verts) { + BMVert *v = BLI_gsetIterator_getKey(&gs_iter); + float dist_to_center_sq = len_squared_v3v3(eq_ctx->q->center, v->co); + + if (dist_to_center_sq <= eq_ctx->q->radius_squared && check_mask(eq_ctx, v) && !BM_vert_is_boundary(v)) + BLI_heap_insert(distheap, dist_to_center_sq, v); + } + } + } + + num_close_verts = BLI_heap_size(distheap); + + for (n = 0; n < num_close_verts; n++) { + LinkData *d = MEM_callocN(sizeof(*d), "Node"); + d->data = BLI_heap_popmin(distheap); + BLI_addtail(&vlist, d); + } + + BLI_heap_free(distheap, NULL); + + curnode = vlist.first; + + /* iterate the list and make pairs of vertices that are closer than the squared limit distance + * and not on part of the same face. The logic here is borrowed from our remove doubles operator */ + while (curnode) { + vprev = (BMVert *)curnode->data; + + prevnode = curnode; + curnode = curnode->next; + + while (curnode) { + vcur = (BMVert *)curnode->data; + + /* vertices belonging to the same face are not eligible for merging */ + if (!BM_edge_exists(vprev, vcur)) { + float dist_sq = len_squared_v3v3(vcur->co, vprev->co); + + if (dist_sq < eq_ctx->q->limit_len_squared) + { + BMVert **pair = BLI_mempool_alloc(eq_ctx->pool); + pair[0] = vprev; + pair[1] = vcur; + +#if 0 + BLI_heap_insert(eq_ctx->q->heap, + min_ff(len_squared_v3v3(eq_ctx->q->center, vcur->co), + len_squared_v3v3(eq_ctx->q->center, vprev->co)), + pair); +#else + BLI_heap_insert(eq_ctx->q->heap, dist_sq, pair); +#endif + } + + /* the two vertices in the pair are obliterated as part of the genus topology change, get a new + * vertex for processing. If the test does not pass then a new vertex must be used as + * previous because it is guaranteed that next vertices will not pass the test */ + BLI_remlink(&vlist, curnode); + MEM_freeN(curnode); + curnode = prevnode->next; + break; + } + + curnode = curnode->next; + } + } + + BLI_freelistN(&vlist); +} + + /*************************** Topology update **************************/ static void bm_edges_from_tri(BMesh *bm, BMVert *v_tri[3], BMEdge *e_tri[3]) @@ -951,48 +1249,7 @@ static void pbvh_bmesh_collapse_edge( /* Delete the tagged faces */ for (i = 0; i < deleted_faces->count; i++) { BMFace *f_del = BLI_buffer_at(deleted_faces, BMFace *, i); - BMLoop *l_iter; - BMVert *v_tri[3]; - BMEdge *e_tri[3]; - int j; - - /* Get vertices and edges of face */ - BLI_assert(f_del->len == 3); - l_iter = BM_FACE_FIRST_LOOP(f_del); - v_tri[0] = l_iter->v; e_tri[0] = l_iter->e; l_iter = l_iter->next; - v_tri[1] = l_iter->v; e_tri[1] = l_iter->e; l_iter = l_iter->next; - v_tri[2] = l_iter->v; e_tri[2] = l_iter->e; - - /* Check if any of the face's vertices are now unused, if so - * remove them from the PBVH */ - for (j = 0; j < 3; j++) { - if (v_tri[j] != v_del && BM_vert_face_count(v_tri[j]) == 1) { - BLI_gset_insert(deleted_verts, v_tri[j]); - pbvh_bmesh_vert_remove(bvh, v_tri[j]); - } - else { - v_tri[j] = NULL; - } - } - - /* Remove the face */ - pbvh_bmesh_face_remove(bvh, f_del); - BM_face_kill(bvh->bm, f_del); - - /* Check if any of the face's edges are now unused by any - * face, if so delete them */ - for (j = 0; j < 3; j++) { - if (BM_edge_is_wire(e_tri[j])) - BM_edge_kill(bvh->bm, e_tri[j]); - } - - /* Delete unused vertices */ - for (j = 0; j < 3; j++) { - if (v_tri[j]) { - BM_log_vert_removed(bvh->bm_log, v_tri[j], eq_ctx->cd_vert_mask_offset); - BM_vert_kill(bvh->bm, v_tri[j]); - } - } + pbvh_bmesh_delete_vert_face(bvh, v_del, f_del, deleted_verts, eq_ctx); } /* Move v_conn to the midpoint of v_conn and v_del (if v_conn still exists, it @@ -1065,6 +1322,95 @@ static bool pbvh_bmesh_collapse_short_edges( return any_collapsed; } +#ifdef USE_HOLE_VOLUME_CLEAN + +static float len_to_tetrahedron_volume(float f) +{ + return (f * f * f) / 6.0f; +} + +static bool pbvh_bmesh_collapse_small_tetrahedrons( + EdgeQueueContext *eq_ctx, + PBVH *bvh, + BLI_Buffer *deleted_faces) +{ + /* length as a tetrahedron volume, x1.5x to remove more... gives a bit nicer results */ + float min_volume = len_to_tetrahedron_volume(bvh->bm_min_edge_len) * 1.5f; + GSet *deleted_verts; + bool any_collapsed = false; + + deleted_verts = BLI_gset_ptr_new("deleted_verts"); + + while (!BLI_heap_is_empty(eq_ctx->q->heap)) { + BMLoop *l_a, *l_b; + BMVert **pair = BLI_heap_popmin(eq_ctx->q->heap); + BMVert *v1 = pair[0], *v2 = pair[1]; + BMEdge *e; + + /* values on either side of the edge */ + BMLoop *l_adj; + BMVert *v1_alt; + BMVert *v2_alt; + BMEdge *e_alt; + + BLI_mempool_free(eq_ctx->pool, pair); + pair = NULL; + + /* Check the verts still exist */ + if (BLI_gset_haskey(deleted_verts, v1) || + BLI_gset_haskey(deleted_verts, v2)) + { + continue; + } + + /* Check that the edge still exists */ + if (!(e = BM_edge_exists(v1, v2))) { + continue; + } + + if (!BM_edge_loop_pair(e, &l_a, &l_b)) { + continue; + } + + v1_alt = l_a->prev->v; + v2_alt = l_b->prev->v; + + if (bm_edge_calc_volume_weighted(e) > min_volume) { + continue; + } + + /* Check that the edge's vertices are still in the PBVH. It's + * possible that an edge collapse has deleted adjacent faces + * and the node has been split, thus leaving wire edges and + * associated vertices. */ + if ((BM_ELEM_CD_GET_INT(e->v1, eq_ctx->cd_vert_node_offset) == DYNTOPO_NODE_NONE) || + (BM_ELEM_CD_GET_INT(e->v2, eq_ctx->cd_vert_node_offset) == DYNTOPO_NODE_NONE)) + { + continue; + } + + any_collapsed = true; + + /* Remove all faces adjacent to the edge, we _KNOW_ there are 2! */ + while ((l_adj = e->l)) { + BMFace *f_adj = l_adj->f; + pbvh_bmesh_face_remove(bvh, f_adj); + BM_face_kill(bvh->bm, f_adj); + } + + e_alt = BM_edge_create(bvh->bm, v1_alt, v2_alt, NULL, BM_CREATE_NO_DOUBLE); + + pbvh_bmesh_collapse_edge(bvh, e_alt, v1_alt, v2_alt, + deleted_verts, + deleted_faces, eq_ctx); + } + + BLI_gset_free(deleted_verts, NULL); + + return any_collapsed; +} +#endif /* USE_HOLE_VOLUME_CLEAN */ + /************************* Called from pbvh.c *************************/ bool pbvh_bmesh_node_raycast(PBVHNode *node, const float ray_start[3], @@ -1107,6 +1453,462 @@ bool pbvh_bmesh_node_raycast(PBVHNode *node, const float ray_start[3], return hit; } +/* remove sides of the bridge when there are adjacent holes, + * so 2 holes form a larger hole (typically what you want) */ +// #define USE_BRIDGE_MERGE_HOLES + +/* disallow bridges sharing vertices */ +#define USE_BRIDGE_STRICT + +#define USE_BRIDGE_CLEAN + +/* radial walk the vert edges */ +static bool bm_vert_ordered_fan_walk(BMVert *v, BLI_Buffer *buf) +{ + BMLoop *l_iter, *l_first; + BMEdge *e_prev; + BLI_assert(buf->count == 0); + + l_iter = l_first = BM_vert_find_first_loop(v); + if (l_iter == NULL) + return false; + + e_prev = l_first->prev->e; + do { + BMVert *v_other; + /* boundary, we're not interested! */ + if (UNLIKELY(l_iter == NULL)) { + return false; + } + v_other = BM_edge_other_vert(e_prev, v); + BLI_buffer_append(buf, BMVert *, v_other); + +#ifdef USE_BRIDGE_MERGE_HOLES + /* ensure all connected faces have tags disabled */ + { + BMLoop *l_first_radial = l_iter->next->radial_next; + BMLoop *l_iter_radial = l_first_radial->radial_next; + if (l_first_radial != l_iter_radial) { + do { + BM_elem_flag_disable(l_iter_radial->prev->v, BM_ELEM_TAG); + } while ((l_iter_radial = l_iter_radial->radial_next) != l_first_radial); + } + BM_elem_flag_disable(v_other, BM_ELEM_TAG); + } +#endif + + } while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first)); + return true; +} + +#ifdef USE_BRIDGE_MERGE_HOLES +static void pbvh_bmesh_delete_edge_face_tagged_radial( + PBVH *bvh, BMLoop *l_rim, EdgeQueueContext *eq_ctx) +{ + /* will only be a single face in most cases (manifold edge) + * but l_rim is attached to the central vertex, so don't touch it */ + BMLoop *l_iter = l_rim->radial_next; + BMLoop *l_next; + if (l_rim != l_iter) { + do { + /* vert on the triangle, not attached to this current edge-loop + * if its tagged we know both bridge-loops share this face and it should be removed */ + BMVert *v_other = l_iter->prev->v; + l_next = l_iter->radial_next; + + if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { + BLI_assert(!BM_vert_in_face(l_iter->f, l_rim->prev->v)); + pbvh_bmesh_delete_edge_face(bvh, l_iter->f, eq_ctx); + printf("Removing border\n"); + } + } while ((l_iter = l_next) != l_rim); + } +} +#endif /* USE_BRIDGE_MERGE_HOLES */ + +#if defined(USE_BRIDGE_MERGE_HOLES) || defined(USE_BRIDGE_STRICT) +static void bm_earray_tag( + BMElemF **earr, int earr_num, + bool tag) +{ + int i; + + if (tag) { + for (i = 0; i < earr_num; i++) { + BM_elem_flag_enable(earr[i], BM_ELEM_TAG); + } + } + else { + for (i = 0; i < earr_num; i++) { + BM_elem_flag_disable(earr[i], BM_ELEM_TAG); + } + } +} +#endif + +#ifdef USE_BRIDGE_STRICT +static bool bm_earray_tag_check_any( + BMElemF **earr, int earr_num) +{ + int i; + + for (i = 0; i < earr_num; i++) { + if (BM_elem_flag_test(earr[i], BM_ELEM_TAG)) { + return true; + } + } + return false; +} +#endif + +static void bm_varray_center( + const BMVert **varr, const int varr_num, + float r_center[3]) +{ + int i; + + zero_v3(r_center); + for (i = 0; i < varr_num; i++) { + add_v3_v3(r_center, varr[i]->co); + } + mul_v3_fl(r_center, 1.0f / (float)varr_num); +} + +static void bm_varray_normal( + const BMVert **varr, int varr_num, + float r_normal[3]) +{ + const BMVert *v_prev = varr[varr_num - 1]; + const BMVert *v_curr = varr[0]; + int i; + + zero_v3(r_normal); + + /* Newell's Method */ + for (i = 0; i < varr_num; v_prev = v_curr, v_curr = varr[++i]) { + add_newell_cross_v3_v3v3(r_normal, v_prev->co, v_curr->co); + } + + normalize_v3(r_normal); +} + +static void bm_varray_dirs_2d( + const BMVert **varr, int varr_num, + float axis_mat[3][3], const float center[3], + float (*r_dirs)[2]) +{ + float center_2d[2]; + int i; + + mul_v2_m3v3(center_2d, axis_mat, center); + + for (i = 0; i < varr_num; i++) { + mul_v2_m3v3(r_dirs[i], axis_mat, varr[i]->co); + sub_v2_v2(r_dirs[i], center_2d); + normalize_v2(r_dirs[i]); + } +} + +static void pbvh_bridge_loops( + PBVH *bvh, + BMVert **eloop_a, int eloop_a_len, + BMVert **eloop_b, int eloop_b_len) +{ + float (*eloop_a_dirs)[2] = BLI_array_alloca(eloop_a_dirs, eloop_a_len); + float (*eloop_b_dirs)[2] = BLI_array_alloca(eloop_b_dirs, eloop_b_len); + float eloop_a_cent[3], eloop_a_normal[3]; + float eloop_b_cent[3], eloop_b_normal[3]; + float axis[3]; + float axis_mat[3][3]; + int a_offset = 0; + int b_offset = 0; + int a_step_base; + int b_step_base; + + BLI_assert(eloop_a_len >= eloop_b_len); + + bm_varray_center((const BMVert **)eloop_a, eloop_a_len, eloop_a_cent); + bm_varray_center((const BMVert **)eloop_b, eloop_b_len, eloop_b_cent); + + bm_varray_normal((const BMVert **)eloop_a, eloop_a_len, eloop_a_normal); + bm_varray_normal((const BMVert **)eloop_b, eloop_b_len, eloop_b_normal); + + if (dot_v3v3(eloop_a_normal, eloop_b_normal) < 0.0f) { + BLI_array_reverse(eloop_b, eloop_b_len); + negate_v3(eloop_b_normal); + } + + add_v3_v3v3(axis, eloop_a_normal, eloop_b_normal); + normalize_v3(axis); + + axis_dominant_v3_to_m3(axis_mat, axis); + + bm_varray_dirs_2d((const BMVert **)eloop_a, eloop_a_len, axis_mat, eloop_a_cent, eloop_a_dirs); + bm_varray_dirs_2d((const BMVert **)eloop_b, eloop_b_len, axis_mat, eloop_b_cent, eloop_b_dirs); + + /* find closest angle on the smaller loop */ + { + float t_best; + int i; + + a_offset = 0; + + t_best = -1.0f; + for (i = 0; i < eloop_b_len; i++) { + float t = dot_v2v2(eloop_a_dirs[a_offset], eloop_b_dirs[i]); + if (t > t_best) { + t_best = t; + b_offset = i; + } + } + } + + a_step_base = 0; + b_step_base = 0; + + do { + BMFace *f_new; + BMVert *v_tri[3]; + + /* Step (false == a, true == b) */ + bool step_side; + + const int a_curr = ((a_step_base + a_offset)) % eloop_a_len; + const int b_curr = ((b_step_base + b_offset)) % eloop_b_len; + const int a_next = ((a_step_base + a_offset) + 1) % eloop_a_len; + const int b_next = ((b_step_base + b_offset) + 1) % eloop_b_len; + + if ((a_step_base != eloop_a_len) && (b_step_base == eloop_b_len)) { + step_side = false; + } + else if ((a_step_base == eloop_a_len) && (b_step_base != eloop_b_len)) { + step_side = true; + } + else { + if (dot_v2v2(eloop_a_dirs[a_curr], eloop_b_dirs[b_next]) < + dot_v2v2(eloop_a_dirs[a_next], eloop_b_dirs[b_curr])) + { + step_side = false; + } + else { + step_side = true; + } + } + + if (step_side == false) { + v_tri[0] = eloop_b[b_curr]; + v_tri[1] = eloop_a[a_curr]; + v_tri[2] = eloop_a[a_next]; + a_step_base += 1; + } + else { + v_tri[0] = eloop_a[a_curr]; + v_tri[2] = eloop_b[b_curr]; + v_tri[1] = eloop_b[b_next]; + b_step_base += 1; + } + BLI_assert(a_step_base <= eloop_a_len); + BLI_assert(b_step_base <= eloop_b_len); + + /* possible loops share verts */ + if (!ELEM(v_tri[0], v_tri[1], v_tri[2]) && + !BM_face_exists(v_tri, 3, NULL)) + { + BMEdge *e_tri[3]; + int i; + BLI_assert(!ELEM(v_tri[1], v_tri[2], v_tri[0]) && + !ELEM(v_tri[2], v_tri[0], v_tri[1])); + + bm_edges_from_tri(bvh->bm, v_tri, e_tri); + + /* (v_tri[1] -> v_tri[2]), needs to have a face else we ignore */ + if (e_tri[1]->l) { + BMLoop *l_rim = e_tri[1]->l; + BMFace *f_rim = l_rim->f; + PBVHNode *n = pbvh_bmesh_node_lookup(bvh, f_rim); + const int ni = n - bvh->nodes; + + /* winding should be correct in most cases (when verts face away from eachother at least)... + * Even so, better base it off adjacent face to keep normals contiguous. */ + if (l_rim->v == v_tri[1]) { + SWAP(BMVert *, v_tri[1], v_tri[2]); + SWAP(BMEdge *, e_tri[0], e_tri[2]); + } + + f_new = pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f_rim); + (void)f_new; + + for (i = 0; i < 3; i++) { + if (!BLI_gset_haskey(n->bm_unique_verts, v_tri[i]) && + !BLI_gset_haskey(n->bm_other_verts, v_tri[i])) + { + BLI_gset_insert(n->bm_other_verts, v_tri[i]); + } + } + } + else { + printf("Ignoring boundary\n"); + } + } + } while ((a_step_base != eloop_a_len) || + (b_step_base != eloop_b_len)); +} + +static void pbvh_bmesh_collapse_close_verts(EdgeQueueContext *eq_ctx, + PBVH *bvh) +{ + int counter = 0; + BLI_buffer_declare_static(BMVert *, edge_verts_v1, BLI_BUFFER_NOP, 32); + BLI_buffer_declare_static(BMVert *, edge_verts_v2, BLI_BUFFER_NOP, 32); +#ifdef USE_BRIDGE_CLEAN + BLI_buffer_declare_static(BMFace *, face_clean, BLI_BUFFER_NOP, 32); +#endif + GSet *deleted_verts = BLI_gset_ptr_new_ex("deleted_verts", BLI_heap_size(eq_ctx->q->heap)); + + while (!BLI_heap_is_empty(eq_ctx->q->heap)) { + BMLoop *l; + BMVert **pair = BLI_heap_popmin(eq_ctx->q->heap); + BMVert *v1, *v2; + + v1 = pair[0]; + v2 = pair[1]; + + edge_verts_v1.count = 0; + edge_verts_v2.count = 0; + + counter++; + + /* check if an edge exists with those two vertices already. + * It is possible if an adjacent vertex pair is joined that + * the two vertices already share an edge. Joining the edge rings + * would then be impossible */ + if (BLI_gset_haskey(deleted_verts, v1) || + BLI_gset_haskey(deleted_verts, v2) || + BM_edge_exists(v1, v2)) + /* no need to check 'BM_vert_is_boundary', walking edges below will do. */ + { + continue; + } + + /* Regarding the check for '< 3' verts, this should NOT happen, + * but have a guard here to prevent crashing for now */ + if (!bm_vert_ordered_fan_walk(v1, &edge_verts_v1) || (edge_verts_v1.count < 3)) + continue; + if (!bm_vert_ordered_fan_walk(v2, &edge_verts_v2) || (edge_verts_v2.count < 3)) + continue; + +#ifdef USE_BRIDGE_STRICT + bm_earray_tag(edge_verts_v1.data, edge_verts_v1.count, false); + bm_earray_tag(edge_verts_v2.data, edge_verts_v2.count, true); + if (bm_earray_tag_check_any(edge_verts_v1.data, edge_verts_v1.count)) { + printf("Bridges share verts!\n"); + continue; + } +#endif + +#ifdef USE_BRIDGE_MERGE_HOLES + bm_earray_tag(edge_verts_v1.data, edge_verts_v1.count, true); + bm_earray_tag(edge_verts_v2.data, edge_verts_v2.count, true); + + /* ensure we don't remove radial faces here */ + BM_elem_flag_disable(v1, BM_ELEM_TAG); + BM_elem_flag_disable(v2, BM_ELEM_TAG); +#endif + + /* Remove the faces (would use 'BM_FACES_OF_VERT' except we can't look on data we remove) */ + while ((l = BM_vert_find_first_loop(v1))) { +#ifdef USE_BRIDGE_MERGE_HOLES + pbvh_bmesh_delete_edge_face_tagged_radial(bvh, l->next, eq_ctx); +#endif + BLI_assert(BM_ELEM_CD_GET_INT(l->f, eq_ctx->cd_face_node_offset) != DYNTOPO_NODE_NONE); + pbvh_bmesh_delete_edge_face(bvh, l->f); + } + while ((l = BM_vert_find_first_loop(v2))) { +#ifdef USE_BRIDGE_MERGE_HOLES + pbvh_bmesh_delete_edge_face_tagged_radial(bvh, l->next, eq_ctx); +#endif + BLI_assert(BM_ELEM_CD_GET_INT(l->f, eq_ctx->cd_face_node_offset) != DYNTOPO_NODE_NONE); + pbvh_bmesh_delete_edge_face(bvh, l->f); + } + + /* Note, maybe this should be done after deletion of the vertices? */ + if (edge_verts_v2.count < edge_verts_v1.count) { + pbvh_bridge_loops( + bvh, + edge_verts_v1.data, edge_verts_v1.count, + edge_verts_v2.data, edge_verts_v2.count); + } + else { + pbvh_bridge_loops( + bvh, + edge_verts_v2.data, edge_verts_v2.count, + edge_verts_v1.data, edge_verts_v1.count); + } + + if (BM_ELEM_CD_GET_INT(v1, eq_ctx->cd_vert_node_offset) != DYNTOPO_NODE_NONE) + pbvh_bmesh_vert_remove(bvh, v1); + if (BM_ELEM_CD_GET_INT(v2, eq_ctx->cd_vert_node_offset) != DYNTOPO_NODE_NONE) + pbvh_bmesh_vert_remove(bvh, v2); + + BM_log_vert_removed(bvh->bm_log, v1, eq_ctx->cd_vert_mask_offset); + BM_vert_kill(bvh->bm, v1); + BLI_gset_insert(deleted_verts, v1); + BM_log_vert_removed(bvh->bm_log, v2, eq_ctx->cd_vert_mask_offset); + BM_vert_kill(bvh->bm, v2); + BLI_gset_insert(deleted_verts, v2); + + +#ifdef USE_BRIDGE_CLEAN + { + BLI_Buffer *bufs[2] = {&edge_verts_v1, &edge_verts_v2}; + int i, j; + + + for (j = 0; j < 2; j++) { + BMVert **varr = BLI_buffer_array(bufs[j], BMVert *); + for (i = 0; i < bufs[j]->count; i++) { + BMVert *v = varr[i]; + + if (!BLI_gset_haskey(deleted_verts, v)) { + BMIter bm_iter; + BMLoop *l; + + face_clean.count = 0; + BM_ITER_ELEM (l, &bm_iter, v, BM_LOOPS_OF_VERT) { + if ((BM_edge_is_boundary(l->prev->e) || + BM_edge_is_boundary(l->e) || + BM_edge_is_boundary(l->next->e))) + { + BLI_buffer_append(&face_clean, BMFace *, l->f); + } + } + + if (face_clean.count != 0) { + BMFace **farr = BLI_buffer_array(&face_clean, BMFace *); + int k; + for (k = 0; k < face_clean.count; k++) { + pbvh_bmesh_delete_vert_face(bvh, NULL, farr[k], deleted_verts, eq_ctx); + printf("Cleaning bad face!\n"); + } + } + } + } + } + } +#endif + + } + BLI_buffer_free(&edge_verts_v1); + BLI_buffer_free(&edge_verts_v2); + +#ifdef USE_BRIDGE_CLEAN + BLI_buffer_free(&face_clean); +#endif + + BLI_gset_free(deleted_verts, NULL); +} + + bool BKE_pbvh_bmesh_node_raycast_detail( PBVHNode *node, const float ray_start[3], const float ray_normal[3], @@ -1272,6 +2074,33 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode, BLI_mempool_destroy(queue_pool); } + if (mode & PBVH_TopologyGenus) { + EdgeQueue q; + BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), + 128, 128, 0); + EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset, cd_vert_node_offset, cd_face_node_offset}; + + close_vert_queue_create(&eq_ctx, bvh, center, radius); + pbvh_bmesh_collapse_close_verts(&eq_ctx, bvh); + BLI_heap_free(q.heap, NULL); + BLI_mempool_destroy(queue_pool); + } + + /* remove low volume areas (test!) */ +#ifdef USE_HOLE_VOLUME_CLEAN + if (mode & PBVH_TopologyGenus) { + EdgeQueue q; + BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMEdge *), + 128, 128, 0); + EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset, cd_vert_node_offset, cd_face_node_offset}; + + tetrahedron_edge_queue_create(&eq_ctx, bvh, center, radius); + pbvh_bmesh_collapse_small_tetrahedrons(&eq_ctx, bvh, &deleted_faces); + BLI_heap_free(q.heap, NULL); + BLI_mempool_destroy(queue_pool); + } +#endif + if (mode & PBVH_Subdivide) { EdgeQueue q; BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), 0, 128, BLI_MEMPOOL_NOP); |