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