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