2 files changed, 270 insertions, 44 deletions

diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index 53e41c1dec8..3d12483dac0 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -140,9 +140,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 14a2ee0c3e7..e84ec9902de 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -29,6 +29,7 @@
 #include "BLI_ghash.h"
 #include "BLI_heap.h"
 #include "BLI_math.h"
+#include "BLI_listbase.h"
 
 #include "BKE_ccg.h"
 #include "BKE_DerivedMesh.h"
@@ -684,6 +685,154 @@ static void short_edge_queue_create(EdgeQueueContext *eq_ctx,
 	}
 }
 
+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);
+		}
+		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);
+	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]);
+		}
+	}
+}
+
+
+/* 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;
+					BLI_heap_insert(eq_ctx->q->heap, dist_sq, pair);
+				}
+
+				/* 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])
@@ -915,48 +1064,7 @@ static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
 	/* 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], eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
-			}
-			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);
-		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
@@ -1071,6 +1179,110 @@ bool pbvh_bmesh_node_raycast(PBVHNode *node, const float ray_start[3],
 	return hit;
 }
 
+/* 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);
+	e_prev = l_first->prev->e;
+	if (l_iter == NULL)
+		return false;
+
+	do {
+		/* boundary, we're not interested! */
+		if (UNLIKELY(l_iter == NULL)) {
+			return false;
+		}
+		BLI_buffer_append(buf, BMVert *, BM_edge_other_vert(e_prev, v));
+	} while (((l_iter = BM_vert_step_fan_loop(l_iter, &e_prev)) != l_first));
+	return true;
+}
+
+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);
+
+	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;
+		}
+
+		if (!bm_vert_ordered_fan_walk(v1, &edge_verts_v1))
+			continue;
+		if (!bm_vert_ordered_fan_walk(v2, &edge_verts_v2))
+			continue;
+
+		/* this should NOT happen, but have a guard here to prevent crashing for now */
+		if (edge_verts_v1.count < 3 || edge_verts_v2.count < 3) {
+			continue;
+		}
+
+		/* Note, maybe this should be done after deletion of the vertices? */
+#if 0
+		if (edge_verts_v2.count > edge_verts_v1.count) {
+			pbvh_bridge_loops(bvh, &edge_verts_v1, &edge_verts_v2, deleted_verts);
+		}
+		else {
+			pbvh_bridge_loops(bvh, &edge_verts_v2, &edge_verts_v1, deleted_verts);
+		}
+#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))) {
+			pbvh_bmesh_delete_vert_face(bvh, v1, l->f, deleted_verts, eq_ctx);
+		}
+		while ((l = BM_vert_find_first_loop(v2))) {
+			pbvh_bmesh_delete_vert_face(bvh, v2, l->f, deleted_verts, eq_ctx);
+		}
+
+		if (BM_ELEM_CD_GET_INT(v1, eq_ctx->cd_vert_node_offset) != DYNTOPO_NODE_NONE)
+			pbvh_bmesh_vert_remove(bvh, v1, eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
+		if (BM_ELEM_CD_GET_INT(v2, eq_ctx->cd_vert_node_offset) != DYNTOPO_NODE_NONE)
+			pbvh_bmesh_vert_remove(bvh, v2, eq_ctx->cd_vert_node_offset, eq_ctx->cd_face_node_offset);
+
+		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);
+	}
+	BLI_buffer_free(&edge_verts_v1);
+	BLI_buffer_free(&edge_verts_v2);
+
+	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],
@@ -1236,6 +1448,18 @@ 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);
+	}
+
 	if (mode & PBVH_Subdivide) {
 		EdgeQueue q;
 		BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), 0, 128, BLI_MEMPOOL_NOP);