destruction of previous slot api. if it returns, it'll
[blender.git] / release / scripts / bpymodules / BPyMesh.py
index 8e93a51916f2fc9d7e10bf96b50ba795f662177a..415c2a12c6972374f7a5542859645054405549f4 100644 (file)
@@ -1,7 +1,116 @@
+# ***** BEGIN GPL LICENSE BLOCK *****
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+#
+# ***** END GPL LICENCE BLOCK *****
+# --------------------------------------------------------------------------
+
+
 import Blender
-from BPyMesh_redux import redux # seperated because of its size.
+import bpy
+import BPyMesh_redux # seperated because of its size.
+# reload(BPyMesh_redux)
+redux= BPyMesh_redux.redux
+
+# python 2.3 has no reversed() iterator. this will only work on lists and tuples
+try:
+       reversed
+except:
+       def reversed(l): return l[::-1]
+
+
+# If python version is less than 2.4, try to get set stuff from module
+try:
+       set
+except:
+       try:
+               from sets import Set as set
+       except:
+               set= None
 
+
+
+
+
+def meshWeight2List(me):
+       ''' Takes a mesh and return its group names and a list of lists, one list per vertex.
+       aligning the each vert list with the group names, each list contains float value for the weight.
+       These 2 lists can be modified and then used with list2MeshWeight to apply the changes.
+       '''
+       
+       # Clear the vert group.
+       groupNames= me.getVertGroupNames()
+       len_groupNames= len(groupNames)
+       
+       if not len_groupNames:
+               # no verts? return a vert aligned empty list
+               return [[] for i in xrange(len(me.verts))], []
+       
+       else:
+               vWeightList= [[0.0]*len_groupNames for i in xrange(len(me.verts))]
+       
+       for group_index, group in enumerate(groupNames):
+               for vert_index, weight in me.getVertsFromGroup(group, 1): # (i,w)  tuples.
+                       vWeightList[vert_index][group_index]= weight
+       
+       # removed this because me may be copying teh vertex groups.
+       #for group in groupNames:
+       #       me.removeVertGroup(group)
+       
+       return groupNames, vWeightList
+
+
+def list2MeshWeight(me, groupNames, vWeightList):
+       ''' Takes a list of groups and a list of vertex Weight lists as created by meshWeight2List
+       and applys it to the mesh.'''
        
