weightpaint_clean, option to clean all vgroups
[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 getEdgeLoopsFromFaces(faces):
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         
311         edges = {}
312         
313         for f in faces:
314                 for i, edkey in enumerate(f.edge_keys):
315                         try:    edges[edkey].append((f, i))
316                         except: edges[edkey] = [(f, i)]
317         
318
319
320 def getMeshFromObject(ob, container_mesh=None, apply_modifiers=True, vgroups=True, scn=None):
321         '''
322         ob - the object that you want to get the mesh from
323         container_mesh - a Blender.Mesh type mesh that is reused to avoid a new datablock per call to getMeshFromObject
324         apply_modifiers - if enabled, subsurf bones etc. will be applied to the returned mesh. disable to get a copy of the mesh.
325         vgroup - For mesh objects only, apply the vgroup to the the copied mesh. (slower)
326         scn - Scene type. avoids getting the current scene each time getMeshFromObject is called.
327         
328         Returns Mesh or None
329         '''
330         
331         if not scn:
332                 scn= Blender.Scene.GetCurrent()
333         if not container_mesh:
334                 mesh = Blender.Mesh.New()       
335         else:
336                 mesh= container_mesh
337                 mesh.verts= None
338         
339         
340         type = ob.getType()
341         dataname = ob.getData(1)
342         tempob= None
343         if apply_modifiers or type != 'Mesh':
344                 try:
345                         mesh.getFromObject(ob)
346                 except:
347                         return None
348         
349         else:
350                 '''
351                 Dont apply modifiers, copy the mesh. 
352                 So we can transform the data. its easiest just to get a copy of the mesh. 
353                 '''
354                 tempob= Blender.Object.New('Mesh')
355                 tempob.shareFrom(ob)
356                 scn.link(tempob)
357                 mesh.getFromObject(tempob)
358                 scn.unlink(tempob)
359         
360         if type == 'Mesh':
361                 if vgroups:
362                         if tempob==None:
363                                 tempob= Blender.Object.New('Mesh')
364                         tempob.link(mesh)
365                         try:
366                                 # Copy the influences if possible.
367                                 groupNames, vWeightDict= meshWeight2Dict(ob.getData(mesh=1))
368                                 dict2MeshWeight(mesh, groupNames, vWeightDict)
369                         except:
370                                 # if the modifier changes the vert count then it messes it up for us.
371                                 pass
372         
373         return mesh
374
375
376 def faceRayIntersect(f, orig, dir):
377         '''
378         Returns face, side
379         Side is the side of a quad we intersect.
380                 side 0 == 0,1,2
381                 side 1 == 0,2,3
382         '''
383         f_v= f.v
384         isect= Blender.Mathutils.Intersect(f_v[0].co, f_v[1].co, f_v[2].co, dir, orig, 1) # 1==clip
385         
386         if isect:
387                 return isect, 0
388         
389         if len(f_v)==4:
390                 isect= Blender.Mathutils.Intersect(f_v[0].co, f_v[2].co, f_v[3].co, dir, orig, 1) # 1==clip
391                 if isect:
392                         return isect, 1
393         return False, 0
394
395
396 def pickMeshRayFace(me, orig, dir):
397         best_dist= 1000000
398         best_isect= best_side= best_face= None
399         for f in me.faces:
400                 isect, side= faceRayIntersect(f, orig, dir)
401                 if isect:
402                         dist= (isect-orig).length
403                         if dist<best_dist:
404                                 best_dist= dist
405                                 best_face= f
406                                 best_side= side
407                                 best_isect= isect
408         
409         return best_face, best_isect, best_side
410
411
412 def pickMeshRayFaceWeight(me, orig, dir):
413         f, isect, side = pickMeshRayFace(me, orig, dir)
414         
415         if f==None:
416                 return None, None, None, None, None
417         
418         f_v= [v.co for v in f]
419         if side==1: # we can leave side 0 without changes.
420                 f_v = f_v[0], f_v[2], f_v[3]
421         
422         l0= (f_v[0]-isect).length
423         l1= (f_v[1]-isect).length
424         l2= (f_v[2]-isect).length
425         
426         w0 = (l1+l2)
427         w1 = (l0+l2)
428         w2 = (l1+l2)
429         
430         totw= w0 + w1 + w2
431         w0=w0/totw
432         w1=w1/totw
433         w2=w2/totw
434         
435         return f, side, w0, w1, w2
436
437
438
439 def pickMeshGroupWeight(me, act_group, orig, dir):
440         f, side, w0, w1, w2= pickMeshRayFaceWeight(me, orig, dir)
441         
442         if f==None:
443                 return None
444                 
445         f_v= f.v
446         if side==0:
447                 f_vi= (f_v[0].index, f_v[1].index, f_v[2].index)
448         else:
449                 f_vi= (f_v[0].index, f_v[2].index, f_v[3].index)
450         
451         vws= [0.0,0.0,0.0]
452         for i in xrange(3):
453                 try:            vws[i]= me.getVertsFromGroup(act_group, 1, [f_vi[i],])[0][1]
454                 except: pass
455         
456         return w0*vws[0] + w1*vws[1]  + w2*vws[2]
457
458 def pickMeshGroupVCol(me, orig, dir):
459         Vector= Blender.Mathutils.Vector
460         f, side, w0, w1, w2= pickMeshRayFaceWeight(me, orig, dir)
461         
462         if f==None:
463                 return None
464         
465         def col2vec(c):
466                 return Vector(c.r, c.g, c.b)
467         
468         if side==0:
469                 idxs= 0,1,2
470         else:
471                 idxs= 0,2,3
472         f_c= f.col
473         f_colvecs= [col2vec(f_c[i]) for i in idxs]
474         return f_colvecs[0]*w0 +  f_colvecs[1]*w1 + f_colvecs[2]*w2
475
476 def edge_face_users(me):
477         ''' 
478         Takes a mesh and returns a list aligned with the meshes edges.
479         Each item is a list of the faces that use the edge
480         would be the equiv for having ed.face_users as a property
481         '''
482         
483         face_edges_dict= dict([(ed.key, (ed.index, [])) for ed in me.edges])
484         for f in me.faces:
485                 fvi= [v.index for v in f]# face vert idx's
486                 for edkey in f.edge_keys:
487                         face_edges_dict[edkey][1].append(f)
488         
489         face_edges= [None] * len(me.edges)
490         for ed_index, ed_faces in face_edges_dict.itervalues():
491                 face_edges[ed_index]= ed_faces
492         
493         return face_edges
494                 
495                 
496 def face_edges(me):
497         '''
498         Returns a list alligned to the meshes faces.
499         each item is a list of lists: that is 
500         face_edges -> face indicies
501         face_edges[i] -> list referencs local faces v indicies 1,2,3 &| 4
502         face_edges[i][j] -> list of faces that this edge uses.
503         crap this is tricky to explain :/
504         '''
505         face_edges= [ [-1] * len(f) for f in me.faces ]
506         
507         face_edges_dict= dict([(ed.key, []) for ed in me.edges])
508         for fidx, f in enumerate(me.faces):
509                 for i, edkey in enumerate(f.edge_keys):
510                         edge_face_users= face_edges_dict[edkey]
511                         edge_face_users.append(f)
512                         face_edges[fidx][i]= edge_face_users
513                         
514         return face_edges
515         
516
517 def facesPlanerIslands(me):
518         DotVecs= Blender.Mathutils.DotVecs
519         
520         def roundvec(v):
521                 return round(v[0], 4), round(v[1], 4), round(v[2], 4)
522         
523         face_props= [(cent, no, roundvec(no), DotVecs(cent, no)) for f in me.faces    for no, cent in ((f.no, f.cent),)]
524         
525         face_edge_users= face_edges(me)
526         islands= []
527         
528         used_faces= [0] * len(me.faces)
529         while True:
530                 new_island= False
531                 for i, used_val in enumerate(used_faces):
532                         if used_val==0:
533                                 island= [i]
534                                 new_island= True
535                                 used_faces[i]= 1
536                                 break
537                 
538                 if not new_island:
539                         break
540                 
541                 island_growing= True
542                 while island_growing:
543                         island_growing= False
544                         for fidx1 in island[:]:
545                                 if used_faces[fidx1]==1:
546                                         used_faces[fidx1]= 2
547                                         face_prop1= face_props[fidx1]
548                                         for ed in face_edge_users[fidx1]:
549                                                 for f2 in ed:
550                                                         fidx2= f2.index
551                                                         if fidx1 != fidx2 and used_faces[fidx2]==0:
552                                                                 island_growing= True
553                                                                 face_prop2= face_props[fidx2]
554                                                                 # normals are the same?
555                                                                 if face_prop1[2]==face_prop2[2]:
556                                                                         if abs(face_prop1[3] - DotVecs(face_prop1[1], face_prop2[0])) < 0.000001:
557                                                                                 used_faces[fidx2]= 1
558                                                                                 island.append(fidx2)
559                 islands.append([me.faces[i] for i in island])
560         return islands
561
562
563
564 def facesUvIslands(me, PREF_IMAGE_DELIMIT=True):
565         DotVecs= Blender.Mathutils.DotVecs
566         def roundvec(v):
567                 return round(v[0], 4), round(v[1], 4)
568         
569         if not me.faceUV:
570                 return [ list(me.faces), ]
571         
572         # make a list of uv dicts
573         face_uvs= [ [roundvec(uv) for uv in f.uv] for f in me.faces]
574         
575         # key - face uv || value - list of face idxs
576         uv_connect_dict= dict([ (uv, [] ) for f_uvs in face_uvs for uv in f_uvs])
577         
578         for i, f_uvs in enumerate(face_uvs):
579                 for uv in f_uvs: # loops through rounded uv values
580                         uv_connect_dict[uv].append(i)
581         islands= []
582         
583         used_faces= [0] * len(me.faces)
584         while True:
585                 new_island= False
586                 for i, used_val in enumerate(used_faces):
587                         if used_val==0:
588                                 island= [i]
589                                 new_island= True
590                                 used_faces[i]= 1
591                                 break
592                 
593                 if not new_island:
594                         break
595                 
596                 island_growing= True
597                 while island_growing:
598                         island_growing= False
599                         for fidx1 in island[:]:
600                                 if used_faces[fidx1]==1:
601                                         used_faces[fidx1]= 2
602                                         for uv in face_uvs[fidx1]:
603                                                 for fidx2 in uv_connect_dict[uv]:
604                                                         if fidx1 != fidx2 and used_faces[fidx2]==0:
605                                                                 if not PREF_IMAGE_DELIMIT or me.faces[fidx1].image==me.faces[fidx2].image:
606                                                                         island_growing= True
607                                                                         used_faces[fidx2]= 1
608                                                                         island.append(fidx2)
609                 
610                 islands.append([me.faces[i] for i in island])
611         return islands
612
613 #def faceUvBounds(me, faces= None):
614         
615
616 def facesUvRotate(me, deg, faces= None, pivot= (0,0)):
617         '''
618         Faces can be None an all faces will be used
619         pivot is just the x/y well rotated about
620         
621         positive deg value for clockwise rotation
622         '''
623         if faces==None: faces= me.faces
624         pivot= Blender.Mathutils.Vector(pivot)
625         
626         rotmat= Blender.Mathutils.RotationMatrix(-deg, 2)
627         
628         for f in faces:
629                 f.uv= [((uv-pivot)*rotmat)+pivot for uv in f.uv]
630
631 def facesUvScale(me, sca, faces= None, pivot= (0,0)):
632         '''
633         Faces can be None an all faces will be used
634         pivot is just the x/y well rotated about
635         sca can be wither an int/float or a vector if you want to
636           scale x/y seperately.
637           a sca or (1.0, 1.0) will do nothing.
638         '''
639         def vecmulti(v1,v2):
640                 '''V2 is unchanged'''
641                 v1[:]= (v1.x*v2.x, v1.y*v2.y)
642                 return v1
643         
644         sca= Blender.Mathutils.Vector(sca)
645         if faces==None: faces= me.faces
646         pivot= Blender.Mathutils.Vector(pivot)
647         
648         for f in faces:
649                 f.uv= [vecmulti(uv-pivot, sca)+pivot for uv in f.uv]
650
651         
652 def facesUvTranslate(me, tra, faces= None, pivot= (0,0)):
653         '''
654         Faces can be None an all faces will be used
655         pivot is just the x/y well rotated about
656         '''
657         if faces==None: faces= me.faces
658         tra= Blender.Mathutils.Vector(tra)
659         
660         for f in faces:
661                 f.uv= [uv+tra for uv in f.uv]
662
663         
664
665 def edgeFaceUserCount(me, faces= None):
666         '''
667         Return an edge aligned list with the count for all the faces that use that edge. -
668         can spesify a subset of the faces, so only those will be counted.
669         '''
670         if faces==None:
671                 faces= me.faces
672                 max_vert= len(me.verts)
673         else:
674                 # find the lighest vert index
675                 pass
676         
677         edge_users= [0] * len(me.edges)
678         
679         edges_idx_dict= dict([(ed.key, ed.index) for ed in me.edges])
680
681         for f in faces:
682                 for edkey in f.edge_keys:
683                         edge_users[edges_idx_dict[edkey]] += 1 
684         
685         return edge_users
686
687
688 #============================================================================#
689 # Takes a face, and a pixel x/y on the image and returns a worldspace x/y/z  #
690 # will return none if the pixel is not inside the faces UV                   #
691 #============================================================================#
692 def getUvPixelLoc(face, pxLoc, img_size = None, uvArea = None):
693         TriangleArea= Blender.Mathutils.TriangleArea
694         Vector= Blender.Mathutils.Vector
695         
696         if not img_size:
697                 w,h = face.image.size
698         else:
699                 w,h= img_size
700         
701         scaled_uvs= [Vector(uv.x*w, uv.y*h) for uv in f.uv]
702         
703         if len(scaled_uvs)==3:
704                 indicies= ((0,1,2),)
705         else:
706                 indicies= ((0,1,2), (0,2,3))
707         
708         for fidxs in indicies:
709                 for i1,i2,i3 in fidxs:
710                         # IS a point inside our triangle?
711                         # UVArea could be cached?
712                         uv_area = TriangleArea(scaled_uvs[i1], scaled_uvs[i2], scaled_uvs[i3])
713                         area0 = TriangleArea(pxLoc, scaled_uvs[i2], scaled_uvs[i3])
714                         area1 = TriangleArea(pxLoc, scaled_uvs[i1],     scaled_uvs[i3])
715                         area2 = TriangleArea(pxLoc, scaled_uvs[i1], scaled_uvs[i2])
716                         if area0 + area1 + area2 > uv_area + 1: # 1 px bleed/error margin.
717                                 pass # if were a quad the other side may contain the pixel so keep looking.
718                         else:
719                                 # We know the point is in the tri
720                                 area0 /= uv_area
721                                 area1 /= uv_area
722                                 area2 /= uv_area
723                                 
724                                 # New location
725                                 return Vector(\
726                                         face.v[i1].co[0]*area0 + face.v[i2].co[0]*area1 + face.v[i3].co[0]*area2,\
727                                         face.v[i1].co[1]*area0 + face.v[i2].co[1]*area1 + face.v[i3].co[1]*area2,\
728                                         face.v[i1].co[2]*area0 + face.v[i2].co[2]*area1 + face.v[i3].co[2]*area2\
729                                 )
730                                 
731         return None
732
733
734 type_tuple= type( (0,) )
735 type_list= type( [] )
736
737
738 # Used for debugging ngon
739 """
740 def draw_loops(loops):
741         
742         me= Blender.Mesh.New()
743         for l in loops:
744                 #~ me= Blender.Mesh.New()
745                 
746                 
747                 i= len(me.verts)
748                 me.verts.extend([v[0] for v in l])
749                 try:
750                         me.verts[0].sel= 1
751                 except:
752                         pass
753                 me.edges.extend([ (j-1, j) for j in xrange(i+1, len(me.verts)) ])
754                 # Close the edge?
755                 me.edges.extend((i, len(me.verts)-1))
756                 
757                 
758                 #~ ob= Blender.Object.New('Mesh')
759                 #~ ob.link(me)
760                 #~ scn= Blender.Scene.GetCurrent()
761                 #~ scn.link(ob)
762                 #~ ob.Layers= scn.Layers
763                 #~ ob.sel= 1
764                 
765                 
766                 
767         # Fill
768         #fill= Blender.Mathutils.PolyFill(loops)
769         #me.faces.extend(fill)
770                 
771         
772         ob= Blender.Object.New('Mesh')
773         ob.link(me)
774         scn= Blender.Scene.GetCurrent()
775         scn.link(ob)
776         ob.Layers= scn.Layers
777         ob.sel= 1
778         Blender.Window.RedrawAll()
779 """
780
781 def ngon(from_data, indices, PREF_FIX_LOOPS= True):
782         '''
783         Takes a polyline of indices (fgon)
784         and returns a list of face indicie lists.
785         Designed to be used for importers that need indices for an fgon to create from existing verts.
786         
787         from_data: either a mesh, or a list/tuple of vectors.
788         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.
789         PREF_FIX_LOOPS: If this is enabled polylines that use loops to make multiple polylines are delt with correctly.
790         '''
791         
792         if not set: # Need sets for this, otherwise do a normal fill.
793                 PREF_FIX_LOOPS= False 
794         
795         Vector= Blender.Mathutils.Vector
796         if not indices:
797                 return []
798         
799         #       return []
800         def rvec(co): return round(co.x, 6), round(co.y, 6), round(co.z, 6)
801         def mlen(co): return abs(co[0])+abs(co[1])+abs(co[2]) # manhatten length of a vector, faster then length
802         
803         def vert_treplet(v, i):
804                 return v, rvec(v), i, mlen(v)
805         
806         def ed_key_mlen(v1, v2):
807                 if v1[3] > v2[3]:
808                         return v2[1], v1[1]
809                 else:
810                         return v1[1], v2[1]
811         
812         
813         if not PREF_FIX_LOOPS:
814                 '''
815                 Normal single concave loop filling
816                 '''
817                 if type(from_data) in (type_tuple, type_list):
818                         verts= [Vector(from_data[i]) for ii, i in enumerate(indices)]
819                 else:
820                         verts= [from_data.verts[i].co for ii, i in enumerate(indices)]
821                 
822                 for i in xrange(len(verts)-1, 0, -1): # same as reversed(xrange(1, len(verts))):
823                         if verts[i][1]==verts[i-1][0]:
824                                 verts.pop(i-1)
825                 
826                 fill= Blender.Geometry.PolyFill([verts])
827                 
828         else:
829                 '''
830                 Seperate this loop into multiple loops be finding edges that are used twice
831                 This is used by lightwave LWO files a lot
832                 '''
833                 
834                 if type(from_data) in (type_tuple, type_list):
835                         verts= [vert_treplet(Vector(from_data[i]), ii) for ii, i in enumerate(indices)]
836                 else:
837                         verts= [vert_treplet(from_data.verts[i].co, ii) for ii, i in enumerate(indices)]
838                         
839                 edges= [(i, i-1) for i in xrange(len(verts))]
840                 if edges:
841                         edges[0]= (0,len(verts)-1)
842                 
843                 if not verts:
844                         return []
845                 
846                 
847                 edges_used= set()
848                 edges_doubles= set()
849                 # We need to check if any edges are used twice location based.
850                 for ed in edges:
851                         edkey= ed_key_mlen(verts[ed[0]], verts[ed[1]])
852                         if edkey in edges_used:
853                                 edges_doubles.add(edkey)
854                         else:
855                                 edges_used.add(edkey)
856                 
857                 # Store a list of unconnected loop segments split by double edges.
858                 # will join later
859                 loop_segments= [] 
860                 
861                 v_prev= verts[0]
862                 context_loop= [v_prev]
863                 loop_segments= [context_loop]
864                 
865                 for v in verts:
866                         if v!=v_prev:
867                                 # Are we crossing an edge we removed?
868                                 if ed_key_mlen(v, v_prev) in edges_doubles:
869                                         context_loop= [v]
870                                         loop_segments.append(context_loop)
871                                 else:
872                                         if context_loop and context_loop[-1][1]==v[1]:
873                                                 #raise "as"
874                                                 pass
875                                         else:
876                                                 context_loop.append(v)
877                                 
878                                 v_prev= v
879                 # Now join loop segments
880                 
881                 def join_seg(s1,s2):
882                         if s2[-1][1]==s1[0][1]: # 
883                                 s1,s2= s2,s1
884                         elif s1[-1][1]==s2[0][1]:
885                                 pass
886                         else:
887                                 return False
888                         
889                         # If were stuill here s1 and s2 are 2 segments in the same polyline
890                         s1.pop() # remove the last vert from s1
891                         s1.extend(s2) # add segment 2 to segment 1
892                         
893                         if s1[0][1]==s1[-1][1]: # remove endpoints double
894                                 s1.pop()
895                         
896                         s2[:]= [] # Empty this segment s2 so we dont use it again.
897                         return True
898                 
899                 joining_segments= True
900                 while joining_segments:
901                         joining_segments= False
902                         segcount= len(loop_segments)
903                         
904                         for j in xrange(segcount-1, -1, -1): #reversed(xrange(segcount)):
905                                 seg_j= loop_segments[j]
906                                 if seg_j:
907                                         for k in xrange(j-1, -1, -1): # reversed(xrange(j)):
908                                                 if not seg_j:
909                                                         break
910                                                 seg_k= loop_segments[k]
911                                                 
912                                                 if seg_k and join_seg(seg_j, seg_k):
913                                                         joining_segments= True
914                 
915                 loop_list= loop_segments
916                 
917                 for verts in loop_list:
918                         while verts and verts[0][1]==verts[-1][1]:
919                                 verts.pop()
920                 
921                 loop_list= [verts for verts in loop_list if len(verts)>2]
922                 # DONE DEALING WITH LOOP FIXING
923                 
924                 
925                 # vert mapping
926                 vert_map= [None]*len(indices)
927                 ii=0
928                 for verts in loop_list:
929                         if len(verts)>2:
930                                 for i, vert in enumerate(verts):
931                                         vert_map[i+ii]= vert[2]
932                                 ii+=len(verts)
933                 
934                 fill= Blender.Geometry.PolyFill([ [v[0] for v in loop] for loop in loop_list ])
935                 #draw_loops(loop_list)
936                 #raise 'done loop'
937                 # map to original indicies
938                 fill= [[vert_map[i] for i in reversed(f)] for f in fill]
939         
940         
941         if not fill:
942                 print 'Warning Cannot scanfill, fallback on a triangle fan.'
943                 fill= [ [0, i-1, i] for i in xrange(2, len(indices)) ]
944         else:
945                 # Use real scanfill.
946                 # See if its flipped the wrong way.
947                 flip= None
948                 for fi in fill:
949                         if flip != None:
950                                 break
951                         for i, vi in enumerate(fi):
952                                 if vi==0 and fi[i-1]==1:
953                                         flip= False
954                                         break
955                                 elif vi==1 and fi[i-1]==0:
956                                         flip= True
957                                         break
958                 
959                 if not flip:
960                         for i, fi in enumerate(fill):
961                                 fill[i]= tuple([ii for ii in reversed(fi)])
962                 
963                 
964                 
965         
966         return fill
967         
968
969
970 # EG
971 '''
972 scn= Scene.GetCurrent()
973 me = scn.getActiveObject().getData(mesh=1)
974 ind= [v.index for v in me.verts if v.sel] # Get indices
975
976 indices = ngon(me, ind) # fill the ngon.
977
978 # Extand the faces to show what the scanfill looked like.
979 print len(indices)
980 me.faces.extend([[me.verts[ii] for ii in i] for i in indices])
981 '''
982
983 def meshCalcNormals(me, vertNormals=None):
984         '''
985         takes a mesh and returns very high quality normals 1 normal per vertex.
986         The normals should be correct, indipendant of topology
987         
988         vertNormals - a list of vectors at least as long as the number of verts in the mesh
989         '''
990         Ang= Blender.Mathutils.AngleBetweenVecs
991         Vector= Blender.Mathutils.Vector
992         SMALL_NUM=0.000001
993         # Weight the edge normals by total angle difference
994         # EDGE METHOD
995         
996         if not vertNormals:
997                 vertNormals= [ Vector() for v in xrange(len(me.verts)) ]
998         else:
999                 for v in vertNormals:
1000                         v.zero()
1001                 
1002         edges={}
1003         for f in me.faces:
1004                 f_v = f.v
1005                 for edkey in f.edge_keys:
1006                         try:    edges[edkey].append(f.no)
1007                         except: edges[edkey]= [f.no]
1008         
1009         # Weight the edge normals by total angle difference
1010         for fnos in edges.itervalues():
1011                 
1012                 len_fnos= len(fnos)
1013                 if len_fnos>1:
1014                         totAngDiff=0
1015                         for j in xrange(len_fnos-1, -1, -1): # same as reversed(xrange(...))
1016                                 for k in xrange(j-1, -1, -1): # same as reversed(xrange(...))
1017                                         #print j,k
1018                                         try:
1019                                                 totAngDiff+= (Ang(fnos[j], fnos[k])) # /180 isnt needed, just to keeop the vert small.
1020                                         except:
1021                                                 pass # Zero length face
1022                         
1023                         # print totAngDiff
1024                         if totAngDiff > SMALL_NUM:
1025                                 '''
1026                                 average_no= Vector()
1027                                 for no in fnos:
1028                                         average_no+=no
1029                                 '''
1030                                 average_no= reduce(lambda a,b: a+b, fnos, Vector())
1031                                 fnos.append(average_no*totAngDiff) # average no * total angle diff
1032                         #else:
1033                         #       fnos[0]
1034                 else:
1035                         fnos.append(fnos[0])
1036         
1037         for ed, v in edges.iteritems():
1038                 vertNormals[ed[0]]+= v[-1]
1039                 vertNormals[ed[1]]+= v[-1]
1040         for i, v in enumerate(me.verts):
1041                 v.no= vertNormals[i]
1042
1043
1044
1045
1046 def pointInsideMesh(ob, pt):
1047         Intersect = Blender.Mathutils.Intersect # 2 less dict lookups.
1048         Vector = Blender.Mathutils.Vector
1049         
1050         def ptInFaceXYBounds(f, pt):
1051                 f_v = f.v
1052                 co= f_v[0].co
1053                 xmax= xmin= co.x
1054                 ymax= ymin= co.y
1055                 
1056                 co= f_v[1].co
1057                 xmax= max(xmax, co.x)
1058                 xmin= min(xmin, co.x)
1059                 ymax= max(ymax, co.y)
1060                 ymin= min(ymin, co.y)
1061                 
1062                 co= f_v[2].co
1063                 xmax= max(xmax, co.x)
1064                 xmin= min(xmin, co.x)
1065                 ymax= max(ymax, co.y)
1066                 ymin= min(ymin, co.y)
1067                 
1068                 if len(f_v)==4: 
1069                         co= f_v[3].co
1070                         xmax= max(xmax, co.x)
1071                         xmin= min(xmin, co.x)
1072                         ymax= max(ymax, co.y)
1073                         ymin= min(ymin, co.y)
1074                 
1075                 # Now we have the bounds, see if the point is in it.
1076                 if\
1077                 pt.x < xmin or\
1078                 pt.y < ymin or\
1079                 pt.x > xmax or\
1080                 pt.y > ymax:
1081                         return False # point is outside face bounds
1082                 else:
1083                         return True # point inside.
1084                 #return xmax, ymax, xmin, ymin
1085         
1086         def faceIntersect(f):
1087                 f_v = f.v
1088                 isect = Intersect(f_v[0].co, f_v[1].co, f_v[2].co, ray, obSpacePt, 1) # Clipped.
1089                 if not isect and len(f) == 4:
1090                         isect = Intersect(f_v[0].co, f_v[2].co, f_v[3].co, ray, obSpacePt, 1) # Clipped.
1091                                 
1092                 if isect and isect.z > obSpacePt.z: # This is so the ray only counts if its above the point. 
1093                         return True
1094                 else:
1095                         return False
1096         
1097         obSpacePt = pt*ob.matrixWorld.copy().invert()
1098         ray = Vector(0,0,-1)
1099         me= ob.getData(mesh=1)
1100         
1101         # Here we find the number on intersecting faces, return true if an odd number (inside), false (outside) if its true.
1102         return len([None for f in me.faces if ptInFaceXYBounds(f, obSpacePt) if faceIntersect(f)]) % 2
1103
1104
1105 # NMesh wrapper
1106 Vector= Blender.Mathutils.Vector
1107 class NMesh(object):
1108         __slots__= 'verts', 'faces', 'edges', 'faceUV', 'materials', 'realmesh'
1109         def __init__(self, mesh):
1110                 '''
1111                 This is an NMesh wrapper that
1112                 mesh is an Mesh as returned by Blender.Mesh.New()
1113                 This class wraps NMesh like access into Mesh
1114                 
1115                 Running NMesh.update() - with this wrapper,
1116                 Will update the realmesh.
1117                 '''
1118                 self.verts= []
1119                 self.faces= []
1120                 self.edges= []
1121                 self.faceUV= False
1122                 self.materials= []
1123                 self.realmesh= mesh
1124         
1125         def addFace(self, nmf):
1126                 self.faces.append(nmf)
1127         
1128         def Face(self, v=[]):
1129                 return NMFace(v)
1130         def Vert(self, x,y,z):
1131                 return NMVert(x,y,z)
1132         
1133         def hasFaceUV(self, flag):
1134                 if flag:
1135                         self.faceUV= True
1136                 else:
1137                         self.faceUV= False
1138         
1139         def addMaterial(self, mat):
1140                 self.materials.append(mat)
1141         
1142         def update(self, recalc_normals=False): # recalc_normals is dummy
1143                 mesh= self.realmesh
1144                 mesh.verts= None # Clears the 
1145                 
1146                 # Add in any verts from faces we may have not added.
1147                 for nmf in self.faces:
1148                         for nmv in nmf.v:
1149                                 if nmv.index==-1:
1150                                         nmv.index= len(self.verts)
1151                                         self.verts.append(nmv)
1152                                         
1153                 
1154                 mesh.verts.extend([nmv.co for nmv in self.verts])
1155                 for i, nmv in enumerate(self.verts):
1156                         nmv.index= i
1157                         mv= mesh.verts[i]
1158                         mv.sel= nmv.sel
1159                 
1160                 good_faces= [nmf for nmf in self.faces if len(nmf.v) in (3,4)]
1161                 #print len(good_faces), 'AAA'
1162                 
1163                 
1164                 #mesh.faces.extend([nmf.v for nmf in self.faces])
1165                 mesh.faces.extend([[mesh.verts[nmv.index] for nmv in nmf.v] for nmf in good_faces])
1166                 if len(mesh.faces):
1167                         if self.faceUV:
1168                                 mesh.faceUV= 1
1169                         
1170                         #for i, nmf in enumerate(self.faces):
1171                         for i, nmf in enumerate(good_faces):
1172                                 mf= mesh.faces[i]
1173                                 if self.faceUV:
1174                                         if len(nmf.uv) == len(mf.v):
1175                                                 mf.uv= [Vector(uv[0], uv[1]) for uv in nmf.uv]
1176                                         if len(nmf.col) == len(mf.v):
1177                                                 for c, i in enumerate(mf.col):
1178                                                         c.r, c.g, c.b= nmf.col[i].r, nmf.col[i].g, nmf.col[i].b
1179                                         if nmf.image:
1180                                                 mf.image= nmf.image
1181                 
1182                 mesh.materials= self.materials[:16]
1183
1184 class NMVert(object):
1185         __slots__= 'co', 'index', 'no', 'sel', 'uvco'
1186         def __init__(self, x,y,z):
1187                 self.co= Vector(x,y,z)
1188                 self.index= None # set on appending.
1189                 self.no= Vector(0,0,1) # dummy
1190                 self.sel= 0
1191                 self.uvco= None
1192 class NMFace(object):
1193         __slots__= 'col', 'flag', 'hide', 'image', 'mat', 'materialIndex', 'mode', 'normal',\
1194         'sel', 'smooth', 'transp', 'uv', 'v'
1195         
1196         def __init__(self, v=[]):
1197                 self.col= []
1198                 self.flag= 0
1199                 self.hide= 0
1200                 self.image= None
1201                 self.mat= 0 # materialIndex needs support too.
1202                 self.mode= 0
1203                 self.normal= Vector(0,0,1)
1204                 self.uv= []
1205                 self.sel= 0
1206                 self.smooth= 0
1207                 self.transp= 0
1208                 self.uv= []
1209                 self.v= [] # a list of nmverts.
1210         
1211 class NMCol(object):
1212         __slots__ = 'r', 'g', 'b', 'a'
1213         def __init__(self):
1214                 self.r= 255
1215                 self.g= 255
1216                 self.b= 255
1217                 self.a= 255
1218
1219
1220 '''
1221
1222 verts_split= [dict() for i in xrange(len(me.verts))]
1223
1224 tot_verts= 0
1225 for f in me.faces:
1226         f_uv= f.uv
1227         for i, v in enumerate(f.v):
1228                 vert_index= v.index # mesh index
1229                 vert_dict= verts_split[vert_index] # get the dict for this vert
1230                 
1231                 uv= f_uv[i]
1232                 # now we have the vert and the face uv well make a unique dict.
1233                 
1234                 vert_key= v.x, v.y, v.x, uv.x, uv.y # ADD IMAGE NAME HETR IF YOU WANT TO SPLIT BY THAT TOO
1235                 value= vert_index, tot_verts # ADD WEIGHT HERE IF YOU NEED.
1236                 try:
1237                         vert_dict[vert_key] # if this is missing it will fail.
1238                 except:
1239                         # this stores a mapping between the split and orig vert indicies
1240                         vert_dict[vert_key]= value 
1241                         tot_verts+= 1
1242
1243 # a flat list of split verts - can add custom weight data here too if you need
1244 split_verts= [None]*tot_verts
1245
1246 for vert_split_dict in verts_split:
1247         for key, value in vert_split_dict.iteritems():
1248                 local_index, split_index= value
1249                 split_verts[split_index]= key
1250
1251 # split_verts - Now you have a list of verts split by their UV.
1252 '''