BMesh: improve path-select fill region w/ ngons
authorCampbell Barton <ideasman42@gmail.com>
Fri, 1 Apr 2016 12:27:31 +0000 (23:27 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Fri, 1 Apr 2016 12:36:06 +0000 (23:36 +1100)
Rewrote to work with ngons and and more complex topology, now uses separate function.
Fixes T48009.

source/blender/bmesh/CMakeLists.txt
source/blender/bmesh/bmesh_tools.h
source/blender/bmesh/tools/bmesh_path.c
source/blender/bmesh/tools/bmesh_path.h
source/blender/bmesh/tools/bmesh_path_region.c [new file with mode: 0644]
source/blender/bmesh/tools/bmesh_path_region.h [new file with mode: 0644]
source/blender/editors/mesh/editmesh_path.c

index 1afa98fd6f8bfb4059b1e9d3f43df4639eb7674d..30fefe37f0e1ee291f25e43ead14563912f16ca7 100644 (file)
@@ -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
index f7f767f91bf54bf7cb012b2ee19edc6cadbd1a01..23212dd085e0c94cc72a7f4da34035f3e5e7563d 100644 (file)
@@ -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"
 
index 79a002f9f4110f702d82997d53ffbdd401f2f117..30b083cacda9143a412cf6b74ca3498a3da28525 100644 (file)
  * 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 *****
  */
 
 
 #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 @@ LinkNode *BM_mesh_calc_path_edge(
 }
 
 
-
 /* -------------------------------------------------------------------- */
 /* BM_mesh_calc_path_face */
 
-#ifdef USE_PATH_FILL
-static void facetag_calc_fill_steps(
-        BMesh *bm, BMFace *f_start, int *steps, int steps_max, BMFace **stack_array,
-        const struct BMCalcPathParams *params)
-{
-       copy_vn_i(steps, bm->totface, steps_max);
-
-       BMFace **stack = stack_array;
-       STACK_DECLARE(stack);
-       STACK_INIT(stack, bm->totface);
-
-       STACK_PUSH(stack, f_start);
-       steps[BM_elem_index_get(f_start)] = 0;
-
-       while (STACK_SIZE(stack) != 0) {
-               BMFace *f_a = STACK_POP(stack);
-               const int f_a_index = BM_elem_index_get(f_a);
-               int step_a = steps[f_a_index];
-
-               if (step_a < steps_max) {
-
-                       {
-                               BMIter liter;
-                               BMLoop *l_a;
-
-                               BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
-                                       BMLoop *l_first, *l_iter;
-
-                                       l_iter = l_first = l_a;
-                                       do {
-                                               BMFace *f_b = l_iter->f;
-                                               if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
-                                                       /* we know 'f_b' is not visited, check it out! */
-                                                       const int f_b_index = BM_elem_index_get(f_b);
-                                                       const int step_b = step_a + 1;
-                                                       if (steps[f_b_index] > step_b) {
-                                                               steps[f_b_index] = step_b;
-                                                               STACK_PUSH(stack, f_b);
-                                                       }
-                                               }
-                                       } while ((l_iter = l_iter->radial_next) != l_first);
-                               }
-                       }
-
-
-                       if (params->use_step_face) {
-                               BMIter liter;
-                               BMLoop *l_a;
-
-                               BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
-                                       BMIter litersub;
-                                       BMLoop *l_b;
-                                       BM_ITER_ELEM (l_b, &litersub, l_a->v, BM_LOOPS_OF_VERT) {
-                                               if ((l_a != l_b) && !BM_loop_share_edge_check(l_a, l_b)) {
-                                                       BMFace *f_b = l_b->f;
-                                                       if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
-                                                               /* we know 'f_b' is not visited, check it out! */
-                                                               const int f_b_index = BM_elem_index_get(f_b);
-                                                               const int step_b = step_a + 1;
-                                                               if (steps[f_b_index] > step_b) {
-                                                                       steps[f_b_index] = step_b;
-                                                                       STACK_PUSH(stack, f_b);
-                                                               }
-                                                       }
-                                               }
-                                       }
-                               }
-                       }
-
-               }
-       }
-}
-#endif /* USE_PATH_FILL */
-
 static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, BMEdge *e)
 {
        float f_a_cent[3];
@@ -768,7 +471,7 @@ static void facetag_add_adjacent(
 
 LinkNode *BM_mesh_calc_path_face(
         BMesh *bm, BMFace *f_src, BMFace *f_dst, const struct BMCalcPathParams *params,
-        bool (*test_fn)(BMFace *, void *user_data), void *user_data)
+        bool (*filter_fn)(BMFace *, void *user_data), void *user_data)
 {
        LinkNode *path = NULL;
        /* BM_ELEM_TAG flag is used to store visited edges */
@@ -783,13 +486,7 @@ LinkNode *BM_mesh_calc_path_face(
        // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG
 
        BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
-               if (test_fn(f, user_data)) {
-                       BM_elem_flag_disable(f, BM_ELEM_TAG);
-               }
-               else {
-                       BM_elem_flag_enable(f, BM_ELEM_TAG);
-               }
-
+               BM_elem_flag_set(f, BM_ELEM_TAG, !filter_fn(f, user_data));
                BM_elem_index_set(f, i); /* set_inline */
        }
        bm->elem_index_dirty &= ~BM_FACE;
@@ -830,36 +527,9 @@ LinkNode *BM_mesh_calc_path_face(
        }
 
        if (f == f_dst) {
-               int path_len = 0;
                do {
                        BLI_linklist_prepend(&path, f);
-                       path_len++;
                } while ((f = faces_prev[BM_elem_index_get(f)]));
-
-#ifdef USE_PATH_FILL
-               if (params->use_fill) {
-                       BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
-                               BM_elem_flag_set(f, BM_ELEM_TAG, !test_fn(f, user_data));
-                       }
-
-                       int *steps_src = MEM_mallocN(sizeof(*steps_src) * totface, __func__);
-                       int *steps_dst = MEM_mallocN(sizeof(*steps_dst) * totface, __func__);
-
-                       /* reuse memory */
-                       BMFace **stack_array = faces_prev;
-                       facetag_calc_fill_steps(bm, f_src, steps_src, path_len, stack_array, params);
-                       facetag_calc_fill_steps(bm, f_dst, steps_dst, path_len, stack_array, params);
-
-                       BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
-                               if (steps_src[i] + steps_dst[i] < path_len) {
-                                       BLI_linklist_prepend(&path, f);
-                               }
-                       }
-
-                       MEM_freeN(steps_src);
-                       MEM_freeN(steps_dst);
-               }
-#endif
        }
 
        MEM_freeN(faces_prev);
