- Home /
Removing internal vertices in a shape
Given a List of Edges (each containing a reference to 2 vertices) I can define a shape. My problem is that a lot of the vertices of the polygon are internal - they lie inside the shape of the polygon - and I need to be able to detect and remove these extra vertices.
Sorry if it's a bit confusing, but a picture's worth a thousand words:
The red edges and vertices are the ones I would like to delete, and the black edges and green vertices are the ones I would like to keep.
I'm sure there's a bit of maths that makes this easy, but I've no clue how to start :P
TLDR: I need to be able to delete all points that don't form the outline of a polygon.
Answer by Bunny83 · Oct 07, 2019 at 10:22 PM
Looks like a duplicate of this one. The main insight is that the inner edges of a mesh are always paired with another one while the outer edges are not. Note that the solution I've posted on the other question assumes that the mesh vertices are fully shared or at least if the aren't shared it's considered an outer edge. For example the default cube in Unity has 6 independent faces. Each face consists of 2 triangles. Those two triangles have one shared edge, the other 4 edges are the outer edges of that face.
Note that since you want to remove the inner vertices, keep in mind that if you actually work with meshes (based on triangles) you would need to re-mesh the outer vertices. Also from your question it's not clear what kind of shapes you might have. Are they always convex? Or can they be concave?
Sorry for the lack of detail - I should explain the scenario in full. I'm trying to generate a shadow mesh for an object, by casting a ray through all of the object's vertices onto a wall, then connecting the resultant points with the same edges as the original mesh. The example I gave above is a drawing of what is generated for a cube when the 'light' (ray origin) is directly behind it. I need to be able to get the outline of these shadows from only the Edge data, which for each edge is as follows: - A start vertex - An end vertex Ultimately, I'm going to create a flat mesh from this data, but I specifically need the outline for various effects (such as a glowing outline). I don't have any reference to the triangles or faces, only edges. Hence, this causes the problem of figuring out what edges connect to others to form faces, so unfortunately none of the solutions in the other thread are of any use.
Thanks for the help.