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