Sign in to follow this  

2D Mesh splitting

This topic is 398 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).

WuIjuTs.png

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.

 

 

 

 

[attachment=33922:bisection.PNG]

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

This topic is 398 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this