index 9df1568f7508d46df6bacdc6cef4af7ff16e1b3d..b6de5e0e4e0cd4a2b057fbc9fae20fcd576b2a9c 100644 (file)
@@ -30,8 +30,6 @@
 struct BMCalcPathParams {
        unsigned int use_topology_distance : 1;
        unsigned int use_step_face : 1;
-       /* return all paths (no longer ordered) */
-       unsigned int use_fill : 1;
 };
 
 struct LinkNode *BM_mesh_calc_path_vert(
@@ -46,7 +44,7 @@ ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5);
 
 struct LinkNode *BM_mesh_calc_path_face(
         BMesh *bm, BMFace *f_src, BMFace *f_dst, const struct BMCalcPathParams *params,
-        bool (*test_fn)(BMFace *, void *), void *user_data)
+        bool (*filter_fn)(BMFace *, void *), void *user_data)
 ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5);
 
 #endif /* __BMESH_PATH_H__ */
diff --git a/source/blender/bmesh/tools/bmesh_path_region.c b/source/blender/bmesh/tools/bmesh_path_region.c
new file mode 100644 (file)
index 0000000..e68dc86
--- /dev/null
@@ -0,0 +1,462 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/tools/bmesh_path_region.c
+ *  \ingroup bmesh
+ *
+ * Find the region defined by the path(s) between 2 elements.
+ * (path isn't ordered).
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_linklist.h"
+#include "BLI_stackdefines.h"
+#include "BLI_alloca.h"
+
+#include "bmesh.h"
+#include "bmesh_path_region.h"  /* own include */
+
+
+/* Special handling of vertices with 2 edges
+ * (act as if the edge-chain is a single edge). */
+#define USE_EDGE_CHAIN
+
+
+#ifdef USE_EDGE_CHAIN
+/**
+ * Takes a vertex with 2 edge users and fills in the vertices at each end-point,
+ * or nothing if if the edges loop back to its self.
+ */
+static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2])
+{
+       BMEdge *e = v_pivot->e;
+       int j = 0;
+       do {
+               BMEdge *e_chain = e;
+               BMVert *v_other = BM_edge_other_vert(e_chain, v_pivot);
+               while (BM_vert_is_edge_pair(v_other)) {
+                       BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_other);
+                       BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_other) == e_chain);
+                       v_other = BM_edge_other_vert(e_chain_next, v_other);
+                       if (v_other == v_pivot) {
+                               return false;
+                       }
+                       e_chain = e_chain_next;
+               }
+               v_end_pair[j++] = v_other;
+       } while ((e = BM_DISK_EDGE_NEXT(e, v_pivot)) != v_pivot->e);
+
+       BLI_assert(j == 2);
+       return true;
+}
+#endif  /* USE_EDGE_CHAIN */
+
+
+/** \name Vertex in Region Checks
+ * \{ */
+
+static bool bm_vert_region_test(BMVert *v, int * const depths[2], const int pass)
+{
+       const int index = BM_elem_index_get(v);
+       return (((depths[0][index] != -1) && (depths[1][index] != -1)) && \
+               ((depths[0][index]        +   depths[1][index]) < pass));
+}
+
+#ifdef USE_EDGE_CHAIN
+static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const int pass)
+{
+       BMVert *v_end_pair[2];
+       if (bm_vert_region_test(v, depths, pass)) {
+               return true;
+       }
+       else if (BM_vert_is_edge_pair(v) &&
+                bm_vert_pair_ends(v, v_end_pair) &&
+                bm_vert_region_test(v_end_pair[0], depths, pass) &&
+                bm_vert_region_test(v_end_pair[1], depths, pass))
+       {
+               return true;
+       }
+
+       return false;
+}
+#else
+static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const int pass)
+{
+       return bm_vert_region_test(v, depths, pass);
+}
+#endif
+
+/** \} */
+
+
+/**
+ * Main logic for calculating region between 2 elements.
+ *
+ * This method works walking (breadth first) over all vertices,
+ * keeping track of topological distance from the source.
+ *
+ * This is done in both directions, after that each vertices 'depth' is added to check
+ * if its less than the number of passes needed to complete the search.
+ * When it is, we know the path is one of possible paths that have the minimum topological distance.
+ *
+ * \note Only verts without BM_ELEM_TAG will be walked over.
+ */
+static LinkNode *mesh_calc_path_region_elem(
+        BMesh *bm,
+        BMElem *ele_src, BMElem *ele_dst,
+        const char path_htype)
+{
+       int      ele_verts_len[2];
+       BMVert **ele_verts[2];
+
+       /* Get vertices from any `ele_src/ele_dst` elements. */
+       for (int side = 0; side < 2; side++) {
+               BMElem *ele = side ? ele_dst : ele_src;
+               int j = 0;
+
+               if (ele->head.htype == BM_FACE) {
+                       BMFace *f = (BMFace *)ele;
+                       ele_verts[side] = BLI_array_alloca(ele_verts[side], f->len);
+
+                       BMLoop *l_first, *l_iter;
+                       l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+                       do {
+                               ele_verts[side][j++] = l_iter->v;
+                       } while ((l_iter = l_iter->next) != l_first);
+               }
+               else if (ele->head.htype == BM_EDGE) {
+                       BMEdge *e = (BMEdge *)ele;
+                       ele_verts[side] = BLI_array_alloca(ele_verts[side], 2);
+
+                       ele_verts[side][j++] = e->v1;
+                       ele_verts[side][j++] = e->v2;
+               }
+               else if (ele->head.htype == BM_VERT) {
+                       BMVert *v = (BMVert *)ele;
+                       ele_verts[side] = BLI_array_alloca(ele_verts[side], 1);
+
+                       ele_verts[side][j++] = v;
+               }
+               else {
+                       BLI_assert(0);
+               }
+               ele_verts_len[side] = j;
+       }
+
+       int *depths[2] = {NULL};
+       int pass = 0;
+
+       BMVert **stack       = MEM_mallocN(sizeof(*stack)       * bm->totvert, __func__);
+       BMVert **stack_other = MEM_mallocN(sizeof(*stack_other) * bm->totvert, __func__);
+
+       STACK_DECLARE(stack);
+       STACK_INIT(stack, bm->totvert);
+
+       STACK_DECLARE(stack_other);
+       STACK_INIT(stack_other, bm->totvert);
+
+       BM_mesh_elem_index_ensure(bm, BM_VERT);
+
+       /* After exhausting all possible elements, we should have found all elements on the 'side_other'.
+        * otherwise, exit early. */
+       bool found_all = false;
+
+       for (int side = 0; side < 2; side++) {
+               const int side_other = !side;
+
+               /* initialize depths to -1 (un-touched), fill in with the depth as we walk over the edges. */
+               depths[side] = MEM_mallocN(sizeof(*depths[side]) * bm->totvert, __func__);
+               copy_vn_i(depths[side], bm->totvert, -1);
+
+               /* needed for second side */
+               STACK_CLEAR(stack);
+               STACK_CLEAR(stack_other);
+
+               for (int i = 0; i < ele_verts_len[side]; i++) {
+                       BMVert *v = ele_verts[side][i];
+                       depths[side][BM_elem_index_get(v)] = 0;
+                       if (v->e && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
+                               STACK_PUSH(stack, v);
+                       }
+               }
+
+#ifdef USE_EDGE_CHAIN
+               /* Expand initial state to end-point vertices when they only have 2x edges,
+                * this prevents odd behavior when source or destination are in the middle of a long chain of edges. */
+               if (ELEM(path_htype, BM_VERT, BM_EDGE)) {
+                       for (int i = 0; i < ele_verts_len[side]; i++) {
+                               BMVert *v = ele_verts[side][i];
+                               BMVert *v_end_pair[2];
+                               if (BM_vert_is_edge_pair(v) && bm_vert_pair_ends(v, v_end_pair)) {
+                                       for (int j = 0; j < 2; j++) {
+                                               const int v_end_index = BM_elem_index_get(v_end_pair[j]);
+                                               if (depths[side][v_end_index] == -1) {
+                                                       depths[side][v_end_index] = 0;
+                                                       if (!BM_elem_flag_test(v_end_pair[j], BM_ELEM_TAG)) {
+                                                               STACK_PUSH(stack, v_end_pair[j]);
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               }
+#endif  /* USE_EDGE_CHAIN */
+
+               /* Keep walking over connected geometry until we find all the vertices in `ele_verts[side_other]`,
+                * or exit the loop when theres no connection. */
+               found_all = false;
+               for (pass = 1; (STACK_SIZE(stack) != 0); pass++) {
+                       while (STACK_SIZE(stack) != 0) {
+                               BMVert *v_a = STACK_POP(stack);
+                               const int v_a_index = BM_elem_index_get(v_a);
+                               BMEdge *e = v_a->e;
+
+                               do {
+                                       BMVert *v_b = BM_edge_other_vert(e, v_a);
+                                       int v_b_index = BM_elem_index_get(v_b);
+                                       if (depths[side][v_b_index] == -1) {
+
+#ifdef USE_EDGE_CHAIN
+                                               /* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */
+                                               {
+                                                       BMEdge *e_chain = e;
+                                                       while (BM_vert_is_edge_pair(v_b) &&
+                                                              ((depths[side][v_b_index] == -1)))
+                                                       {
+                                                               depths[side][v_b_index] = pass;
+
+                                                               BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_b);
+                                                               BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_b) == e_chain);
+                                                               v_b = BM_edge_other_vert(e_chain_next, v_b);
+                                                               v_b_index = BM_elem_index_get(v_b);
+                                                               e_chain = e_chain_next;
+                                                       }
+                                               }
+#endif  /* USE_EDGE_CHAIN */
+
+                                               /* Add the other vertex to the stack, to be traversed in the next pass. */
+                                               if (depths[side][v_b_index] == -1) {
+#ifdef USE_EDGE_CHAIN
+                                                       BLI_assert(!BM_vert_is_edge_pair(v_b));
+#endif
+                                                       BLI_assert(pass == depths[side][v_a_index] + 1);
+                                                       depths[side][v_b_index] = pass;
+                                                       if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
+                                                               STACK_PUSH(stack_other, v_b);
+                                                       }
+                                               }
+                                       }
+                               } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != v_a->e);
+                       }
+
+                       /* Stop searching once theres none left.
+                        * Note that this looks in-efficient, however until the target elements reached,
+                        * it will exit immediately.
+                        * After that, it takes as many passes as the element has edges to finish off. */
+                       found_all = true;
+                       for (int i = 0; i < ele_verts_len[side_other]; i++) {
+                               if (depths[side][BM_elem_index_get(ele_verts[side_other][i])] == -1) {
+                                       found_all = false;
+                                       break;
+                               }
+                       }
+                       if (found_all == true) {
+                               pass++;
+                               break;
+                       }
+
+                       STACK_SWAP(stack, stack_other);
+               }
+
+               /* if we have nothing left, and didn't find all elements on the other side,
+                * exit early and don't continue */
+               if (found_all == false) {
+                       break;
+               }
+       }
+
+       MEM_freeN(stack);
+       MEM_freeN(stack_other);
+
+
+       /* Now we have depths recorded from both sides,
+        * select elements that use tagged verts. */
+       LinkNode *path = NULL;
+
+       if (found_all == false) {
+               /* fail! (do nothing) */
+       }
+       else if (path_htype == BM_FACE) {
+               BMIter fiter;
+               BMFace *f;
+
+               BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
+                       if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
+                               /* check all verts in face are tagged */
+                               BMLoop *l_first, *l_iter;
+                               l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+                               bool ok = true;
+                               do {
+                                       if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) {
+                                               ok = false;
+                                               break;
+                                       }
+                               } while ((l_iter = l_iter->next) != l_first);
+
+                               if (ok) {
+                                       BLI_linklist_prepend(&path, f);
+                               }
+                       }
+               }
+       }
+       else if (path_htype == BM_EDGE) {
+               BMIter eiter;
+               BMEdge *e;
+
+               BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
+                       if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
+                               /* check all verts in edge are tagged */
+                               bool ok = true;
+                               for (int j = 0; j < 2; j++) {
+                                       if (!bm_vert_region_test_chain(*((&e->v1) + j), depths, pass)) {
+                                               ok = false;
+                                               break;
+                                       }
+                               }
+
+                               if (ok) {
+                                       BLI_linklist_prepend(&path, e);
+                               }
+                       }
+               }
+       }
+       else if (path_htype == BM_VERT) {
+               BMIter viter;
+               BMVert *v;
+
+               BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
+                       if (bm_vert_region_test_chain(v, depths, pass)) {
+                               BLI_linklist_prepend(&path, v);
+                       }
+               }
+       }
+
+
+       for (int side = 0; side < 2; side++) {
+               if (depths[side]) {
+                       MEM_freeN(depths[side]);
+               }
+       }
+
+       return path;
+}
+
+#undef USE_EDGE_CHAIN
+
+
+/** \name Main Functions (exposed externally).
+ * \{ */
+
+LinkNode *BM_mesh_calc_path_region_vert(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*filter_fn)(BMVert *, void *user_data), void *user_data)
+{
+       LinkNode *path = NULL;
+       /* BM_ELEM_TAG flag is used to store visited verts */
+       BMVert *v;
+       BMIter viter;
+       int i;
+
+       BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
+               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;
+
+       path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_VERT);
+
+       return path;
+}
+
+LinkNode *BM_mesh_calc_path_region_edge(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*filter_fn)(BMEdge *, void *user_data), void *user_data)
+{
+       LinkNode *path = NULL;
+       /* BM_ELEM_TAG flag is used to store visited verts */
+       BMEdge *e;
+       BMIter eiter;
+       int i;
+
+       /* flush flag to verts */
+       BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false);
+
+       BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
+               bool test;
+               BM_elem_flag_set(e, BM_ELEM_TAG, test = !filter_fn(e, user_data));
+
+               /* flush tag to verts */
+               if (test == false) {
+                       for (int j = 0; j < 2; j++) {
+                               BM_elem_flag_disable(*((&e->v1) + j), BM_ELEM_TAG);
+                       }
+               }
+       }
+
+       path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_EDGE);
+
+       return path;
+}
+
+LinkNode *BM_mesh_calc_path_region_face(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*filter_fn)(BMFace *, void *user_data), void *user_data)
+{
+       LinkNode *path = NULL;
+       /* BM_ELEM_TAG flag is used to store visited verts */
+       BMFace *f;
+       BMIter fiter;
+       int i;
+
+       /* flush flag to verts */
+       BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false);
+
+       BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
+               bool test;
+               BM_elem_flag_set(f, BM_ELEM_TAG, test = !filter_fn(f, user_data));
+
+               /* flush tag to verts */
+               if (test == false) {
+                       BMLoop *l_first, *l_iter;
+                       l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+                       do {
+                               BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG);
+                       } while ((l_iter = l_iter->next) != l_first);
+               }
+       }
+
+       path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_FACE);
+
+       return path;
+}
+
+/** \} */
diff --git a/source/blender/bmesh/tools/bmesh_path_region.h b/source/blender/bmesh/tools/bmesh_path_region.h
new file mode 100644 (file)
index 0000000..06e56a5
--- /dev/null
@@ -0,0 +1,43 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_PATH_REGION_H__
+#define __BMESH_PATH_REGION_H__
+
+/** \file blender/bmesh/tools/bmesh_path_region.h
+ *  \ingroup bmesh
+ */
+
+struct LinkNode *BM_mesh_calc_path_region_vert(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*test_fn)(BMVert *, void *user_data), void *user_data)
+ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3);
+
+struct LinkNode *BM_mesh_calc_path_region_edge(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*test_fn)(BMEdge *, void *user_data), void *user_data)
+ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3);
+
+struct LinkNode *BM_mesh_calc_path_region_face(
+        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
+        bool (*test_fn)(BMFace *, void *user_data), void *user_data)
+ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3);
+
+#endif /* __BMESH_PATH_REGION_H__ */
index 1a8eae784aa5d963d3dd19996883be45e2e0cd7a..55ed0e521ea112a7177673889bc327bc1c050bc3 100644 (file)
@@ -128,17 +128,26 @@ static void mouse_mesh_shortest_path_vert(
 
        struct UserData user_data = {bm, obedit->data, op_params};
        LinkNode *path = NULL;
+       bool is_path_ordered = false;
 
        if (v_act && (v_act != v_dst)) {
-               if ((path = BM_mesh_calc_path_vert(
-                        bm, v_act, v_dst,
-                        &(const struct BMCalcPathParams) {
-                            .use_topology_distance = op_params->use_topology_distance,
-                            .use_step_face = op_params->use_face_step,
-                            .use_fill = op_params->use_fill,
-                        },
-                        verttag_filter_cb, &user_data)))
-               {
+               if (op_params->use_fill) {
+                       path = BM_mesh_calc_path_region_vert(
+                               bm, (BMElem *)v_act, (BMElem *)v_dst,
+                               verttag_filter_cb, &user_data);
+               }
+               else {
+                       is_path_ordered = true;
+                       path = BM_mesh_calc_path_vert(
+                               bm, v_act, v_dst,
+                               &(const struct BMCalcPathParams) {
+                                   .use_topology_distance = op_params->use_topology_distance,
+                                   .use_step_face = op_params->use_face_step,
+                               },
+                               verttag_filter_cb, &user_data);
+               }
+
+               if (path) {
                        if (op_params->track_active) {
                                BM_select_history_remove(bm, v_act);
                        }
@@ -163,9 +172,13 @@ static void mouse_mesh_shortest_path_vert(
                int depth = 1;
                node = path;
                do {
-                       if (WM_operator_properties_checker_interval_test(&op_params->interval_params, depth)) {
+                       if ((is_path_ordered == false) ||
+                           WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
+                       {
                                verttag_set_cb((BMVert *)node->link, !all_set, &user_data);
-                               v_dst_last = node->link;
+                               if (is_path_ordered) {
+                                       v_dst_last = node->link;
+                               }
                        }
                } while ((void)depth++, (node = node->next));
 
@@ -302,19 +315,28 @@ static void mouse_mesh_shortest_path_edge(
        struct UserData user_data = {bm, obedit->data, op_params};
        LinkNode *path = NULL;
        Mesh *me = obedit->data;
+       bool is_path_ordered = false;
 
        edgetag_ensure_cd_flag(scene, obedit->data);
 
        if (e_act && (e_act != e_dst)) {
-               if ((path = BM_mesh_calc_path_edge(
-                        bm, e_act, e_dst,
-                        &(const struct BMCalcPathParams) {
-                            .use_topology_distance = op_params->use_topology_distance,
-                            .use_step_face = op_params->use_face_step,
-                            .use_fill = op_params->use_fill,
-                        },
-                        edgetag_filter_cb, &user_data)))
-               {
+               if (op_params->use_fill) {
+                       path = BM_mesh_calc_path_region_edge(
+                               bm, (BMElem *)e_act, (BMElem *)e_dst,
+                               edgetag_filter_cb, &user_data);
+               }
+               else {
+                       is_path_ordered = true;
+                       path = BM_mesh_calc_path_edge(
+                               bm, e_act, e_dst,
+                               &(const struct BMCalcPathParams) {
+                                   .use_topology_distance = op_params->use_topology_distance,
+                                   .use_step_face = op_params->use_face_step,
+                               },
+                               edgetag_filter_cb, &user_data);
+               }
+
+               if (path) {
                        if (op_params->track_active) {
                                BM_select_history_remove(bm, e_act);
                        }
@@ -339,9 +361,13 @@ static void mouse_mesh_shortest_path_edge(
                int depth = 1;
                node = path;
                do {
-                       if (WM_operator_properties_checker_interval_test(&op_params->interval_params, depth)) {
+                       if ((is_path_ordered == false) ||
+                           WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
+                       {
                                edgetag_set_cb((BMEdge *)node->link, !all_set, &user_data);
-                               e_dst_last = node->link;
+                               if (is_path_ordered) {
+                                       e_dst_last = node->link;
+                               }
                        }
                } while ((void)depth++, (node = node->next));
 
@@ -433,18 +459,28 @@ static void mouse_mesh_shortest_path_face(
 
        struct UserData user_data = {bm, obedit->data, op_params};
        LinkNode *path = NULL;
+       bool is_path_ordered = false;
 
        if (f_act) {
+               if (op_params->use_fill) {
+                       path = BM_mesh_calc_path_region_face(
+                               bm, (BMElem *)f_act, (BMElem *)f_dst,
+                               facetag_filter_cb, &user_data);
+               }
+               else {
+                       is_path_ordered = true;
+                       path = BM_mesh_calc_path_face(
+                               bm, f_act, f_dst,
+                               &(const struct BMCalcPathParams) {
+                                   .use_topology_distance = op_params->use_topology_distance,
+                                   .use_step_face = op_params->use_face_step,
+                               },
+                               facetag_filter_cb, &user_data);
+               }
+
+
                if (f_act != f_dst) {
-                       if ((path = BM_mesh_calc_path_face(
-                                bm, f_act, f_dst,
-                                &(const struct BMCalcPathParams) {
-                                    .use_topology_distance = op_params->use_topology_distance,
-                                    .use_step_face = op_params->use_face_step,
-                                    .use_fill = op_params->use_fill,
-                                },
-                                facetag_filter_cb, &user_data)))
-                       {
+                       if (path) {
                                if (op_params->track_active) {
                                        BM_select_history_remove(bm, f_act);
                                }
@@ -470,9 +506,13 @@ static void mouse_mesh_shortest_path_face(
                int depth = 1;
                node = path;
                do {
-                       if (WM_operator_properties_checker_interval_test(&op_params->interval_params, depth)) {
+                       if ((is_path_ordered == false) ||
+                           WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
+                       {
                                facetag_set_cb((BMFace *)node->link, !all_set, &user_data);
-                               f_dst_last = node->link;
+                               if (is_path_ordered) {
+                                       f_dst_last = node->link;
+                               }
                        }
                } while ((void)depth++, (node = node->next));