QuickHull generates bad hull sometimes when multiple triangles share the same plane.

[jitspoe]

Godot version:
3.2.3
3.2.4.rc2

OS/device including version:
Windows 10

Issue description:
QuickHull fails to merge edges sometimes and results in generating multiple of the same plane and wrong geometry. Errors printed to the log include things like:
core\math\quick_hull.cpp:402 - Condition "O == 0" is true. Continuing.
core\math\quick_hull.cpp:399 - Condition "!F" is true. Continuing.
core\math\quick_hull.cpp:428 - Condition "!F2" is true. Continuing.

Example:

Edit: Just tried in 3.2.4.rc2, and the result was slightly different, but still broken:

(Should just be an octagon)

Steps to reproduce:
Generate a convex collision from something like a cylinder or another object that has many triangles on the same face, preferably at some odd angle. Doesn't always reproduce.

Notes:
I've stepped through the QuickHull::build() function, and the problem seems to reside in the logic to merge faces and remove edges on a single plane. It makes some assumptions about the structure/order of vertices. If things overlap instead of being next to each other, the algorithm falls apart. When the errors happen, extra planes are left in the hull that shouldn't be there.

It might be better to just generate the the planes, ignoring edges and verts, then generate the edges and verts at the end based on plane intersections. It would also be nice if the edge generation was optional, because it's only necessary when displaying the hull, not when using it for collision purposes.

Minimal reproduction project:
test_quickull.zip

[lentsius-bark]

Same issue occurs when I generate convex collision shape on this model. Attaching it for testing purposes.
03.zip

[jitspoe]

I started rewriting this in a way that was a bit more readable, but hit a bit of a snag: I couldn't figure out a good way to sort a Vector using values external to what's in the vector.

This might provide a helpful starting point for somebody, though:

	/* CREATE MESHDATA */

	r_mesh.faces.clear();
	r_mesh.edges.clear();

	for (List<Face>::Element* face_element = faces.front(); face_element; face_element = face_element->next()) {
		Geometry::MeshData::Face mesh_face;
		mesh_face.plane = face_element->get().plane;
		uint32_t* vert_indices = face_element->get().vertices;
		for (int i = 0; i < 3; i++) {
			mesh_face.indices.push_back(vert_indices[i]);
		}

		// Remove faces with duplicate planes and merge vertices into this face.
		for (List<Face>::Element* other_face = face_element->next(); other_face; other_face = other_face->next()) {
			if (other_face->get().plane.is_equal_approx(mesh_face.plane)) {
				uint32_t* vert_indices = other_face->get().vertices;
				for (int i = 0; i < 3; i++) {
					// Only add unique vertex
					bool unique = true;
					for (int oi = 0; oi < mesh_face.indices.size(); ++oi) {
						if (mesh_face.indices[oi] == vert_indices[i]) {
							unique = false;
							break;
						}
						if (unique) {
							mesh_face.indices.push_back(vert_indices[i]);
						}
					}
				}

				other_face->erase();
			}
		}

		// Reorder vertices
		Vector3 center_point = Vector3();
		int32_t s = mesh_face.indices.size();
		for (int i = 0; i < s; ++i) {
			center_point += p_points[mesh_face.indices[i]];
		}
		center_point /= s;
		//mesh_face.indices.sort_custom()

		r_mesh.faces.push_back(mesh_face);
		// TODO: Quick hack to get some edges in there -- need to do it better.
		for (int i = 0; i < mesh_face.indices.size(); ++i) { // Could optimize
			Geometry::MeshData::Edge edge;
			edge.a = mesh_face.indices[i];
			if (i + 1 < mesh_face.indices.size()) {
				edge.b = mesh_face.indices[i + 1];
			}
			else {
				edge.b = mesh_face.indices[0];
			}
			r_mesh.edges.push_back(edge);
		}
		r_mesh.vertices = p_points;
	}

Basically, I wanted to sort the vertices using their position, but each vertex is stored in the array as an index, so I'd have to look up the actual vertex position in another Vector using the vertex index, but the custom sort uses a struct with an operator override instead of a lambda, so I'm not sure if that's even possible or if I'd have to write a custom sort. Anybody know some C++ voodoo to make sort_custom() do what I want?

Anyway, just to clarify what the issue is here, there are triangles created between all the vertices, and it tries to merge them into a single face. The algorthm assumes the triangles line up neatly (left), when in reality, they sometimes overlap (right), so it's not possible to merge as you go.

[Zireael07]

Can't help with the C++, just chiming in that I am having the same issue with autogenerated hulls. I am not 100% certain which mesh is causing those, as the collisions work just fine, but I do get the log messages (and they are quite spammy, I am suspecting it's either the roads or buildings in my project)