[Bf-blender-cvs] [329bf8e1bf0] master: BMesh: improve edge rotate when edges share faces

Campbell Barton noreply at git.blender.org
Sun Nov 26 07:39:15 CET 2017


Commit: 329bf8e1bf0e9c74a7ef9426dcb237df9ac1287d
Author: Campbell Barton
Date:   Sun Nov 26 17:48:00 2017 +1100
Branches: master
https://developer.blender.org/rB329bf8e1bf0e9c74a7ef9426dcb237df9ac1287d

BMesh: improve edge rotate when edges share faces

Previously outcome depended on order of edges,
now the longest boundary edges are rotated first,
then the faces connected edges.

This gives more predictable results, allowing regions containing
a vertex fan to be rotated onto the next vertex.

===================================================================

M	source/blender/bmesh/operators/bmo_rotate_edge.c

===================================================================

diff --git a/source/blender/bmesh/operators/bmo_rotate_edge.c b/source/blender/bmesh/operators/bmo_rotate_edge.c
index e4b15c6a0ef..d4cafdd0dde 100644
--- a/source/blender/bmesh/operators/bmo_rotate_edge.c
+++ b/source/blender/bmesh/operators/bmo_rotate_edge.c
@@ -27,62 +27,234 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_math.h"
+#include "BLI_heap.h"
 
 #include "bmesh.h"
 
 #include "intern/bmesh_operators_private.h" /* own include */
 
-void bmo_rotate_edges_exec(BMesh *bm, BMOperator *op)
+#define EDGE_OUT   1
+#define FACE_MARK 1
+
+/**
+ * Rotate edges where every edge has it's own faces (we can rotate in any order).
+ */
+static void bm_rotate_edges_simple(
+        BMesh *bm, BMOperator *op,
+        const short check_flag, const bool use_ccw)
 {
 	BMOIter siter;
-	BMEdge *e, *e2;
-	const bool use_ccw   = BMO_slot_bool_get(op->slots_in, "use_ccw");
-	const bool is_single = BMO_slot_buffer_count(op->slots_in, "edges") == 1;
-	short check_flag = is_single ?
-	            BM_EDGEROT_CHECK_EXISTS :
-	            BM_EDGEROT_CHECK_EXISTS | BM_EDGEROT_CHECK_DEGENERATE;
-
-#define EDGE_OUT   1
-#define FACE_TAINT 1
+	BMEdge *e;
 
 	BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
 		/**
 		 * this ends up being called twice, could add option to not to call check in
 		 * #BM_edge_rotate to get some extra speed */
 		if (BM_edge_rotate_check(e)) {
-			BMFace *fa, *fb;
-			if (BM_edge_face_pair(e, &fa, &fb)) {
+			BMEdge *e_rotate = BM_edge_rotate(bm, e, use_ccw, check_flag);
+			if (e_rotate != NULL) {
+				BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
+			}
+		}
+	}
+}
+
+
+/**
+ * Edge length is just a way of ordering that's independent of order in the edges argument,
+ * we could use some other method since ideally all edges will be rotated,
+ * this just happens to be simple to calculate.
+ */
+static float bm_edge_calc_rotate_cost(const BMEdge *e)
+{
+	return -BM_edge_calc_length_squared(e);
+}
+
+/**
+ * Check if this edge is a boundary: Are more than one of the connected faces edges rotating too?
+ */
+static float bm_edge_rotate_is_boundary(const BMEdge *e)
+{
+	/* Number of adjacent shared faces. */
+	int count = 0;
+	BMLoop *l_radial_iter = e->l;
+	do {
+		/* Skip this edge. */
+		BMLoop *l_iter = l_radial_iter->next;
+		do {
+			BMEdge *e_iter = l_iter->e;
+			const int e_iter_index = BM_elem_index_get(e_iter);
+			if ((e_iter_index != -1)) {
+				if (count == 1) {
+					return false;
+				}
+				count += 1;
+				break;
+			}
+		} while ((l_iter = l_iter->next) != l_radial_iter);
+	} while ((l_radial_iter = l_radial_iter->radial_next) != e->l);
+	return true;
+}
+
+/**
+ * Rotate edges where edges share faces,
+ * edges which could not rotate need to be re-considered after neighbors are rotated.
+ */
+static void bm_rotate_edges_shared(
+        BMesh *bm, BMOperator *op,
+        short check_flag, const bool use_ccw, const int edges_len)
+{
+	Heap *heap = BLI_heap_new_ex(edges_len);
+	HeapNode **eheap_table = MEM_mallocN(sizeof(*eheap_table) * edges_len, __func__);
+	int edges_len_rotate = 0;
+
+	{
+		BMIter iter;
+		BMEdge *e;
+		BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+			BM_elem_index_set(e, -1);  /* set_dirty! */
+		}
+		bm->elem_index_dirty |= BM_EDGE;
+	}
+
+	{
+		BMOIter siter;
+		BMEdge *e;
+		uint i;
+		BMO_ITER_INDEX (e, &siter, op->slots_in, "edges", BM_EDGE, i) {
+			BM_elem_index_set(e, BM_edge_is_manifold(e) ? i : -1);  /* set_dirty! */
+			eheap_table[i] = NULL;
+		}
+	}
 
