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