[Bf-blender-cvs] [c6b27dd] master: BMesh: improve path-select fill region w/ ngons

Campbell Barton noreply at git.blender.org
Fri Apr 1 14:33:39 CEST 2016


Commit: c6b27dd4fa02b2609a18ce3aa9c71b64e12b500d
Author: Campbell Barton
Date:   Fri Apr 1 23:27:31 2016 +1100
Branches: master
https://developer.blender.org/rBc6b27dd4fa02b2609a18ce3aa9c71b64e12b500d

BMesh: improve path-select fill region w/ ngons

Rewrote to work with ngons and and more complex topology, now uses separate function.
Fixes T48009.

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

M	source/blender/bmesh/CMakeLists.txt
M	source/blender/bmesh/bmesh_tools.h
M	source/blender/bmesh/tools/bmesh_path.c
M	source/blender/bmesh/tools/bmesh_path.h
A	source/blender/bmesh/tools/bmesh_path_region.c
A	source/blender/bmesh/tools/bmesh_path_region.h
M	source/blender/editors/mesh/editmesh_path.c

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

diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 1afa98f..30fefe3 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -148,6 +148,8 @@ set(SRC
 	tools/bmesh_intersect.h
 	tools/bmesh_path.c
 	tools/bmesh_path.h
+	tools/bmesh_path_region.c
+	tools/bmesh_path_region.h
 	tools/bmesh_region_match.c
 	tools/bmesh_region_match.h
 	tools/bmesh_triangulate.c
diff --git a/source/blender/bmesh/bmesh_tools.h b/source/blender/bmesh/bmesh_tools.h
index f7f767f..23212dd 100644
--- a/source/blender/bmesh/bmesh_tools.h
+++ b/source/blender/bmesh/bmesh_tools.h
@@ -41,6 +41,7 @@ extern "C" {
 #include "tools/bmesh_edgenet.h"
 #include "tools/bmesh_edgesplit.h"
 #include "tools/bmesh_path.h"
+#include "tools/bmesh_path_region.h"
 #include "tools/bmesh_region_match.h"
 #include "tools/bmesh_triangulate.h"
 
diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c
index 79a002f..30b083c 100644
--- a/source/blender/bmesh/tools/bmesh_path.c
+++ b/source/blender/bmesh/tools/bmesh_path.c
@@ -15,13 +15,6 @@
  * along with this program; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  *
- * The Original Code is Copyright (C) 2004 Blender Foundation.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): none yet.
- *
  * ***** END GPL LICENSE BLOCK *****
  */
 
@@ -36,14 +29,11 @@
 
 #include "BLI_math.h"
 #include "BLI_linklist.h"
-#include "BLI_stackdefines.h"
 #include "BLI_heap.h"
 
 #include "bmesh.h"
 #include "bmesh_path.h"  /* own include */
 
-/* optionally expand all paths (result is no longer ordered) */
-#define USE_PATH_FILL
 
 /* -------------------------------------------------------------------- */
 /* Generic Helpers */
@@ -71,72 +61,6 @@ static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3
 /* -------------------------------------------------------------------- */
 /* BM_mesh_calc_path_vert */
 
-#ifdef USE_PATH_FILL
-static void verttag_calc_fill_steps(
-        BMesh *bm, BMVert *v_start, int *steps, int steps_max, BMVert **stack_array,
-        const struct BMCalcPathParams *params)
-{
-	copy_vn_i(steps, bm->totvert, steps_max);
-
-	BMVert **stack = stack_array;
-	STACK_DECLARE(stack);
-	STACK_INIT(stack, bm->totvert);
-
-	STACK_PUSH(stack, v_start);
-	steps[BM_elem_index_get(v_start)] = 0;
-
-	while (STACK_SIZE(stack) != 0) {
-		BMVert *v_a = STACK_POP(stack);
-		const int v_a_index = BM_elem_index_get(v_a);
-		int step_a = steps[v_a_index];
-
-		if (step_a < steps_max) {
-			{
-				BMIter eiter;
-				BMEdge *e;
-				/* loop over faces of face, but do so by first looping over loops */
-				BM_ITER_ELEM (e, &eiter, v_a, BM_EDGES_OF_VERT) {
-					BMVert *v_b = BM_edge_other_vert(e, v_a);
-					if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
-						/* we know 'v_b' is not visited, check it out! */
-						const int v_b_index = BM_elem_index_get(v_b);
-						const int step_b = step_a + 1;
-						if (steps[v_b_index] > step_b) {
-							steps[v_b_index] = step_b;
-							STACK_PUSH(stack, v_b);
-						}
-					}
-				}
-			}
-
-			if (params->use_step_face) {
-				BMIter liter;
-				BMLoop *l;
-				/* loop over faces of face, but do so by first looping over loops */
-				BM_ITER_ELEM (l, &liter, v_a, BM_LOOPS_OF_VERT) {
-					if (l->f->len > 3) {
-						/* skip loops on adjacent edges */
-						BMLoop *l_iter = l->next->next;
-						do {
-							BMVert *v_b = l_iter->v;
-							if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
-								/* we know 'v_b' is not visited, check it out! */
-								const int v_b_index = BM_elem_index_get(v_b);
-								const int step_b = step_a + 1;
-								if (steps[v_b_index] > step_b) {
-									steps[v_b_index] = step_b;
-									STACK_PUSH(stack, v_b);
-								}
-							}
-						} while ((l_iter = l_iter->next) != l->prev);
-					}
-				}
-			}
-		}
-	}
-}
-#endif /* USE_PATH_FILL */
-
 static void verttag_add_adjacent(
         Heap *heap, BMVert *v_a, BMVert **verts_prev, float *cost,
         const struct BMCalcPathParams *params)
