# HG changeset patch
# User Teemu Piippo <teemu.s.piippo@gmail.com>
# Date 1656845051 -10800
# Node ID 9727e545b0bc766545e4072c4a56fe517a02d6ec
# Parent  216f02b50b0af7f6ae79f7ecc934fbbbe25f1c9c
Extract the triangulation and triangle merging code into a new source file and clean it up somewhat

diff -r 216f02b50b0a -r 9727e545b0bc CMakeLists.txt
--- a/CMakeLists.txt	Sun Jul 03 13:21:49 2022 +0300
+++ b/CMakeLists.txt	Sun Jul 03 13:44:11 2022 +0300
@@ -74,6 +74,7 @@
 	src/model.cpp
 	src/parser.cpp
 	src/polygoncache.cpp
+	src/triangulate.cpp
 	src/uiutilities.cpp
 	src/version.cpp
 	src/vertexmap.cpp
@@ -106,6 +107,7 @@
 	src/parser.h
 	src/polygoncache.h
 	src/settings.h
+	src/triangulate.h
 	src/typeconversions.h
 	src/uiutilities.h
 	src/version.h
diff -r 216f02b50b0a -r 9727e545b0bc src/layers/edittools.cpp
--- a/src/layers/edittools.cpp	Sun Jul 03 13:21:49 2022 +0300
+++ b/src/layers/edittools.cpp	Sun Jul 03 13:44:11 2022 +0300
@@ -18,24 +18,13 @@
 
 #include <QMouseEvent>
 #include <QPainter>
-#include "thirdparty/earcut.h"
 #include "src/model.h"
 #include "src/ui/objecteditor.h"
 #include "src/gl/partrenderer.h"
 #include "src/circularprimitive.h"
 #include "src/layers/edittools.h"
 #include "src/invert.h"
-
-// Make mapbox::earcut work with glm::vec3
-template<> struct mapbox::util::nth<0, glm::vec3>
-{
-	static constexpr float get(const glm::vec3& t) { return t.x; }
-};
-
-template<> struct mapbox::util::nth<1, glm::vec3>
-{
-	static constexpr float get(const glm::vec3& t) { return t.y; }
-};
+#include "src/triangulate.h"
 
 EditTools::EditTools(QObject* parent) :
 	QObject{parent},
@@ -416,68 +405,6 @@
 	}
 }
 
