From a3d391a32578483ede32fcd27266cd703f951e37 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Sun, 14 Oct 2007 18:32:42 +0000
Subject: [PATCH] Try to generate longer strips Fix a bug with strips starting
 with a triangle Add some more debug output Optimize vertex order

---
 mesh_export.py | 118 +++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 94 insertions(+), 24 deletions(-)

diff --git a/mesh_export.py b/mesh_export.py
index 75db9d12..bafbf917 100644
--- 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:
-- 
2.45.2