Added a function to BPyMesh - getFaceLoopEdges(faces, seams=[])
[blender.git] / release / scripts / bpymodules / BPyMesh.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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
16 #
17 # ***** END GPL LICENCE BLOCK *****
18 # --------------------------------------------------------------------------
19
20
21 import Blender
22 import BPyMesh_redux # seperated because of its size.
23 # reload(BPyMesh_redux)
24 redux= BPyMesh_redux.redux
25
26 # python 2.3 has no reversed() iterator. this will only work on lists and tuples
27 try:
28         reversed
29 except:
30         def reversed(l): return l[::-1]
31
32
33 # If python version is less than 2.4, try to get set stuff from module
34 try:
35         set
36 except:
37         try:
38                 from sets import Set as set
39         except:
40                 set= None
41
42
43
44
45
46 def meshWeight2List(me):
47         ''' Takes a mesh and return its group names and a list of lists, one list per vertex.
48         aligning the each vert list with the group names, each list contains float value for the weight.
49         These 2 lists can be modified and then used with list2MeshWeight to apply the changes.
50         '''
51         
52         # Clear the vert group.
53         groupNames= me.getVertGroupNames()
54         len_groupNames= len(groupNames)
55         
56         if not len_groupNames:
57                 # no verts? return a vert aligned empty list
58                 return [[] for i in xrange(len(me.verts))]
59         
60         else:
61                 vWeightList= [[0.0]*len_groupNames for i in xrange(len(me.verts))]
62         
63         for group_index, group in enumerate(groupNames):
64                 for vert_index, weight in me.getVertsFromGroup(group, 1): # (i,w)  tuples.
65                         vWeightList[vert_index][group_index]= weight
66         
67         # removed this because me may be copying teh vertex groups.
68         #for group in groupNames:
69         #       me.removeVertGroup(group)
70         
71         return groupNames, vWeightList
72
73
74 def list2MeshWeight(me, groupNames, vWeightList):
75         ''' Takes a list of groups and a list of vertex Weight lists as created by meshWeight2List
76         and applys it to the mesh.'''
77         
78         if len(vWeightList) != len(me.verts):
79                 raise 'Error, Lists Differ in size, do not modify your mesh.verts before updating the weights'
80         
81         act_group = me.activeGroup
82         
83         # Clear the vert group.
84         currentGroupNames= me.getVertGroupNames()
85         for group in currentGroupNames:
86                 me.removeVertGroup(group) # messes up the active group.
87         
88         # Add clean unused vert groupNames back
89         currentGroupNames= me.getVertGroupNames()
90         for group in groupNames:
91                 me.addVertGroup(group)
92         
93         add_ = Blender.Mesh.AssignModes.ADD
94         
95         vertList= [None]
96         for i, v in enumerate(me.verts):
97                 vertList[0]= i
98                 for group_index, weight in enumerate(vWeightList[i]):
99                         if weight:
100                                 try:
101                                         me.assignVertsToGroup(groupNames[group_index], vertList, min(1, max(0, weight)), add_)
102                                 except:
103                                         pass # vert group is not used anymore.
104         
105         try:    me.activeGroup = act_group
106         except: pass
107         
108         me.update()
109
110
111
112
113 def meshWeight2Dict(me):
114         ''' Takes a mesh and return its group names and a list of dicts, one dict per vertex.
115         using the group as a key and a float value for the weight.
116         These 2 lists can be modified and then used with dict2MeshWeight to apply the changes.
117         '''
118         
119         vWeightDict= [dict() for i in xrange(len(me.verts))] # Sync with vertlist.
120         
121         # Clear the vert group.
122         groupNames= me.getVertGroupNames()
123         
124         for group in groupNames:
125                 for vert_index, weight in me.getVertsFromGroup(group, 1): # (i,w)  tuples.
126                         vWeightDict[vert_index][group]= weight
127         
128         # removed this because me may be copying teh vertex groups.
129         #for group in groupNames:
130         #       me.removeVertGroup(group)
131         
132         return groupNames, vWeightDict
133
134
135 def dict2MeshWeight(me, groupNames, vWeightDict):
136         ''' Takes a list of groups and a list of vertex Weight dicts as created by meshWeight2Dict
137         and applys it to the mesh.'''
138         
139         if len(vWeightDict) != len(me.verts):
140                 raise 'Error, Lists Differ in size, do not modify your mesh.verts before updating the weights'
141         
142         act_group = me.activeGroup
143         
144         # Clear the vert group.
145         currentGroupNames= me.getVertGroupNames()
146         for group in currentGroupNames:
147                 if group not in groupNames:
148                         me.removeVertGroup(group) # messes up the active group.
149                 else:
150                         me.removeVertsFromGroup(group)
151         
152         # Add clean unused vert groupNames back
153         currentGroupNames= me.getVertGroupNames()
154         for group in groupNames:
155                 if group not in currentGroupNames:
156                         me.addVertGroup(group)
157         
158         add_ = Blender.Mesh.AssignModes.ADD
159         
160         vertList= [None]
161         for i, v in enumerate(me.verts):
162                 vertList[0]= i
163                 for group, weight in vWeightDict[i].iteritems():
164                         try:
165                                 me.assignVertsToGroup(group, vertList, min(1, max(0, weight)), add_)
166                         except:
167                                 pass # vert group is not used anymore.
168         
169         try:    me.activeGroup = act_group
170         except: pass
171         
172         me.update()
173
174 def dictWeightMerge(dict_weights):
175         '''
176         Takes dict weight list and merges into 1 weight dict item and returns it
177         '''
178         
179         if not dict_weights:
180                 return {}
181         
182         keys= []
183         for weight in dict_weights:
184                 keys.extend([ (k, 0.0) for k in weight.iterkeys() ])
185         
186         new_wdict = dict(keys)
187         
188         len_dict_weights= len(dict_weights)
189         
190         for weight in dict_weights:
191                 for group, value in weight.iteritems():
192                         new_wdict[group] += value/len_dict_weights
193         
194         return new_wdict
195
196
197 FLIPNAMES=[\
198 ('Left','Right'),\
199 ('_L','_R'),\
200 ('-L','-R'),\
201 ('.L','.R'),\
202 ]
203
204 def dictWeightFlipGroups(dict_weight, groupNames, createNewGroups):
205         '''
206         Returns a weight with flip names
207         dict_weight - 1 vert weight.
208         groupNames - because we may need to add new group names.
209         dict_weight - Weather to make new groups where needed.
210         '''
211         
212         def flipName(name):
213                 for n1,n2 in FLIPNAMES:
214                         for nA, nB in ( (n1,n2), (n1.lower(),n2.lower()), (n1.upper(),n2.upper()) ):
215                                 if createNewGroups:
216                                         newName= name.replace(nA,nB)
217                                         if newName!=name:
218                                                 if newName not in groupNames:
219                                                         groupNames.append(newName)
220                                                 return newName
221                                         
222                                         newName= name.replace(nB,nA)
223                                         if newName!=name:
224                                                 if newName not in groupNames:
225                                                         groupNames.append(newName)
226                                                 return newName
227                                 
228                                 else:
229                                         newName= name.replace(nA,nB)
230                                         if newName!=name and newName in groupNames:
231                                                 return newName
232                                         
233                                         newName= name.replace(nB,nA)
234                                         if newName!=name and newName in groupNames:
235                                                 return newName
236                 
237                 return name
238                 
239         if not dict_weight:
240                 return dict_weight, groupNames
241         
242         
243         new_wdict = {}
244         for group, weight in dict_weight.iteritems():
245                 flipname= flipName(group)
246                 new_wdict[flipname]= weight
247         
248         return new_wdict, groupNames
249
250
251 def mesh2linkedFaces(me):
252         '''
253         Splits the mesh into connected parts,
254         these parts are returned as lists of faces.
255         used for seperating cubes from other mesh elements in the 1 mesh
256         '''
257         
258         # Build vert face connectivity
259         vert_faces= [[] for i in xrange(len(me.verts))]
260         for f in me.faces:
261                 for v in f:
262                         vert_faces[v.index].append(f)
263         
264         # sort faces into connectivity groups
265         face_groups= [[f] for f in me.faces]
266         face_mapping = range(len(me.faces)) # map old, new face location
267         
268         # Now clump faces iterativly
269         ok= True
270         while ok:
271                 ok= False
272                 
273                 for i, f in enumerate(me.faces):
274                         mapped_index= face_mapping[f.index]
275                         mapped_group= face_groups[mapped_index]
276                         
277                         for v in f:
278                                 for nxt_f in vert_faces[v.index]:
279                                         if nxt_f != f:
280                                                 nxt_mapped_index= face_mapping[nxt_f.index]
281                                                 
282                                                 # We are not a part of the same group
283                                                 if mapped_index != nxt_mapped_index:
284                                                         
285                                                         ok= True
286                                                         
287                                                         # Assign mapping to this group so they all map to this group
288                                                         for grp_f in face_groups[nxt_mapped_index]:
289                                                                 face_mapping[grp_f.index] = mapped_index
290                                                         
291                                                         # Move faces into this group
292                                                         mapped_group.extend(face_groups[nxt_mapped_index])
293                                                         
294                                                         # remove reference to the list
295                                                         face_groups[nxt_mapped_index]= None 
296                                                 
297                                                 
298         # return all face groups that are not null
299         # this is all the faces that are connected in their own lists.
300         return [fg for fg in face_groups if fg]
301
302
303
304 def getFaceLoopEdges(faces, seams=[]):
305         '''
306         Takes me.faces or a list of faces and returns the edge loops
307         These edge loops are the edges that sit between quads, so they dont touch
308         1 quad, not not connected will make 2 edge loops, both only containing 2 edges.
309         
310         return a list of edge key lists
311         [ [(0,1), (4, 8), (3,8)], ...]
312         
313         optionaly, seams are edge keys that will be removed
314         '''
315         
316         OTHER_INDEX = 2,3,0,1 # opposite face index
317         
318         edges = {}
319         
320         for f in faces:
321                 if len(f) == 4:
322                         edge_keys = f.edge_keys
323                         for i, edkey in enumerate(f.edge_keys):
324                                 try:    edges[edkey].append(edge_keys[OTHER_INDEX[i]])
325                                 except: edges[edkey] =  [ edge_keys[OTHER_INDEX[i]] ]
326         
327         for edkey in seams:
328                 edges[edkey] = []
329         
330         # Collect edge loops here
331         edge_loops = [] 
332         
333         for edkey, ed_adj in edges.iteritems():
334                 if 0 <len(ed_adj) < 3: # 1 or 2
335                         # Seek the first edge
336                         context_loop = [edkey, ed_adj[0]]
337                         edge_loops.append(context_loop)
338                         if len(ed_adj) == 2:
339                                 other_dir = ed_adj[1]
340                         else:
341                                 other_dir = None
342                         
343                         ed_adj[:] = []
344                         
345                         flipped = False
346                         
347                         while 1:
348                                 # from knowing the last 2, look for th next.
349                                 ed_adj = edges[context_loop[-1]]
350                                 if len(ed_adj) != 2:
351                                         
352                                         if other_dir and flipped==False: # the original edge had 2 other edges
353                                                 flipped = True # only flip the list once
354                                                 context_loop.reverse()
355                                                 ed_adj[:] = []
356                                                 context_loop.append(other_dir) # save 1 lookiup
357                                                 
358                                                 ed_adj = edges[context_loop[-1]]
359                                                 if len(ed_adj) != 2:
360                                                         ed_adj[:] = []
361                                                         break
362                                         else:
363                                                 ed_adj[:] = []
364                                                 break
365                                 
366                                 i = ed_adj.index(context_loop[-2])
367                                 context_loop.append( ed_adj[ not  i] )
368                                 
369                                 # Dont look at this again
370                                 ed_adj[:] = []
371
372         
373         return edge_loops
374         
375
376
377 def getMeshFromObject(ob, container_mesh=None, apply_modifiers=True, vgroups=True, scn=None):
378         '''
379         ob - the object that you want to get the mesh from
380         container_mesh - a Blender.Mesh type mesh that is reused to avoid a new datablock per call to getMeshFromObject
381         apply_modifiers - if enabled, subsurf bones etc. will be applied to the returned mesh. disable to get a copy of the mesh.
382         vgroup - For mesh objects only, apply the vgroup to the the copied mesh. (slower)
383         scn - Scene type. avoids getting the current scene each time getMeshFromObject is called.
384         
385         Returns Mesh or None
386         '''
387         
388         if not scn:
389                 scn= Blender.Scene.GetCurrent()
390         if not container_mesh:
391                 mesh = Blender.Mesh.New()       
392         else:
393                 mesh= container_mesh
394                 mesh.verts= None
395         
396         
397         type = ob.getType()
398         dataname = ob.getData(1)
399         tempob= None
400         if apply_modifiers or type != 'Mesh':
401                 try:
402                         mesh.getFromObject(ob)
403                 except:
404                         return None
405         
406         else:
407                 '''
408                 Dont apply modifiers, copy the mesh. 
409                 So we can transform the data. its easiest just to get a copy of the mesh. 
410                 '''
411                 tempob= Blender.Object.New('Mesh')
412                 tempob.shareFrom(ob)
413                 scn.link(tempob)
414                 mesh.getFromObject(tempob)
415                 scn.unlink(tempob)
416         
417         if type == 'Mesh':
418                 if vgroups:
419                         if tempob==None:
420                                 tempob= Blender.Object.New('Mesh')
421                         tempob.link(mesh)
422                         try:
423                                 # Copy the influences if possible.
424                                 groupNames, vWeightDict= meshWeight2Dict(ob.getData(mesh=1))
425                                 dict2MeshWeight(mesh, groupNames, vWeightDict)
426                         except:
427                                 # if the modifier changes the vert count then it messes it up for us.
428                                 pass
429         
430         return mesh
431
432
433 def faceRayIntersect(f, orig, dir):
434         '''
435         Returns face, side
436         Side is the side of a quad we intersect.
437                 side 0 == 0,1,2
438                 side 1 == 0,2,3
439         '''
440         f_v= f.v
441         isect= Blender.Mathutils.Intersect(f_v[0].co, f_v[1].co, f_v[2].co, dir, orig, 1) # 1==clip
442         
443         if isect:
444                 return isect, 0
445         
446         if len(f_v)==4:
447                 isect= Blender.Mathutils.Intersect(f_v[0].co, f_v[2].co, f_v[3].co, dir, orig, 1) # 1==clip
448                 if isect:
449                         return isect, 1
450         return False, 0
451
452
453 def pickMeshRayFace(me, orig, dir):
454         best_dist= 1000000
455         best_isect= best_side= best_face= None
456         for f in me.faces:
457                 isect, side= faceRayIntersect(f, orig, dir)
458                 if isect:
459                         dist= (isect-orig).length
460                         if dist<best_dist:
461                                 best_dist= dist
462                                 best_face= f
463                                 best_side= side
464                                 best_isect= isect
465         
466         return best_face, best_isect, best_side
467
468
469 def pickMeshRayFaceWeight(me, orig, dir):
470         f, isect, side = pickMeshRayFace(me, orig, dir)
471         
472         if f==None:
473                 return None, None, None, None, None
474         
475         f_v= [v.co for v in f]
476         if side==1: # we can leave side 0 without changes.
477                 f_v = f_v[0], f_v[2], f_v[3]
478         
479         l0= (f_v[0]-isect).length
480         l1= (f_v[1]-isect).length
481         l2= (f_v[2]-isect).length
482         
483         w0 = (l1+l2)
484         w1 = (l0+l2)
485         w2 = (l1+l2)
486         
487         totw= w0 + w1 + w2
488         w0=w0/totw
489         w1=w1/totw
490         w2=w2/totw
491         
492         return f, side, w0, w1, w2
493
494
495
496 def pickMeshGroupWeight(me, act_group, orig, dir):
497         f, side, w0, w1, w2= pickMeshRayFaceWeight(me, orig, dir)
498         
499         if f==None:
500                 return None
501                 
502         f_v= f.v
503         if side==0:
504                 f_vi= (f_v[0].index, f_v[1].index, f_v[2].index)
505         else:
506                 f_vi= (f_v[0].index, f_v[2].index, f_v[3].index)
507         
508         vws= [0.0,0.0,0.0]
509         for i in xrange(3):
510                 try:            vws[i]= me.getVertsFromGroup(act_group, 1, [f_vi[i],])[0][1]
511                 except: pass
512         
513         return w0*vws[0] + w1*vws[1]  + w2*vws[2]
514
515 def pickMeshGroupVCol(me, orig, dir):
516         Vector= Blender.Mathutils.Vector
517         f, side, w0, w1, w2= pickMeshRayFaceWeight(me, orig, dir)
518         
519         if f==None:
520                 return None
521         
522         def col2vec(c):
523                 return Vector(c.r, c.g, c.b)
524         
525         if side==0:
526                 idxs= 0,1,2
527         else:
528                 idxs= 0,2,3
529         f_c= f.col
530         f_colvecs= [col2vec(f_c[i]) for i in idxs]
531         return f_colvecs[0]*w0 +  f_colvecs[1]*w1 + f_colvecs[2]*w2
532
533 def edge_face_users(me):
534         ''' 
535         Takes a mesh and returns a list aligned with the meshes edges.
536         Each item is a list of the faces that use the edge
537         would be the equiv for having ed.face_users as a property
538         '''
539         
540         face_edges_dict= dict([(ed.key, (ed.index, [])) for ed in me.edges])
541         for f in me.faces:
542                 fvi= [v.index for v in f]# face vert idx's
543                 for edkey in f.edge_keys:
544                         face_edges_dict[edkey][1].append(f)
545         
546         face_edges= [None] * len(me.edges)
547         for ed_index, ed_faces in face_edges_dict.itervalues():
548                 face_edges[ed_index]= ed_faces
549         
550         return face_edges
551                 
552                 
553 def face_edges(me):
554         '''
555         Returns a list alligned to the meshes faces.
556         each item is a list of lists: that is 
557         face_edges -> face indicies
558         face_edges[i] -> list referencs local faces v indicies 1,2,3 &| 4
559         face_edges[i][j] -> list of faces that this edge uses.
560         crap this is tricky to explain :/
561         '''
562         face_edges= [ [-1] * len(f) for f in me.faces ]
563         
564         face_edges_dict= dict([(ed.key, []) for ed in me.edges])
565         for fidx, f in enumerate(me.faces):
566                 for i, edkey in enumerate(f.edge_keys):
567                         edge_face_users= face_edges_dict[edkey]
568                         edge_face_users.append(f)
569                         face_edges[fidx][i]= edge_face_users
570                         
571         return face_edges
572         
573
574 def facesPlanerIslands(me):
575         DotVecs= Blender.Mathutils.DotVecs
576         
577         def roundvec(v):
578                 return round(v[0], 4), round(v[1], 4), round(v[2], 4)
579         
580         face_props= [(cent, no, roundvec(no), DotVecs(cent, no)) for f in me.faces    for no, cent in ((f.no, f.cent),)]
581         
582         face_edge_users= face_edges(me)
583         islands= []
584         
585         used_faces= [0] * len(me.faces)
586         while True:
587                 new_island= False
588                 for i, used_val in enumerate(used_faces):
589                         if used_val==0:
590                                 island= [i]
591                                 new_island= True
592                                 used_faces[i]= 1
593                                 break
594                 
595                 if not new_island:
596                         break
597                 
598                 island_growing= True
599                 while island_growing:
600                         island_growing= False
601                         for fidx1 in island[:]:
602                                 if used_faces[fidx1]==1:
603                                         used_faces[fidx1]= 2
604                                         face_prop1= face_props[fidx1]
605                                         for ed in face_edge_users[fidx1]:
606                                                 for f2 in ed:
607                                                         fidx2= f2.index
608                                                         if fidx1 != fidx2 and used_faces[fidx2]==0:
609                                                                 island_growing= True
610                                                                 face_prop2= face_props[fidx2]
611                                                                 # normals are the same?
612                                                                 if face_prop1[2]==face_prop2[2]:
613                                                                         if abs(face_prop1[3] - DotVecs(face_prop1[1], face_prop2[0])) < 0.000001:
614                                                                                 used_faces[fidx2]= 1
615                                                                                 island.append(fidx2)
616                 islands.append([me.faces[i] for i in island])
617         return islands
618
619
620
621 def facesUvIslands(me, PREF_IMAGE_DELIMIT=True):
622         DotVecs= Blender.Mathutils.DotVecs
623         def roundvec(v):
624                 return round(v[0], 4), round(v[1], 4)
625         
626         if not me.faceUV:
627                 return [ list(me.faces), ]
628         
629         # make a list of uv dicts
630         face_uvs= [ [roundvec(uv) for uv in f.uv] for f in me.faces]
631         
632         # key - face uv || value - list of face idxs
633         uv_connect_dict= dict([ (uv, [] ) for f_uvs in face_uvs for uv in f_uvs])
634         
635         for i, f_uvs in enumerate(face_uvs):
636                 for uv in f_uvs: # loops through rounded uv values
637                         uv_connect_dict[uv].append(i)
638         islands= []
639         
640         used_faces= [0] * len(me.faces)
641         while True:
642                 new_island= False
643                 for i, used_val in enumerate(used_faces):
644                         if used_val==0:
645                                 island= [i]
646                                 new_island= True
647                                 used_faces[i]= 1
648                                 break
649                 
650                 if not new_island:
651                         break
652                 
653                 island_growing= True
654                 while island_growing:
655                         island_growing= False
656                         for fidx1 in island[:]:
657                                 if used_faces[fidx1]==1:
658                                         used_faces[fidx1]= 2
659                                         for uv in face_uvs[fidx1]:
660                                                 for fidx2 in uv_connect_dict[uv]:
661                                                         if fidx1 != fidx2 and used_faces[fidx2]==0:
662                                                                 if not PREF_IMAGE_DELIMIT or me.faces[fidx1].image==me.faces[fidx2].image:
663                                                                         island_growing= True
664                                                                         used_faces[fidx2]= 1
665                                                                         island.append(fidx2)
666                 
667                 islands.append([me.faces[i] for i in island])
668         return islands
669
670 #def faceUvBounds(me, faces= None):
671         
672
673 def facesUvRotate(me, deg, faces= None, pivot= (0,0)):
674         '''
675         Faces can be None an all faces will be used
676         pivot is just the x/y well rotated about
677         
678         positive deg value for clockwise rotation
679         '''
680         if faces==None: faces= me.faces
681         pivot= Blender.Mathutils.Vector(pivot)
682         
683         rotmat= Blender.Mathutils.RotationMatrix(-deg, 2)
684         
685         for f in faces:
686                 f.uv= [((uv-pivot)*rotmat)+pivot for uv in f.uv]
687
688 def facesUvScale(me, sca, faces= None, pivot= (0,0)):
689         '''
690         Faces can be None an all faces will be used
691         pivot is just the x/y well rotated about
692         sca can be wither an int/float or a vector if you want to
693           scale x/y seperately.
694           a sca or (1.0, 1.0) will do nothing.
695         '''
696         def vecmulti(v1,v2):
697                 '''V2 is unchanged'''
698                 v1[:]= (v1.x*v2.x, v1.y*v2.y)
699                 return v1
700         
701         sca= Blender.Mathutils.Vector(sca)
702         if faces==None: faces= me.faces
703         pivot= Blender.Mathutils.Vector(pivot)
704         
705         for f in faces:
706                 f.uv= [vecmulti(uv-pivot, sca)+pivot for uv in f.uv]
707
708         
709 def facesUvTranslate(me, tra, faces= None, pivot= (0,0)):
710         '''
711         Faces can be None an all faces will be used
712         pivot is just the x/y well rotated about
713         '''
714         if faces==None: faces= me.faces
715         tra= Blender.Mathutils.Vector(tra)
716         
717         for f in faces:
718                 f.uv= [uv+tra for uv in f.uv]
719
720         
721
722 def edgeFaceUserCount(me, faces= None):
723         '''
724         Return an edge aligned list with the count for all the faces that use that edge. -
725         can spesify a subset of the faces, so only those will be counted.
726         '''
727         if faces==None:
728                 faces= me.faces
729                 max_vert= len(me.verts)
730         else:
731                 # find the lighest vert index
732                 pass
733         
734         edge_users= [0] * len(me.edges)
735         
736         edges_idx_dict= dict([(ed.key, ed.index) for ed in me.edges])
737
738         for f in faces:
739                 for edkey in f.edge_keys:
740                         edge_users[edges_idx_dict[edkey]] += 1 
741         
742         return edge_users
743
744
745 #============================================================================#
746 # Takes a face, and a pixel x/y on the image and returns a worldspace x/y/z  #
747 # will return none if the pixel is not inside the faces UV                   #
748 #============================================================================#
749 def getUvPixelLoc(face, pxLoc, img_size = None, uvArea = None):
750         TriangleArea= Blender.Mathutils.TriangleArea
751         Vector= Blender.Mathutils.Vector
752         
753         if not img_size:
754                 w,h = face.image.size
755         else:
756                 w,h= img_size
757         
758         scaled_uvs= [Vector(uv.x*w, uv.y*h) for uv in f.uv]
759         
760         if len(scaled_uvs)==3:
761                 indicies= ((0,1,2),)
762         else:
763                 indicies= ((0,1,2), (0,2,3))
764         
765         for fidxs in indicies:
766                 for i1,i2,i3 in fidxs:
767                         # IS a point inside our triangle?
768                         # UVArea could be cached?
769                         uv_area = TriangleArea(scaled_uvs[i1], scaled_uvs[i2], scaled_uvs[i3])
770                         area0 = TriangleArea(pxLoc, scaled_uvs[i2], scaled_uvs[i3])
771                         area1 = TriangleArea(pxLoc, scaled_uvs[i1],     scaled_uvs[i3])
772                         area2 = TriangleArea(pxLoc, scaled_uvs[i1], scaled_uvs[i2])
773                         if area0 + area1 + area2 > uv_area + 1: # 1 px bleed/error margin.
774                                 pass # if were a quad the other side may contain the pixel so keep looking.
775                         else:
776                                 # We know the point is in the tri
777                                 area0 /= uv_area
778                                 area1 /= uv_area
779                                 area2 /= uv_area
780                                 
781                                 # New location
782                                 return Vector(\
783                                         face.v[i1].co[0]*area0 + face.v[i2].co[0]*area1 + face.v[i3].co[0]*area2,\
784                                         face.v[i1].co[1]*area0 + face.v[i2].co[1]*area1 + face.v[i3].co[1]*area2,\
785                                         face.v[i1].co[2]*area0 + face.v[i2].co[2]*area1 + face.v[i3].co[2]*area2\
786                                 )
787                                 
788         return None
789
790
791 type_tuple= type( (0,) )
792 type_list= type( [] )
793
794
795 # Used for debugging ngon
796 """
797 def draw_loops(loops):
798         
799         me= Blender.Mesh.New()
800         for l in loops:
801                 #~ me= Blender.Mesh.New()
802                 
803                 
804                 i= len(me.verts)
805                 me.verts.extend([v[0] for v in l])
806                 try:
807                         me.verts[0].sel= 1
808                 except:
809                         pass
810                 me.edges.extend([ (j-1, j) for j in xrange(i+1, len(me.verts)) ])
811                 # Close the edge?
812                 me.edges.extend((i, len(me.verts)-1))
813                 
814                 
815                 #~ ob= Blender.Object.New('Mesh')
816                 #~ ob.link(me)
817                 #~ scn= Blender.Scene.GetCurrent()
818                 #~ scn.link(ob)
819                 #~ ob.Layers= scn.Layers
820                 #~ ob.sel= 1
821                 
822                 
823                 
824         # Fill
825         #fill= Blender.Mathutils.PolyFill(loops)
826         #me.faces.extend(fill)
827                 
828         
829         ob= Blender.Object.New('Mesh')
830         ob.link(me)
831         scn= Blender.Scene.GetCurrent()
832         scn.link(ob)
833         ob.Layers= scn.Layers
834         ob.sel= 1
835         Blender.Window.RedrawAll()
836 """
837
838 def ngon(from_data, indices, PREF_FIX_LOOPS= True):
839         '''
840         Takes a polyline of indices (fgon)
841         and returns a list of face indicie lists.
842         Designed to be used for importers that need indices for an fgon to create from existing verts.
843         
844         from_data: either a mesh, or a list/tuple of vectors.
845         indices: a list of indicies to use this list is the ordered closed polyline to fill, and can be a subset of the data given.
846         PREF_FIX_LOOPS: If this is enabled polylines that use loops to make multiple polylines are delt with correctly.
847         '''
848         
849         if not set: # Need sets for this, otherwise do a normal fill.
850                 PREF_FIX_LOOPS= False 
851         
852         Vector= Blender.Mathutils.Vector
853         if not indices:
854                 return []
855         
856         #       return []
857         def rvec(co): return round(co.x, 6), round(co.y, 6), round(co.z, 6)
858         def mlen(co): return abs(co[0])+abs(co[1])+abs(co[2]) # manhatten length of a vector, faster then length
859         
860         def vert_treplet(v, i):
861                 return v, rvec(v), i, mlen(v)
862         
863         def ed_key_mlen(v1, v2):
864                 if v1[3] > v2[3]:
865                         return v2[1], v1[1]
866                 else:
867                         return v1[1], v2[1]
868         
869         
870         if not PREF_FIX_LOOPS:
871                 '''
872                 Normal single concave loop filling
873                 '''
874                 if type(from_data) in (type_tuple, type_list):
875                         verts= [Vector(from_data[i]) for ii, i in enumerate(indices)]
876                 else:
877                         verts= [from_data.verts[i].co for ii, i in enumerate(indices)]
878                 
879                 for i in xrange(len(verts)-1, 0, -1): # same as reversed(xrange(1, len(verts))):
880                         if verts[i][1]==verts[i-1][0]:
881                                 verts.pop(i-1)
882                 
883                 fill= Blender.Geometry.PolyFill([verts])
884                 
885         else:
886                 '''
887                 Seperate this loop into multiple loops be finding edges that are used twice
888                 This is used by lightwave LWO files a lot
889                 '''
890                 
891                 if type(from_data) in (type_tuple, type_list):
892                         verts= [vert_treplet(Vector(from_data[i]), ii) for ii, i in enumerate(indices)]
893                 else:
894                         verts= [vert_treplet(from_data.verts[i].co, ii) for ii, i in enumerate(indices)]
895                         
896                 edges= [(i, i-1) for i in xrange(len(verts))]
897                 if edges:
898                         edges[0]= (0,len(verts)-1)
899                 
900                 if not verts:
901                         return []
902                 
903                 
904                 edges_used= set()
905                 edges_doubles= set()
906                 # We need to check if any edges are used twice location based.
907                 for ed in edges:
908                         edkey= ed_key_mlen(verts[ed[0]], verts[ed[1]])
909                         if edkey in edges_used:
910                                 edges_doubles.add(edkey)
911                         else:
912                                 edges_used.add(edkey)
913                 
914                 # Store a list of unconnected loop segments split by double edges.
915                 # will join later
916                 loop_segments= [] 
917                 
918                 v_prev= verts[0]
919                 context_loop= [v_prev]
920                 loop_segments= [context_loop]
921                 
922                 for v in verts:
923                         if v!=v_prev:
924                                 # Are we crossing an edge we removed?
925                                 if ed_key_mlen(v, v_prev) in edges_doubles:
926                                         context_loop= [v]
927                                         loop_segments.append(context_loop)
928                                 else:
929                                         if context_loop and context_loop[-1][1]==v[1]:
930                                                 #raise "as"
931                                                 pass
932                                         else:
933                                                 context_loop.append(v)
934                                 
935                                 v_prev= v
936                 # Now join loop segments
937                 
938                 def join_seg(s1,s2):
939                         if s2[-1][1]==s1[0][1]: # 
940                                 s1,s2= s2,s1
941                         elif s1[-1][1]==s2[0][1]:
942                                 pass
943                         else:
944                                 return False
945                         
946                         # If were stuill here s1 and s2 are 2 segments in the same polyline
947                         s1.pop() # remove the last vert from s1
948                         s1.extend(s2) # add segment 2 to segment 1
949                         
950                         if s1[0][1]==s1[-1][1]: # remove endpoints double
951                                 s1.pop()
952                         
953                         s2[:]= [] # Empty this segment s2 so we dont use it again.
954                         return True
955                 
956                 joining_segments= True
957                 while joining_segments:
958                         joining_segments= False
959                         segcount= len(loop_segments)
960                         
961                         for j in xrange(segcount-1, -1, -1): #reversed(xrange(segcount)):
962                                 seg_j= loop_segments[j]
963                                 if seg_j:
964                                         for k in xrange(j-1, -1, -1): # reversed(xrange(j)):
965                                                 if not seg_j:
966                                                         break
967                                                 seg_k= loop_segments[k]
968                                                 
969                                                 if seg_k and join_seg(seg_j, seg_k):
970                                                         joining_segments= True
971                 
972                 loop_list= loop_segments
973                 
974                 for verts in loop_list:
975                         while verts and verts[0][1]==verts[-1][1]:
976                                 verts.pop()
977                 
978                 loop_list= [verts for verts in loop_list if len(verts)>2]
979                 # DONE DEALING WITH LOOP FIXING
980                 
981                 
982                 # vert mapping
983                 vert_map= [None]*len(indices)
984                 ii=0
985                 for verts in loop_list:
986                         if len(verts)>2:
987                                 for i, vert in enumerate(verts):
988                                         vert_map[i+ii]= vert[2]
989                                 ii+=len(verts)
990                 
991                 fill= Blender.Geometry.PolyFill([ [v[0] for v in loop] for loop in loop_list ])
992                 #draw_loops(loop_list)
993                 #raise 'done loop'
994                 # map to original indicies
995                 fill= [[vert_map[i] for i in reversed(f)] for f in fill]
996         
997         
998         if not fill:
999                 print 'Warning Cannot scanfill, fallback on a triangle fan.'
1000                 fill= [ [0, i-1, i] for i in xrange(2, len(indices)) ]
1001         else:
1002                 # Use real scanfill.
1003                 # See if its flipped the wrong way.
1004                 flip= None
1005                 for fi in fill:
1006                         if flip != None:
1007                                 break
1008                         for i, vi in enumerate(fi):
1009                                 if vi==0 and fi[i-1]==1:
1010                                         flip= False
1011                                         break
1012                                 elif vi==1 and fi[i-1]==0:
1013                                         flip= True
1014                                         break
1015                 
1016                 if not flip:
1017                         for i, fi in enumerate(fill):
1018                                 fill[i]= tuple([ii for ii in reversed(fi)])
1019                 
1020                 
1021                 
1022         
1023         return fill
1024         
1025
1026
1027 # EG
1028 '''
1029 scn= Scene.GetCurrent()
1030 me = scn.getActiveObject().getData(mesh=1)
1031 ind= [v.index for v in me.verts if v.sel] # Get indices
1032
1033 indices = ngon(me, ind) # fill the ngon.
1034
1035 # Extand the faces to show what the scanfill looked like.
1036 print len(indices)
1037 me.faces.extend([[me.verts[ii] for ii in i] for i in indices])
1038 '''
1039
1040 def meshCalcNormals(me, vertNormals=None):
1041         '''
1042         takes a mesh and returns very high quality normals 1 normal per vertex.
1043         The normals should be correct, indipendant of topology
1044         
1045         vertNormals - a list of vectors at least as long as the number of verts in the mesh
1046         '''
1047         Ang= Blender.Mathutils.AngleBetweenVecs
1048         Vector= Blender.Mathutils.Vector
1049         SMALL_NUM=0.000001
1050         # Weight the edge normals by total angle difference
1051         # EDGE METHOD
1052         
1053         if not vertNormals:
1054                 vertNormals= [ Vector() for v in xrange(len(me.verts)) ]
1055         else:
1056                 for v in vertNormals:
1057                         v.zero()
1058                 
1059         edges={}
1060         for f in me.faces:
1061                 f_v = f.v
1062                 for edkey in f.edge_keys:
1063                         try:    edges[edkey].append(f.no)
1064                         except: edges[edkey]= [f.no]
1065         
1066         # Weight the edge normals by total angle difference
1067         for fnos in edges.itervalues():
1068                 
1069                 len_fnos= len(fnos)
1070                 if len_fnos>1:
1071                         totAngDiff=0
1072                         for j in xrange(len_fnos-1, -1, -1): # same as reversed(xrange(...))
1073                                 for k in xrange(j-1, -1, -1): # same as reversed(xrange(...))
1074                                         #print j,k
1075                                         try:
1076                                                 totAngDiff+= (Ang(fnos[j], fnos[k])) # /180 isnt needed, just to keeop the vert small.
1077                                         except:
1078                                                 pass # Zero length face
1079                         
1080                         # print totAngDiff
1081                         if totAngDiff > SMALL_NUM:
1082                                 '''
1083                                 average_no= Vector()
1084                                 for no in fnos:
1085                                         average_no+=no
1086                                 '''
1087                                 average_no= reduce(lambda a,b: a+b, fnos, Vector())
1088                                 fnos.append(average_no*totAngDiff) # average no * total angle diff
1089                         #else:
1090                         #       fnos[0]
1091                 else:
1092                         fnos.append(fnos[0])
1093         
1094         for ed, v in edges.iteritems():
1095                 vertNormals[ed[0]]+= v[-1]
1096                 vertNormals[ed[1]]+= v[-1]
1097         for i, v in enumerate(me.verts):
1098                 v.no= vertNormals[i]
1099
1100
1101
1102
1103 def pointInsideMesh(ob, pt):
1104         Intersect = Blender.Mathutils.Intersect # 2 less dict lookups.
1105         Vector = Blender.Mathutils.Vector
1106         
1107         def ptInFaceXYBounds(f, pt):
1108                 f_v = f.v
1109                 co= f_v[0].co
1110                 xmax= xmin= co.x
1111                 ymax= ymin= co.y
1112                 
1113                 co= f_v[1].co
1114                 xmax= max(xmax, co.x)
1115                 xmin= min(xmin, co.x)
1116                 ymax= max(ymax, co.y)
1117                 ymin= min(ymin, co.y)
1118                 
1119                 co= f_v[2].co
1120                 xmax= max(xmax, co.x)
1121                 xmin= min(xmin, co.x)
1122                 ymax= max(ymax, co.y)
1123                 ymin= min(ymin, co.y)
1124                 
1125                 if len(f_v)==4: 
1126                         co= f_v[3].co
1127                         xmax= max(xmax, co.x)
1128                         xmin= min(xmin, co.x)
1129                         ymax= max(ymax, co.y)
1130                         ymin= min(ymin, co.y)
1131                 
1132                 # Now we have the bounds, see if the point is in it.
1133                 if\
1134                 pt.x < xmin or\
1135                 pt.y < ymin or\
1136                 pt.x > xmax or\
1137                 pt.y > ymax:
1138                         return False # point is outside face bounds
1139                 else:
1140                         return True # point inside.
1141                 #return xmax, ymax, xmin, ymin
1142         
1143         def faceIntersect(f):
1144                 f_v = f.v
1145                 isect = Intersect(f_v[0].co, f_v[1].co, f_v[2].co, ray, obSpacePt, 1) # Clipped.
1146                 if not isect and len(f) == 4:
1147                         isect = Intersect(f_v[0].co, f_v[2].co, f_v[3].co, ray, obSpacePt, 1) # Clipped.
1148                                 
1149                 if isect and isect.z > obSpacePt.z: # This is so the ray only counts if its above the point. 
1150                         return True
1151                 else:
1152                         return False
1153         
1154         obSpacePt = pt*ob.matrixWorld.copy().invert()
1155         ray = Vector(0,0,-1)
1156         me= ob.getData(mesh=1)
1157         
1158         # Here we find the number on intersecting faces, return true if an odd number (inside), false (outside) if its true.
1159         return len([None for f in me.faces if ptInFaceXYBounds(f, obSpacePt) if faceIntersect(f)]) % 2
1160
1161
1162 # NMesh wrapper
1163 Vector= Blender.Mathutils.Vector
1164 class NMesh(object):
1165         __slots__= 'verts', 'faces', 'edges', 'faceUV', 'materials', 'realmesh'
1166         def __init__(self, mesh):
1167                 '''
1168                 This is an NMesh wrapper that
1169                 mesh is an Mesh as returned by Blender.Mesh.New()
1170                 This class wraps NMesh like access into Mesh
1171                 
1172                 Running NMesh.update() - with this wrapper,
1173                 Will update the realmesh.
1174                 '''
1175                 self.verts= []
1176                 self.faces= []
1177                 self.edges= []
1178                 self.faceUV= False
1179                 self.materials= []
1180                 self.realmesh= mesh
1181         
1182         def addFace(self, nmf):
1183                 self.faces.append(nmf)
1184         
1185         def Face(self, v=[]):
1186                 return NMFace(v)
1187         def Vert(self, x,y,z):
1188                 return NMVert(x,y,z)
1189         
1190         def hasFaceUV(self, flag):
1191                 if flag:
1192                         self.faceUV= True
1193                 else:
1194                         self.faceUV= False
1195         
1196         def addMaterial(self, mat):
1197                 self.materials.append(mat)
1198         
1199         def update(self, recalc_normals=False): # recalc_normals is dummy
1200                 mesh= self.realmesh
1201                 mesh.verts= None # Clears the 
1202                 
1203                 # Add in any verts from faces we may have not added.
1204                 for nmf in self.faces:
1205                         for nmv in nmf.v:
1206                                 if nmv.index==-1:
1207                                         nmv.index= len(self.verts)
1208                                         self.verts.append(nmv)
1209                                         
1210                 
1211                 mesh.verts.extend([nmv.co for nmv in self.verts])
1212                 for i, nmv in enumerate(self.verts):
1213                         nmv.index= i
1214                         mv= mesh.verts[i]
1215                         mv.sel= nmv.sel
1216                 
1217                 good_faces= [nmf for nmf in self.faces if len(nmf.v) in (3,4)]
1218                 #print len(good_faces), 'AAA'
1219                 
1220                 
1221                 #mesh.faces.extend([nmf.v for nmf in self.faces])
1222                 mesh.faces.extend([[mesh.verts[nmv.index] for nmv in nmf.v] for nmf in good_faces])
1223                 if len(mesh.faces):
1224                         if self.faceUV:
1225                                 mesh.faceUV= 1
1226                         
1227                         #for i, nmf in enumerate(self.faces):
1228                         for i, nmf in enumerate(good_faces):
1229                                 mf= mesh.faces[i]
1230                                 if self.faceUV:
1231                                         if len(nmf.uv) == len(mf.v):
1232                                                 mf.uv= [Vector(uv[0], uv[1]) for uv in nmf.uv]
1233                                         if len(nmf.col) == len(mf.v):
1234                                                 for c, i in enumerate(mf.col):
1235                                                         c.r, c.g, c.b= nmf.col[i].r, nmf.col[i].g, nmf.col[i].b
1236                                         if nmf.image:
1237                                                 mf.image= nmf.image
1238                 
1239                 mesh.materials= self.materials[:16]
1240
1241 class NMVert(object):
1242         __slots__= 'co', 'index', 'no', 'sel', 'uvco'
1243         def __init__(self, x,y,z):
1244                 self.co= Vector(x,y,z)
1245                 self.index= None # set on appending.
1246                 self.no= Vector(0,0,1) # dummy
1247                 self.sel= 0
1248                 self.uvco= None
1249 class NMFace(object):
1250         __slots__= 'col', 'flag', 'hide', 'image', 'mat', 'materialIndex', 'mode', 'normal',\
1251         'sel', 'smooth', 'transp', 'uv', 'v'
1252         
1253         def __init__(self, v=[]):
1254                 self.col= []
1255                 self.flag= 0
1256                 self.hide= 0
1257                 self.image= None
1258                 self.mat= 0 # materialIndex needs support too.
1259                 self.mode= 0
1260                 self.normal= Vector(0,0,1)
1261                 self.uv= []
1262                 self.sel= 0
1263                 self.smooth= 0
1264                 self.transp= 0
1265                 self.uv= []
1266                 self.v= [] # a list of nmverts.
1267         
1268 class NMCol(object):
1269         __slots__ = 'r', 'g', 'b', 'a'
1270         def __init__(self):
1271                 self.r= 255
1272                 self.g= 255
1273                 self.b= 255
1274                 self.a= 255
1275
1276
1277 '''
1278
1279 verts_split= [dict() for i in xrange(len(me.verts))]
1280
1281 tot_verts= 0
1282 for f in me.faces:
1283         f_uv= f.uv
1284         for i, v in enumerate(f.v):
1285                 vert_index= v.index # mesh index
1286                 vert_dict= verts_split[vert_index] # get the dict for this vert
1287                 
1288                 uv= f_uv[i]
1289                 # now we have the vert and the face uv well make a unique dict.
1290                 
1291                 vert_key= v.x, v.y, v.x, uv.x, uv.y # ADD IMAGE NAME HETR IF YOU WANT TO SPLIT BY THAT TOO
1292                 value= vert_index, tot_verts # ADD WEIGHT HERE IF YOU NEED.
1293                 try:
1294                         vert_dict[vert_key] # if this is missing it will fail.
1295                 except:
1296                         # this stores a mapping between the split and orig vert indicies
1297                         vert_dict[vert_key]= value 
1298                         tot_verts+= 1
1299
1300 # a flat list of split verts - can add custom weight data here too if you need
1301 split_verts= [None]*tot_verts
1302
1303 for vert_split_dict in verts_split:
1304         for key, value in vert_split_dict.iteritems():
1305                 local_index, split_index= value
1306                 split_verts[split_index]= key
1307
1308 # split_verts - Now you have a list of verts split by their UV.
1309 '''