@@ -196,7 +120,7 @@ static void verttag_add_adjacent(
 
 LinkNode *BM_mesh_calc_path_vert(
         BMesh *bm, BMVert *v_src, BMVert *v_dst, const struct BMCalcPathParams *params,
-        bool (*test_fn)(BMVert *, void *user_data), void *user_data)
+        bool (*filter_fn)(BMVert *, void *user_data), void *user_data)
 {
 	LinkNode *path = NULL;
 	/* BM_ELEM_TAG flag is used to store visited edges */
@@ -211,13 +135,7 @@ LinkNode *BM_mesh_calc_path_vert(
 	// BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG
 
 	BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
-		if (test_fn(v, user_data)) {
-			BM_elem_flag_disable(v, BM_ELEM_TAG);
-		}
-		else {
-			BM_elem_flag_enable(v, BM_ELEM_TAG);
-		}
-
+		BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data));
 		BM_elem_index_set(v, i); /* set_inline */
 	}
 	bm->elem_index_dirty &= ~BM_VERT;
@@ -258,36 +176,9 @@ LinkNode *BM_mesh_calc_path_vert(
 	}
 
 	if (v == v_dst) {
-		int path_len = 0;
 		do {
 			BLI_linklist_prepend(&path, v);
-			path_len++;
 		} while ((v = verts_prev[BM_elem_index_get(v)]));
-
-#ifdef USE_PATH_FILL
-		if (params->use_fill) {
-			BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
-				BM_elem_flag_set(v, BM_ELEM_TAG, !test_fn(v, user_data));
-			}
-
-			int *steps_src = MEM_mallocN(sizeof(*steps_src) * totvert, __func__);
-			int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totvert, __func__);
-
-			/* reuse memory */
-			BMVert **stack_array = verts_prev;
-			verttag_calc_fill_steps(bm, v_src, steps_src, path_len, stack_array, params);
-			verttag_calc_fill_steps(bm, v_dst, steps_dst, path_len, stack_array, params);
-
-			BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
-				if (steps_src[i] + steps_dst[i] < path_len) {
-					BLI_linklist_prepend(&path, v);
-				}
-			}
-
-			MEM_freeN(steps_src);
-			MEM_freeN(steps_dst);
-		}
-#endif
 	}
 
 	MEM_freeN(verts_prev);
