Repository: godotengine/godot
File: core/math/convex_hull.cpp (C++)

Code before:
		}
	}

	return shift;
}

Error ConvexHullComputer::convex_hull(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_mesh) {
	r_mesh = Geometry3D::MeshData(); // clear

	if (p_points.size() == 0) {
		return FAILED; // matches QuickHull
	}

	ConvexHullComputer ch;
	ch.compute(p_points.ptr(), p_points.size(), -1.0, -1.0);

	r_mesh.vertices = ch.vertices;

	// Copy the edges over. There's two "half-edges" for every edge, so we pick only one of them.
	r_mesh.edges.resize(ch.edges.size() / 2);
	uint32_t edges_copied = 0;
	for (uint32_t i = 0; i < ch.edges.size(); i++) {
		uint32_t a = (&ch.edges[i])->get_source_vertex();
		uint32_t b = (&ch.edges[i])->get_target_vertex();
		if (a < b) { // Copy only the "canonical" edge. For the reverse edge, this will be false.
			ERR_BREAK(edges_copied >= (uint32_t)r_mesh.edges.size());
			r_mesh.edges.write[edges_copied].a = a;
			r_mesh.edges.write[edges_copied].b = b;
			edges_copied++;
		}
	}
	if (edges_copied != (uint32_t)r_mesh.edges.size()) {
		ERR_PRINT("Invalid edge count.");
	}

	r_mesh.faces.resize(ch.faces.size());
	for (uint32_t i = 0; i < ch.faces.size(); i++) {
		const Edge *e_start = &ch.edges[ch.faces[i]];
		const Edge *e = e_start;
		Geometry3D::MeshData::Face &face = r_mesh.faces.write[i];

		do {
			face.indices.push_back(e->get_target_vertex());

			e = e->get_next_edge_of_face();
		} while (e != e_start);

		// reverse indices: Godot wants clockwise, but this is counter-clockwise
		if (face.indices.size() > 2) {
			// reverse all but the first index.
			int *indices = face.indices.ptrw();

Review comment (suggestion):
I was going to say we had a `fill()` method for this, but I see it was added to 3.x in #60426 but not yet added to 4.x. Might be worth adding this at the same time as it is fairly common? :thinking: 

Code after:
			} while (e != first_edge);
		}
	}

	return shift;
}

Error ConvexHullComputer::convex_hull(const Vector<Vector3> &p_points, Geometry3D::MeshData &r_mesh) {
	r_mesh = Geometry3D::MeshData(); // clear

	if (p_points.size() == 0) {
		return FAILED; // matches QuickHull
	}

	ConvexHullComputer ch;
	ch.compute(p_points.ptr(), p_points.size(), -1.0, -1.0);

	r_mesh.vertices = ch.vertices;

	// Tag which face each edge belongs to
	LocalVector<int32_t> edge_faces;
	edge_faces.resize(ch.edges.size());

	for (uint32_t i = 0; i < ch.edges.size(); i++) {
		edge_faces[i] = -1;
	}

	for (uint32_t i = 0; i < ch.faces.size(); i++) {
		const Edge *e_start = &ch.edges[ch.faces[i]];
		const Edge *e = e_start;
		do {
			int64_t ofs = e - ch.edges.ptr();
			edge_faces[ofs] = i;

			e = e->get_next_edge_of_face();
		} while (e != e_start);
	}

	// Copy the edges over. There's two "half-edges" for every edge, so we pick only one of them.
	r_mesh.edges.resize(ch.edges.size() / 2);
	OAHashMap<uint64_t, int32_t> edge_map;
	edge_map.reserve(ch.edges.size() * 4); // The higher the capacity, the faster the insert

	uint32_t edges_copied = 0;
	for (uint32_t i = 0; i < ch.edges.size(); i++) {
		ERR_CONTINUE(edge_faces[i] == -1); // Sanity check

		uint32_t a = (&ch.edges[i])->get_source_vertex();
		uint32_t b = (&ch.edges[i])->get_target_vertex();
		if (a < b) { // Copy only the "canonical" edge. For the reverse edge, this will be false.
			ERR_BREAK(edges_copied >= (uint32_t)r_mesh.edges.size());