Clip line to triangle in 2D?
Author
Hi there,
the last day I thought about how I could clip a line to a triangle in 2D. I have a triangle ABC and a line PQ.
Now I want the line P'Q' that is clipped to the triangle (e. g. has no extend outside the triangle) - if the line is completely outside this should be found out.
I thought that I test for both points P and Q of the line if they are inside my triangle (via barycentric cooridnates). So the simplest case is both are inside and I have to do nothing :).
The nexst case is P is in and Q is out (or vice versa) - what to do now? check the line for intersections with every triangle edge and get the new line PQ' (P'Q resp. if other way round)?
Third case is both, P and Q, are outside and I need to check if the line intersects the trinagle and clip it. How to do this? Again I could check the line for intersection with every edge of the triangle.
I think I could come up with a naive solution (the one above) - but I looks pretty slow to me. Are there any algorithms that do what I want?
Thank you very much,
Tom
the standard clipping method would be to clip the segment using the infinite lines passing through the triangle edges. You keep clipping your segment with each edge you test against. That ultimately will reduce your segment to the portion inside.
You can do some basic culling using the segment end points to reject cases.
[Edited by - oliii on September 17, 2008 8:44:53 AM]
You can do some basic culling using the segment end points to reject cases.
[Edited by - oliii on September 17, 2008 8:44:53 AM]
Author
well, thanks for your reply. I can not really see how the approach you mentioned has to be done.
If I caluclate the intersections between my segment PQ and all 3 infinite lines I end up with 3 inersection points. How do I know which intersections are the ones being my clipped segment?
Thanks in advance
If I caluclate the intersections between my segment PQ and all 3 infinite lines I end up with 3 inersection points. How do I know which intersections are the ones being my clipped segment?
Thanks in advance
Quote:Original post by VooDooTom
If I caluclate the intersections between my segment PQ and all 3 infinite lines I end up with 3 inersection points. How do I know which intersections are the ones being my clipped segment?
Take your original line and clip it against one infinite line, then take that output and clip it against the next infinite line etc. You only have to deal with one intersection point at a time, and your line segment will only get smaller until you've got your final result.
This approach will work for any convex hull, just make sure to generate your infinite lines consistently so you know which half is "inside" and which is "outside".
You'll need to clip the line to each edge of the 2d triangle assuming that each edge has a sort of "normal", pointing, for example, to the inside of the triangle.
So, starting with the end points of your line, you will test the first edge.
If both points are "out" then jump out (the line is outside)
if both in then feed them to the next edge
if they cross, find the intersection and feed the "in" point and the intersection to the next edge
Do for the 3 edges and the resulting output vertices are your clipped line.
It can be extended in 3d space and with n planes.
EDIT:
cool OrangyTang! same reply same time ;)
So, starting with the end points of your line, you will test the first edge.
If both points are "out" then jump out (the line is outside)
if both in then feed them to the next edge
if they cross, find the intersection and feed the "in" point and the intersection to the next edge
Do for the 3 edges and the resulting output vertices are your clipped line.
It can be extended in 3d space and with n planes.
EDIT:
cool OrangyTang! same reply same time ;)
Author
Hi there,
thank you for your explanations - I think now I got it :)
My solution for all convex polygons is:
Edit: Found a mistake, corrected it.
Hope this works :)
[Edited by - VooDooTom on September 17, 2008 10:49:04 AM]
thank you for your explanations - I think now I got it :)
My solution for all convex polygons is:
bool clip_line_to_triangle(const point3f vertices[], int num_vertices, point3f &p, point3f &q) { point3f normal = cross( normalize(vertices[1]-vertices[0]), normalize(vertices[2]-vertices[1])); point3f n1; point3f n2; bool p_outside; bool q_outside; int index2; // go through all edges for (int i = 0; i < num_vertices; ++i) { index2 = (i+1)%num_vertices; n1 = cross(normalize(p-vertices),normalize(vertices[index2]-p)); n2 = cross(normalize(q-vertices),normalize(vertices[index2]-q)); p_outside = dot(normal,n1) < -0.001f; q_outside = dot(normal,n2) < -0.001f; if (p_outside) { if (!q_outside) { line_line_intersect(vertices, vertices[index2], p, q, p); // save the intersection in p } else { // if both points are "outside" of the edge, we can leave return false; } } else { if (q_outside) { line_line_intersect(vertices, vertices[index2], p, q, q); // save the intersection in q } } } return true;}Edit: Found a mistake, corrected it.
Hope this works :)
[Edited by - VooDooTom on September 17, 2008 10:49:04 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement