xatlas: Redo our custom changes, but properly documented

4 files changed, 268 insertions, 3 deletions

diff --git a/thirdparty/xatlas/avoid-failing-on-bad-geometry.patch b/thirdparty/xatlas/avoid-failing-on-bad-geometry.patch
new file mode 100644
index 0000000000..a28cd9f82b
--- /dev/null
+++ b/thirdparty/xatlas/avoid-failing-on-bad-geometry.patch
@@ -0,0 +1,157 @@
+diff --git a/thirdparty/xatlas/xatlas.cpp b/thirdparty/xatlas/xatlas.cpp
+index df5ef94db..eb0824a51 100644
+--- a/thirdparty/xatlas/xatlas.cpp
++++ b/thirdparty/xatlas/xatlas.cpp
+@@ -1276,6 +1276,9 @@ class Vertex
+ {
+ public:
+ 	uint32_t id;
++	// -- GODOT start --
++	uint32_t original_id;
++	// -- GODOT end --
+ 	Edge *edge;
+ 	Vertex *next;
+ 	Vertex *prev;
+@@ -1283,7 +1286,10 @@ public:
+ 	Vector3 nor;
+ 	Vector2 tex;
+ 
+-	Vertex(uint32_t id) : id(id), edge(NULL), pos(0.0f), nor(0.0f), tex(0.0f)
++	// -- GODOT start --
++	//Vertex(uint32_t id) : id(id), edge(NULL), pos(0.0f), nor(0.0f), tex(0.0f)
++	Vertex(uint32_t id) : id(id), original_id(id), edge(NULL), pos(0.0f), nor(0.0f), tex(0.0f)
++	// -- GODOT end --
+ 	{
+ 		next = this;
+ 		prev = this;
+@@ -1934,6 +1940,64 @@ public:
+ 		return f;
+ 	}
+ 
++	// -- GODOT start --
++	Face *addUniqueFace(uint32_t v0, uint32_t v1, uint32_t v2) {
++
++		int base_vertex = m_vertexArray.size();
++
++		uint32_t ids[3] = { v0, v1, v2 };
++
++		Vector3 base[3] = {
++			m_vertexArray[v0]->pos,
++			m_vertexArray[v1]->pos,
++			m_vertexArray[v2]->pos,
++		};
++
++		//make sure its not a degenerate
++		bool degenerate = distanceSquared(base[0], base[1]) < NV_EPSILON || distanceSquared(base[0], base[2]) < NV_EPSILON || distanceSquared(base[1], base[2]) < NV_EPSILON;
++		xaDebugAssert(!degenerate);
++
++		float min_x = 0;
++
++		for (int i = 0; i < 3; i++) {
++			if (i == 0 || m_vertexArray[v0]->pos.x < min_x) {
++				min_x = m_vertexArray[v0]->pos.x;
++			}
++		}
++
++		float max_x = 0;
++
++		for (int j = 0; j < m_vertexArray.size(); j++) {
++			if (j == 0 || m_vertexArray[j]->pos.x > max_x) { //vertex already exists
++				max_x = m_vertexArray[j]->pos.x;
++			}
++		}
++
++		//separate from everything else, in x axis
++		for (int i = 0; i < 3; i++) {
++
++			base[i].x -= min_x;
++			base[i].x += max_x + 10.0;
++		}
++
++		for (int i = 0; i < 3; i++) {
++			Vertex *v = new Vertex(m_vertexArray.size());
++			v->pos = base[i];
++			v->nor = m_vertexArray[ids[i]]->nor,
++			v->tex = m_vertexArray[ids[i]]->tex,
++
++			v->original_id = ids[i];
++			m_vertexArray.push_back(v);
++		}
++
++		uint32_t indexArray[3];
++		indexArray[0] = base_vertex + 0;
++		indexArray[1] = base_vertex + 1;
++		indexArray[2] = base_vertex + 2;
++		return addFace(indexArray, 3, 0, 3);
++	}
++	// -- GODOT end --
++
+ 	// These functions disconnect the given element from the mesh and delete it.
+ 
+ 	// @@ We must always disconnect edge pairs simultaneously.
+@@ -2915,6 +2979,14 @@ Mesh *triangulate(const Mesh *inputMesh)
+ 					Vector2 p0 = polygonPoints[i0];
+ 					Vector2 p1 = polygonPoints[i1];
+ 					Vector2 p2 = polygonPoints[i2];
++
++					// -- GODOT start --
++					bool degenerate = distance(p0, p1) < NV_EPSILON || distance(p0, p2) < NV_EPSILON || distance(p1, p2) < NV_EPSILON;
++					if (degenerate) {
++						continue;
++					}
++					// -- GODOT end --
++
+ 					float d = clamp(dot(p0 - p1, p2 - p1) / (length(p0 - p1) * length(p2 - p1)), -1.0f, 1.0f);
+ 					float angle = acosf(d);
+ 					float area = triangleArea(p0, p1, p2);
+@@ -2938,6 +3010,11 @@ Mesh *triangulate(const Mesh *inputMesh)
+ 						}
+ 					}
+ 				}
++				// -- GODOT start --
++				if (!bestIsValid)
++					break;
++				// -- GODOT end --
++
+ 				xaDebugAssert(minAngle <= 2 * PI);
+ 				// Clip best ear:
+ 				uint32_t i0 = (bestEar + size - 1) % size;
+@@ -5606,7 +5683,10 @@ public:
+ 				}
+ 				if (chartMeshIndices[vertex->id] == ~0) {
+ 					chartMeshIndices[vertex->id] = m_chartMesh->vertexCount();
+-					m_chartToOriginalMap.push_back(vertex->id);
++					// -- GODOT start --
++					//m_chartToOriginalMap.push_back(vertex->id);
++					m_chartToOriginalMap.push_back(vertex->original_id);
++					// -- GODOT end --
+ 					m_chartToUnifiedMap.push_back(unifiedMeshIndices[unifiedVertex->id]);
+ 					halfedge::Vertex *v = m_chartMesh->addVertex(vertex->pos);
+ 					v->nor = vertex->nor;
+@@ -5699,7 +5779,10 @@ public:
+ 				const halfedge::Vertex *vertex = it.current()->vertex;
+ 				if (chartMeshIndices[vertex->id] == ~0) {
+ 					chartMeshIndices[vertex->id] = m_chartMesh->vertexCount();
+-					m_chartToOriginalMap.push_back(vertex->id);
++					// -- GODOT start --
++					//m_chartToOriginalMap.push_back(vertex->id);
++					m_chartToOriginalMap.push_back(vertex->original_id);
++					// -- GODOT end --
+ 					halfedge::Vertex *v = m_chartMesh->addVertex(vertex->pos);
+ 					v->nor = vertex->nor;
+ 					v->tex = vertex->tex; // @@ Not necessary.
+@@ -7573,6 +7656,14 @@ AddMeshError AddMesh(Atlas *atlas, const InputMesh &mesh, bool useColocalVertice
+ 			}
+ 		}
+ 		internal::halfedge::Face *face = heMesh->addFace(tri[0], tri[1], tri[2]);
++
++		// -- GODOT start --
++		if (!face && heMesh->errorCode == internal::halfedge::Mesh::ErrorCode::AlreadyAddedEdge) {
++			//there is still hope for this, no reason to not add, at least add as separate
++			face = heMesh->addUniqueFace(tri[0], tri[1], tri[2]);
++		}
++		// -- GODOT end --
++
+ 		if (!face) {
+ 			if (heMesh->errorCode == internal::halfedge::Mesh::ErrorCode::AlreadyAddedEdge)
+ 				error.code = AddMeshErrorCode::AlreadyAddedEdge;
diff --git a/thirdparty/xatlas/build-fix-limits.patch b/thirdparty/xatlas/build-fix-limits.patch
new file mode 100644
index 0000000000..00d07371c0
--- /dev/null
+++ b/thirdparty/xatlas/build-fix-limits.patch
@@ -0,0 +1,14 @@
+diff --git a/thirdparty/xatlas/xatlas.h b/thirdparty/xatlas/xatlas.h
+index 7e556c6c3..dbf8ca08c 100644
+--- a/thirdparty/xatlas/xatlas.h
++++ b/thirdparty/xatlas/xatlas.h
+@@ -3,6 +3,9 @@
+ #ifndef XATLAS_H
+ #define XATLAS_H
+ #include <float.h> // FLT_MAX
++// -- GODOT start --
++#include <limits.h> // INT_MAX, UINT_MAX
++// -- GODOT end --
+ 
+ namespace xatlas {
+ 
diff --git a/thirdparty/xatlas/xatlas.cpp b/thirdparty/xatlas/xatlas.cpp
index df5ef94dbb..eb0824a517 100644
--- a/thirdparty/xatlas/xatlas.cpp
+++ b/thirdparty/xatlas/xatlas.cpp
@@ -1276,6 +1276,9 @@ class Vertex
 {
 public:
 	uint32_t id;
+	// -- GODOT start --
+	uint32_t original_id;
+	// -- GODOT end --
 	Edge *edge;
 	Vertex *next;
 	Vertex *prev;
@@ -1283,7 +1286,10 @@ public:
 	Vector3 nor;
 	Vector2 tex;
 
-	Vertex(uint32_t id) : id(id), edge(NULL), pos(0.0f), nor(0.0f), tex(0.0f)
+	// -- GODOT start --
+	//Vertex(uint32_t id) : id(id), edge(NULL), pos(0.0f), nor(0.0f), tex(0.0f)
+	Vertex(uint32_t id) : id(id), original_id(id), edge(NULL), pos(0.0f), nor(0.0f), tex(0.0f)
+	// -- GODOT end --
 	{
 		next = this;
 		prev = this;
@@ -1934,6 +1940,64 @@ public:
 		return f;
 	}
 
+	// -- GODOT start --
+	Face *addUniqueFace(uint32_t v0, uint32_t v1, uint32_t v2) {
+
+		int base_vertex = m_vertexArray.size();
+
+		uint32_t ids[3] = { v0, v1, v2 };
+
+		Vector3 base[3] = {
+			m_vertexArray[v0]->pos,
+			m_vertexArray[v1]->pos,
+			m_vertexArray[v2]->pos,
+		};
+
+		//make sure its not a degenerate
+		bool degenerate = distanceSquared(base[0], base[1]) < NV_EPSILON || distanceSquared(base[0], base[2]) < NV_EPSILON || distanceSquared(base[1], base[2]) < NV_EPSILON;
+		xaDebugAssert(!degenerate);
+
+		float min_x = 0;
+
+		for (int i = 0; i < 3; i++) {
+			if (i == 0 || m_vertexArray[v0]->pos.x < min_x) {
+				min_x = m_vertexArray[v0]->pos.x;
+			}
+		}
+
+		float max_x = 0;
+
+		for (int j = 0; j < m_vertexArray.size(); j++) {
+			if (j == 0 || m_vertexArray[j]->pos.x > max_x) { //vertex already exists
+				max_x = m_vertexArray[j]->pos.x;
+			}
+		}
+
+		//separate from everything else, in x axis
+		for (int i = 0; i < 3; i++) {
+
+			base[i].x -= min_x;
+			base[i].x += max_x + 10.0;
+		}
+
+		for (int i = 0; i < 3; i++) {
+			Vertex *v = new Vertex(m_vertexArray.size());
+			v->pos = base[i];
+			v->nor = m_vertexArray[ids[i]]->nor,
+			v->tex = m_vertexArray[ids[i]]->tex,
+
+			v->original_id = ids[i];
+			m_vertexArray.push_back(v);
+		}
+
+		uint32_t indexArray[3];
+		indexArray[0] = base_vertex + 0;
+		indexArray[1] = base_vertex + 1;
+		indexArray[2] = base_vertex + 2;
+		return addFace(indexArray, 3, 0, 3);
+	}
+	// -- GODOT end --
+
 	// These functions disconnect the given element from the mesh and delete it.
 
 	// @@ We must always disconnect edge pairs simultaneously.
@@ -2915,6 +2979,14 @@ Mesh *triangulate(const Mesh *inputMesh)
 					Vector2 p0 = polygonPoints[i0];
 					Vector2 p1 = polygonPoints[i1];
 					Vector2 p2 = polygonPoints[i2];
+
+					// -- GODOT start --
+					bool degenerate = distance(p0, p1) < NV_EPSILON || distance(p0, p2) < NV_EPSILON || distance(p1, p2) < NV_EPSILON;
+					if (degenerate) {
+						continue;
+					}
+					// -- GODOT end --
+
 					float d = clamp(dot(p0 - p1, p2 - p1) / (length(p0 - p1) * length(p2 - p1)), -1.0f, 1.0f);
 					float angle = acosf(d);
 					float area = triangleArea(p0, p1, p2);
@@ -2938,6 +3010,11 @@ Mesh *triangulate(const Mesh *inputMesh)
 						}
 					}
 				}
+				// -- GODOT start --
+				if (!bestIsValid)
+					break;
+				// -- GODOT end --
+
 				xaDebugAssert(minAngle <= 2 * PI);
 				// Clip best ear:
 				uint32_t i0 = (bestEar + size - 1) % size;
@@ -5606,7 +5683,10 @@ public:
 				}
 				if (chartMeshIndices[vertex->id] == ~0) {
 					chartMeshIndices[vertex->id] = m_chartMesh->vertexCount();
-					m_chartToOriginalMap.push_back(vertex->id);
+					// -- GODOT start --
+					//m_chartToOriginalMap.push_back(vertex->id);
+					m_chartToOriginalMap.push_back(vertex->original_id);
+					// -- GODOT end --
 					m_chartToUnifiedMap.push_back(unifiedMeshIndices[unifiedVertex->id]);
 					halfedge::Vertex *v = m_chartMesh->addVertex(vertex->pos);
 					v->nor = vertex->nor;
@@ -5699,7 +5779,10 @@ public:
 				const halfedge::Vertex *vertex = it.current()->vertex;
 				if (chartMeshIndices[vertex->id] == ~0) {
 					chartMeshIndices[vertex->id] = m_chartMesh->vertexCount();
-					m_chartToOriginalMap.push_back(vertex->id);
+					// -- GODOT start --
+					//m_chartToOriginalMap.push_back(vertex->id);
+					m_chartToOriginalMap.push_back(vertex->original_id);
+					// -- GODOT end --
 					halfedge::Vertex *v = m_chartMesh->addVertex(vertex->pos);
 					v->nor = vertex->nor;
 					v->tex = vertex->tex; // @@ Not necessary.
@@ -7573,6 +7656,14 @@ AddMeshError AddMesh(Atlas *atlas, const InputMesh &mesh, bool useColocalVertice
 			}
 		}
 		internal::halfedge::Face *face = heMesh->addFace(tri[0], tri[1], tri[2]);
+
+		// -- GODOT start --
+		if (!face && heMesh->errorCode == internal::halfedge::Mesh::ErrorCode::AlreadyAddedEdge) {
+			//there is still hope for this, no reason to not add, at least add as separate
+			face = heMesh->addUniqueFace(tri[0], tri[1], tri[2]);
+		}
+		// -- GODOT end --
+
 		if (!face) {
 			if (heMesh->errorCode == internal::halfedge::Mesh::ErrorCode::AlreadyAddedEdge)
 				error.code = AddMeshErrorCode::AlreadyAddedEdge;
diff --git a/thirdparty/xatlas/xatlas.h b/thirdparty/xatlas/xatlas.h
index 7e556c6c36..dbf8ca08c7 100644
--- a/thirdparty/xatlas/xatlas.h
+++ b/thirdparty/xatlas/xatlas.h
@@ -3,6 +3,9 @@
 #ifndef XATLAS_H
 #define XATLAS_H
 #include <float.h> // FLT_MAX
+// -- GODOT start --
+#include <limits.h> // INT_MAX, UINT_MAX
+// -- GODOT end --
 
 namespace xatlas {