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