diff options
Diffstat (limited to 'release/scripts/modules/bpy_extras/mesh_utils.py')
| -rw-r--r-- | release/scripts/modules/bpy_extras/mesh_utils.py | 338 |
1 files changed, 338 insertions, 0 deletions
diff --git a/release/scripts/modules/bpy_extras/mesh_utils.py b/release/scripts/modules/bpy_extras/mesh_utils.py index 5bacff7b0cc..9ec8ee98e41 100644 --- a/release/scripts/modules/bpy_extras/mesh_utils.py +++ b/release/scripts/modules/bpy_extras/mesh_utils.py @@ -67,3 +67,341 @@ def mesh_linked_faces(mesh): # return all face groups that are not null # this is all the faces that are connected in their own lists. return [fg for fg in face_groups if fg] + + +def edge_face_count_dict(mesh): + face_edge_keys = [face.edge_keys for face in mesh.faces] + face_edge_count = {} + for face_keys in face_edge_keys: + for key in face_keys: + try: + face_edge_count[key] += 1 + except: + face_edge_count[key] = 1 + + return face_edge_count + + +def edge_face_count(mesh): + edge_face_count_dict = edge_face_count_dict(mesh) + return [edge_face_count_dict.get(ed.key, 0) for ed in mesh.edges] + + +def edge_loops_from_faces(mesh, faces=None, seams=()): + """ + Edge loops defined by faces + + Takes me.faces or a list of faces and returns the edge loops + These edge loops are the edges that sit between quads, so they dont touch + 1 quad, note: not connected will make 2 edge loops, both only containing 2 edges. + + return a list of edge key lists + [ [(0,1), (4, 8), (3,8)], ...] + + return a list of edge vertex index lists + """ + + OTHER_INDEX = 2, 3, 0, 1 # opposite face index + + if faces is None: + faces = mesh.faces + + edges = {} + + for f in faces: +# if len(f) == 4: + if f.vertices_raw[3] != 0: + edge_keys = f.edge_keys + for i, edkey in enumerate(f.edge_keys): + edges.setdefault(edkey, []).append(edge_keys[OTHER_INDEX[i]]) + + for edkey in seams: + edges[edkey] = [] + + # Collect edge loops here + edge_loops = [] + + for edkey, ed_adj in edges.items(): + if 0 < len(ed_adj) < 3: # 1 or 2 + # Seek the first edge + context_loop = [edkey, ed_adj[0]] + edge_loops.append(context_loop) + if len(ed_adj) == 2: + other_dir = ed_adj[1] + else: + other_dir = None + + ed_adj[:] = [] + + flipped = False + + while 1: + # from knowing the last 2, look for th next. + ed_adj = edges[context_loop[-1]] + if len(ed_adj) != 2: + + if other_dir and flipped == False: # the original edge had 2 other edges + flipped = True # only flip the list once + context_loop.reverse() + ed_adj[:] = [] + context_loop.append(other_dir) # save 1 lookiup + + ed_adj = edges[context_loop[-1]] + if len(ed_adj) != 2: + ed_adj[:] = [] + break + else: + ed_adj[:] = [] + break + + i = ed_adj.index(context_loop[-2]) + context_loop.append(ed_adj[not i]) + + # Dont look at this again + ed_adj[:] = [] + + return edge_loops + + +def edge_loops_from_edges(mesh, edges=None): + """ + Edge loops defined by edges + + Takes me.edges or a list of edges and returns the edge loops + + return a list of vertex indices. + [ [1, 6, 7, 2], ...] + + closed loops have matching start and end values. + """ + line_polys = [] + + # Get edges not used by a face + if edges is None: + edges = mesh.edges + + if not hasattr(edges, "pop"): + edges = edges[:] + + edge_dict = {ed.key: ed for ed in mesh.edges if ed.select} + + while edges: + current_edge = edges.pop() + vert_end, vert_start = current_edge.vertices[:] + line_poly = [vert_start, vert_end] + + ok = True + while ok: + ok = False + #for i, ed in enumerate(edges): + i = len(edges) + while i: + i -= 1 + ed = edges[i] + v1, v2 = ed.vertices + if v1 == vert_end: + line_poly.append(v2) + vert_end = line_poly[-1] + ok = 1 + del edges[i] + # break + elif v2 == vert_end: + line_poly.append(v1) + vert_end = line_poly[-1] + ok = 1 + del edges[i] + #break + elif v1 == vert_start: + line_poly.insert(0, v2) + vert_start = line_poly[0] + ok = 1 + del edges[i] + # break + elif v2 == vert_start: + line_poly.insert(0, v1) + vert_start = line_poly[0] + ok = 1 + del edges[i] + #break + line_polys.append(line_poly) + + return line_polys + + +def ngon_tesselate(from_data, indices, fix_loops=True): + ''' + Takes a polyline of indices (fgon) + and returns a list of face indicie lists. + Designed to be used for importers that need indices for an fgon to create from existing verts. + + from_data: either a mesh, or a list/tuple of vectors. + indices: a list of indices to use this list is the ordered closed polyline to fill, and can be a subset of the data given. + fix_loops: If this is enabled polylines that use loops to make multiple polylines are delt with correctly. + ''' + + from mathutils import Vector + vector_to_tuple = Vector.to_tuple + + if not indices: + return [] + + def mlen(co): + return abs(co[0]) + abs(co[1]) + abs(co[2]) # manhatten length of a vector, faster then length + + def vert_treplet(v, i): + return v, vector_to_tuple(v, 6), i, mlen(v) + + def ed_key_mlen(v1, v2): + if v1[3] > v2[3]: + return v2[1], v1[1] + else: + return v1[1], v2[1] + + if not PREF_FIX_LOOPS: + ''' + Normal single concave loop filling + ''' + if type(from_data) in (tuple, list): + verts = [Vector(from_data[i]) for ii, i in enumerate(indices)] + else: + verts = [from_data.vertices[i].co for ii, i in enumerate(indices)] + + for i in range(len(verts) - 1, 0, -1): # same as reversed(xrange(1, len(verts))): + if verts[i][1] == verts[i - 1][0]: + verts.pop(i - 1) + + fill = fill_polygon([verts]) + + else: + ''' + Seperate this loop into multiple loops be finding edges that are used twice + This is used by lightwave LWO files a lot + ''' + + if type(from_data) in (tuple, list): + verts = [vert_treplet(Vector(from_data[i]), ii) for ii, i in enumerate(indices)] + else: + verts = [vert_treplet(from_data.vertices[i].co, ii) for ii, i in enumerate(indices)] + + edges = [(i, i - 1) for i in range(len(verts))] + if edges: + edges[0] = (0, len(verts) - 1) + + if not verts: + return [] + + edges_used = set() + edges_doubles = set() + # We need to check if any edges are used twice location based. + for ed in edges: + edkey = ed_key_mlen(verts[ed[0]], verts[ed[1]]) + if edkey in edges_used: + edges_doubles.add(edkey) + else: + edges_used.add(edkey) + + # Store a list of unconnected loop segments split by double edges. + # will join later + loop_segments = [] + + v_prev = verts[0] + context_loop = [v_prev] + loop_segments = [context_loop] + + for v in verts: + if v != v_prev: + # Are we crossing an edge we removed? + if ed_key_mlen(v, v_prev) in edges_doubles: + context_loop = [v] + loop_segments.append(context_loop) + else: + if context_loop and context_loop[-1][1] == v[1]: + #raise "as" + pass + else: + context_loop.append(v) + + v_prev = v + # Now join loop segments + + def join_seg(s1, s2): + if s2[-1][1] == s1[0][1]: + s1, s2 = s2, s1 + elif s1[-1][1] == s2[0][1]: + pass + else: + return False + + # If were stuill here s1 and s2 are 2 segments in the same polyline + s1.pop() # remove the last vert from s1 + s1.extend(s2) # add segment 2 to segment 1 + + if s1[0][1] == s1[-1][1]: # remove endpoints double + s1.pop() + + s2[:] = [] # Empty this segment s2 so we dont use it again. + return True + + joining_segments = True + while joining_segments: + joining_segments = False + segcount = len(loop_segments) + + for j in range(segcount - 1, -1, -1): # reversed(range(segcount)): + seg_j = loop_segments[j] + if seg_j: + for k in range(j - 1, -1, -1): # reversed(range(j)): + if not seg_j: + break + seg_k = loop_segments[k] + + if seg_k and join_seg(seg_j, seg_k): + joining_segments = True + + loop_list = loop_segments + + for verts in loop_list: + while verts and verts[0][1] == verts[-1][1]: + verts.pop() + + loop_list = [verts for verts in loop_list if len(verts) > 2] + # DONE DEALING WITH LOOP FIXING + + # vert mapping + vert_map = [None] * len(indices) + ii = 0 + for verts in loop_list: + if len(verts) > 2: + for i, vert in enumerate(verts): + vert_map[i + ii] = vert[2] + ii += len(verts) + + fill = tesselate_polygon([[v[0] for v in loop] for loop in loop_list]) + #draw_loops(loop_list) + #raise 'done loop' + # map to original indices + fill = [[vert_map[i] for i in reversed(f)] for f in fill] + + if not fill: + print('Warning Cannot scanfill, fallback on a triangle fan.') + fill = [[0, i - 1, i] for i in range(2, len(indices))] + else: + # Use real scanfill. + # See if its flipped the wrong way. + flip = None + for fi in fill: + if flip != None: + break + for i, vi in enumerate(fi): + if vi == 0 and fi[i - 1] == 1: + flip = False + break + elif vi == 1 and fi[i - 1] == 0: + flip = True + break + + if not flip: + for i, fi in enumerate(fill): + fill[i] = tuple([ii for ii in reversed(fi)]) + + return fill |