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