From ea6445c234d1db93e7c62cce228e94b2b652c1c5 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Thu, 9 Aug 2012 23:21:45 +0300
Subject: [PATCH] Refactor strip generation code and add comments

---
 blender/io_mesh_mspgl/export_mspgl.py | 54 +++++++++++++++------------
 blender/io_mesh_mspgl/mesh.py         | 19 +++++++---
 2 files changed, 45 insertions(+), 28 deletions(-)

diff --git a/blender/io_mesh_mspgl/export_mspgl.py b/blender/io_mesh_mspgl/export_mspgl.py
index 0e96c424..124114e5 100644
--- a/blender/io_mesh_mspgl/export_mspgl.py
+++ b/blender/io_mesh_mspgl/export_mspgl.py
@@ -94,6 +94,7 @@ class Exporter:
 		island_strips = []
 		while 1:
 			if not island:
+				# No current island; find any unused face to start from
 				queue = []
 				for f in mesh.faces:
 					if not f.flag:
@@ -104,38 +105,46 @@ class Exporter:
 				if not queue:
 					break
 
+				# Find all faces connected to the first one
 				while queue:
-					f = queue[0]
-					del queue[0]
-					island.append(f)
+					face = queue.pop(0)
+					island.append(face)
 
-					for e in f.edges:
-						other = e.other_face(f)
-						if other and not other.flag:
-							other.flag = True
-							queue.append(other)
+					for n in f.get_neighbors():
+						n.flag = True
+						queue.append(n)
 
+				# Unflag the island for the next phase
 				for f in island:
 					f.flag = False
 
+			# Find an unused face with as few unused neighbors as possible, but
+			# at least one.  This heuristic gives a preference to faces in corners
+			# or along borders of a non-closed island.
 			best = 5
 			face = None
 			for f in island:
 				if f.flag:
 					continue
-				score = 0
-				for e in f.edges:
-					other = e.other_face(f)
-					if other and not other.flag:
-						score += 1
+
+				score = sum(n.flag for n in f.get_neighbors())
 				if score>0 and score<best:
 					face = f
 					best = score
 
-			if not face:
+			if face:
+				# Create a strip starting from the face.  This will flag the faces.
+				strip = mesh.create_strip(face, self.max_strip_len)
+				if strip:
+					island_strips.append(strip)
+			else:
+				# Couldn't find a candidate face for starting a strip, so we're
+				# done with this island
 				while island_strips:
 					best = 0
 					if cache:
+						# Find the strip that benefits the most from the current
+						# contents of the vertex cache
 						best_hits = 0
 						for i in range(len(island_strips)):
 							hits = cache.test_strip(island_strips[i])
@@ -143,28 +152,23 @@ class Exporter:
 								best = i
 								best_hits = hits
 
-					s = island_strips[best]
-					del island_strips[best]
-					strips.append(s)
+					strip = island_strips.pop(best)
+					strips.append(strip)
 
 					if cache:
-						cache.fetch_strip(s)
+						cache.fetch_strip(strip)
 
 				faces_done += len(island)
 				if progress:
 					progress.set_progress(float(faces_done)/len(mesh.faces))
 
+				# Collect any faces that weren't used in strips
 				loose += [f for f in island if not f.flag]
 				for f in island:
 					f.flag = True
 
 				island = []
 				island_strips = []
-				continue
-
-			strip = mesh.create_strip(face, self.max_strip_len)
-			if strip:
-				island_strips.append(strip)
 
 		if cache:
 			cache = VertexCache(self.cache_size)
@@ -175,6 +179,8 @@ class Exporter:
 
 			for s in strips:
 				if big_strip:
+					# Generate glue elements, ensuring that the next strip begins at
+					# an even position
 					glue = [big_strip[-1], s[0]]
 					if len(big_strip)%2:
 						glue += [s[0]]
@@ -188,6 +194,8 @@ class Exporter:
 					total_hits += cache.fetch_strip(s)
 
 			for f in loose:
+				# Add loose faces to the end.  This wastes space, using five
+				# elements per triangle and six elements per quad.
 				if len(big_strip)%2:
 					order = (-1, -2, 0, 1)
 				else:
diff --git a/blender/io_mesh_mspgl/mesh.py b/blender/io_mesh_mspgl/mesh.py
index 8b3ad370..d674dbdb 100644
--- a/blender/io_mesh_mspgl/mesh.py
+++ b/blender/io_mesh_mspgl/mesh.py
@@ -90,6 +90,10 @@ class Face:
 				return e
 		raise KeyError("No edge %s"%(key,))
 
+	def get_neighbors(self):
+		neighbors = [e.other_face(f) for e in self.edges]
+		return list(filter(bool, neighbors))
+
 
 class Line:
 	def __init__(self, e):
@@ -358,6 +362,7 @@ class Mesh:
 				v.bino.normalize()
 
 	def create_strip(self, face, max_len):
+		# Find an edge with another unused face next to it
 		edge = None
 		for e in face.edges:
 			other = e.other_face(face)
@@ -368,6 +373,8 @@ class Mesh:
 		if not edge:
 			return None
 
+		# Add initial vertices so that we'll complete the edge on the first
+		# iteration
 		vertices = face.pivot_vertices(*edge.vertices)
 		if len(vertices)==3:
 			result = [vertices[-1], vertices[0]]
@@ -375,10 +382,13 @@ class Mesh:
 			result = [vertices[-2], vertices[-1]]
 
 		while 1:
+			face.flag = True
+
 			vertices = face.pivot_vertices(*result[-2:])
 			k = len(result)%2
 
-			face.flag = True
+			# Quads need special handling because the winding of every other
+			# triangle in the strip is reversed
 			if len(vertices)==4 and not k:
 				result.append(vertices[3])
 			result.append(vertices[2])
@@ -388,11 +398,10 @@ class Mesh:
 			if len(result)>=max_len:
 				break
 
+			# Hop over the last edge
 			edge = face.get_edge(*result[-2:])
-
-			next = edge.other_face(face)
-			if not next or next.flag:
+			face = edge.other_face(face)
+			if not face or face.flag:
 				break
-			face = next
 
 		return result
-- 
2.43.0