1# ##### BEGIN GPL LICENSE BLOCK #####
2#
3#  This program is free software; you can redistribute it and/or
4#  modify it under the terms of the GNU General Public License
5#  as published by the Free Software Foundation; either version 2
6#  of the License, or (at your option) any later version.
7#
8#  This program is distributed in the hope that it will be useful,
9#  but WITHOUT ANY WARRANTY; without even the implied warranty of
10#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11#  GNU General Public License for more details.
12#
13#  You should have received a copy of the GNU General Public License
14#  along with this program; if not, write to the Free Software Foundation,
15#  Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
16#
17# ##### END GPL LICENSE BLOCK #####
18
19# <pep8 compliant>
20
21# Utilities to detect the next matching element (vert/edge/face)
22# based on an existing pair of elements.
23
24import bmesh
25
26__all__ = (
27    "select_prev",
28    "select_next",
29)
30
31
32def other_edges_over_face(e):
33    # Can yield same edge multiple times, its fine.
34    for l in e.link_loops:
35        yield l.link_loop_next.edge
36        yield l.link_loop_prev.edge
37
38
39def other_edges_over_edge(e):
40    # Can yield same edge multiple times, its fine.
41    for v in e.verts:
42        for e_other in v.link_edges:
43            if e_other is not e:
44                if not e.is_wire:
45                    yield e_other
46
47
48def verts_from_elem(ele):
49    ele_type = type(ele)
50    if ele_type is bmesh.types.BMFace:
51        return [l.vert for l in ele.loops]
52    elif ele_type is bmesh.types.BMEdge:
53        return [v for v in ele.verts]
54    elif ele_type is bmesh.types.BMVert:
55        return [ele]
56    else:
57        raise TypeError("wrong type")
58
59
60def edges_from_elem(ele):
61    ele_type = type(ele)
62    if ele_type is bmesh.types.BMFace:
63        return [l.edge for l in ele.loops]
64    elif ele_type is bmesh.types.BMEdge:
65        return [ele]
66    elif ele_type is bmesh.types.BMVert:
67        return [e for e in ele.link_edges]
68    else:
69        raise TypeError("wrong type")
70
71
72def elems_depth_search(ele_init, depths, other_edges_over_cb, results_init=None):
73    """
74    List of depths -> List of elems that match those depths.
75    """
76
77    depth_max = max(depths)
78    depth_min = min(depths)
79    depths_sorted = tuple(sorted(depths))
80
81    stack_old = edges_from_elem(ele_init)
82    stack_new = []
83
84    stack_visit = set(stack_old)
85
86    vert_depths = {}
87    vert_depths_setdefault = vert_depths.setdefault
88
89    depth = 0
90    while stack_old and depth <= depth_max:
91        for ele in stack_old:
92            for v in verts_from_elem(ele):
93                vert_depths_setdefault(v, depth)
94            for ele_other in other_edges_over_cb(ele):
95                stack_visit_len = len(stack_visit)
96                stack_visit.add(ele_other)
97                if stack_visit_len != len(stack_visit):
98                    stack_new.append(ele_other)
99        stack_new, stack_old = stack_old, stack_new
100        stack_new[:] = []
101        depth += 1
102
103    # now we have many verts in vert_depths which are attached to elements
104    # which are candidates for matching with depths
105    if type(ele_init) is bmesh.types.BMFace:
106        test_ele = {
107            l.face for v, depth in vert_depths.items()
108            if depth >= depth_min for l in v.link_loops}
109    elif type(ele_init) is bmesh.types.BMEdge:
110        test_ele = {
111            e for v, depth in vert_depths.items()
112            if depth >= depth_min for e in v.link_edges if not e.is_wire}
113    else:
114        test_ele = {
115            v for v, depth in vert_depths.items()
116            if depth >= depth_min}
117
118    result_ele = set()
119
120    vert_depths_get = vert_depths.get
121    # re-used each time, will always be the same length
122    depths_test = [None] * len(depths)
123
124    for ele in test_ele:
125        verts_test = verts_from_elem(ele)
126        if len(verts_test) != len(depths):
127            continue
128        if results_init is not None and ele not in results_init:
129            continue
130        if ele in result_ele:
131            continue
132
133        ok = True
134        for i, v in enumerate(verts_test):
135            depth = vert_depths_get(v)
136            if depth is not None:
137                depths_test[i] = depth
138            else:
139                ok = False
140                break
141
142        if ok:
143            if depths_sorted == tuple(sorted(depths_test)):
144                # Note, its possible the order of sorted items moves the values out-of-order.
145                # for this we could do a circular list comparison,
146                # however - this is such a rare case that we're ignoring it.
147                result_ele.add(ele)
148
149    return result_ele
150
151
152def elems_depth_measure(ele_dst, ele_src, other_edges_over_cb):
153    """
154    Returns·ele_dst vert depths from ele_src, aligned with ele_dst verts.
155    """
156
157    stack_old = edges_from_elem(ele_src)
158    stack_new = []
159
160    stack_visit = set(stack_old)
161
162    # continue until we've reached all verts in the destination
163    ele_dst_verts = verts_from_elem(ele_dst)
164    all_dst = set(ele_dst_verts)
165    all_dst_discard = all_dst.discard
166
167    vert_depths = {}
168
169    depth = 0
170    while stack_old and all_dst:
171        for ele in stack_old:
172            for v in verts_from_elem(ele):
173                len_prev = len(all_dst)
174                all_dst_discard(v)
175                if len_prev != len(all_dst):
176                    vert_depths[v] = depth
177
178            for ele_other in other_edges_over_cb(ele):
179                stack_visit_len = len(stack_visit)
180                stack_visit.add(ele_other)
181                if stack_visit_len != len(stack_visit):
182                    stack_new.append(ele_other)
183        stack_new, stack_old = stack_old, stack_new
184        stack_new[:] = []
185        depth += 1
186
187    if not all_dst:
188        return [vert_depths[v] for v in ele_dst_verts]
189    else:
190        return None
191
192
193def find_next(ele_dst, ele_src):
194    depth_src_a = elems_depth_measure(ele_dst, ele_src, other_edges_over_edge)
195    depth_src_b = elems_depth_measure(ele_dst, ele_src, other_edges_over_face)
196
197    # path not found
198    if depth_src_a is None or depth_src_b is None:
199        return []
200
201    depth_src = tuple(zip(depth_src_a, depth_src_b))
202
203    candidates = elems_depth_search(ele_dst, depth_src_a, other_edges_over_edge)
204    candidates = elems_depth_search(ele_dst, depth_src_b, other_edges_over_face, candidates)
205    candidates.discard(ele_src)
206    candidates.discard(ele_dst)
207    if not candidates:
208        return []
209
210    # Now we have to pick which is the best next-element,
211    # do this by calculating the element with the largest
212    # variation in depth from the relationship to the source.
213    # ... So we have the highest chance of stepping onto the opposite element.
214    diff_best = 0
215    ele_best = None
216    ele_best_ls = []
217    for ele_test in candidates:
218        depth_test_a = elems_depth_measure(ele_dst, ele_test, other_edges_over_edge)
219        depth_test_b = elems_depth_measure(ele_dst, ele_test, other_edges_over_face)
220        if depth_test_a is None or depth_test_b is None:
221            continue
222        depth_test = tuple(zip(depth_test_a, depth_test_b))
223        # square so a few high values win over many small ones
224        diff_test = sum((abs(a[0] - b[0]) ** 2) +
225                        (abs(a[1] - b[1]) ** 2) for a, b in zip(depth_src, depth_test))
226        if diff_test > diff_best:
227            diff_best = diff_test
228            ele_best = ele_test
229            ele_best_ls[:] = [ele_best]
230        elif diff_test == diff_best:
231            if ele_best is None:
232                ele_best = ele_test
233            ele_best_ls.append(ele_test)
234
235    if len(ele_best_ls) > 1:
236        ele_best_ls_init = ele_best_ls
237        ele_best_ls = []
238        depth_accum_max = -1
239        for ele_test in ele_best_ls_init:
240            depth_test_a = elems_depth_measure(ele_src, ele_test, other_edges_over_edge)
241            depth_test_b = elems_depth_measure(ele_src, ele_test, other_edges_over_face)
242            if depth_test_a is None or depth_test_b is None:
243                continue
244            depth_accum_test = (
245                sum(depth_test_a) + sum(depth_test_b))
246
247            if depth_accum_test > depth_accum_max:
248                depth_accum_max = depth_accum_test
249                ele_best = ele_test
250                ele_best_ls[:] = [ele_best]
251            elif depth_accum_test == depth_accum_max:
252                # we have multiple bests, don't return any
253                ele_best_ls.append(ele_test)
254
255    return ele_best_ls
256
257
258# expose for operators
259def select_next(bm, report):
260    import bmesh
261    ele_pair = [None, None]
262    for i, ele in enumerate(reversed(bm.select_history)):
263        ele_pair[i] = ele
264        if i == 1:
265            break
266
267    if ele_pair[-1] is None:
268        report({'INFO'}, "Selection pair not found")
269        return False
270
271    ele_pair_next = find_next(*ele_pair)
272
273    if len(ele_pair_next) > 1:
274        # We have multiple options,
275        # check topology around the element and find the closest match
276        # (allow for sloppy comparison if exact checks fail).
277
278        def ele_uuid(ele):
279            ele_type = type(ele)
280            if ele_type is bmesh.types.BMFace:
281                ret = [len(f.verts) for l in ele.loops for f in l.edge.link_faces if f is not ele]
282            elif ele_type is bmesh.types.BMEdge:
283                ret = [len(l.face.verts) for l in ele.link_loops]
284            elif ele_type is bmesh.types.BMVert:
285                ret = [len(l.face.verts) for l in ele.link_loops]
286            else:
287                raise TypeError("wrong type")
288            return tuple(sorted(ret))
289
290        def ele_uuid_filter():
291
292            def pass_fn(seq):
293                return seq
294
295            def sum_set(seq):
296                return sum(set(seq))
297
298            uuid_cmp = ele_uuid(ele_pair[0])
299            ele_pair_next_uuid = [(ele, ele_uuid(ele)) for ele in ele_pair_next]
300
301            # Attempt to find the closest match,
302            # start specific, use increasingly more approximate comparisons.
303            for fn in (pass_fn, set, sum_set, len):
304                uuid_cmp_test = fn(uuid_cmp)
305                ele_pair_next_uuid_test = [
306                    (ele, uuid) for (ele, uuid) in ele_pair_next_uuid
307                    if uuid_cmp_test == fn(uuid)
308                ]
309                if len(ele_pair_next_uuid_test) > 1:
310                    ele_pair_next_uuid = ele_pair_next_uuid_test
311                elif len(ele_pair_next_uuid_test) == 1:
312                    return [ele for (ele, uuid) in ele_pair_next_uuid_test]
313            return []
314
315        ele_pair_next[:] = ele_uuid_filter()
316
317        del ele_uuid, ele_uuid_filter
318
319    if len(ele_pair_next) != 1:
320        report({'INFO'}, "No single next item found")
321        return False
322
323    ele = ele_pair_next[0]
324    if ele.hide:
325        report({'INFO'}, "Next element is hidden")
326        return False
327
328    ele.select_set(False)
329    ele.select_set(True)
330    bm.select_history.discard(ele)
331    bm.select_history.add(ele)
332    if type(ele) is bmesh.types.BMFace:
333        bm.faces.active = ele
334    return True
335
336
337def select_prev(bm, report):
338    import bmesh
339    for ele in reversed(bm.select_history):
340        break
341    else:
342        report({'INFO'}, "Last selected not found")
343        return False
344
345    ele.select_set(False)
346
347    for i, ele in enumerate(reversed(bm.select_history)):
348        if i == 1:
349            if type(ele) is bmesh.types.BMFace:
350                bm.faces.active = ele
351            break
352
353    return True
354