# HG changeset patch
# User Teemu Piippo <teemu.s.piippo@gmail.com>
# Date 1656848106 -10800
# Node ID af6633412a6cd72dfef6df6879f0e0d3b60e02da
# Parent  9727e545b0bc766545e4072c4a56fe517a02d6ec
Cleanup polygonize a bit

diff -r 9727e545b0bc -r af6633412a6c src/layers/edittools.cpp
--- a/src/layers/edittools.cpp	Sun Jul 03 13:44:11 2022 +0300
+++ b/src/layers/edittools.cpp	Sun Jul 03 14:35:06 2022 +0300
@@ -440,8 +440,7 @@
 	else if (this->numpoints > 2) {
 		for (const PlainPolygonElement& poly : polygonize(
 			this->polygon.begin(),
-			this->polygon.begin() + static_cast<long>(this->numpoints),
-			this->gridMatrix)
+			this->polygon.begin() + static_cast<long>(this->numpoints))
 		) {
 			result.push_back(AppendToModel{
 				.newElement = elementFromPolygonAndColor(poly, MAIN_COLOR),
diff -r 9727e545b0bc -r af6633412a6c src/triangulate.cpp
--- a/src/triangulate.cpp	Sun Jul 03 13:44:11 2022 +0300
+++ b/src/triangulate.cpp	Sun Jul 03 14:35:06 2022 +0300
@@ -13,36 +13,58 @@
 	static constexpr float get(const glm::vec3& t) { return t.y; }
 };
 
-using indextype = std::uint16_t;
-using indexpair = std::pair<indextype, indextype>;
-struct boundaryinfo
+namespace triangulate
 {
-	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;
-};
+	struct triangleid
+	{
+		std::size_t id;
+		constexpr auto operator<=>(const triangleid&) const = default;
+	};
+	//! \brief Index type of vertex
+	using index_t = std::uint16_t;
+	//! \brief Pair of vertex indices, forming a triangle boundary
+	using boundary_t = std::pair<index_t, index_t>;
+	//! \brief Additional information about a triangle boundary
+	struct triangleinfo
+	{
+		//! \brief What's the third vertex of this triangle
+		index_t third_vertex;
+		//! \brief Id of triangle (starting position of the triangle in the result
+		//! value of mapbox::earcut)
+		triangleid triangleid;
+	};
+	using triangleinfomap_t = std::map<boundary_t, triangleinfo>;
+	struct MergedTriangles
+	{
+		//! \brief List of merged quadrilaterals
+		std::vector<Quadrilateral> quadrilaterals;
+		//! \brief Ids of cut triangles
+		std::set<triangleid> cutTriangles;
+	};
+	static MergedTriangles mergeTriangles(
+		const std::vector<std::uint16_t>& indices,
+		std::vector<glm::vec3>::const_iterator polyBegin);
+}
 
 static bool findQuadsToMerge(
-	const boundarymap_t& boundaries,
+	const triangulate::triangleinfomap_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;
+	for (
+		triangulate::triangleinfomap_t::const_iterator it1 = boundaries.begin();
+		it1 != boundaries.end();
+		++it1
+	) {
+		const triangulate::boundary_t& boundary = it1->first;
+		const triangulate::triangleinfo& earcut_triangle_1 = it1->second;
 		// .. the ones we haven't already been merged...
-		if (not iscut(boundary1.triangleid)) {
+		if (not iscut(earcut_triangle_1.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);
+			const triangulate::boundary_t inverse_boundary = std::make_pair(boundary.second, boundary.first);
+			const triangulate::triangleinfomap_t::const_iterator it2 = boundaries.find(inverse_boundary);
 			// 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
@@ -53,42 +75,45 @@
 	return foundQuads;
 }
 
-static MergedTriangles mergeTriangles(
+static triangulate::MergedTriangles triangulate::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){
+	const auto iscut = [&result](const triangleid i){
 		return result.cutTriangles.find(i) != result.cutTriangles.end();
 	};
 	const auto addMergedQuad = [&result, polyBegin](
-		boundarymap_t::const_iterator it1,
-		boundarymap_t::const_iterator it2
+		triangleinfomap_t::const_iterator it1,
+		triangleinfomap_t::const_iterator it2
 	) {
-		const indexpair& common_indices = it1->first;
-		const boundaryinfo& boundary_1 = it1->second;
-		const boundaryinfo& boundary_2 = it2->second;
+		const boundary_t& shared_boundary = it1->first;
+		const triangleinfo& earcut_triangle_1 = it1->second;
+		const triangleinfo& earcut_triangle_2 = it2->second;
 		const Quadrilateral quad{
-			*(polyBegin + common_indices.first),
-			*(polyBegin + boundary_2.third),
-			*(polyBegin + common_indices.second),
-			*(polyBegin + boundary_1.third),
+			*(polyBegin + shared_boundary.first),
+			*(polyBegin + earcut_triangle_2.third_vertex),
+			*(polyBegin + shared_boundary.second),
+			*(polyBegin + earcut_triangle_1.third_vertex),
 		};
 		if (isConvex(quad)) {
 			result.quadrilaterals.push_back(quad);
-			result.cutTriangles.insert(boundary_1.triangleid);
-			result.cutTriangles.insert(boundary_2.triangleid);
+			result.cutTriangles.insert(earcut_triangle_1.triangleid);
+			result.cutTriangles.insert(earcut_triangle_2.triangleid);
 			return true;
 		}
 		else {
 			return false;
 		}
 	};
-	boundarymap_t boundaries;
+	triangleinfomap_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};
+			boundaries[key] = triangleinfo{
+				.third_vertex = indices[i + o3],
+				.triangleid = {i},
+			};
 		};
 		add(0, 1, 2);
 		add(1, 2, 0);
@@ -101,41 +126,35 @@
 	return result;
 }
 
+//! \brief Polygonize a polygon into triangles and try merge as many of them
+//! as possible into quadrilaterals. The polygons must all reside in the same
+//! plane.
 std::vector<PlainPolygonElement> polygonize(
 	std::vector<glm::vec3>::const_iterator begin,
-	std::vector<glm::vec3>::const_iterator end,
-	const glm::mat4& planeMatrix)
+	std::vector<glm::vec3>::const_iterator end)
 {
 	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)));