+       if len(vWeightList) != len(me.verts):
+               raise 'Error, Lists Differ in size, do not modify your mesh.verts before updating the weights'
+       
+       act_group = me.activeGroup
+       
+       # Clear the vert group.
+       currentGroupNames= me.getVertGroupNames()
+       for group in currentGroupNames:
+               me.removeVertGroup(group) # messes up the active group.
+       
+       # Add clean unused vert groupNames back
+       currentGroupNames= me.getVertGroupNames()
+       for group in groupNames:
+               me.addVertGroup(group)
+       
+       add_ = Blender.Mesh.AssignModes.ADD
+       
+       vertList= [None]
+       for i, v in enumerate(me.verts):
+               vertList[0]= i
+               for group_index, weight in enumerate(vWeightList[i]):
+                       if weight:
+                               try:
+                                       me.assignVertsToGroup(groupNames[group_index], vertList, min(1, max(0, weight)), add_)
+                               except:
+                                       pass # vert group is not used anymore.
+       
+       try:    me.activeGroup = act_group
+       except: pass
+       
+       me.update()
+
+
+
+
 def meshWeight2Dict(me):
        ''' Takes a mesh and return its group names and a list of dicts, one dict per vertex.
        using the group as a key and a float value for the weight.
@@ -14,8 +123,8 @@ def meshWeight2Dict(me):
        groupNames= me.getVertGroupNames()
        
        for group in groupNames:
-               for index, weight in me.getVertsFromGroup(group, 1): # (i,w)  tuples.
-                       vWeightDict[index][group]= weight
+               for vert_index, weight in me.getVertsFromGroup(group, 1): # (i,w)  tuples.
+                       vWeightDict[vert_index][group]= weight
        
        # removed this because me may be copying teh vertex groups.
        #for group in groupNames:
@@ -31,6 +140,8 @@ def dict2MeshWeight(me, groupNames, vWeightDict):
        if len(vWeightDict) != len(me.verts):
                raise 'Error, Lists Differ in size, do not modify your mesh.verts before updating the weights'
        
+       act_group = me.activeGroup
+       
        # Clear the vert group.
        currentGroupNames= me.getVertGroupNames()
        for group in currentGroupNames:
@@ -56,6 +167,9 @@ def dict2MeshWeight(me, groupNames, vWeightDict):
                        except:
                                pass # vert group is not used anymore.
        
+       try:    me.activeGroup = act_group
+       except: pass
+       
        me.update()
 
 def dictWeightMerge(dict_weights):
@@ -133,7 +247,131 @@ def dictWeightFlipGroups(dict_weight, groupNames, createNewGroups):
                new_wdict[flipname]= weight
        
        return new_wdict, groupNames
+
+
+def mesh2linkedFaces(me):
+       '''
+       Splits the mesh into connected parts,
+       these parts are returned as lists of faces.
+       used for seperating cubes from other mesh elements in the 1 mesh
+       '''
+       
+       # Build vert face connectivity
+       vert_faces= [[] for i in xrange(len(me.verts))]
+       for f in me.faces:
+               for v in f:
+                       vert_faces[v.index].append(f)
+       
+       # sort faces into connectivity groups
+       face_groups= [[f] for f in me.faces]
+       face_mapping = range(len(me.faces)) # map old, new face location
        
+       # Now clump faces iterativly
+       ok= True
+       while ok:
+               ok= False
+               
+               for i, f in enumerate(me.faces):
+                       mapped_index= face_mapping[f.index]
+                       mapped_group= face_groups[mapped_index]
+                       
+                       for v in f:
+                               for nxt_f in vert_faces[v.index]:
+                                       if nxt_f != f:
+                                               nxt_mapped_index= face_mapping[nxt_f.index]
+                                               
+                                               # We are not a part of the same group
+                                               if mapped_index != nxt_mapped_index:
+                                                       
+                                                       ok= True
+                                                       
+                                                       # Assign mapping to this group so they all map to this group
+                                                       for grp_f in face_groups[nxt_mapped_index]:
+                                                               face_mapping[grp_f.index] = mapped_index
+                                                       
+                                                       # Move faces into this group
+                                                       mapped_group.extend(face_groups[nxt_mapped_index])
+                                                       
+                                                       # remove reference to the list
+                                                       face_groups[nxt_mapped_index]= None 
+                                               
+                                               
+       # return all face groups that are not null
+       # this is all the faces that are connected in their own lists.
+       return [fg for fg in face_groups if fg]
+
+
+def getFaceLoopEdges(faces, seams=[]):
+       '''
+       Takes me.faces or a list of faces and returns the edge loops
+       These edge loops are the edges that sit between quads, so they dont touch
+       1 quad, not not connected will make 2 edge loops, both only containing 2 edges.
+       
+       return a list of edge key lists
+       [ [(0,1), (4, 8), (3,8)], ...]
+       
+       optionaly, seams are edge keys that will be removed
+       '''
+       
+       OTHER_INDEX = 2,3,0,1 # opposite face index
+       
+       edges = {}
+       
+       for f in faces:
+               if len(f) == 4:
+                       edge_keys = f.edge_keys
+                       for i, edkey in enumerate(f.edge_keys):
+                               edges.setdefault(edkey, []).append(edge_keys[OTHER_INDEX[i]])
+       
+       for edkey in seams:
+               edges[edkey] = []
+       
+       # Collect edge loops here
+       edge_loops = [] 
+       
+       for edkey, ed_adj in edges.iteritems():
+               if 0 <len(ed_adj) < 3: # 1 or 2
+                       # Seek the first edge
+                       context_loop = [edkey, ed_adj[0]]
+                       edge_loops.append(context_loop)
+                       if len(ed_adj) == 2:
+                               other_dir = ed_adj[1]
+                       else:
+                               other_dir = None
+                       
+                       ed_adj[:] = []
+                       
+                       flipped = False
+                       
+                       while 1:
+                               # from knowing the last 2, look for th next.
+                               ed_adj = edges[context_loop[-1]]
+                               if len(ed_adj) != 2:
+                                       
+                                       if other_dir and flipped==False: # the original edge had 2 other edges
+                                               flipped = True # only flip the list once
+                                               context_loop.reverse()
+                                               ed_adj[:] = []
+                                               context_loop.append(other_dir) # save 1 lookiup
+                                               
+                                               ed_adj = edges[context_loop[-1]]
+                                               if len(ed_adj) != 2:
+                                                       ed_adj[:] = []
+                                                       break
+                                       else:
+                                               ed_adj[:] = []
+                                               break
+                               
+                               i = ed_adj.index(context_loop[-2])
+                               context_loop.append( ed_adj[ not  i] )
+                               
+                               # Dont look at this again
+                               ed_adj[:] = []
+
+       
+       return edge_loops
+       
+
 
 def getMeshFromObject(ob, container_mesh=None, apply_modifiers=True, vgroups=True, scn=None):
        '''
