Commit: 54ee22130ca0ce59500c6eddb562b78eb4526bcd
Author: Campbell Barton
Date: Sat Oct 11 14:17:14 2014 +0200
Branches: dyntopo_holes
https://developer.blender.org/rB54ee22130ca0ce59500c6eddb562b78eb4526bcd
Merge branch 'master' into dyntopo_holes
Conflicts:
source/blender/blenkernel/intern/pbvh_bmesh.c
===================================================================
===================================================================
diff --cc source/blender/blenkernel/intern/pbvh_bmesh.c
index 28c01e0,9e18d54..e0cf9ee
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@@ -764,224 -722,6 +802,224 @@@ static void short_edge_queue_create(Edg
}
}
+#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],
eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
++ pbvh_bmesh_vert_remove(bvh, v_tri[j]);
+ }
+ else {
+ v_tri[j] = NULL;
+ }
+ }
+
+ /* Remove the face */
- pbvh_bmesh_face_remove(bvh, f_del, eq_ctx->cd_vert_node_offset,
eq_ctx->cd_face_node_offset);
++ 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,
EdgeQueueContext *eq_ctx)
++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, eq_ctx->cd_vert_node_offset,
eq_ctx->cd_face_node_offset);
++ 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])
@@@ -1283,95 -1065,6 +1322,95 @@@ static bool pbvh_bmesh_collapse_short_e
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,
eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
++ 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],
@@@ -1414,462 -1107,6 +1453,462 @@@
retu
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
