Line to plane distance test, how to check certain distances
Author
I have a line-plane intersection function working for testing collisions with spheres and planes. The code is doing what I expect it to do, but there are a few flaws that need to be worked out with this technique.
First of all, it's very possible (and common) for the sphere's outer surface to be touching the plane, but not the sphere's traveling path. Such a case would be when the sphere falls straight down, very close to a polygon, but its center would be outside the polygon. There needs to be an edge collision test.
Looking through various ways to test edge collision, I decided that an "all-in-one" collision function would be best for my needs. Since all I'm doing is checking sphere collisions with other things, all I need is to do is compute the closest distance between a sphere's traveling path and the plane. And if that distance < radius of sphere, we have a collision.
I'm not looking for a complete code solution, but rather hoping I can adapt my current code and rework it somehow so that instead of checking for a line-plane intersection (meaning the distance between the two is exactly 0), it checks for a certain distance between the plane at some point in the line. So the function could say "distance = sphere's radius at point x, y, z on the line" and I can update the sphere's position to that point and carry on with reacting to the collision.
How are you doing the collision testing right now?
[Edited by - HyperGeometry on October 28, 2007 6:39:22 AM]
[Edited by - HyperGeometry on October 28, 2007 6:39:22 AM]
Author
The object stores a straight line each frame to show where it traveled, and if that line were to cross a triangle in the geometry, it would tell where in that line (in relation to its length) the intersection occurred.
I'm using the triangle's barycentric coordinates to see if the point is currently inside the triangle. This is the only case where it will return true. Now like I said before, I'm no longer interested in "something in triangle" tests. To get a more accurate representation of a sphere colliding with a triangle, I need to check for the closest distance between the line and a triangle.
bool polyCollide() { // SVect is a vector structure SVect v0 = frame.begin; SVect v1 = frame.end; // p2 is one of the vertices of the triangle // any vertex can be used SVect diff1_0 = v1.subtract(v0); SVect diff2_0 = v0.subtract(p2); // n is the normal of the triangle if (n.dotProduct(diff1_0) != 0) { // Line is not co-planar // now check against plane float u = (n.dotProduct(diff2_0)) / (n.dotProduct(diff1_0)); float px = v0.x + (u * (v1.x - v0.x)); float py = v0.y + (u * (v1.y - v0.y)); float pz = v0.z + (u * (v1.z - v0.z)); SVect vPoint(px, py, pz); // all the points in a line segment would have a "u" value between // 0 and 1. Anything other than that means that the intersection // happened outside the segment, but still along the line if (u >= 0.0f && u <= 1.0f) { // Line segment crosses the plane (but not necessarily // the triangle on the plane) /* Barycentric coordinate check */ } }}I'm using the triangle's barycentric coordinates to see if the point is currently inside the triangle. This is the only case where it will return true. Now like I said before, I'm no longer interested in "something in triangle" tests. To get a more accurate representation of a sphere colliding with a triangle, I need to check for the closest distance between the line and a triangle.
Quote:Original post by JustChrisComputing the closest distance between the line segment and the triangle will tell you if the sphere intersected the triangle, but not when or where.
The object stores a straight line each frame to show where it traveled, and if that line were to cross a triangle in the geometry, it would tell where in that line (in relation to its length) the intersection occurred.
*** Source Snippet Removed ***
I'm using the triangle's barycentric coordinates to see if the point is currently inside the triangle. This is the only case where it will return true. Now like I said before, I'm no longer interested in "something in triangle" tests. To get a more accurate representation of a sphere colliding with a triangle, I need to check for the closest distance between the line and a triangle.
Computing when and where reduces, essentially, to raytracing the CSO of the sphere and the triangle, which is an object made up of a 'thickened' triangle, three cylindrical segments, and three spherical segments. This in turn can be broken down into various segment-triangle, segment-cylinder, and segment-sphere tests, all of which are well-documented online and elsewhere (good references include geometrictools.com [Dave Eberly's site], Christer Ericson's collision detection book, and Kasper Fauerby's article on intersection testing using swept ellipsoids).
Hmm, someone please correct me if I'm wrong here...
A plane could be described using the equation
Where
And the sphere could be described with
Then, I reason, the d in the plane equation equals distance from origin along the normal. Then if you take out d from the sphere using the plane's normal the distance between the two d:s could be used to find a collision. Specifically, using the equations above you get
Which leads to
And thus, if I'm right, you have the time of intersection though I'm not sure how one should go about determining wheather or not that point is on the polygon. Hope that makes sense, my notation is a bit arbitrary.
[EDIT]
Oh and I do believe that the actual point of intersection would be
You should be able to check this point the same way as before.
[Edited by - HyperGeometry on October 28, 2007 3:22:52 PM]
A plane could be described using the equation
Where
And the sphere could be described with
Then, I reason, the d in the plane equation equals distance from origin along the normal. Then if you take out d from the sphere using the plane's normal the distance between the two d:s could be used to find a collision. Specifically, using the equations above you get
Which leads to
And thus, if I'm right, you have the time of intersection though I'm not sure how one should go about determining wheather or not that point is on the polygon. Hope that makes sense, my notation is a bit arbitrary.
[EDIT]
Oh and I do believe that the actual point of intersection would be
You should be able to check this point the same way as before.
[Edited by - HyperGeometry on October 28, 2007 3:22:52 PM]
Quote:Original post by HyperGeometryJust FYI, your equations don't show up for those of us using the 'classic black' theme (I've made that mistake too, only the other way around :).
Hmm, someone please correct me if I'm wrong here...
A plane could be described using the equation
Where
And the sphere could be described with
Then, I reason, the d in the plane equation equals distance from origin along the normal. Then if you take out d from the sphere using the plane's normal the distance between the two d:s could be used to find a collision. Specifically, using the equations above you get
Which leads to
And thus, if I'm right, you have the time of intersection though I'm not sure how one should go about determining wheather or not that point is on the polygon. Hope that makes sense, my notation is a bit arbitrary.
Quote:Original post by jyk
Just FYI, your equations don't show up for those of us using the 'classic black' theme (I've made that mistake too, only the other way around :).
Thank you, I didn't know. The images are now also links to the same equations.
Author
HyperGeometry, thanks for the help. But I'm not familiar with that particular sphere formula. I already had in consideration that I wasn't going to know exactly the time and place where the sphere first collides, just by finding the line's shortest distance to the plane. The time t would just be between a range of values like between 0 and 1, is that correct? I mean, the number is probably just a relative value until it is used in practice.
If this is correct, then considering that the speed is constant during the entire frame, I could just use time t to get the distance along the line of travel where the sphere collided and mark that point P, which would give me the center of the sphere. Then extend a line parallel to the triangle's normal from P to where it touches the triangle and I'll get the point of collision. Correct me if I'm wrong.
Jyk, I'm not familiar with the raytracing approach you described. Can you tell me what the CSO of a shape is? And is it really necessary to evaluate more geometric volumes given by this CSO? I didn't think evaluating this problem would get so deep.
If this is correct, then considering that the speed is constant during the entire frame, I could just use time t to get the distance along the line of travel where the sphere collided and mark that point P, which would give me the center of the sphere. Then extend a line parallel to the triangle's normal from P to where it touches the triangle and I'll get the point of collision. Correct me if I'm wrong.
Jyk, I'm not familiar with the raytracing approach you described. Can you tell me what the CSO of a shape is? And is it really necessary to evaluate more geometric volumes given by this CSO? I didn't think evaluating this problem would get so deep.
Quote:Original post by JustChris
HyperGeometry, thanks for the help. But I'm not familiar with that particular sphere formula. I already had in consideration that I wasn't going to know exactly the time and place where the sphere first collides, just by finding the line's shortest distance to the plane. The time t would just be between a range of values like between 0 and 1, is that correct? I mean, the number is probably just a relative value until it is used in practice.
Sorry about being confusing. It's not actually a sphere formula as such, i just assume it's a sphere with radius r. And yes t, in your case, would be between 0 and 1 if the intersection happens this frame and v is the difference in position between the start and end positions.
Quote:Original post by JustChris
If this is correct, then considering that the speed is constant during the entire frame, I could just use time t to get the distance along the line of travel where the sphere collided and mark that point P, which would give me the center of the sphere. Then extend a line parallel to the triangle's normal from P to where it touches the triangle and I'll get the point of collision. Correct me if I'm wrong.
Correct.
Author
Jyk, I understand what you mean when you are talking about the CSO of the sphere and a triangle. With a line-circle collision the collision area is a rectangle with two semi-circles, and when I pictured the form with the triangle that's when it kicked in.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