+	const glm::vec3 xvec = *begin - *(begin + 1);
+	const glm::vec3 yvec = *(begin + 2) - *(begin + 1);
+	const glm::vec3 zvec = glm::cross(xvec, yvec);
+	const glm::mat3 inverseMatrix = glm::inverse(glm::mat3{xvec, yvec, zvec});
 	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});
+		polygon2d.push_back(inverseMatrix * glm::vec4{*it, 1});
 	}
-	const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons);
-	MergedTriangles mergedTriangles = mergeTriangles(indices, begin);
+	const std::vector<triangulate::index_t> indices = mapbox::earcut<triangulate::index_t>(polygons);
+	triangulate::MergedTriangles mergedTriangles = triangulate::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()) {
+		if (not mergedTriangles.cutTriangles.contains({i})) {
 			Triangle tri = triangle(
 				*(begin + indices[i]),
 				*(begin + indices[i + 1]),
 				*(begin + indices[i + 2]));
-			if (shouldInvert < 0) {
-				invert(tri);
-			}
 			result.push_back(tri);
 		}
 	}
diff -r 9727e545b0bc -r af6633412a6c src/triangulate.h
--- a/src/triangulate.h	Sun Jul 03 13:44:11 2022 +0300
+++ b/src/triangulate.h	Sun Jul 03 14:35:06 2022 +0300
@@ -4,5 +4,4 @@
 
 std::vector<PlainPolygonElement> polygonize(
 	std::vector<glm::vec3>::const_iterator begin,
-	std::vector<glm::vec3>::const_iterator end,
-	const glm::mat4& planeMatrix);
+	std::vector<glm::vec3>::const_iterator end);