-struct MergedTriangles
-{
-	std::vector<Quadrilateral> quadrilaterals;
-	std::set<std::size_t> cutTriangles;
-};
-
-static MergedTriangles mergeTriangles(
-	const std::vector<std::uint16_t>& indices,
-	const std::vector<glm::vec3>& polygon)
-{
-	MergedTriangles result;
-	using indextype = std::uint16_t;
-	using indexpair = std::pair<indextype, indextype>;
-	struct boundaryinfo { indextype third; std::size_t triangleid; };
-	std::map<indexpair, boundaryinfo> boundaries;
-	for (std::size_t i = 0; i < indices.size(); i += 3) {
-		const auto add = [&](const std::size_t o1, const std::size_t o2, const std::size_t o3){
-			const auto key = std::make_pair(indices[i + o1], indices[i + o2]);
-			boundaries[key] = {indices[i + o3], i};
-		};
-		add(0, 1, 2);
-		add(1, 2, 0);
-		add(2, 0, 1);
-	}
-	std::vector<std::array<indextype, 4>> quadindices;
-	std::vector<Quadrilateral> quads;
-	bool repeat = true;
-	const auto iscut = [&result](const std::size_t i){
-		return result.cutTriangles.find(i) != result.cutTriangles.end();
-	};
-	while (repeat) {
-		repeat = false;
-		// Go through triangle boundaries
-		for (const auto& it1 : boundaries) {
-			const indexpair& pair1 = it1.first;
-			const boundaryinfo& boundary1 = it1.second;
-			// .. the ones we haven't already merged anyway
-			if (not iscut(boundary1.triangleid)) {
-				// Look for its inverse boundary to find the touching triangle
-				const auto pair2 = std::make_pair(pair1.second, pair1.first);
-				const auto it2 = boundaries.find(pair2);
-				// Also if that hasn't been cut
-				if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) {
-					const Quadrilateral quad{
-						polygon[pair1.first],
-						polygon[it2->second.third],
-						polygon[pair1.second],
-						polygon[boundary1.third],
-					};
-					if (isConvex(quad)) {
-						result.quadrilaterals.push_back(quad);
-						result.cutTriangles.insert(boundary1.triangleid);
-						result.cutTriangles.insert(it2->second.triangleid);
-						repeat = true;
-					}
-				}
-			}
-		}
-	}
-	return result;
-}
-
 
 const std::vector<ModelAction> EditTools::circleModeActions() const
 {
@@ -511,41 +438,15 @@
 		result.push_back(AppendToModel{edge(this->polygon[0], this->polygon[1])});
 	}
 	else if (this->numpoints > 2) {
-		const glm::mat4 inverseGrid = glm::inverse(this->gridMatrix);
-		std::vector<std::vector<glm::vec3>> polygons{1};
-		std::vector<glm::vec3>& polygon2d = polygons.back();
-		polygon2d.reserve(this->numpoints);
-		for (std::size_t i = 0; i < this->numpoints; ++i) {
-			polygon2d.push_back(inverseGrid * glm::vec4{this->polygon[i], 1});
-		}
-		// mapbox::earcut will always produce a CCW polygon, so if we're drawing
-		// a CW polygon, we should invert the result afterwards
-		const float shouldInvert = glm::dot(
-			glm::vec3{inverseGrid[2]},
-			glm::cross(this->polygon[0] - this->polygon[1], this->polygon[2] - this->polygon[1]));
-		using indextype = std::uint16_t;
-		const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons);
-		MergedTriangles mergedTriangles = mergeTriangles(indices, this->polygon);
-		for (Quadrilateral& quad : mergedTriangles.quadrilaterals) {
-			if (shouldInvert < 0) {
-				invert(quad);
-			}
+		for (const PlainPolygonElement& poly : polygonize(
+			this->polygon.begin(),
+			this->polygon.begin() + static_cast<long>(this->numpoints),
+			this->gridMatrix)
+		) {
 			result.push_back(AppendToModel{
-				.newElement = Colored<Quadrilateral>{quad, MAIN_COLOR},
+				.newElement = elementFromPolygonAndColor(poly, MAIN_COLOR),
 			});
 		}
-		for (std::size_t i = 0; i < indices.size(); i += 3) {
-			if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) {
-				Colored<Triangle> tri = triangle(
-					this->polygon[indices[i]],
-					this->polygon[indices[i + 1]],
-					this->polygon[indices[i + 2]]);
-				if (shouldInvert < 0) {
-					invert(tri);
-				}
-				result.push_back(AppendToModel{tri});
-			}
-		}
 	}
 	return result;
 }
