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