• 13
• 18
• 19
• 27
• 10

# Line to plane distance test, how to check certain distances

This topic is 3789 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
How are you doing the collision testing right now?

[Edited by - HyperGeometry on October 28, 2007 6:39:22 AM]

##### Share on other sites
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.

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.

##### Share on other sites
Quote:
 Original post by JustChrisThe 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 the closest distance between the line segment and the triangle will tell you if the sphere intersected the triangle, but not when or where.

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).

##### Share on other sites
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

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]

##### Share on other sites
Quote:
 Original post by HyperGeometryHmm, someone please correct me if I'm wrong here...A plane could be described using the equationWhereAnd the sphere could be described withThen, 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 getWhich leads toAnd 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.
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 :).

##### Share on other sites
Quote:
 Original post by jykJust 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.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by JustChrisHyperGeometry, 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 JustChrisIf 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.