Distance from line to triangle
Hi
I''m trying to implement some collition checking, but cannot find a formula to determine the smallest distance from a line to a triangle in 3D space. Does anybody here know how to do this ?
Tommy
This method only detects whether a line intersects a triangle. I was thinking more of the distance to the triangle, so that I could represent objects (the player) as a cylinder, and check wheter the triangle is more than the cylinder''s radius away.
well, for a segment, you can check the distance of all vertices of the tri to the line, then the distance of the end point of the line the triangle distance, then the distance of the end points of the line to the triangle plane (if the point is ''above the trinagle though, so you need to check the projection of the point into the triangle and see if it is in the triange, likePointInTriangle()).
then you take the minimum distance, and it should give you the distance of a segment to a triangle. but it won;t detect if the segment intersected
then you take the minimum distance, and it should give you the distance of a segment to a triangle. but it won;t detect if the segment intersected
Thanks oliii, I''ll try this later to see how it works. I realized now that the cylinder will never ''tilt'', so I''m trying a method to do a 2D circle / point collition test using the XZ coordinates, and then a min/max test on the y coordinate. If this works, it''ll probably be the faster way
My method didn''t work to well for large triangles, so I''m going to try your suggestion now. I did not quite understand the second test, though: "the distance of the end point of the line the triangle distance" - what does this mean?
Also; Am I on the wrong track here - is there a better way to do player/triangle intersection (without the obvious way to use a trianglemesh for the player) ?
Also; Am I on the wrong track here - is there a better way to do player/triangle intersection (without the obvious way to use a trianglemesh for the player) ?
brain fart here
1) tri verts vs segment
2) segment verts vs tri segments
3) segment verts vs triangle plane, if segment vert above/below triangle.
note that, you can group 2) and 3) into one function, as if segment verts are above/below triangle, no need to test the triangle edges.
take the minimum, and that should do it.
as far as player triangle collisions go, there are other solutions, like use a sphere/cylinder and test for intersection, or do a swept test with a sphere/ellispoid against triangles.
Again, you can apply the same principle, and break down the triangle into a plane and segments for various tests.
see ellipsoid collision
for box intersection, it's a little trickier, look for separation axis algorithms.
[edited by - oliii on January 11, 2004 5:35:12 PM]
1) tri verts vs segment
2) segment verts vs tri segments
3) segment verts vs triangle plane, if segment vert above/below triangle.
note that, you can group 2) and 3) into one function, as if segment verts are above/below triangle, no need to test the triangle edges.
take the minimum, and that should do it.
as far as player triangle collisions go, there are other solutions, like use a sphere/cylinder and test for intersection, or do a swept test with a sphere/ellispoid against triangles.
Again, you can apply the same principle, and break down the triangle into a plane and segments for various tests.
see ellipsoid collision
for box intersection, it's a little trickier, look for separation axis algorithms.
[edited by - oliii on January 11, 2004 5:35:12 PM]
You want the distance from the line to tri or the line to the tri''s plane. Cause if you want the distance from a point to tri it is different than a line to a tri, considering the line doesn''t have to hit the tri.
I think the best way to see if a line hits the tri is with a few tests.
________________
Do 2 test, a point to plane at the beginning and a point to plane at the end, this will give you 2 distances. If they change signs then it passed through that tris plane. Therefore it is possible to eliminate most collisions on step one.
Next step, move up to where the point is on the plane and do a point in tri collide test, and from there you will know whether the line hits the plane. Also if so how far it went in (the second distance). You can also eleminate hitting backfaces if the point starts off on the wrong side.
Anyone know of a quicker way? I feel the point in tri test is fairly computational. But I think the 2 point distance to plane test make up for the occasional tri-point.
The point in tri and point to plane formulas should be readily avaible on the net, just go through google.
Olii I don''t get the tri verts vs segment test there is a formula for point in poly online which you can tweak to allow a little error (when you check the point on plane it will never lie perfectly on the plane).
But even more important if you are using a collision system from startch I would just recommend getting one already out. Buildling a tree system or BSD for it is tough (well, not too tough but tougher than this testing stuff), just get Opcode, coldet, or mess with Tokamak so when you do you line-tri testing it quickly eliminates what you have to test. You can make them only return close triangles and do the testing yourself seeing as how they are Overlap rather than Swept testing (but in your case for a line it really isn''t overlap or swept).
Oh, and also if you want a cylinder testing I am not sure but I think you can find some code for it fairly easy for examples. I am pretty sure most 3rd Person shooters use it. I just like circles(like use 3 to represent a cylinder probably actually the same computation). But circles are pretty easy once you get the hang of it (with a little help from Olii).
I think the best way to see if a line hits the tri is with a few tests.
________________
Do 2 test, a point to plane at the beginning and a point to plane at the end, this will give you 2 distances. If they change signs then it passed through that tris plane. Therefore it is possible to eliminate most collisions on step one.
Next step, move up to where the point is on the plane and do a point in tri collide test, and from there you will know whether the line hits the plane. Also if so how far it went in (the second distance). You can also eleminate hitting backfaces if the point starts off on the wrong side.
Anyone know of a quicker way? I feel the point in tri test is fairly computational. But I think the 2 point distance to plane test make up for the occasional tri-point.
The point in tri and point to plane formulas should be readily avaible on the net, just go through google.
Olii I don''t get the tri verts vs segment test there is a formula for point in poly online which you can tweak to allow a little error (when you check the point on plane it will never lie perfectly on the plane).
But even more important if you are using a collision system from startch I would just recommend getting one already out. Buildling a tree system or BSD for it is tough (well, not too tough but tougher than this testing stuff), just get Opcode, coldet, or mess with Tokamak so when you do you line-tri testing it quickly eliminates what you have to test. You can make them only return close triangles and do the testing yourself seeing as how they are Overlap rather than Swept testing (but in your case for a line it really isn''t overlap or swept).
Oh, and also if you want a cylinder testing I am not sure but I think you can find some code for it fairly easy for examples. I am pretty sure most 3rd Person shooters use it. I just like circles(like use 3 to represent a cylinder probably actually the same computation). But circles are pretty easy once you get the hang of it (with a little help from Olii).
Whops I just re-read the posts and my idea for 3 spheres for a cylinder doesn''t work as good as ellipsoid collision. But spheres are definitely the fastest thing you can test for.
quote:Original post by jimmynelson
Olii I don''t get the tri verts vs segment test there is a formula for point in poly online which you can tweak to allow a little error (when you check the point on plane it will never lie perfectly on the plane).
tri vert vs segment : you calcualte the distance of the 3 vertices against the segment or line.
for testing if a point is above / on the triangle, you build planes at the edges with normal equal to Edge.Dir x Tri.Normal. Then you test if the point if front facing (or back-facing) the 3 planes.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement