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-80 compliant> 20 21__all__ = ( 22 "mesh_linked_uv_islands", 23 "mesh_linked_triangles", 24 "edge_face_count_dict", 25 "edge_face_count", 26 "edge_loops_from_edges", 27 "ngon_tessellate", 28 "triangle_random_points", 29) 30 31 32def mesh_linked_uv_islands(mesh): 33 """ 34 Splits the mesh into connected polygons, use this for separating cubes from 35 other mesh elements within 1 mesh datablock. 36 37 :arg mesh: the mesh used to group with. 38 :type mesh: :class:`bpy.types.Mesh` 39 :return: lists of lists containing polygon indices 40 :rtype: list 41 """ 42 uv_loops = [luv.uv[:] for luv in mesh.uv_layers.active.data] 43 poly_loops = [poly.loop_indices for poly in mesh.polygons] 44 luv_hash = {} 45 luv_hash_get = luv_hash.get 46 luv_hash_ls = [None] * len(uv_loops) 47 for pi, poly_indices in enumerate(poly_loops): 48 for li in poly_indices: 49 uv = uv_loops[li] 50 uv_hub = luv_hash_get(uv) 51 if uv_hub is None: 52 uv_hub = luv_hash[uv] = [pi] 53 else: 54 uv_hub.append(pi) 55 luv_hash_ls[li] = uv_hub 56 57 poly_islands = [] 58 59 # 0 = none, 1 = added, 2 = searched 60 poly_tag = [0] * len(poly_loops) 61 62 while True: 63 poly_index = -1 64 for i in range(len(poly_loops)): 65 if poly_tag[i] == 0: 66 poly_index = i 67 break 68 69 if poly_index != -1: 70 island = [poly_index] 71 poly_tag[poly_index] = 1 72 poly_islands.append(island) 73 else: 74 break # we're done 75 76 added = True 77 while added: 78 added = False 79 for poly_index in island[:]: 80 if poly_tag[poly_index] == 1: 81 for li in poly_loops[poly_index]: 82 for poly_index_shared in luv_hash_ls[li]: 83 if poly_tag[poly_index_shared] == 0: 84 added = True 85 poly_tag[poly_index_shared] = 1 86 island.append(poly_index_shared) 87 poly_tag[poly_index] = 2 88 89 return poly_islands 90 91 92def mesh_linked_triangles(mesh): 93 """ 94 Splits the mesh into connected triangles, use this for separating cubes from 95 other mesh elements within 1 mesh datablock. 96 97 :arg mesh: the mesh used to group with. 98 :type mesh: :class:`bpy.types.Mesh` 99 :return: lists of lists containing triangles. 100 :rtype: list 101 """ 102 103 # Build vert face connectivity 104 vert_tris = [[] for i in range(len(mesh.vertices))] 105 for t in mesh.loop_triangles: 106 for v in t.vertices: 107 vert_tris[v].append(t) 108 109 # sort triangles into connectivity groups 110 tri_groups = [[t] for t in mesh.loop_triangles] 111 # map old, new tri location 112 tri_mapping = list(range(len(mesh.loop_triangles))) 113 114 # Now clump triangles iteratively 115 ok = True 116 while ok: 117 ok = False 118 119 for t in mesh.loop_triangles: 120 mapped_index = tri_mapping[t.index] 121 mapped_group = tri_groups[mapped_index] 122 123 for v in t.vertices: 124 for nxt_t in vert_tris[v]: 125 if nxt_t != t: 126 nxt_mapped_index = tri_mapping[nxt_t.index] 127 128 # We are not a part of the same group 129 if mapped_index != nxt_mapped_index: 130 ok = True 131 132 # Assign mapping to this group so they 133 # all map to this group 134 for grp_t in tri_groups[nxt_mapped_index]: 135 tri_mapping[grp_t.index] = mapped_index 136 137 # Move triangles into this group 138 mapped_group.extend(tri_groups[nxt_mapped_index]) 139 140 # remove reference to the list 141 tri_groups[nxt_mapped_index] = None 142 143 # return all tri groups that are not null 144 # this is all the triangles that are connected in their own lists. 145 return [tg for tg in tri_groups if tg] 146 147 148def edge_face_count_dict(mesh): 149 """ 150 :return: dict of edge keys with their value set to the number of 151 faces using each edge. 152 :rtype: dict 153 """ 154 155 face_edge_count = {} 156 loops = mesh.loops 157 edges = mesh.edges 158 for poly in mesh.polygons: 159 for i in poly.loop_indices: 160 key = edges[loops[i].edge_index].key 161 try: 162 face_edge_count[key] += 1 163 except: 164 face_edge_count[key] = 1 165 166 return face_edge_count 167 168 169def edge_face_count(mesh): 170 """ 171 :return: list face users for each item in mesh.edges. 172 :rtype: list 173 """ 174 edge_face_count = edge_face_count_dict(mesh) 175 get = dict.get 176 return [get(edge_face_count, ed.key, 0) for ed in mesh.edges] 177 178 179def edge_loops_from_edges(mesh, edges=None): 180 """ 181 Edge loops defined by edges 182 183 Takes me.edges or a list of edges and returns the edge loops 184 185 return a list of vertex indices. 186 [ [1, 6, 7, 2], ...] 187 188 closed loops have matching start and end values. 189 """ 190 line_polys = [] 191 192 # Get edges not used by a face 193 if edges is None: 194 edges = mesh.edges 195 196 if not hasattr(edges, "pop"): 197 edges = edges[:] 198 199 while edges: 200 current_edge = edges.pop() 201 vert_end, vert_start = current_edge.vertices[:] 202 line_poly = [vert_start, vert_end] 203 204 ok = True 205 while ok: 206 ok = False 207 # for i, ed in enumerate(edges): 208 i = len(edges) 209 while i: 210 i -= 1 211 ed = edges[i] 212 v1, v2 = ed.vertices 213 if v1 == vert_end: 214 line_poly.append(v2) 215 vert_end = line_poly[-1] 216 ok = 1 217 del edges[i] 218 # break 219 elif v2 == vert_end: 220 line_poly.append(v1) 221 vert_end = line_poly[-1] 222 ok = 1 223 del edges[i] 224 # break 225 elif v1 == vert_start: 226 line_poly.insert(0, v2) 227 vert_start = line_poly[0] 228 ok = 1 229 del edges[i] 230 # break 231 elif v2 == vert_start: 232 line_poly.insert(0, v1) 233 vert_start = line_poly[0] 234 ok = 1 235 del edges[i] 236 # break 237 line_polys.append(line_poly) 238 239 return line_polys 240 241 242def ngon_tessellate(from_data, indices, fix_loops=True, debug_print=True): 243 """ 244 Takes a polyline of indices (ngon) and returns a list of face 245 index lists. Designed to be used for importers that need indices for an 246 ngon to create from existing verts. 247 248 :arg from_data: either a mesh, or a list/tuple of vectors. 249 :type from_data: list or :class:`bpy.types.Mesh` 250 :arg indices: a list of indices to use this list 251 is the ordered closed polyline 252 to fill, and can be a subset of the data given. 253 :type indices: list 254 :arg fix_loops: If this is enabled polylines 255 that use loops to make multiple 256 polylines are delt with correctly. 257 :type fix_loops: bool 258 """ 259 260 from mathutils.geometry import tessellate_polygon 261 from mathutils import Vector 262 vector_to_tuple = Vector.to_tuple 263 264 if not indices: 265 return [] 266 267 def mlen(co): 268 # Manhatten length of a vector, faster then length. 269 return abs(co[0]) + abs(co[1]) + abs(co[2]) 270 271 def vert_from_vector_with_extra_data(v, i): 272 # Calculate data per-vector, for reuse. 273 return v, vector_to_tuple(v, 6), i, mlen(v) 274 275 def ed_key_mlen(v1, v2): 276 if v1[3] > v2[3]: 277 return v2[1], v1[1] 278 else: 279 return v1[1], v2[1] 280 281 if not fix_loops: 282 # Normal single concave loop filling. 283 284 if type(from_data) in {tuple, list}: 285 verts = [Vector(from_data[i]) for ii, i in enumerate(indices)] 286 else: 287 verts = [from_data.vertices[i].co for ii, i in enumerate(indices)] 288 289 # same as reversed(range(1, len(verts))): 290 for i in range(len(verts) - 1, 0, -1): 291 if verts[i][1] == verts[i - 1][0]: 292 verts.pop(i - 1) 293 294 fill = tessellate_polygon([verts]) 295 296 else: 297 # Separate this loop into multiple loops be finding edges that are 298 # used twice. This is used by Light-Wave LWO files a lot. 299 300 if type(from_data) in {tuple, list}: 301 verts = [ 302 vert_from_vector_with_extra_data(Vector(from_data[i]), ii) 303 for ii, i in enumerate(indices) 304 ] 305 else: 306 verts = [ 307 vert_from_vector_with_extra_data(from_data.vertices[i].co, ii) 308 for ii, i in enumerate(indices) 309 ] 310 311 edges = [(i, i - 1) for i in range(len(verts))] 312 if edges: 313 edges[0] = (0, len(verts) - 1) 314 315 if not verts: 316 return [] 317 318 edges_used = set() 319 edges_doubles = set() 320 # We need to check if any edges are used twice location based. 321 for ed in edges: 322 edkey = ed_key_mlen(verts[ed[0]], verts[ed[1]]) 323 if edkey in edges_used: 324 edges_doubles.add(edkey) 325 else: 326 edges_used.add(edkey) 327 328 # Store a list of unconnected loop segments split by double edges. 329 # will join later 330 loop_segments = [] 331 332 v_prev = verts[0] 333 context_loop = [v_prev] 334 loop_segments = [context_loop] 335 336 for v in verts: 337 if v != v_prev: 338 # Are we crossing an edge we removed? 339 if ed_key_mlen(v, v_prev) in edges_doubles: 340 context_loop = [v] 341 loop_segments.append(context_loop) 342 else: 343 if context_loop and context_loop[-1][1] == v[1]: 344 pass 345 else: 346 context_loop.append(v) 347 348 v_prev = v 349 # Now join loop segments 350 351 def join_seg(s1, s2): 352 if s2[-1][1] == s1[0][1]: 353 s1, s2 = s2, s1 354 elif s1[-1][1] == s2[0][1]: 355 pass 356 else: 357 return False 358 359 # If were still here s1 and s2 are 2 segments in the same poly-line. 360 s1.pop() # remove the last vert from s1 361 s1.extend(s2) # add segment 2 to segment 1 362 363 if s1[0][1] == s1[-1][1]: # remove endpoints double 364 s1.pop() 365 366 del s2[:] # Empty this segment s2 so we don't use it again. 367 return True 368 369 joining_segments = True 370 while joining_segments: 371 joining_segments = False 372 segcount = len(loop_segments) 373 374 for j in range(segcount - 1, -1, -1): # reversed(range(segcount)): 375 seg_j = loop_segments[j] 376 if seg_j: 377 for k in range(j - 1, -1, -1): # reversed(range(j)): 378 if not seg_j: 379 break 380 seg_k = loop_segments[k] 381 382 if seg_k and join_seg(seg_j, seg_k): 383 joining_segments = True 384 385 loop_list = loop_segments 386 387 for verts in loop_list: 388 while verts and verts[0][1] == verts[-1][1]: 389 verts.pop() 390 391 loop_list = [verts for verts in loop_list if len(verts) > 2] 392 # DONE DEALING WITH LOOP FIXING 393 394 # vert mapping 395 vert_map = [None] * len(indices) 396 ii = 0 397 for verts in loop_list: 398 if len(verts) > 2: 399 for i, vert in enumerate(verts): 400 vert_map[i + ii] = vert[2] 401 ii += len(verts) 402 403 fill = tessellate_polygon([[v[0] for v in loop] for loop in loop_list]) 404 # draw_loops(loop_list) 405 #raise Exception("done loop") 406 # map to original indices 407 fill = [[vert_map[i] for i in f] for f in fill] 408 409 if not fill: 410 if debug_print: 411 print('Warning Cannot scanfill, fallback on a triangle fan.') 412 fill = [[0, i - 1, i] for i in range(2, len(indices))] 413 else: 414 # Use real scan-fill. 415 # See if its flipped the wrong way. 416 flip = None 417 for fi in fill: 418 if flip is not None: 419 break 420 for i, vi in enumerate(fi): 421 if vi == 0 and fi[i - 1] == 1: 422 flip = False 423 break 424 elif vi == 1 and fi[i - 1] == 0: 425 flip = True 426 break 427 428 if not flip: 429 for i, fi in enumerate(fill): 430 fill[i] = tuple([ii for ii in reversed(fi)]) 431 432 return fill 433 434 435def triangle_random_points(num_points, loop_triangles): 436 """ 437 Generates a list of random points over mesh loop triangles. 438 439 :arg num_points: the number of random points to generate on each triangle. 440 :type int: 441 :arg loop_triangles: list of the triangles to generate points on. 442 :type loop_triangles: :class:`bpy.types.MeshLoopTriangle`, sequence 443 :return: list of random points over all triangles. 444 :rtype: list 445 """ 446 447 from random import random 448 449 # For each triangle, generate the required number of random points 450 sampled_points = [None] * (num_points * len(loop_triangles)) 451 for i, lt in enumerate(loop_triangles): 452 # Get triangle vertex coordinates 453 verts = lt.id_data.vertices 454 ltv = lt.vertices[:] 455 tv = (verts[ltv[0]].co, verts[ltv[1]].co, verts[ltv[2]].co) 456 457 for k in range(num_points): 458 u1 = random() 459 u2 = random() 460 u_tot = u1 + u2 461 462 if u_tot > 1: 463 u1 = 1.0 - u1 464 u2 = 1.0 - u2 465 466 side1 = tv[1] - tv[0] 467 side2 = tv[2] - tv[0] 468 469 p = tv[0] + u1 * side1 + u2 * side2 470 471 sampled_points[num_points * i + k] = p 472 473 return sampled_points 474