Jump to content
  • Advertisement
Sign in to follow this  
Daniel Protopopov

Triangulation woes

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!