@@ -300,86 +191,6 @@ LinkNode *BM_mesh_calc_path_vert(
 /* -------------------------------------------------------------------- */
 /* BM_mesh_calc_path_edge */
 
-#ifdef USE_PATH_FILL
-static void edgetag_calc_fill_steps(
-        BMesh *bm, BMEdge *e_start, int *steps, int steps_max, BMEdge **stack_array,
-        const struct BMCalcPathParams *params)
-{
-	copy_vn_i(steps, bm->totedge, steps_max);
-
-	BMEdge **stack = stack_array;
-	STACK_DECLARE(stack);
-	STACK_INIT(stack, bm->totedge);
-
-	STACK_PUSH(stack, e_start);
-	steps[BM_elem_index_get(e_start)] = 0;
-
-	while (STACK_SIZE(stack) != 0) {
-		BMEdge *e_a = STACK_POP(stack);
-		const int e_a_index = BM_elem_index_get(e_a);
-		int step_a = steps[e_a_index];
-
-		if (step_a < steps_max) {
-			/* unlike vert/face, stepping faces disables scanning connected edges
-			 * and only steps over faces (selecting a ring of edges instead of a loop) */
-			if (params->use_step_face == false) {
-				BMIter viter;
-				BMVert *v;
-
-				BMIter eiter;
-				BMEdge *e_b;
-
-				BM_ITER_ELEM (v, &viter, e_a, BM_VERTS_OF_EDGE) {
-					BM_ITER_ELEM (e_b, &eiter, v, BM_EDGES_OF_VERT) {
-						if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) {
-							/* we know 'e_b' is not visited, check it out! */
-							const int e_b_index = BM_elem_index_get(e_b);
-							const int step_b = step_a + 1;
-							if (steps[e_b_index] > step_b) {
-								steps[e_b_index] = step_b;
-								STACK_PUSH(stack, e_b);
-							}
-						}
-					}
-				}
-			}
-			else {
-				BMLoop *l_first, *l_iter;
-
-				l_iter = l_first = e_a->l;
-				do {
-					BMLoop *l_cycle_iter, *l_cycle_end;
-
-					l_cycle_iter = l_iter->next;
-					l_cycle_end = l_iter;
-
-					/* good, but we need to allow this otherwise paths may fail to connect at all */
-		#if 0
-					if (l_iter->f->len > 3) {
-						l_cycle_iter = l_cycle_iter->next;
-						l_cycle_end = l_cycle_end->prev;
-					}
-		#endif
-
-					do {
-						BMEdge *e_b = l_cycle_iter->e;
-						if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) {
-							/* we know 'e_b' is not visited, check it out! */
-							const int e_b_index = BM_elem_index_get(e_b);
-							const int step_b = step_a + 1;
-							if (steps[e_b_index] > step_b) {
-								steps[e_b_index] = step_b;
-								STACK_PUSH(stack, e_b);
-							}
-						}
-					} while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_end);
-				} while ((l_iter = l_iter->radial_next) != l_first);
-			}
-		}
-	}
-}
-#endif /* USE_PATH_FILL */
-
 static float edgetag_cut_cost_vert(BMEdge *e_a, BMEdge *e_b, BMVert *v)
 {
 	BMVert *v1 = BM_edge_other_vert(e_a, v);
@@ -496,13 +307,7 @@ LinkNode *BM_mesh_calc_path_edge(
 	BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */);
 
 	BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
-		if (filter_fn(e, user_data)) {
-			BM_elem_flag_disable(e, BM_ELEM_TAG);
-		}
-		else {
-			BM_elem_flag_enable(e, BM_ELEM_TAG);
-		}
-
+		BM_elem_flag_set(e, BM_ELEM_TAG, !filter_fn(e, user_data));
 		BM_elem_index_set(e, i); /* set_inline */
 	}
 	bm->elem_index_dirty &= ~BM_EDGE;
@@ -543,36 +348,9 @@ LinkNode *BM_mesh_calc_path_edge(
 	}
 
 	if (e == e_dst) {
-		int path_len = 0;
 		do {
 			BLI_linklist_prepend(&path, e);
-			path_len++;
 		} while ((e = edges_prev[BM_elem_index_get(e)]));
-
-#ifdef USE_PATH_FILL
-		if (params->use_fill) {
-			BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
-				BM_elem_flag_set(e, BM_ELEM_TAG, !filter_fn(e, user_data));
-			}
-
-			int *steps_src = MEM_mallocN(sizeof(*steps_src) * totedge, __func__);
-			int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totedge, __func__);
-
-			/* reuse memory */
-			BMEdge **stack_array = edges_prev;
-			edgetag_calc_fill_steps(bm, e_src, steps_src, path_len, stack_array, params);
-			edgetag_calc_fill_steps(bm, e_dst, steps_dst, path_len, stack_array, params);
-
-			BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
-				if (steps_src[i] + steps_dst[i] < path_len) {
-					BLI_linklist_prepend(&path, e);
-				}
-			}
-
-			MEM_freeN(steps_src);
-			MEM_freeN(steps_dst);
-		}
-#endif
 	}
 
 	MEM_freeN(edges_prev);
@@ -583,84 +361,9 @@ LinkN

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list