diff -r 216f02b50b0a -r 9727e545b0bc src/triangulate.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/triangulate.cpp	Sun Jul 03 13:44:11 2022 +0300
@@ -0,0 +1,143 @@
+#include "src/triangulate.h"
+#include "thirdparty/earcut.h"
+#include "src/invert.h"
+
+// Make mapbox::earcut work with glm::vec3
+template<> struct mapbox::util::nth<0, glm::vec3>
+{
+	static constexpr float get(const glm::vec3& t) { return t.x; }
+};
+
+template<> struct mapbox::util::nth<1, glm::vec3>
+{
+	static constexpr float get(const glm::vec3& t) { return t.y; }
+};
+
+using indextype = std::uint16_t;
+using indexpair = std::pair<indextype, indextype>;
+struct boundaryinfo
+{
+	indextype third;
+	std::size_t triangleid;
+};
+using boundarymap_t = std::map<indexpair, boundaryinfo>;
+
+struct MergedTriangles
+{
+	std::vector<Quadrilateral> quadrilaterals;
+	std::set<std::size_t> cutTriangles;
+};
+
+static bool findQuadsToMerge(
+	const boundarymap_t& boundaries,
+	auto&& iscut,
+	auto&& addMergedQuad
+) {
+	bool foundQuads = false;
+	// Go through triangle boundaries
+	for (boundarymap_t::const_iterator it1 = boundaries.begin(); it1 != boundaries.end(); ++it1) {
+		const indexpair& pair1 = it1->first;
+		const boundaryinfo& boundary1 = it1->second;
+		// .. the ones we haven't already been merged...
+		if (not iscut(boundary1.triangleid)) {
+			// Look for its inverse boundary to find the touching triangle
+			const indexpair inverse_boundary_key = std::make_pair(pair1.second, pair1.first);
+			const boundarymap_t::const_iterator it2 = boundaries.find(inverse_boundary_key);
+			// Also if that hasn't been cut
+			if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) {
+				// Continue until no more new quads are found
+				foundQuads |= addMergedQuad(it1, it2);
+			}
+		}
+	}
+	return foundQuads;
+}
+
+static MergedTriangles mergeTriangles(
+	const std::vector<std::uint16_t>& indices,
+	std::vector<glm::vec3>::const_iterator polyBegin)
+{
+	MergedTriangles result;
+	const auto iscut = [&result](const std::size_t i){
+		return result.cutTriangles.find(i) != result.cutTriangles.end();
+	};
+	const auto addMergedQuad = [&result, polyBegin](
+		boundarymap_t::const_iterator it1,
+		boundarymap_t::const_iterator it2
+	) {
+		const indexpair& common_indices = it1->first;
+		const boundaryinfo& boundary_1 = it1->second;
+		const boundaryinfo& boundary_2 = it2->second;
+		const Quadrilateral quad{
+			*(polyBegin + common_indices.first),
+			*(polyBegin + boundary_2.third),
+			*(polyBegin + common_indices.second),
+			*(polyBegin + boundary_1.third),
+		};
+		if (isConvex(quad)) {
+			result.quadrilaterals.push_back(quad);
+			result.cutTriangles.insert(boundary_1.triangleid);
+			result.cutTriangles.insert(boundary_2.triangleid);
+			return true;
+		}
+		else {
+			return false;
+		}
+	};
+	boundarymap_t boundaries;
+	for (std::size_t i = 0; i < indices.size(); i += 3) {
+		const auto add = [&](const std::size_t o1, const std::size_t o2, const std::size_t o3){
+			const auto key = std::make_pair(indices[i + o1], indices[i + o2]);
+			boundaries[key] = {indices[i + o3], i};
+		};
+		add(0, 1, 2);
+		add(1, 2, 0);
+		add(2, 0, 1);
+	}
+	bool repeat = true;
+	while (repeat) {
+		repeat = findQuadsToMerge(boundaries, iscut, addMergedQuad);
+	}
+	return result;
+}
+
+std::vector<PlainPolygonElement> polygonize(
+	std::vector<glm::vec3>::const_iterator begin,
+	std::vector<glm::vec3>::const_iterator end,
+	const glm::mat4& planeMatrix)
+{
+	std::vector<PlainPolygonElement> result;
+	const glm::mat4 inverseGrid = glm::inverse(planeMatrix);
+	// mapbox::earcut will always produce a CCW polygon, so if we're drawing
+	// a CW polygon, we should invert the result afterwards
+	const float shouldInvert = glm::dot(
+		glm::vec3{inverseGrid[2]},
+		glm::cross(*begin - *(begin + 1), *(begin + 2) - *(begin + 1)));
+	std::vector<std::vector<glm::vec3>> polygons{1};
+	std::vector<glm::vec3>& polygon2d = polygons.back();
+	polygon2d.reserve(static_cast<std::size_t>(end - begin));
+	for (std::vector<glm::vec3>::const_iterator it = begin; it != end; ++it) {
+		polygon2d.push_back(inverseGrid * glm::vec4{*it, 1});
+	}
+	const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons);
+	MergedTriangles mergedTriangles = mergeTriangles(indices, begin);
+	for (Quadrilateral& quad : mergedTriangles.quadrilaterals) {
+		if (shouldInvert < 0) {
+			invert(quad);
+		}
+		result.push_back(quad);
+	}
+	for (std::size_t i = 0; i < indices.size(); i += 3) {
+		if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) {
+			Triangle tri = triangle(
+				*(begin + indices[i]),
+				*(begin + indices[i + 1]),
+				*(begin + indices[i + 2]));
+			if (shouldInvert < 0) {
+				invert(tri);
+			}
+			result.push_back(tri);
+		}
+	}
+	return result;
+}
diff -r 216f02b50b0a -r 9727e545b0bc src/triangulate.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/triangulate.h	Sun Jul 03 13:44:11 2022 +0300
@@ -0,0 +1,8 @@
+#pragma once
+#include "src/basics.h"
+#include "src/model.h"
+
+std::vector<PlainPolygonElement> polygonize(
+	std::vector<glm::vec3>::const_iterator begin,
+	std::vector<glm::vec3>::const_iterator end,
+	const glm::mat4& planeMatrix);