BMesh: add select next/prev operator

This uses selection history to select the next vert/edge/face based on surrounding topology.
Select previous just removes the last selected element.

Uses key-bindings: Ctrl-Shift +/-

2 files changed, 344 insertions, 0 deletions

diff --git a/release/scripts/startup/bl_operators/bmesh/find_adjacent.py b/release/scripts/startup/bl_operators/bmesh/find_adjacent.py
new file mode 100644
index 00000000000..bfe44ee187c
--- /dev/null
+++ b/release/scripts/startup/bl_operators/bmesh/find_adjacent.py
@@ -0,0 +1,294 @@
+# ##### 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 #####
+
+# <pep8 compliant>
+
+# Utilities to detect the next matching element (vert/edge/face)
+# based on an existing pair of elements.
+
+import bmesh
+
+
+def other_edges_over_face(e):
+    # Can yield same edge multiple times, its fine.
+    for l in e.link_loops:
+        yield l.link_loop_next.edge
+        yield l.link_loop_prev.edge
+
+
+def other_edges_over_edge(e):
+    # Can yield same edge multiple times, its fine.
+    for v in e.verts:
+        for e_other in v.link_edges:
+            if e_other is not e:
+                if not e.is_wire:
+                    yield e_other
+
+
+def verts_from_elem(ele):
+    ele_type = type(ele)
+    if ele_type is bmesh.types.BMFace:
+        return [l.vert for l in ele.loops]
+    elif ele_type is bmesh.types.BMEdge:
+        return [v for v in ele.verts]
+    elif ele_type is bmesh.types.BMVert:
+        return [ele]
+    else:
+        raise TypeError("wrong type")
+
+
+def edges_from_elem(ele):
+    ele_type = type(ele)
+    if ele_type is bmesh.types.BMFace:
+        return [l.edge for l in ele.loops]
+    elif ele_type is bmesh.types.BMEdge:
+        return [ele]
+    elif ele_type is bmesh.types.BMVert:
+        return [e for e in ele.link_edges]
+    else:
+        raise TypeError("wrong type")
+
+
+def elems_depth_search(ele_init, depths, other_edges_over_cb, results_init=None):
+    """
+    List of depths -> List of elems that match those depths.
+    """
+
+    depth_max = max(depths)
+    depth_min = min(depths)
+    depths_sorted = tuple(sorted(depths))
+
+    stack_old = edges_from_elem(ele_init)
+    stack_new = []
+
+    stack_visit = set(stack_old)
+
+    vert_depths = {}
+    vert_depths_setdefault = vert_depths.setdefault
+
+    depth = 0
+    while stack_old and depth <= depth_max:
+        for ele in stack_old:
+            for v in verts_from_elem(ele):
+                vert_depths_setdefault(v, depth)
+            for ele_other in other_edges_over_cb(ele):
+                stack_visit_len = len(stack_visit)
+                stack_visit.add(ele_other)
+                if stack_visit_len != len(stack_visit):
+                    stack_new.append(ele_other)
+        stack_new, stack_old = stack_old, stack_new
+        stack_new[:] = []
+        depth += 1
+
+    # now we have many verts in vert_depths which are attached to elements
+    # which are candidates for matching with depths
+    if type(ele_init) is bmesh.types.BMFace:
+        test_ele = {
+            l.face for v, depth in vert_depths.items()
+            if depth >= depth_min for l in v.link_loops}
+    elif type(ele_init) is bmesh.types.BMEdge:
+        test_ele = {
+            e for v, depth in vert_depths.items()
+            if depth >= depth_min for e in v.link_edges if not e.is_wire}
+    else:
+        test_ele = {
+            v for v, depth in vert_depths.items()
+            if depth >= depth_min for e in v.link_edges if not e.is_wire}
+
+    result_ele = set()
+
+    vert_depths_get = vert_depths.get
+    # re-used each time, will always be the same length
+    depths_test = [None] * len(depths)
+
+    for ele in test_ele:
+        verts_test = verts_from_elem(ele)
+        if len(verts_test) != len(depths):
+            continue
+        if results_init is not None and ele not in results_init:
+            continue
+        if ele in result_ele:
+            continue
+
+        ok = True
+        for i, v in enumerate(verts_test):
+            depth = vert_depths_get(v)
+            if depth is not None:
+                depths_test[i] = depth
+            else:
+                ok = False
+                break
+
+        if ok:
+            if depths_sorted == tuple(sorted(depths_test)):
+                # Note, its possible the order of sorted items moves the values out-of-order.
+                # for this we could do a circular list comparison,
+                # however - this is such a rare case that we're ignoring it.
+                result_ele.add(ele)
+
+    return result_ele
+
+
+def elems_depth_measure(ele_dst, ele_src, other_edges_over_cb):
+    """
+    Returns·ele_dst vert depths from ele_src, aligned with ele_dst verts.
+    """
+
+    stack_old = edges_from_elem(ele_src)
+    stack_new = []
+
+    stack_visit = set(stack_old)
+
+    # continue until we've reached all verts in the destination
+    ele_dst_verts = verts_from_elem(ele_dst)
+    all_dst = set(ele_dst_verts)
+    all_dst_discard = all_dst.discard
+
+    vert_depths = {}
+
+    depth = 0
+    while stack_old and all_dst:
+        for ele in stack_old:
+            for v in verts_from_elem(ele):
+                len_prev = len(all_dst)
+                all_dst_discard(v)
+                if len_prev != len(all_dst):
+                    vert_depths[v] = depth
+
+            for ele_other in other_edges_over_cb(ele):
+                stack_visit_len = len(stack_visit)
+                stack_visit.add(ele_other)
+                if stack_visit_len != len(stack_visit):
+                    stack_new.append(ele_other)
+        stack_new, stack_old = stack_old, stack_new
+        stack_new[:] = []
+        depth += 1
+
+    return [vert_depths[v] for v in ele_dst_verts]
+
+
+def find_next(ele_dst, ele_src):
+    depth_src_a = elems_depth_measure(ele_dst, ele_src, other_edges_over_edge)
+    depth_src_b = elems_depth_measure(ele_dst, ele_src, other_edges_over_face)
+    depth_src = tuple(zip(depth_src_a, depth_src_b))
+
+    if depth_src is None:
+        return []
+
+    candidates = elems_depth_search(ele_dst, depth_src_a, other_edges_over_edge)
+    candidates = elems_depth_search(ele_dst, depth_src_b, other_edges_over_face, candidates)
+    candidates.discard(ele_src)
+    if not candidates:
+        return []
+
+    # Now we have to pick which is the best next-element,
+    # do this by calculating the element with the largest
+    # variation in depth from the relationship to the source.
+    # ... So we have the highest chance of stepping onto the opposite element.
+    diff_best = 0
+    ele_best = None
+    ele_best_tot = 0
+    ele_best_ls = []
+    for ele_test in candidates:
+        depth_test_a = elems_depth_measure(ele_dst, ele_test, other_edges_over_edge)
+        depth_test_b = elems_depth_measure(ele_dst, ele_test, other_edges_over_face)
+        depth_test = tuple(zip(depth_test_a, depth_test_b))
+        # square so a few high values win over many small ones
+        diff_test = sum((abs(a[0] - b[0]) ** 2) +
+                        (abs(a[1] - b[1]) ** 2) for a, b in zip(depth_src, depth_test))
+        if diff_test > diff_best:
+            diff_best = diff_test
+            ele_best = ele_test
+            ele_best_tot = 1
+            ele_best_ls[:] = [ele_best]
+        elif diff_test == diff_best:
+            if ele_best is None:
+                ele_best = ele_test
+            ele_best_tot += 1
+            ele_best_ls.append(ele_test)
+
+    if len(ele_best_ls) > 1:
+        ele_best_ls_init = ele_best_ls
+        ele_best_ls = []
+        depth_accum_max = -1
+        for ele_test in ele_best_ls_init:
+            depth_accum_test = (
+                sum(elems_depth_measure(ele_src, ele_test, other_edges_over_edge)) +
+                sum(elems_depth_measure(ele_src, ele_test, other_edges_over_face)))
+
+            if depth_accum_test > depth_accum_max:
+                depth_accum_max = depth_accum_test
+                ele_best = ele_test
+                ele_best_ls[:] = [ele_best]
+            elif depth_accum_test == depth_accum_max:
+                # we have multiple bests, don't return any
+                ele_best_ls.append(ele_test)
+
+    return ele_best_ls
+
+
+# expose for operators
+def select_next(bm, report):
+    import bmesh
+    ele_pair = [None, None]
+    for i, ele in enumerate(reversed(bm.select_history)):
+        ele_pair[i] = ele
+        if i == 1:
+            break
+
+    if ele_pair[-1] is None:
+        report({'INFO'}, "Selection pair not found")
+        return False
+
+    ele_pair_next = find_next(*ele_pair)
+    if len(ele_pair_next) != 1:
+        report({'INFO'}, "No single next item found")
+        return False
+
+    ele = ele_pair_next[0]
+    if ele.hide:
+        report({'INFO'}, "Next element is hidden")
+        return False
+
+    ele.select_set(False)
+    ele.select_set(True)
+    bm.select_history.add(ele)
+    if type(ele) is bmesh.types.BMFace:
+        bm.faces.active = ele
+    return True
+
+
+def select_prev(bm, report):
+    import bmesh
+    for ele in reversed(bm.select_history):
+        break
+    else:
+        report({'INFO'}, "Last selected not found")
+        return False
+
+    ele.select_set(False)
+
+    for ele in reversed(bm.select_history):
+        break
+    else:
+        return True
+
+    if type(ele) is bmesh.types.BMFace:
+        bm.faces.active = ele
+    return True
+
diff --git a/release/scripts/startup/bl_operators/mesh.py b/release/scripts/startup/bl_operators/mesh.py
index ea504d48448..be74f8dbc0e 100644
--- a/release/scripts/startup/bl_operators/mesh.py
+++ b/release/scripts/startup/bl_operators/mesh.py
@@ -148,3 +148,53 @@ class MeshMirrorUV(Operator):
                         double_warn)
 
         return {'FINISHED'}
