# Triangulation woes

This topic is 3346 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey all, I am trying to create a game with dynamic geometry, but have stumbled upon a problem of triangulating the 2D polygon. The picture below depicts an example of what is happening when I insert vertices of "crack"(yellow line) into world outline, excluding those that were inside the "crack" on world boundary: I am looking for an advice or some points on how this can be fixed. There are a few other ways, ones that I tried involve doing direct poly-poly CSG with Farseer and external triangulation library GPC (C# wrapped); first one produces desirable results to certain extent, while last one can't stand to it most of the times. My idea was to store level vertices in a texture and then convert them back and forth while performing "carving" operations on the texture itself, however this may introduce peformance issues (not yet tested) at times of texture-to-polygon conversion. A solution I am looking must involve polygons as I use Farseer library for physics, and it uses polygon outlines for testing (not solid polygon where it has vertices inside of it and not just on the outline). Can anyone suggest anything, please? I will give this abit of a thought, but dynamic CSG seems to provide more of a challenge than I originally anticipated. (Note that I am doing all this in 2D) Thanks!

##### Share on other sites
It seems to me you're not creating a new polygon. Unless I do not understand the problem, shouldn't the crack split a polygon into 2 smaller polygons? First one should become vertices 0 to 33 + crack and back to 0 and the second would be crack + 34 to 40 and back to the crack. That would also preserve the order of vertices (counter-clockwise).

##### Share on other sites
I don't really see why this is a problem. If you have replaced the vertices that were around the edge with vertices for the crack then i don't see why it wouldn't tessellate. I implemented ear clipping and the only times it screwed up were when i passed it strangely ordered points.

##### Share on other sites
I am sorry for failure to mention the general algorithm, but it works pretty much as Dave thought it would: the crack vertices would be inserted into the outline right after vertex 33, replacing those between 34 and 40 inclusive.

As far as I can figure out, this seemed to me as failure to properly triangulate concave polygon; as seen from second picture, the program assumed the polygon to be convex (0-1-21-23 to 27 to 29-33-45)

I will attempt to figure this out as Farseer' triangulation algorithm may not be of exact quality as expected.

##### Share on other sites
I am going to use this post to ask another question, if it's okay: while using GPC, what is the optimal solution to avoid an effect like the one below, where triangulation is failing.

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633724
• Total Posts
3013556
×