Try to generate longer strips

Fix a bug with strips starting with a triangle
Add some more debug output
Optimize vertex order

diff --git a/mesh_export.py b/mesh_export.py
index 75db9d12dd1d1ab70faf9347c2b247f822155604..bafbf917e527eea2b7c7e230b2115dce987e4012 100644 (file)
--- a/mesh_export.py
+++ b/mesh_export.py
@@ -76,6 +76,13 @@ class Face:
                        if flags[i] and not flags[(i+l-1)%l]:
                                return self.verts[i:]+self.verts[:i]
 
+       def get_edge(self, v1, v2):     
+               i1=v1.index
+               i2=v2.index
+               for e in self.edges:
+                       if (e.v1.index==i1 or e.v1.index==i2) and (e.v2.index==i1 or e.v2.index==i2):
+                               return e
+
 
 class SmoothGroup:
        def __init__(self, index):
@@ -161,6 +168,7 @@ class Exporter:
                self.use_strips=True
                self.use_degen_tris=True
                self.debug=False
+               self.strip_debug=False
 
        def find_smooth_group(self, face, sg):
                face.smooth_group=sg
@@ -187,17 +195,20 @@ class Exporter:
                if not edge:
                        return None
 
-               if self.debug:
-                       print "Starting strip from %s"%[v.index for v in face.verts]
+               if self.strip_debug:
+                       print "Starting strip from %s, edge %s"%([v.index for v in face.verts], (edge.v1.index, edge.v2.index))
 
                verts=face.get_vertices_from(edge.v1, edge.v2)
-               result=[verts[-2], verts[-1]]
+               if len(verts)==3:
+                       result=[verts[-1], verts[0]]
+               else:
+                       result=[verts[-2], verts[-1]]
 
                while 1:
                        verts=face.get_vertices_from(*result[-2:])
                        k=len(result)%2
-                       if self.debug:
-                               print "  %d %s"%(len(result), [v.index for v in verts])
+                       if self.strip_debug:
+                               print "  Adding %s"%[v.index for v in verts]
 
                        face.flag=True
                        if len(verts)==4 and not k:
@@ -206,24 +217,28 @@ class Exporter:
                        if len(verts)==4 and k:
                                result.append(verts[3])
 
-                       i1=result[-2].index
-                       i2=result[-1].index
-                       ekey=(min(i1, i2), max(i1, i2))
-                       for e in face.edges:
-                               if e.key==ekey:
-                                       edge=e
-                                       break
+                       edge=face.get_edge(*result[-2:])
+
+                       if self.strip_debug:
+                               print "  Next edge is %s"%((edge.v1.index, edge.v2.index), )
 
                        next=edge.other_face(face)
                        if not next or next.smooth_group.index!=face.smooth_group.index or next.flag:
                                break
                        face=next
 
-               if self.debug:
+               if self.strip_debug:
                        print "  %s"%[v.index for v in result]
 
                return result
 
+       def get_locality(self, strip):
+               total=0
+               for i in range(1, len(strip)):
+                       if strip[i].index!=strip[i-1].index:
+                               total+=1.0/(abs(strip[i].index-strip[i-1].index))
+               return total/len(strip)
+
        def export(self):
                scene=bpy.data.scenes.active
 
@@ -246,7 +261,8 @@ class Exporter:
                        e.check_smooth(smooth_limit)
 
                if self.debug:
-                       print "%d faces, %d edges"%(len(faces), len(edges))
+                       ntris=sum([len(f.verts)-2 for f in faces])
+                       print "%d faces (%d triangles), %d edges"%(len(faces), ntris, len(edges))
 
                smooth_groups=[]
                for f in faces:
@@ -268,26 +284,58 @@ class Exporter:
                                verts.append(v)
 
                if self.debug:
-                       print "%d smooth groups:"%(len(smooth_groups))
+                       print "%d smooth groups:"%len(smooth_groups)
                        for i in range(len(smooth_groups)):
                                sg=smooth_groups[i]
                                print "  %d: %d faces, %d vertices"%(i, len(sg.faces), len(sg.verts))
+                       print "%d vertices total"%len(verts)
 
                strips=[]
                if self.use_strips:
-                       for sg in smooth_groups:
-                               for f in sg.faces:
-                                       if not f.flag:
-                                               strip=self.create_strip(f)
-                                               if strip:
-                                                       strips.append(strip)
+                       while 1:
+                               best=5
+                               face=None
+                               for f in faces:
+                                       if f.flag:
+                                               continue
+                                       score=0
+                                       for e in f.edges:
+                                               other=e.other_face(f)
+                                               if other and other.smooth_group.index==f.smooth_group.index and not other.flag:
+                                                       score+=1
+                                       if score>0 and score<best:
+                                               face=f
+                                               best=score
+                               if not face:
+                                       break
+                               strip=self.create_strip(face)
+                               if strip:
+                                       strips.append(strip)
+
+                       if self.debug:
+                               print "%d strips:"%len(strips)
+                               for i in range(len(strips)):
+                                       print "  %d: %d indices"%(i, len(strips[i]))
+                               print "%d loose faces"%len([f for f in faces if not f.flag])
+                               nind=sum([len(s) for s in strips])+sum([len(f.verts) for f in faces if not f.flag])
+                               print "%d indices total"%nind
 
                        if self.use_degen_tris:
                                big_strip=[]
-                               for s in strips:
+                               while strips:
+                                       strip=None
+                                       if big_strip:
+                                               for i in range(len(strips)):
+                                                       if strips[i][0].index==big_strip[-1].index:
+                                                               strip=strips.pop(i)
+                                                               break
+                                       if not strip:
+                                               strip=strips.pop(0)
                                        if big_strip:
-                                               big_strip+=[big_strip[-1], s[0]]
-                                       big_strip+=s
+                                               if strip[0].index!=big_strip[-1].index:
+                                                       big_strip+=[big_strip[-1]]
+                                               big_strip+=[strip[0]]
+                                       big_strip+=strip
 
                                for f in faces:
                                        if not f.flag:
@@ -299,6 +347,28 @@ class Exporter:
                                                f.flag=True
 
                                strips=[big_strip]
+                               
+                               if self.debug:
+                                       nind=len(big_strip)
+                                       print "Big strip has %d indices"%len(big_strip)
+
+               if self.debug:
+                       print "%.2f vertices per triangle"%(float(nind)/ntris)
+                       print "Locality before optimization: "+" ".join(["%.3f"%self.get_locality(s) for s in strips])
+
+               used=[False]*len(verts)
+               i=0
+               for s in strips:
+                       for v in s:
+                               if not used[v.index]:
+                                       used[v.index]=True
+                                       v.index=i
+                                       i+=1
+
+               verts.sort(cmp=lambda x,y: cmp(x.index, y.index))
+
+               if self.debug:
+                       print "Locality after optimization: "+" ".join(["%.3f"%self.get_locality(s) for s in strips])
 
                self.out_file.write("vertices NORMAL3")
                if mesh.faceUV: