Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/release/scripts/modules/bpy_extras/mesh_utils.py
diff options
context:
space:
mode:
Diffstat (limited to 'release/scripts/modules/bpy_extras/mesh_utils.py')
-rw-r--r--release/scripts/modules/bpy_extras/mesh_utils.py510
1 files changed, 510 insertions, 0 deletions
diff --git a/release/scripts/modules/bpy_extras/mesh_utils.py b/release/scripts/modules/bpy_extras/mesh_utils.py
new file mode 100644
index 00000000000..ecd620ff2c9
--- /dev/null
+++ b/release/scripts/modules/bpy_extras/mesh_utils.py
@@ -0,0 +1,510 @@
+# ##### 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-80 compliant>
+
+__all__ = (
+ "mesh_linked_faces",
+ "edge_face_count_dict",
+ "edge_face_count",
+ "edge_loops_from_faces",
+ "edge_loops_from_edges",
+ "ngon_tesselate",
+ "face_random_points",
+)
+
+
+def mesh_linked_faces(mesh):
+ """
+ Splits the mesh into connected faces, use this for seperating cubes from
+ other mesh elements within 1 mesh datablock.
+
+ :arg mesh: the mesh used to group with.
+ :type mesh: :class:`Mesh`
+ :return: lists of lists containing faces.
+ :rtype: list
+ """
+
+ # Build vert face connectivity
+ vert_faces = [[] for i in range(len(mesh.vertices))]
+ for f in mesh.faces:
+ for v in f.vertices:
+ vert_faces[v].append(f)
+
+ # sort faces into connectivity groups
+ face_groups = [[f] for f in mesh.faces]
+ face_mapping = list(range(len(mesh.faces))) # map old, new face location
+
+ # Now clump faces iterativly
+ ok = True
+ while ok:
+ ok = False
+
+ for i, f in enumerate(mesh.faces):
+ mapped_index = face_mapping[f.index]
+ mapped_group = face_groups[mapped_index]
+
+ for v in f.vertices:
+ for nxt_f in vert_faces[v]:
+ if nxt_f != f:
+ nxt_mapped_index = face_mapping[nxt_f.index]
+
+ # We are not a part of the same group
+ if mapped_index != nxt_mapped_index:
+ ok = True
+
+ # Assign mapping to this group so they
+ # all map to this group
+ for grp_f in face_groups[nxt_mapped_index]:
+ face_mapping[grp_f.index] = mapped_index
+
+ # Move faces into this group
+ mapped_group.extend(face_groups[nxt_mapped_index])
+
+ # remove reference to the list
+ face_groups[nxt_mapped_index] = None
+
+ # 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):
+ """
+ :return: dict of edge keys with their value set to the number of
+ faces using each edge.
+ :rtype: dict
+ """
+ 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):
+ """
+ :return: list face users for each item in mesh.edges.
+ :rtype: list
+ """
+ edge_face_count = edge_face_count_dict(mesh)
+ get = dict.get
+ return [get(edge_face_count, 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)], ...]
+
+ :arg mesh: the mesh used to get edge loops from.
+ :type mesh: :class:`Mesh`
+ :arg faces: optional face list to only use some of the meshes faces.
+ :type faces: :class:`MeshFaces`, sequence or or NoneType
+ :return: return a list of edge vertex index lists.
+ :rtype: list
+ """
+
+ 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:
+ # the original edge had 2 other edges
+ if other_dir and flipped == False:
+ 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[:]
+
+ 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.geometry import tesselate_polygon
+ from mathutils import Vector
+ vector_to_tuple = Vector.to_tuple
+
+ if not indices:
+ return []
+
+ def mlen(co):
+ # manhatten length of a vector, faster then length
+ return abs(co[0]) + abs(co[1]) + abs(co[2])
+
+ 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 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)]
+
+ # same as reversed(range(1, len(verts))):
+ for i in range(len(verts) - 1, 0, -1):
+ if verts[i][1] == verts[i - 1][0]:
+ verts.pop(i - 1)
+
+ fill = tesselate_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
+
+
+def face_random_points(num_points, faces):
+ """
+ Generates a list of random points over mesh faces.
+
+ :arg num_points: the number of random points to generate on each face.
+ :type int:
+ :arg faces: list of the faces to generate points on.
+ :type faces: :class:`MeshFaces`, sequence
+ :return: list of random points over all faces.
+ :rtype: list
+ """
+
+ from random import random
+ from mathutils.geometry import area_tri
+
+ # Split all quads into 2 tris, tris remain unchanged
+ tri_faces = []
+ for f in faces:
+ tris = []
+ verts = f.id_data.vertices
+ fv = f.vertices[:]
+ tris.append((verts[fv[0]].co,
+ verts[fv[1]].co,
+ verts[fv[2]].co,
+ ))
+ if len(fv) == 4:
+ tris.append((verts[fv[0]].co,
+ verts[fv[3]].co,
+ verts[fv[2]].co,
+ ))
+ tri_faces.append(tris)
+
+ # For each face, generate the required number of random points
+ sampled_points = [None] * (num_points * len(faces))
+ for i, tf in enumerate(tri_faces):
+ for k in range(num_points):
+ # If this is a quad, we need to weight its 2 tris by their area
+ if len(tf) != 1:
+ area1 = area_tri(*tf[0])
+ area2 = area_tri(*tf[1])
+ area_tot = area1 + area2
+
+ area1 = area1 / area_tot
+ area2 = area2 / area_tot
+
+ vecs = tf[0 if (random() < area1) else 1]
+ else:
+ vecs = tf[0]
+
+ u1 = random()
+ u2 = random()
+ u_tot = u1 + u2
+
+ if u_tot > 1:
+ u1 = 1.0 - u1
+ u2 = 1.0 - u2
+
+ side1 = vecs[1] - vecs[0]
+ side2 = vecs[2] - vecs[0]
+
+ p = vecs[0] + u1 * side1 + u2 * side2
+
+ sampled_points[num_points * i + k] = p
+
+ return sampled_points
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-23 03:17:55 +0300