1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
|
# ##### 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:`bpy.types.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 iteratively
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:`bpy.types.Mesh`
:arg faces: optional face list to only use some of the meshes faces.
:type faces: :class:`bpy.types.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.vertices) == 4:
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 the 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 look-up
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 don't 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 is not 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:`bpy.types.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
|