From 3aefe3f4132cccc64d21fd7a0ca14eb5967d77f5 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Sun, 5 May 2019 02:16:22 +0300
Subject: [PATCH] Explicitly triangulate faces in the Blender exporter

Previously they were implicitly triangulated during strip generation,
with the idea that it would be more flexible.  However I have some
doubts of its benefits and existing strip generation algorithms tend
to deal exclusively in triangles.
---
 blender/io_mspgl/mesh.py | 70 ++++++++++++++++++++++++++++++++++++++--
 1 file changed, 67 insertions(+), 3 deletions(-)

diff --git a/blender/io_mspgl/mesh.py b/blender/io_mspgl/mesh.py
index b58637b7..10c2c214 100644
--- a/blender/io_mspgl/mesh.py
+++ b/blender/io_mspgl/mesh.py
@@ -9,12 +9,16 @@ class Edge:
 	def __init__(self, edge):
 		if edge.__class__==Edge:
 			self._edge = edge._edge
-			self.vertices = edge.vertices[:]
 			self.smooth = edge.smooth
 		else:
 			self._edge = edge
 			self.smooth = False
-		self.key = edge.key
+		if edge:
+			self.vertices = edge.vertices[:]
+			self.key = edge.key
+		else:
+			self.vertices = []
+			self.key = None
 		self.faces = []
 
 	def __getattr__(self, attr):
@@ -275,6 +279,64 @@ class Mesh:
 
 		self.lines += other.lines
 
+	def prepare_triangles(self, progress):
+		face_count = len(self.faces)
+		for i in range(face_count):
+			f = self.faces[i]
+			nverts = len(f.vertices)
+			if nverts==3:
+				continue
+
+			# Calculate normals at each vertex of the face
+			edge_vecs = []
+			for j in range(nverts):
+				edge_vecs.append(f.vertices[(j+1)%nverts].co-f.vertices[j].co)
+
+			normals = []
+			for j in range(nverts):
+				normals.append(edge_vecs[j].cross(edge_vecs[j-1]).normalized())
+
+			# Check which diagonal results in a flatter triangulation
+			flatness1 = normals[0].dot(normals[2])
+			flatness2 = normals[1].dot(normals[3])
+			cut_index = 1 if flatness1>flatness2 else 0
+
+			nf = Face(f)
+			nf.index = len(self.faces)
+			self.faces.append(nf)
+
+			ne = Edge(None)
+			ne.index = len(self.edges)
+			self.edges.append(ne)
+
+			nf.vertices = [f.vertices[cut_index], f.vertices[2], f.vertices[3]]
+			nf.loop_indices = [f.loop_indices[cut_index], f.loop_indices[2], f.loop_indices[3]]
+			for v in nf.vertices:
+				v.faces.append(nf)
+
+			ne.vertices = [f.vertices[cut_index], f.vertices[2+cut_index]]
+			for v in ne.vertices:
+				v.edges.append(ne)
+			ne.key = make_edge_key(ne.vertices[0].index, ne.vertices[1].index)
+			ne.smooth = True
+
+			f.vertices[3-cut_index].faces.remove(f)
+			del f.vertices[3-cut_index]
+			f.loop_indices = [f.loop_indices[0], f.loop_indices[1], f.loop_indices[2+cut_index]]
+
+			ne.faces = [f, nf]
+			if cut_index==0:
+				nf.edges = [ne, f.edges[2], f.edges[3]]
+				f.edges = [f.edges[0], f.edges[1], ne]
+			else:
+				nf.edges = [f.edges[1], f.edges[2], ne]
+				f.edges = [f.edges[0], ne, f.edges[3]]
+
+			f.normal = normals[1-cut_index]
+			nf.normal = normals[3-cut_index]
+
+			progress.set_progress(i/face_count)
+
 	def prepare_smoothing(self, progress):
 		smooth_limit = -1
 		if self.smoothing=='NONE':
@@ -594,7 +656,7 @@ def create_mesh_from_object(context, obj, progress):
 	if obj.type!="MESH":
 		raise Exception("Object is not a mesh")
 
-	progress.push_task("Preparing mesh", 0.0, 0.3)
+	progress.push_task("Preparing mesh", 0.0, 0.2)
 
 	objs = [(obj, mathutils.Matrix())]
 	i = 0
@@ -629,6 +691,8 @@ def create_mesh_from_object(context, obj, progress):
 		else:
 			mesh = me
 
+	progress.set_task("Triangulating", 0.2, 0.3)
+	mesh.prepare_triangles(progress)
 	progress.set_task("Smoothing", 0.3, 0.6)
 	mesh.prepare_smoothing(progress)
 	progress.set_task("Vertex groups", 0.6, 0.7)
-- 
2.45.2