Jump to content
  • Advertisement
Sign in to follow this  

2D Mesh splitting

This topic is 706 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

Hi, currently in my job we need to split JUST a quad ( two triangles) by a line, this will happen only once and the line might have any inclination (in 2D). So I was investigating at the algorithms for mesh splitting/clipping and they seem to be a bit complex, since they all involve cutting complex meshes.

I was wondering if there was a simple technique that can be used for my specific use case ( just 2 triangles).


Edited by ramiro_fages

Share this post

Link to post
Share on other sites

A direct algorithm seems simple enough, assuming your quad is actually two triangles as you described.


First, find the coordinates of the line you are using for the split.  If it matches the existing triangle line, do nothing, it is already split on that line.


Next, compute the intersection points, green in the image attached.


If the intersection exactly matches the corners in the other direction, split both triangles in half at the central intersection point.


Otherwise, the lines will be on one side or the other of the existing quad.  On the big side split the quad from the central intersection and the outside corner. On the little side split it into two triangles from the central intersection, the edge intersection, and the each of the outer corners.  Repeat on both triangles.






Share this post

Link to post
Share on other sites

Adding to frob's suggestion, the configuration in the diagram is only one of the possible ones: the line can also cross

  • the other pair of non-consecutive square edges and the diagonal
  • or two consecutive square edges but not the diagonal (two ways),
  • or it can be collinear with any one of the 5 edges,
  • or it can touch the square at any one vertex of the convex hull (four ways),
  • or it can have no intersection.

You can distinguish the 15 cases by the result of intersection tests between the line and each of the 5 edges and/or tests of which side of the line the four square corners lie on,

Rebuilding geometry in the 6 nontrivial cases will be easy: given vertices in a fixed order (adding to the four original ones the two or three new ones from intersections) the lines and triangles will have a fixed structure. that can be figured out from diagrams.

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!