Sign in to follow this  

Line to plane distance test, how to check certain distances

This topic is 3727 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

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by JustChris
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 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 this post


Link to post
Share on other sites
Hmm, someone please correct me if I'm wrong here...

A plane could be described using the equation

\normal ax+by+cz+d=0

Where

\normal d=-(ax_0+by_0+cz_0)

And the sphere could be described with

\normal \text{radius } r \\ \text{origin } S(t)=S_0 + tV

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

\normal ax_0+by_0+cz_0 = a(x_{s_0} + tx_v) + b(y_{s_0} + ty_v) + c(z_{s_0} + tz_v) - r

Which leads to

\large t = \frac{ax_0+by_0+cz_0 - ax_{s_0}-by_{s_0}-cz_{s_0} + r}{ax_v+by_v+cz_v}

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

\large P=S_0+tV-rN \\ \text{where N is the normal}

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 this post


Link to post
Share on other sites
Quote:
Original post by HyperGeometry
Hmm, someone please correct me if I'm wrong here...

A plane could be described using the equation

\normal ax+by+cz+d=0

Where

\normal d=-(ax_0+by_0+cz_0)

And the sphere could be described with

\normal \text{radius } r \\ \text{origin } S(t)=S_0 + tV

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

\normal ax_0+by_0+cz_0 = a(x_{s_0} + tx_v) + b(y_{s_0} + ty_v) + c(z_{s_0} + tz_v) - r

Which leads to

\large t = \frac{ax_0+by_0+cz_0 - ax_{s_0}-by_{s_0}-cz_{s_0} + r}{ax_v+by_v+cz_v}

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.
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
I'm guessing that CSO here means Configuration Space Obstacle, which is how this sort of thing is described in some fields. The idea is that you shrink the moving object to a single point, and the obstacle is expanded by the shape of the object (the kolmogorov sum of the object and the obstacle). The expanded obstacle is the configuration space obstacle. Since the original object is now a point, testing for collision with the CSO when moving in a straight line becomes a raytracing problem.

Spheres are convenient in some ways because they are so simple. The obstacle is just expanded in all directions by the radius of the sphere to get the CSO. A point becomes a sphere, an infinite line becomes an infinite cylinder, an infinite plane becomes a slab (a solid region bounded by two infinite planes).

If you are looking for a collision between the sphere and an infinite plane, then Hypergeometry's solution works. If you have a sphere and a triangle, you'll use jyk's approach.

Share this post


Link to post
Share on other sites
Sign in to follow this