+
+
+class MeshSelectNext(Operator):
+    """Select the next element (using selection order)"""
+    bl_idname = "mesh.select_next_item"
+    bl_label = "Select Next Element"
+    bl_options = {'REGISTER', 'UNDO'}
+
+    @classmethod
+    def poll(cls, context):
+        return (context.mode == 'EDIT_MESH')
+
+    def execute(self, context):
+        import bmesh
+        from .bmesh import find_adjacent
+
+        obj = context.active_object
+        me = obj.data
+        bm = bmesh.from_edit_mesh(me)
+
+        if find_adjacent.select_next(bm, self.report):
+            bm.select_flush_mode()
+            bmesh.update_edit_mesh(me, False)
+
+        return {'FINISHED'}
+
+
+class MeshSelectPrev(Operator):
+    """Select the next element (using selection order)"""
+    bl_idname = "mesh.select_prev_item"
+    bl_label = "Select Previous Element"
+    bl_options = {'REGISTER', 'UNDO'}
+
+    @classmethod
+    def poll(cls, context):
+        return (context.mode == 'EDIT_MESH')
+
+    def execute(self, context):
+        import bmesh
+        from .bmesh import find_adjacent
+
+        obj = context.active_object
+        me = obj.data
+        bm = bmesh.from_edit_mesh(me)
+
+        if find_adjacent.select_prev(bm, self.report):
+            bm.select_flush_mode()
+            bmesh.update_edit_mesh(me, False)
+
+        return {'FINISHED'}