@@ -147,20 +385,19 @@ def getMeshFromObject(ob, container_mesh=None, apply_modifiers=True, vgroups=Tru
        '''
        
        if not scn:
-               scn= Blender.Scene.GetCurrent()
+               scn= bpy.data.scenes.active
        if not container_mesh:
-               mesh = Blender.Mesh.New()       
+               mesh = bpy.data.meshes.new(ob.name)     
        else:
                mesh= container_mesh
                mesh.verts= None
        
-       
-       type = ob.getType()
+       ob_type = ob.type
        dataname = ob.getData(1)
        tempob= None
-       if apply_modifiers or type != 'Mesh':
+       if apply_modifiers or ob_type != 'Mesh':
                try:
-                       mesh.getFromObject(ob.name)
+                       mesh.getFromObject(ob)
                except:
                        return None
        
@@ -169,20 +406,19 @@ def getMeshFromObject(ob, container_mesh=None, apply_modifiers=True, vgroups=Tru
                Dont apply modifiers, copy the mesh. 
                So we can transform the data. its easiest just to get a copy of the mesh. 
                '''
-               tempob= Blender.Object.New('Mesh')
-               tempob.shareFrom(ob)
-               scn.link(tempob)
-               mesh.getFromObject(tempob.name)
-               scn.unlink(tempob)
+               tempob= scn.objects.new(ob.getData(mesh=1))
+               mesh.getFromObject(tempob)
+               scn.objects.unlink(tempob)
        
-       if type == 'Mesh':
+       if ob_type == 'Mesh':
                if vgroups:
                        if tempob==None:
                                tempob= Blender.Object.New('Mesh')
+                       
                        tempob.link(mesh)
                        try:
                                # Copy the influences if possible.
-                               groupNames, vWeightDict= meshWeight2Dict(tempMe)
+                               groupNames, vWeightDict= meshWeight2Dict(ob.getData(mesh=1))
                                dict2MeshWeight(mesh, groupNames, vWeightDict)
                        except:
                                # if the modifier changes the vert count then it messes it up for us.
@@ -191,7 +427,7 @@ def getMeshFromObject(ob, container_mesh=None, apply_modifiers=True, vgroups=Tru
        return mesh
 
 
-def faceRayIntersect(f, orig, dir):
+def faceRayIntersect(f, orig, rdir):
        '''
        Returns face, side
        Side is the side of a quad we intersect.
@@ -199,23 +435,23 @@ def faceRayIntersect(f, orig, dir):
                side 1 == 0,2,3
        '''
        f_v= f.v
-       isect= Blender.Mathutils.Intersect(f_v[0].co, f_v[1].co, f_v[2].co, dir, orig, 1) # 1==clip
+       isect= Blender.Mathutils.Intersect(f_v[0].co, f_v[1].co, f_v[2].co, rdir, orig, 1) # 1==clip
        
        if isect:
                return isect, 0
        
        if len(f_v)==4:
-               isect= Blender.Mathutils.Intersect(f_v[0].co, f_v[2].co, f_v[3].co, dir, orig, 1) # 1==clip
+               isect= Blender.Mathutils.Intersect(f_v[0].co, f_v[2].co, f_v[3].co, rdir, orig, 1) # 1==clip
                if isect:
                        return isect, 1
        return False, 0
 
 
-def pickMeshRayFace(me, orig, dir):
+def pickMeshRayFace(me, orig, rdir):
        best_dist= 1000000
        best_isect= best_side= best_face= None
        for f in me.faces:
-               isect, side= faceRayIntersect(f, orig, dir)
+               isect, side= faceRayIntersect(f, orig, rdir)
                if isect:
                        dist= (isect-orig).length
                        if dist<best_dist:
@@ -223,14 +459,17 @@ def pickMeshRayFace(me, orig, dir):
                                best_face= f
                                best_side= side
                                best_isect= isect
-       f= best_face
-       isect= best_isect
-       side= best_side
+       
+       return best_face, best_isect, best_side
+
+
+def pickMeshRayFaceWeight(me, orig, rdir):
+       f, isect, side = pickMeshRayFace(me, orig, rdir)
        
        if f==None:
                return None, None, None, None, None
        
-       f_v= [v.co for v in f.v]
+       f_v= [v.co for v in f]
        if side==1: # we can leave side 0 without changes.
                f_v = f_v[0], f_v[2], f_v[3]
        
@@ -251,9 +490,12 @@ def pickMeshRayFace(me, orig, dir):
 
 
 
-def pickMeshGroupWeight(me, act_group, orig, dir):
-       f, side, w0, w1, w2= pickMeshRayFace(me, orig, dir)
+def pickMeshGroupWeight(me, act_group, orig, rdir):
+       f, side, w0, w1, w2= pickMeshRayFaceWeight(me, orig, rdir)
        
+       if f==None:
+               return None
+               
        f_v= f.v
        if side==0:
                f_vi= (f_v[0].index, f_v[1].index, f_v[2].index)
@@ -267,9 +509,12 @@ def pickMeshGroupWeight(me, act_group, orig, dir):
        
        return w0*vws[0] + w1*vws[1]  + w2*vws[2]
 
-def pickMeshGroupVCol(me, orig, dir):
+def pickMeshGroupVCol(me, orig, rdir):
        Vector= Blender.Mathutils.Vector
-       f, side, w0, w1, w2= pickMeshRayFace(me, orig, dir)
+       f, side, w0, w1, w2= pickMeshRayFaceWeight(me, orig, rdir)
+       
+       if f==None:
+               return None
        
        def col2vec(c):
                return Vector(c.r, c.g, c.b)
@@ -282,14 +527,6 @@ def pickMeshGroupVCol(me, orig, dir):
        f_colvecs= [col2vec(f_c[i]) for i in idxs]
        return f_colvecs[0]*w0 +  f_colvecs[1]*w1 + f_colvecs[2]*w2
 
-# reuse me more.
-def sorted_edge_indicies(ed):
-       i1= ed.v1.index
-       i2= ed.v2.index
-       if i1>i2:
-               i1,i2= i2,i1
-       return i1, i2
-
 def edge_face_users(me):
        ''' 
        Takes a mesh and returns a list aligned with the meshes edges.
@@ -297,17 +534,11 @@ def edge_face_users(me):
        would be the equiv for having ed.face_users as a property
        '''
        
-       face_edges_dict= dict([(sorted_edge_indicies(ed), (ed.index, [])) for ed in me.edges])
+       face_edges_dict= dict([(ed.key, (ed.index, [])) for ed in me.edges])
        for f in me.faces:
-               fvi= [v.index for v in f.v]# face vert idx's
-               for i in xrange(len(f)):
-                       i1= fvi[i]
-                       i2= fvi[i-1]
-                       
-                       if i1>i2:
-                               i1,i2= i2,i1
-                       
-                       face_edges_dict[i1,i2][1].append(f)
+               fvi= [v.index for v in f]# face vert idx's
+               for edkey in f.edge_keys:
+                       face_edges_dict[edkey][1].append(f)
        
        face_edges= [None] * len(me.edges)
        for ed_index, ed_faces in face_edges_dict.itervalues():
@@ -325,21 +556,13 @@ def face_edges(me):
        face_edges[i][j] -> list of faces that this edge uses.
        crap this is tricky to explain :/
        '''
-       face_edges= [ [None] * len(f) for f in me.faces ]
+       face_edges= [ [-1] * len(f) for f in me.faces ]
        
-       face_edges_dict= dict([(sorted_edge_indicies(ed), []) for ed in me.edges])
+       face_edges_dict= dict([(ed.key, []) for ed in me.edges])
        for fidx, f in enumerate(me.faces):
-               fvi= [v.index for v in f.v]# face vert idx's
-               for i in xrange(len(f)):
-                       i1= fvi[i]
-                       i2= fvi[i-1]
-                       
-                       if i1>i2:
-                               i1,i2= i2,i1
-                       
-                       edge_face_users= face_edges_dict[i1,i2]
+               for i, edkey in enumerate(f.edge_keys):
+                       edge_face_users= face_edges_dict[edkey]
                        edge_face_users.append(f)
-                       
                        face_edges[fidx][i]= edge_face_users
                        
        return face_edges
@@ -507,19 +730,12 @@ def edgeFaceUserCount(me, faces= None):
        
        edge_users= [0] * len(me.edges)
        
-       edges_idx_dict= dict([(sorted_edge_indicies(ed), ed.index) for ed in me.edges])
+       edges_idx_dict= dict([(ed.key, ed.index) for ed in me.edges])
 
        for f in faces:
-               fvi= [v.index for v in f.v]# face vert idx's
-               for i in xrange(len(f)):
-                       i1= fvi[i]
-                       i2= fvi[i-1]
-                       
-                       if i1>i2:
-                               i1,i2= i2,i1
-                       
-                       edge_users[edges_idx_dict[i1,i2]] += 1 
-                       
+               for edkey in f.edge_keys:
+                       edge_users[edges_idx_dict[edkey]] += 1 
+       
        return edge_users
 
 
@@ -569,14 +785,14 @@ def getUvPixelLoc(face, pxLoc, img_size = None, uvArea = None):
        return None
 
 
-type_tuple= type( (0,) )
-type_list= type( [] )
-
-
+# Used for debugging ngon
+"""
 def draw_loops(loops):
        
        me= Blender.Mesh.New()
        for l in loops:
+               #~ me= Blender.Mesh.New()
+               
                
                i= len(me.verts)
                me.verts.extend([v[0] for v in l])
@@ -586,7 +802,17 @@ def draw_loops(loops):
                        pass
                me.edges.extend([ (j-1, j) for j in xrange(i+1, len(me.verts)) ])
                # Close the edge?
-               #me.edges.extend((i, len(me.verts)-1))
+               me.edges.extend((i, len(me.verts)-1))
+               
+               
+               #~ ob= Blender.Object.New('Mesh')
+               #~ ob.link(me)
+               #~ scn= Blender.Scene.GetCurrent()
+               #~ scn.link(ob)
+               #~ ob.Layers= scn.Layers
+               #~ ob.sel= 1
+               
+               
                
        # Fill
        #fill= Blender.Mathutils.PolyFill(loops)
@@ -599,245 +825,177 @@ def draw_loops(loops):
        scn.link(ob)
        ob.Layers= scn.Layers
        ob.sel= 1
-
-"""
-def ngon(from_data, indices, PREF_FIX_LOOPS= True):
-       Vector= Blender.Mathutils.Vector
-       
-       def rvec(co): return round(co.x, 5), round(co.y, 5), round(co.z, 5)
-       def vert_treplet(v, i):
-               return v, rvec(v), i
-       
-       if type(from_data) in (type_tuple, type_list):
-               verts= [vert_treplet(Vector(from_data[i]), ii) for ii, i in enumerate(indices)]
-       else:
-               verts= [vert_treplet(from_data.verts[i].co, ii) for ii, i in enumerate(indices)]
-       
-       if PREF_FIX_LOOPS:
-               
-               
-               len_verts= len(verts)
-               loop_list= []
-               vert_dict= {}
-               i= 1
-               while i<len(verts):
-                       
-                       vertkey= verts[i][1]
-                       
-                       loop_idx= 0
-                       try: # is this a loop back on one of the last edges?
-                               loop_idx= vert_dict[vertkey]
-                               
-                       except:
-                               vert_dict[vertkey]= i
-                               
-                       if loop_idx and abs(loop_idx-i)>2:
-                                       
-                               # print 'Found loop', i-loop_idx
-                               loop_list.append(verts[loop_idx:i])
-                               #print loop_list
-                               verts[loop_idx:i+1]= [] #verts[loop_idx:i+1]= []
-                               i= loop_idx+1
-                               
-                               for v in loop_list[-1]:
-                                       try:
-                                               del vert_dict[v[1]]
-                                       except:
-                                               pass
-                                       
-                               
-                       i+=1
-               
-               loop_list.append(verts)
-       
-       
-       
-       
-       # vert mapping
-       vert_map= [None]*len(indices)
-       ii=0
-       for verts in loop_list:
-               for i, vert in enumerate(verts):
-                       vert_map[i+ii]= vert[2]
-               
-               ii+=len(verts)
-       
-       fill= Blender.Mathutils.PolyFill([ [v[0] for v in loop] for loop in loop_list])
-       #draw_loops(loop_list)
-       #raise 'loopy'
-       # map to original indicies
-       
-       return [[vert_map[i] for i in reversed(f)] for f in fill]
+       Blender.Window.RedrawAll()
 """
 
 def ngon(from_data, indices, PREF_FIX_LOOPS= True):
-       # print 'NGON', len(indices)
        '''
-       takes a polyline of indices (fgon)
+       Takes a polyline of indices (fgon)
        and returns a list of face indicie lists.
        Designed to be used for importers that need indices for an fgon to create from existing verts.
        
        from_data: either a mesh, or a list/tuple of vectors.
        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.
-       PREF_FIX_LOOPS: If this is enabled polylines that use loops to make ultiple polylines are delt with correctly.
+       PREF_FIX_LOOPS: If this is enabled polylines that use loops to make multiple polylines are delt with correctly.
        '''
-       Mesh= Blender.Mesh
-       Window= Blender.Window
-       Scene= Blender.Scene
-       Object= Blender.Object
-       
-       if len(indices) < 4:
-               return [indices]
-       temp_mesh_name= '~NGON_TEMP~'
-       is_editmode= Window.EditMode()
-       if is_editmode:
-               Window.EditMode(0)
-       try:
-               temp_mesh = Mesh.Get(temp_mesh_name)
-               if temp_mesh.users!=0:
-                       temp_mesh = Mesh.New(temp_mesh_name)
-       except:
-               temp_mesh = Mesh.New(temp_mesh_name)
-               
-       if type(from_data) in (type_tuple, type_list):
-               # From a list/tuple of vectors
-               temp_mesh.verts.extend( [from_data[i] for i in indices] )
-               #temp_mesh.edges.extend( [(temp_mesh.verts[i], temp_mesh.verts[i-1]) for i in xrange(len(temp_mesh.verts))] )
-               edges= [(i, i-1) for i in xrange(len(temp_mesh.verts))]
-       else:
-               # From a mesh
-               temp_mesh.verts.extend( [from_data.verts[i].co for i in indices] )
-               #temp_mesh.edges.extend( [(temp_mesh.verts[i], temp_mesh.verts[i-1]) for i in xrange(len(temp_mesh.verts))] )
-               edges= [(i, i-1) for i in xrange(len(temp_mesh.verts))]
-       if edges:
-               edges[0]= (0,len(temp_mesh.verts)-1)
        
+       if not set: # Need sets for this, otherwise do a normal fill.
+               PREF_FIX_LOOPS= False 
+       
+       Vector= Blender.Mathutils.Vector
+       if not indices:
+               return []
+       
+       #       return []
        def rvec(co): return round(co.x, 6), round(co.y, 6), round(co.z, 6)
-       def mlen(co): return co[0]+co[1]+co[2] # manhatten length of a vector
+       def mlen(co): return abs(co[0])+abs(co[1])+abs(co[2]) # manhatten length of a vector, faster then length
        
-       if PREF_FIX_LOOPS:
-               edge_used_count= {}
+       def vert_treplet(v, i):
+               return v, rvec(v), i, mlen(v)
+       
+       def ed_key_mlen(v1, v2):
+               if v1[3] > v2[3]:
+                       return v2[1], v1[1]
+               else:
+                       return v1[1], v2[1]
+       
+       
+       if not PREF_FIX_LOOPS:
+               '''
+               Normal single concave loop filling
+               '''
+               if type(from_data) in (tuple, list):
+                       verts= [Vector(from_data[i]) for ii, i in enumerate(indices)]
+               else:
+                       verts= [from_data.verts[i].co for ii, i in enumerate(indices)]
                
-               rounded_verts= [rvec(v.co) for v in temp_mesh.verts] # rounded verts we can use as dict keys.
+               for i in xrange(len(verts)-1, 0, -1): # same as reversed(xrange(1, len(verts))):
+                       if verts[i][1]==verts[i-1][0]:
+                               verts.pop(i-1)
                
-               # We need to check if any edges are used twice location based.
-               for ed_idx, ed in enumerate(edges):
-                       ed_v1= rounded_verts[ed[0]]
-                       ed_v2= rounded_verts[ed[1]]
+               fill= Blender.Geometry.PolyFill([verts])
+               
+       else:
+               '''
+               Seperate this loop into multiple loops be finding edges that are used twice
+               This is used by lightwave LWO files a lot
+               '''
+               
+               if type(from_data) in (tuple, list):
+                       verts= [vert_treplet(Vector(from_data[i]), ii) for ii, i in enumerate(indices)]
+               else:
+                       verts= [vert_treplet(from_data.verts[i].co, ii) for ii, i in enumerate(indices)]
                        
-                       if ed_v1==ed_v2: # Same locations, remove the edge.
-                               edges[ed_idx]= None
+               edges= [(i, i-1) for i in xrange(len(verts))]
+               if edges:
+                       edges[0]= (0,len(verts)-1)
+               
+               if not verts:
+                       return []
+               
+               
+               edges_used= set()
+               edges_doubles= set()
+               # We need to check if any edges are used twice location based.
+               for ed in edges:
+                       edkey= ed_key_mlen(verts[ed[0]], verts[ed[1]])
+                       if edkey in edges_used:
+                               edges_doubles.add(edkey)
                        else:
-                               if mlen(ed_v1) < mlen(ed_v2):
-                                       edkey= ed_v1, ed_v2
+                               edges_used.add(edkey)
+               
+               # Store a list of unconnected loop segments split by double edges.
+               # will join later
+               loop_segments= [] 
+               
+               v_prev= verts[0]
+               context_loop= [v_prev]
+               loop_segments= [context_loop]
+               
+               for v in verts:
+                       if v!=v_prev:
+                               # Are we crossing an edge we removed?
+                               if ed_key_mlen(v, v_prev) in edges_doubles:
+                                       context_loop= [v]
+                                       loop_segments.append(context_loop)
                                else:
-                                       edkey= ed_v2, ed_v1
+                                       if context_loop and context_loop[-1][1]==v[1]:
+                                               #raise "as"
+                                               pass
+                                       else:
+                                               context_loop.append(v)
                                
-                               try:
-                                       edge_user_list= edge_used_count[edkey]
-                                       edge_user_list.append(ed_idx)
-                                       
-                                       # remove edges if there are doubles.
-                                       if len(edge_user_list) > 1:
-                                               for edidx in edge_user_list:\
-                                                       edges[edidx]= None
-                               except:
-                                       edge_used_count[edkey]= [ed_idx]
+                               v_prev= v
+               # Now join loop segments
                
+               def join_seg(s1,s2):
+                       if s2[-1][1]==s1[0][1]: # 
+                               s1,s2= s2,s1
+                       elif s1[-1][1]==s2[0][1]:
+                               pass
+                       else:
+                               return False
+                       
+                       # If were stuill here s1 and s2 are 2 segments in the same polyline
+                       s1.pop() # remove the last vert from s1
+                       s1.extend(s2) # add segment 2 to segment 1
+                       
+                       if s1[0][1]==s1[-1][1]: # remove endpoints double
+                               s1.pop()
+                       
+                       s2[:]= [] # Empty this segment s2 so we dont use it again.
+                       return True
                
-               # Now remove double verts
-               vert_doubles= {}
-               for edidx, ed in enumerate(edges):
-                       if ed != None:
-                               ed_v1= rounded_verts[ed[0]]
-                               ed_v2= rounded_verts[ed[1]]
-                               
-                               if ed_v1==ed_v2:
-                                       edges[edidx]= None # will clear later, edge is zero length.
-                                       #print 'REMOVING DOUBLES'
-                                       
-                               else:
-                                       # Try and replace with an existing vert or add teh one we use.
-                                       try:    edges[edidx]= vert_doubles[ed_v1], ed[1]
-                                       except:
-                                               vert_doubles[ed_v1]= ed[0]
-                                               #print 'REMOVING DOUBLES'
+               joining_segments= True
+               while joining_segments:
+                       joining_segments= False
+                       segcount= len(loop_segments)
+                       
+                       for j in xrange(segcount-1, -1, -1): #reversed(xrange(segcount)):
+                               seg_j= loop_segments[j]
+                               if seg_j:
+                                       for k in xrange(j-1, -1, -1): # reversed(xrange(j)):
+                                               if not seg_j:
+                                                       break
+                                               seg_k= loop_segments[k]
                                                
-                                       try:    edges[edidx]= ed[0], vert_doubles[ed_v2]
-                                       except:
-                                               vert_doubles[ed_v2]= ed[1]
-                                               #print 'REMOVING DOUBLES'
+                                               if seg_k and join_seg(seg_j, seg_k):
+                                                       joining_segments= True
                
-               edges= [ed for ed in edges if ed != None] # != None
-               # Done removing double edges!
+               loop_list= loop_segments
                
-       # DONE DEALING WITH LOOP FIXING
-       
+               for verts in loop_list:
+                       while verts and verts[0][1]==verts[-1][1]:
+                               verts.pop()
+               
+               loop_list= [verts for verts in loop_list if len(verts)>2]
+               # DONE DEALING WITH LOOP FIXING
+               
+               
+               # vert mapping
+               vert_map= [None]*len(indices)
+               ii=0
+               for verts in loop_list:
+                       if len(verts)>2:
+                               for i, vert in enumerate(verts):
+                                       vert_map[i+ii]= vert[2]
+                               ii+=len(verts)
+               
+               fill= Blender.Geometry.PolyFill([ [v[0] for v in loop] for loop in loop_list ])
+               #draw_loops(loop_list)
+               #raise 'done loop'
+               # map to original indicies
+               fill= [[vert_map[i] for i in reversed(f)] for f in fill]
        
        
-       temp_mesh.edges.extend(edges)
-               
-       # Move verts to middle and normalize.
-       # For a good fill we need to normalize and scale the vert location.
-       
-       xmax=ymax=zmax= -1<<30
-       xmin=ymin=zmin= 1<<30
-       for v in temp_mesh.verts:
-               co= v.co
-               x= co.x
-               y= co.y
-               z= co.z
-               if x<xmin: xmin=x
-               if y<ymin: ymin=y
-               if z<zmin: zmin=z
-               if x>xmax: xmax=x
-               if y>ymax: ymax=y
-               if z>zmax: zmax=z
-       
-       # get the bounds on the largist axis
-       size= xmax-xmin
-       size= max(size, ymax-ymin)
-       size= max(size, zmax-zmin)
-       
-       xmid= (xmin+xmax)/2
-       ymid= (ymin+ymax)/2
-       zmid= (zmin+zmax)/2
-
-       x=x/len(temp_mesh.verts)
-       y=y/len(temp_mesh.verts)
-       z=z/len(temp_mesh.verts)
-       
-       for v in temp_mesh.verts:
-               co= v.co
-               co.x= (co.x-xmid)/size
-               co.y= (co.y-ymid)/size
-               co.z= (co.z-zmid)/size
-       # finished resizing the verts.
-       
-       oldmode = Mesh.Mode()
-       Mesh.Mode(Mesh.SelectModes['VERTEX'])
-       temp_mesh.sel= 1 # Select all verst     
-       
-       # Must link to scene
-       scn= Scene.GetCurrent()
-       temp_ob= Object.New('Mesh')
-       temp_ob.link(temp_mesh)
-       scn.link(temp_ob)
-       
-       temp_mesh.fill()
-       scn.unlink(temp_ob)
-       Mesh.Mode(oldmode)
-       
-       new_indices= [ [v.index for v in f.v]  for f in temp_mesh.faces ]
-       
-       if not new_indices: # JUST DO A FAN, Cant Scanfill
-               print 'Warning Cannot scanfill!- Fallback on a triangle fan.'
-               new_indices = [ [0, i-1, i] for i in xrange(2, len(indices)) ]
+       if not fill:
+               print 'Warning Cannot scanfill, fallback on a triangle fan.'
+               fill= [ [0, i-1, i] for i in xrange(2, len(indices)) ]
        else:
                # Use real scanfill.
                # See if its flipped the wrong way.
                flip= None
-               for fi in new_indices:
+               for fi in fill:
                        if flip != None:
                                break
                        for i, vi in enumerate(fi):
@@ -849,17 +1007,13 @@ def ngon(from_data, indices, PREF_FIX_LOOPS= True):
                                        break
                
                if not flip:
-                       for fi in new_indices:
-                               fi.reverse()
-       
-       if is_editmode:
-               Window.EditMode(1)
+                       for i, fi in enumerate(fill):
+                               fill[i]= tuple([ii for ii in reversed(fi)])
+               
+               
                
-       # Save some memory and forget about the verts.
-       # since we cant unlink the mesh.
-       temp_mesh.verts= None 
        
-       return new_indices
+       return fill
        
 
 
@@ -897,24 +1051,18 @@ def meshCalcNormals(me, vertNormals=None):
                
        edges={}
        for f in me.faces:
-               for i in xrange(len(f)):
-                       i1, i2= f.v[i].index, f.v[i-1].index
-                       if i1<i2:
-                               i1,i2= i2,i1
-                               
-                       try:
-                               edges[i1, i2].append(f.no)
-                       except:
-                               edges[i1, i2]= [f.no]
-                               
+               f_v = f.v
+               for edkey in f.edge_keys:
+                       edges.setdefault(edkey, []).append(f.no)
+       
        # Weight the edge normals by total angle difference
        for fnos in edges.itervalues():
                
                len_fnos= len(fnos)
                if len_fnos>1:
                        totAngDiff=0
-                       for j in reversed(xrange(len_fnos)):
-                               for k in reversed(xrange(j)):
+                       for j in xrange(len_fnos-1, -1, -1): # same as reversed(xrange(...))
+                               for k in xrange(j-1, -1, -1): # same as reversed(xrange(...))
                                        #print j,k
                                        try:
                                                totAngDiff+= (Ang(fnos[j], fnos[k])) # /180 isnt needed, just to keeop the vert small.
@@ -949,25 +1097,25 @@ def pointInsideMesh(ob, pt):
        Vector = Blender.Mathutils.Vector
        
        def ptInFaceXYBounds(f, pt):
-                       
-               co= f.v[0].co
+               f_v = f.v
+               co= f_v[0].co
                xmax= xmin= co.x
                ymax= ymin= co.y
                
-               co= f.v[1].co
+               co= f_v[1].co
                xmax= max(xmax, co.x)
                xmin= min(xmin, co.x)
                ymax= max(ymax, co.y)
                ymin= min(ymin, co.y)
                
-               co= f.v[2].co
+               co= f_v[2].co
                xmax= max(xmax, co.x)
                xmin= min(xmin, co.x)
                ymax= max(ymax, co.y)
                ymin= min(ymin, co.y)
                
-               if len(f)==4: 
-                       co= f.v[3].co
+               if len(f_v)==4: 
+                       co= f_v[3].co
                        xmax= max(xmax, co.x)
                        xmin= min(xmin, co.x)
                        ymax= max(ymax, co.y)
@@ -985,22 +1133,17 @@ def pointInsideMesh(ob, pt):
                #return xmax, ymax, xmin, ymin
        
        def faceIntersect(f):
-               isect = Intersect(f.v[0].co, f.v[1].co, f.v[2].co, ray, obSpacePt, 1) # Clipped.
+               f_v = f.v
+               isect = Intersect(f_v[0].co, f_v[1].co, f_v[2].co, ray, obSpacePt, 1) # Clipped.
                if not isect and len(f) == 4:
-                       isect = Intersect(f.v[0].co, f.v[2].co, f.v[3].co, ray, obSpacePt, 1) # Clipped.
+                       isect = Intersect(f_v[0].co, f_v[2].co, f_v[3].co, ray, obSpacePt, 1) # Clipped.
                                
                if isect and isect.z > obSpacePt.z: # This is so the ray only counts if its above the point. 
                        return True
                else:
                        return False
        
-       
-       obImvMat = Blender.Mathutils.Matrix(ob.matrixWorld)
-       obImvMat.invert()
-       pt.resize4D()
-       obSpacePt = pt* obImvMat
-       pt.resize3D()
-       obSpacePt.resize3D()
+       obSpacePt = pt*ob.matrixWorld.copy().invert()
        ray = Vector(0,0,-1)
        me= ob.getData(mesh=1)
        
@@ -1008,6 +1151,33 @@ def pointInsideMesh(ob, pt):
        return len([None for f in me.faces if ptInFaceXYBounds(f, obSpacePt) if faceIntersect(f)]) % 2
 
 
+def faceAngles(f):
+       '''
+       Returns the angle between all corners in a tri or a quad
+       
+       '''
+       AngleBetweenVecs = Blender.Mathutils.AngleBetweenVecs
+       def Ang(a1,a2):
+               try:            return AngleBetweenVecs(a1,a2)
+               except:         return 180
+       
+       if len(f) == 3:
+               if type(f) in (tuple, list):    v1,v2,v3 = f
+               else:                                                   v1,v2,v3 = [v.co for v in f]
+               a1= Ang(v2-v1,v3-v1)
+               a2= Ang(v1-v2,v3-v2)
+               a3 = 180 - (a1+a2) # a3= Mathutils.AngleBetweenVecs(v2-v3,v1-v3)
+               return a1,a2,a3
+       
+       else:
+               if type(f) in (tuple, list):    v1,v2,v3,v4 = f
+               else:                                                   v1,v2,v3,v4 = [v.co for v in f]
+               a1= Ang(v2-v1,v4-v1)
+               a2= Ang(v1-v2,v3-v2)
+               a3= Ang(v2-v3,v4-v3)
+               a4= Ang(v3-v4,v1-v4)
+               return a1,a2,a3,a4
+
 # NMesh wrapper
 Vector= Blender.Mathutils.Vector
 class NMesh(object):