# How to simplify a 2D mesh with messed up topology while keeping as much of the shape as possible and as efficiently as possible?

I'm trying to figure out a way to simplify any 2D mesh during runtime in Unity with broken up topology so that it will have more uniform topology and retain as much of its original shape as possible.

Here is a basic example of a circle with messed up topology:

Here is what I'm looking to achieve after applying simplification:

I also want this to work for any 2D mesh whether it's concave or convex. I've currently tried using the Marching Squares approach to reform the mesh but the results are too blocky and sharp.

How would I go about doing this? What might be the most efficient algorithms? Are there any existing libraries that I could look at to mess around with?

• Do you have adjacency information for this mesh (eg. a simple way to iterate over the edges and query which triangles they're adjacent to)? Dec 16, 2021 at 12:29
• I want to ask something. Please tell me why 2d has to have vertices inside of the mesh? to have all equal triangles? To draw something I always used vertices just outside (but shapes I draw were usually simple).. Dec 16, 2021 at 16:41
• @DMGregory I am using a half-edge system but the connections are broken due to the changes I made to the shape's topology like the first image suggests. My fallback was to "snapshot" the mesh with RayCasts to get a general shape but the results are too rough and sharp for my liking. Dec 16, 2021 at 18:42
• By "broken", do you mean you no longer have a valid half-edge representation of the modified mesh? The changes you make should update the half-edge data structure too, so that you retain adjacency information about the modified mesh. You'll need that kind of info to successfully retopologize it. Dec 16, 2021 at 18:44
• @DMGregory I'm using a CSG library to to mesh boolean out shapes out of an existing mesh which seems to break my half-edge connections. I'm using the half-edge system for other things as well such as vertex displacement and as soon as I perform that mesh boolean operation and manipulate the mesh afterwards, the program will crash (most likely due to a circular while loop which I don't know how to fix). Dec 16, 2021 at 19:08

## 1 Answer

I see two ways to do this. However, I don't expect anything to be really fast, you might want to do this asynchronously.

• Figure out the perimeter shape, simplify it, and fill in the shape
• Iterate over pairs of vertices, and if they are very close together, do one of two things:
1. Merge them together
2. Move them further apart

The second option can be applied iteratively, while I think the first option is simpler, so let's talk about that one.

To figure out the perimeter, find a vertex where the angles of triangles around it does not add up to 360 degrees, meaning it can't be completely surrounded by triangles. Then, move along the edge, this would be done by finding the edge on the clockwise side of the gap of triangles.

Once you have this line, simplify it: For each pair of vertices, if they are very close together, merge them.

This is a simple approach, and you can of course take the curvature of the line into account too: straight line segments can be simplified even if the vertices are further apart.

Then, you can fill in the shape with a grid of triangulated squares or hexagons and connect the perimeter vertices with the closest one of the fill-in vertices.

This will not result in a perfect distribution of vertices, but it will have a way lower vertex count than the original. You can also run a couple steps of a mass-spring simulation (with the perimeter pinned) to relax the infill, if you have the time.

Some pseudo-code:

edgePoints = points where all neighbors, sorted by angle relative to the point, are connected to either adjacent neighbor.

var edgePoint = vertices.Where(vertex => {
var neighbors = GetNeighbors(vertex).OrderBy(pt => (pt - vertex).Angle).ToList();
for(var i = 0; i < neighbors.Count; ++i)
{
if (neighbors[i] is not connected to neighbors[(i + 1) % neighbors.Count])
return true;
}
return false;
}).First();

// To walk around the edge, take the neighbor of each point that is on the clockwise side of the disconnected neighbors.


I hope this simple explanation is enough for you to figure out what to do!