9ec8ee98e4195583ba3142bee3e3f8a230f024d3
[blender.git] / release / scripts / modules / bpy_extras / mesh_utils.py
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
22 def mesh_linked_faces(mesh):
23     '''
24     Splits the mesh into connected parts,
25     these parts are returned as lists of faces.
26     used for seperating cubes from other mesh elements in the 1 mesh
27     '''
28
29     # Build vert face connectivity
30     vert_faces = [[] for i in range(len(mesh.vertices))]
31     for f in mesh.faces:
32         for v in f.vertices:
33             vert_faces[v].append(f)
34
35     # sort faces into connectivity groups
36     face_groups = [[f] for f in mesh.faces]
37     face_mapping = list(range(len(mesh.faces)))  # map old, new face location
38
39     # Now clump faces iterativly
40     ok = True
41     while ok:
42         ok = False
43
44         for i, f in enumerate(mesh.faces):
45             mapped_index = face_mapping[f.index]
46             mapped_group = face_groups[mapped_index]
47
48             for v in f.vertices:
49                 for nxt_f in vert_faces[v]:
50                     if nxt_f != f:
51                         nxt_mapped_index = face_mapping[nxt_f.index]
52
53                         # We are not a part of the same group
54                         if mapped_index != nxt_mapped_index:
55                             ok = True
56
57                             # Assign mapping to this group so they all map to this group
58                             for grp_f in face_groups[nxt_mapped_index]:
59                                 face_mapping[grp_f.index] = mapped_index
60
61                             # Move faces into this group
62                             mapped_group.extend(face_groups[nxt_mapped_index])
63
64                             # remove reference to the list
65                             face_groups[nxt_mapped_index] = None
66
67     # return all face groups that are not null
68     # this is all the faces that are connected in their own lists.
69     return [fg for fg in face_groups if fg]
70
71
72 def edge_face_count_dict(mesh):
73     face_edge_keys = [face.edge_keys for face in mesh.faces]
74     face_edge_count = {}
75     for face_keys in face_edge_keys:
76         for key in face_keys:
77             try:
78                 face_edge_count[key] += 1
79             except:
80                 face_edge_count[key] = 1
81
82     return face_edge_count
83
84
85 def edge_face_count(mesh):
86     edge_face_count_dict = edge_face_count_dict(mesh)
87     return [edge_face_count_dict.get(ed.key, 0) for ed in mesh.edges]
88
89
90 def edge_loops_from_faces(mesh, faces=None, seams=()):
91     """
92     Edge loops defined by faces
93
94     Takes me.faces or a list of faces and returns the edge loops
95     These edge loops are the edges that sit between quads, so they dont touch
96     1 quad, note: not connected will make 2 edge loops, both only containing 2 edges.
97
98     return a list of edge key lists
99     [ [(0,1), (4, 8), (3,8)], ...]
100
101     return a list of edge vertex index lists
102     """
103
104     OTHER_INDEX = 2, 3, 0, 1  # opposite face index
105
106     if faces is None:
107         faces = mesh.faces
108
109     edges = {}
110
111     for f in faces:
112 #            if len(f) == 4:
113         if f.vertices_raw[3] != 0:
114             edge_keys = f.edge_keys
115             for i, edkey in enumerate(f.edge_keys):
116                 edges.setdefault(edkey, []).append(edge_keys[OTHER_INDEX[i]])
117
118     for edkey in seams:
119         edges[edkey] = []
120
121     # Collect edge loops here
122     edge_loops = []
123
124     for edkey, ed_adj in edges.items():
125         if 0 < len(ed_adj) < 3:  # 1 or 2
126             # Seek the first edge
127             context_loop = [edkey, ed_adj[0]]
128             edge_loops.append(context_loop)
129             if len(ed_adj) == 2:
130                 other_dir = ed_adj[1]
131             else:
132                 other_dir = None
133
134             ed_adj[:] = []
135
136             flipped = False
137
138             while 1:
139                 # from knowing the last 2, look for th next.
140                 ed_adj = edges[context_loop[-1]]
141                 if len(ed_adj) != 2:
142
143                     if other_dir and flipped == False:  # the original edge had 2 other edges
144                         flipped = True  # only flip the list once
145                         context_loop.reverse()
146                         ed_adj[:] = []
147                         context_loop.append(other_dir)  # save 1 lookiup
148
149                         ed_adj = edges[context_loop[-1]]
150                         if len(ed_adj) != 2:
151                             ed_adj[:] = []
152                             break
153                     else:
154                         ed_adj[:] = []
155                         break
156
157                 i = ed_adj.index(context_loop[-2])
158                 context_loop.append(ed_adj[not  i])
159
160                 # Dont look at this again
161                 ed_adj[:] = []
162
163     return edge_loops
164
165
166 def edge_loops_from_edges(mesh, edges=None):
167     """
168     Edge loops defined by edges
169
170     Takes me.edges or a list of edges and returns the edge loops
171
172     return a list of vertex indices.
173     [ [1, 6, 7, 2], ...]
174
175     closed loops have matching start and end values.
176     """
177     line_polys = []
178
179     # Get edges not used by a face
180     if edges is None:
181         edges = mesh.edges
182
183     if not hasattr(edges, "pop"):
184         edges = edges[:]
185
186     edge_dict = {ed.key: ed for ed in mesh.edges if ed.select}
187
188     while edges:
189         current_edge = edges.pop()
190         vert_end, vert_start = current_edge.vertices[:]
191         line_poly = [vert_start, vert_end]
192
193         ok = True
194         while ok:
195             ok = False
196             #for i, ed in enumerate(edges):
197             i = len(edges)
198             while i:
199                 i -= 1
200                 ed = edges[i]
201                 v1, v2 = ed.vertices
202                 if v1 == vert_end:
203                     line_poly.append(v2)
204                     vert_end = line_poly[-1]
205                     ok = 1
206                     del edges[i]
207                     # break
208                 elif v2 == vert_end:
209                     line_poly.append(v1)
210                     vert_end = line_poly[-1]
211                     ok = 1
212                     del edges[i]
213                     #break
214                 elif v1 == vert_start:
215                     line_poly.insert(0, v2)
216                     vert_start = line_poly[0]
217                     ok = 1
218                     del edges[i]
219                     # break
220                 elif v2 == vert_start:
221                     line_poly.insert(0, v1)
222                     vert_start = line_poly[0]
223                     ok = 1
224                     del edges[i]
225                     #break
226         line_polys.append(line_poly)
227
228     return line_polys
229
230
231 def ngon_tesselate(from_data, indices, fix_loops=True):
232     '''
233     Takes a polyline of indices (fgon)
234     and returns a list of face indicie lists.
235     Designed to be used for importers that need indices for an fgon to create from existing verts.
236
237     from_data: either a mesh, or a list/tuple of vectors.
238     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.
239     fix_loops: If this is enabled polylines that use loops to make multiple polylines are delt with correctly.
240     '''
241
242     from mathutils import Vector
243     vector_to_tuple = Vector.to_tuple
244
245     if not indices:
246         return []
247
248     def mlen(co):
249         return abs(co[0]) + abs(co[1]) + abs(co[2])  # manhatten length of a vector, faster then length
250
251     def vert_treplet(v, i):
252         return v, vector_to_tuple(v, 6), i, mlen(v)
253
254     def ed_key_mlen(v1, v2):
255         if v1[3] > v2[3]:
256             return v2[1], v1[1]
257         else:
258             return v1[1], v2[1]
259
260     if not PREF_FIX_LOOPS:
261         '''
262         Normal single concave loop filling
263         '''
264         if type(from_data) in (tuple, list):
265             verts = [Vector(from_data[i]) for ii, i in enumerate(indices)]
266         else:
267             verts = [from_data.vertices[i].co for ii, i in enumerate(indices)]
268
269         for i in range(len(verts) - 1, 0, -1):  # same as reversed(xrange(1, len(verts))):
270             if verts[i][1] == verts[i - 1][0]:
271                 verts.pop(i - 1)
272
273         fill = fill_polygon([verts])
274
275     else:
276         '''
277         Seperate this loop into multiple loops be finding edges that are used twice
278         This is used by lightwave LWO files a lot
279         '''
280
281         if type(from_data) in (tuple, list):
282             verts = [vert_treplet(Vector(from_data[i]), ii) for ii, i in enumerate(indices)]
283         else:
284             verts = [vert_treplet(from_data.vertices[i].co, ii) for ii, i in enumerate(indices)]
285
286         edges = [(i, i - 1) for i in range(len(verts))]
287         if edges:
288             edges[0] = (0, len(verts) - 1)
289
290         if not verts:
291             return []
292
293         edges_used = set()
294         edges_doubles = set()
295         # We need to check if any edges are used twice location based.
296         for ed in edges:
297             edkey = ed_key_mlen(verts[ed[0]], verts[ed[1]])
298             if edkey in edges_used:
299                 edges_doubles.add(edkey)
300             else:
301                 edges_used.add(edkey)
302
303         # Store a list of unconnected loop segments split by double edges.
304         # will join later
305         loop_segments = []
306
307         v_prev = verts[0]
308         context_loop = [v_prev]
309         loop_segments = [context_loop]
310
311         for v in verts:
312             if v != v_prev:
313                 # Are we crossing an edge we removed?
314                 if ed_key_mlen(v, v_prev) in edges_doubles:
315                     context_loop = [v]
316                     loop_segments.append(context_loop)
317                 else:
318                     if context_loop and context_loop[-1][1] == v[1]:
319                         #raise "as"
320                         pass
321                     else:
322                         context_loop.append(v)
323
324                 v_prev = v
325         # Now join loop segments
326
327         def join_seg(s1, s2):
328             if s2[-1][1] == s1[0][1]:
329                 s1, s2 = s2, s1
330             elif s1[-1][1] == s2[0][1]:
331                 pass
332             else:
333                 return False
334
335             # If were stuill here s1 and s2 are 2 segments in the same polyline
336             s1.pop()  # remove the last vert from s1
337             s1.extend(s2)  # add segment 2 to segment 1
338
339             if s1[0][1] == s1[-1][1]:  # remove endpoints double
340                 s1.pop()
341
342             s2[:] = []  # Empty this segment s2 so we dont use it again.
343             return True
344
345         joining_segments = True
346         while joining_segments:
347             joining_segments = False
348             segcount = len(loop_segments)
349
350             for j in range(segcount - 1, -1, -1):  # reversed(range(segcount)):
351                 seg_j = loop_segments[j]
352                 if seg_j:
353                     for k in range(j - 1, -1, -1):  # reversed(range(j)):
354                         if not seg_j:
355                             break
356                         seg_k = loop_segments[k]
357
358                         if seg_k and join_seg(seg_j, seg_k):
359                             joining_segments = True
360
361         loop_list = loop_segments
362
363         for verts in loop_list:
364             while verts and verts[0][1] == verts[-1][1]:
365                 verts.pop()
366
367         loop_list = [verts for verts in loop_list if len(verts) > 2]
368         # DONE DEALING WITH LOOP FIXING
369
370         # vert mapping
371         vert_map = [None] * len(indices)
372         ii = 0
373         for verts in loop_list:
374             if len(verts) > 2:
375                 for i, vert in enumerate(verts):
376                     vert_map[i + ii] = vert[2]
377                 ii += len(verts)
378
379         fill = tesselate_polygon([[v[0] for v in loop] for loop in loop_list])
380         #draw_loops(loop_list)
381         #raise 'done loop'
382         # map to original indices
383         fill = [[vert_map[i] for i in reversed(f)] for f in fill]
384
385     if not fill:
386         print('Warning Cannot scanfill, fallback on a triangle fan.')
387         fill = [[0, i - 1, i] for i in range(2, len(indices))]
388     else:
389         # Use real scanfill.
390         # See if its flipped the wrong way.
391         flip = None
392         for fi in fill:
393             if flip != None:
394                 break
395             for i, vi in enumerate(fi):
396                 if vi == 0 and fi[i - 1] == 1:
397                     flip = False
398                     break
399                 elif vi == 1 and fi[i - 1] == 0:
400                     flip = True
401                     break
402
403         if not flip:
404             for i, fi in enumerate(fill):
405                 fill[i] = tuple([ii for ii in reversed(fi)])
406
407     return fill