-				/* check we're untouched */
-				if (BMO_face_flag_test(bm, fa, FACE_TAINT) == false &&
-				    BMO_face_flag_test(bm, fb, FACE_TAINT) == false)
-				{
+	/* First operate on boundary edges, this is often all that's needed,
+	 * regions that have no boundaries are handles after. */
+	enum {
+		PASS_TYPE_BOUNDARY = 0,
+		PASS_TYPE_ALL = 1,
+		PASS_TYPE_DONE = 2,
+	};
+	uint pass_type = PASS_TYPE_BOUNDARY;
 
-					/* don't touch again (faces will be freed so run before rotating the edge) */
-					BMO_face_flag_enable(bm, fa, FACE_TAINT);
-					BMO_face_flag_enable(bm, fb, FACE_TAINT);
 
-					if (!(e2 = BM_edge_rotate(bm, e, use_ccw, check_flag))) {
+	while ((pass_type != PASS_TYPE_DONE) && (edges_len_rotate != edges_len)) {
+		BLI_assert(BLI_heap_is_empty(heap));
+		{
+			BMOIter siter;
+			BMEdge *e;
+			uint i;
+			BMO_ITER_INDEX (e, &siter, op->slots_in, "edges", BM_EDGE, i) {
+				BLI_assert(eheap_table[i] == NULL);
 
-						BMO_face_flag_disable(bm, fa, FACE_TAINT);
-						BMO_face_flag_disable(bm, fb, FACE_TAINT);
-#if 0
-						BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Could not rotate edge");
-						return;
-#endif
+				bool ok = (BM_elem_index_get(e) != -1) && BM_edge_rotate_check(e);
 
-						continue;
+				if (ok) {
+					if (pass_type == PASS_TYPE_BOUNDARY) {
+						ok = bm_edge_rotate_is_boundary(e);
 					}
+				}
+
+				if (ok) {
+					float cost = bm_edge_calc_rotate_cost(e);
+					eheap_table[i] = BLI_heap_insert(heap, cost, e);
+				}
+			}
+		}
+
+		if (BLI_heap_is_empty(heap)) {
+			pass_type += 1;
+			continue;
+		}
+
+		const int edges_len_rotate_prev = edges_len_rotate;
+		while (!BLI_heap_is_empty(heap)) {
+			BMEdge *e_best = BLI_heap_popmin(heap);
+			eheap_table[BM_elem_index_get(e_best)] = NULL;
 
-					BMO_edge_flag_enable(bm, e2, EDGE_OUT);
+			/* No problem if this fails, re-evaluate if faces connected to this edge are touched. */
+			if (BM_edge_rotate_check(e_best)) {
+				BMEdge *e_rotate = BM_edge_rotate(bm, e_best, use_ccw, check_flag);
+				if (e_rotate != NULL) {
+					BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
+
+					/* invalidate so we don't try touch this again. */
+					BM_elem_index_set(e_rotate, -1);  /* set_dirty! */
+
+					edges_len_rotate += 1;
+
+					/* Note: we could validate all edges which have not been rotated
+					 * (not just previously degenerate edges).
+					 * However there is no real need - they can be left until they're popped off the queue. */
+
+					/* We don't know the exact topology after rotating the edge,
+					 * so loop over all faces attached to the new edge, typically this will only be two faces. */
+					BMLoop *l_radial_iter = e_rotate->l;
+					do {
+						/* Skip this edge. */
+						BMLoop *l_iter = l_radial_iter->next;
+						do {
+							BMEdge *e_iter = l_iter->e;
+							const int e_iter_index = BM_elem_index_get(e_iter);
+							if ((e_iter_index != -1) && (eheap_table[e_iter_index] == NULL)) {
+								if (BM_edge_rotate_check(e_iter)) {
+									/* Previously degenerate, now valid. */
+									float cost = bm_edge_calc_rotate_cost(e_iter);
+									eheap_table[e_iter_index] = BLI_heap_insert(heap, cost, e_iter);
+								}
+							}
+						} while ((l_iter = l_iter->next) != l_radial_iter);
+					} while ((l_radial_iter = l_radial_iter->radial_next) != e_rotate->l);
 				}
 			}
 		}
+
+		/* If no actions were taken, move onto the next pass. */
+		if (edges_len_rotate == edges_len_rotate_prev) {
+			pass_type += 1;
+			continue;
+		}
 	}
 
-	BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
+	BLI_heap_free(heap, NULL);
+	MEM_freeN(eheap_table);
+}
 
-#undef EDGE_OUT
-#undef FACE_TAINT
+void bmo_rotate_edges_exec(BMesh *bm, BMOperator *op)
+{
+	BMOIter siter;
+	BMEdge *e;
+	const int edges_len  = BMO_slot_buffer_count(op->slots_in, "edges");
+	const bool use_ccw   = BMO_slot_bool_get(op->slots_in, "use_ccw");
+	const bool is_single = (edges_len ==  1);
+	short check_flag = is_single ?
+	        BM_EDGEROT_CHECK_EXISTS :
+	        BM_EDGEROT_CHECK_EXISTS | BM_EDGEROT_CHECK_DEGENERATE;
+
+	bool is_simple = true;
+	if (is_single == false) {
+		BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
+			BMFace *f_pair[2];
+			if (BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) {
+				for (uint i = 0; i < ARRAY_SIZE(f_pair); i += 1) {
+					if (BMO_face_flag_test(bm, f_pair[i], FACE_MARK)) {
+						is_simple = false;
+						break;
+					}
+					BMO_face_flag_enable(bm, f_pair[i], FACE_MARK);
+				}
+				if (is_simple == false) {
+					break;
+				}
+			}
+		}
+	}
 
+	if (is_simple) {
+		bm_rotate_edges_simple(bm, op, use_ccw, check_flag);
+	}
+	else {
+		bm_rotate_edges_shared(bm, op, check_flag, use_ccw, edges_len);
+	}
+
+	BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
 }



More information about the Bf-blender-cvs mailing list