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