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