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