- Home /
How can I find the terminal edges on a mesh, after removing triangles from it?
Hi guys, I'm trying to implement a convex hull algorithm. I am able to remove all the faces from a mesh, that the point to be added "sees", but I'm having trouble finding the position of the remaining edges after deletion. I'd like to generate triangles from the edges around the hole and the point I need to add to the hull. Here are the 2 relevant functions I have:
private List<int> FindFacesUnderPoint(ref Mesh currentMesh, Vector3 currentPoint, ref List<Vector3> points)
{
List<int> trianglesToDelete = new List<int>();
for (int i = 0; i < currentMesh.triangles.Length; i += 3)
{
Vector3 normal = currentMesh.normals[i];
Vector3 pointToVert = currentPoint - currentMesh.vertices[i];
float product = Vector3.Dot(pointToVert, normal);
if (product > 0)
{
trianglesToDelete.Add(i);
trianglesToDelete.Add(i+1);
trianglesToDelete.Add(i+2);
points.Add(currentMesh.vertices[i]);
points.Add(currentMesh.vertices[i+1]);
points.Add(currentMesh.vertices[i+2]);
}
}
points = points.Distinct().ToList(); // remove duplicates
return trianglesToDelete;
}
Here I return the indices of the triangles I want to delete (which works, see function below), and write to my "points" list, the positions of the extremities of each edge, that I will then take in clockwise order from the point I want to add to the hull, so my triangles wind properly.
private void DeleteTriangles(ref Mesh currentMesh, List<int> tris)
{
var t = currentMesh.triangles;
for (int i = 0; i < tris.Count; i += 3)
{
t[tris[i]] = 0;
t[tris[i+1]] = 0;
t[tris[i+2]] = 0;
}
currentMesh.triangles = t;
}
The DeleteTriangles function deletes the correct triangles, but when I feed my "points" list from FindFacesUnderPoint to my Patch function (that I left out for brevity) from all points in front of it, not just the ones where edges have been removed. How can I get these points?
Here is a gif I made that illustrates the problem: when the point circled in blue gets added to the hull, the edge I marked in yellow gets split up into 2 because also this middle point is "in front of" the one circled in blue. I've thought of computing a 2D convex hull to only take convex ones from this list, but there must be an easier way. Any help would be greatly appreciated.
Your answer
Follow this Question
Related Questions
instantiate object and align with object surface 2 Answers
What is the order/connection of array elements in mesh.vertices? 2 Answers
How to remove white blinking edge on mesh? 1 Answer
Creating a mesh for an overview map 0 Answers
Using compute shader, how to take every vertex of a mesh and make a cube spawn and move to each one? 0 Answers