Moving sphere against triangle collision

Started by
32 comments, last by Charles B 19 years, 4 months ago
See my last post to see where this is all coming from. I invented my own algorithm for this, hehe. All testing so far looks like it works flawlessly. Still, I would like to know if anyone can see and point out any potential problems with it. First, the function's purpose is to report a collision when a sphere moves into or through a triangle. It will also fail to report a collision if the sphere's original position is intersecting a triangle before it moves, but this should never happen [smile] This is how it works. Keep in mind that this is totally unoptimized testing code. Also written more for readablity than efficiency.

// va, vb, and vc are the vertices of the triangle, while "normal" is it's normal.
BOOL MovingSphereTriangleCol(const VEC &pos_old, const VEC &pos_new, FLOAT radius, const VEC &va, const VEC &vb, const VEC &vc, const VEC &normal)
{
    // Create a ray (later on, this can be done outside of this method and the ray passed to it. Since all triangles will use the same ray)
    VEC ray_pos = pos_old;
    VEC ray_dir = normalized( pos_new - pos_old );
    FLOAT ray_length = length( pos_new - pos_old );

    // Intersect this ray with the triangle plane,
    // but push the plane out by the radius of the sphere
    // FLOAT IntersectPlane(const VEC &any_plane_pos, const VEC &plane_normal, const VEC &ray_pos, const VEC &ray_dir)
    FLOAT distance_to_pushed_plane = IntersectPlane( va + (normal * radius), normal, ray_pos, ray_dir );

    // If the distance negative, we are moving the other direction
    // Note I have not coded the condition where the ray is parallel to the plane yet
    if( distance_to_pushed_plane < 0.0f )
        return FALSE;

    // If we didn't hit the pushed plane, we can't hit the triangle
    if( distance_to_pushed_plane > ray_length )
        return FALSE;

    // Push this intersect point back to the real plane of the triangle
    VEC pushed_hit = ray_pos + (ray_dir * distance_to_pushed_plane);
    VEC tri_plane_hit = pushed_hit + ( normal * -radius );

    // See where this point is relative to the triangle
    // KVal_TriEdge GetTriangleEdgeThatPointIsOutsideOf(const VEC &va, const VEC &vb, const VEC &vc, const VEC &point)
    KVal_TriEdge tri_edge = GetTriangleEdgeThatPointIsOutsideOf( va, vb, vc, tri_plane_hit );

    // If inside the triangle, it definitely collided on the triangle face
    if(tri_edge == TRI_EDGE_INSIDE)
        return TRUE;

    // Get the closest point on the triangle (edge) to the plane intersect point
    VEC closest;
    switch( tri_edge )
    {
        //   GetClosestPointOnLineToPoint(VEC *closest, const VEC &line_a, const VEC &line_b, const VEC &point)
        case TRI_EDGE_AB: GetClosestPointOnLineToPoint( &closest, va, vb, tri_plane_hit ); break;
        case TRI_EDGE_BC: GetClosestPointOnLineToPoint( &closest, vb, vc, tri_plane_hit ); break;
        case TRI_EDGE_CA: GetClosestPointOnLineToPoint( &closest, vc, va, tri_plane_hit ); break;
    }

    // Do an intersect with a sphere on this edge location
    // Note that by "capsule" below, I'm meaning the connection of the two sphere locations by a cylinder
    // FLOAT IntersectSphere(const VEC &sphere_pos, FLOAT sphere_radius, const VEC &ray_pos, const VEC &ray_dir)
    FLOAT dist_to_edge_from_capsule = IntersectSphere( closest, radius, ray_pos, ray_dir );

    return dist_to_edge_from_capsule >= 0.0f && dist_to_edge_from_capsule < ray_length;
}


edit: fixed a terrible typo on the last line What do you think? Too much math for a simple job? [smile] Please let me know if anyone can spot any danger or holes in this routine. Also let me know if something in the function doesn't make sense. I changed it around a lot to make it more friendly. I may have some variable names that are not matching [wink] Thanks for any suggestions [Edited by - Jiia on November 11, 2004 7:36:34 PM]
Advertisement
Have you put this through some tests? Such as carrying out the collision and drawing the results, including contact points and normals?

Just looking over your code, there are a couple of things that don't look quite right to me. I hesitate to say anything though, because I could easily be wrong. But if you were to test it and find that it failed in certain cases, I have some ideas about where the problems might be...

One consideration is that the sphere can be 'behind' two edges, in which case it can potentially collide with either of them. But maybe you're handling that case...

Anyway, blah blah blah. The real question is, does it work? And does it work under all conditions (that you can devise tests for anyway)?
This Article by Paul Nettle does basically the same thing and there is a well known issue with it...

When I tried to implement Nettle's code I ran into this problem:
the closest point on the triangle to the collision point of the plane is not necessarily going to be the point where the sphere collides...

I have absolutely no idea why this is... it seems counterintuitive to me... but I recorded actual instances where the triangle and the sphere are clearly colliding, but not at the closest point on the edge... so my code didn't notice it...

As far as I know, the only real way to accurately do this is to test a "sweeping sphere" against the triangle using quadratic equations... Kaspar Fauerby has a good explanation of this in his article but I can't seem to find it at the moment...
It's hard to explain the closest-point thing without pictures, but just because a sphere happens to hit the *plane* of the triangle at point X doesn't mean that point Y, where it actually hits the triangle, will be the closest point on the triangle to point X.

You are correct about using quadratics - I know of no working implementation that solves the problem geometrically (that doesn't mean there isn't one, though, and I'd certainly be interested if there were).

Get ahold of Kasper Fauerby's paper if you can. I have it but I'm not sure if it's appropriate to just pass it around (?). It contains the equations for sweeping a sphere against a point (commonly available) and against a line segment (a little harder to find).
Actually, this method is not using the triangle's plane intersect point to find the closest edge point. It intersects the plane after it has been pushed out by radius. It then pushes that intersect point back to the real plane and uses that to find the closest edge point. If a sphere hits the triangle, it's ray will always hit on this plane area, unless it hits an edge (hits the side of the triangle, rather than it's face, passing through its plane to do so).

It seems to work perfectly, except when the ray origin starts behind the plane + (normal * radius). This only happens if the sphere is moving mostly parallel to the triangle, and hits it's edge. Like if you didn't lift your foot high enough on a step, it bumps into the corner. Here it is failing, but only on the triangles that would be facing up. The tris facing your foot would still stop ya.

In any rate, the problem lies where I'm trying to place a sphere where the ray will most likely intersect it, but on an edge. This sphere location is slightly off when the ray is at extreme angles to the triangle plane. It is rare, but unacceptable. I think I'm going to be forced to find the closest point on the missed edge to a line, rather than point. I know this will fix all of the problems.

Another potential fix may be to pull the ray origin back farther until it is outside of this pushed plane. I think I'll try this first [smile]

Here is a picture of what I'm saying. If half of the sphere (half sphere = full radius) is as thick as this pushed plane, where can the sphere ray hit the pushed plane that the sphere would not hit on the real plane?
Image Hosted by ImageShack.us

[Edited by - Jiia on November 11, 2004 8:53:52 PM]
Quote:Original post by Jiia
Actually, this method is not using the triangle's plane intersect point to find the closest edge point. It intersects the plane after it has been pushed out by radius. It then pushes that intersect point back to the real plane and uses that to find the closest edge point. If a sphere hits the triangle, it's ray will always hit on this plane area, unless it hits an edge (hits the side of the triangle, rather than it's face, passing through its plane to do so).


Hello again...

I don't want you to feel like I'm putting you down... I think you're doing some really creative thinking here... stuff that I would never have been able to come up with on my own...

But I still think that if you read Nettle's paper you'll find that you are doing almost exactly the same thing... the only difference is that you're pushing the plane out by the sphere's radius and Nettle pushes the ray over by the sphere's radius... and if you think about it, that gives you the same result...

Thus I would imagine (obviously I'm not sure and could be wrong) that the same flaws in his algorithm will pop up in yours...

Trust me, I did not want to believe that I had to use quadratics... I tried all kinds of different methods for picking the point on the triangle that I would test against the sphere... to no avail

With all that said, I have not actually tried your code yet and it is possible that you have fixed the Nettle algorithm... I know there are other people on GDNet who are more proficient at collision detection than I and I'm hoping that they will notice this thread...

by the way, if you are interested, I found Kasper Fauerby's paper: collision.pdf
Quote:Original post by TempusElf
I don't want you to feel like I'm putting you down... I think you're doing some really creative thinking here... stuff that I would never have been able to come up with on my own...

But I still think that if you read Nettle's paper you'll find that you are doing almost exactly the same thing... the only difference is that you're pushing the plane out by the sphere's radius and Nettle pushes the ray over by the sphere's radius... and if you think about it, that gives you the same result...

I don't think there is a way to move the ray after intersection that would have the same effect as intersecting the plane pushed out, is there? Well, unless you did some kind of crazy angle calculation and multiplied that with radius.

Okay, this much I'm almost positive of. Let me know if you can think of a situation where this is not true. If the sphere starts outside of the pushed plane, and the intersecting ray from the start position to the new position intersects the pushed plane, that ray location is exactly where the sphere will hit the triangle along it's movement path. I'm not saying the ray is telling us where on the triangle it hits, I'm saying the ray tells us how far the sphere moved before it intersected the triangle.

The problem I'm having is when the start position starts inside of the pushed plane. This happens when the sphere is moving almost parallel to it. I don't see any other problems so far.

Now it's time to admit that I totally suck at math [lol] My facts = weak theories. But I'm working on it. That's why I'm playing with this stuff. Okay, that's a lie. I just want to have invincible collision for my game. But the math boost is a good thing [wink]
Arg... If I had web hosting I could draw a picture that would show you what I mean... This image from Nettle's article will have to suffice



B is the velocity of the object... it has been moved over by the purple ray which represents the opposite of the plane's normal

OK

now on top of this same image imagine your algorithm (I'm trying to show you that I think you come up with the same result)

you would, instead of moving B, leave it's origin at the center of the sphere and collide it against your pushed plane... you would then project that collision point back onto the original plane, and if I understand your algorithm correctly, you would end up with the exact same point that Nettle has circled here

I know you're not saying that the point is where the sphere collides, but neither is Nettle... that's what I'm trying to tell you... the two algorithms are very similar... so similar that I believe they are nearly the same.. and if you search the forums for his name you'll find that many people have discovered the subtle flaw
Image Shack will let you upload unlimited images that stay on the net until they've not be viewed for a year [smile]

I'm extremely curious to know what this flaw is. I'll look around and see if I can figure it out.

Also, when the ray does not intersect the inside of the triangle, I place a sphere on the closest edge and do another intersect there. This doesn't fix the flaw? Also, I have yet to figure out HOW to place the sphere in exactly the right place on the edges yet. Doing an intersect with a capsule (cylinder on edge, spheres on vertices) on the missed edge, or even all edges would surely be perfect. Or, even if I can find the closest point on a line to another line, the idea is the same. Placing the sphere there should definitely work.
When I was trying to implement Nettle, the problem I kept having was that when I determined that the sphere does not hit the triangle head on (meaning in the middle of the triangle), but it may hit the triangle on the edge, the point on the edge of the triangle that I picked to test against would sometimes not be the point where the sphere actually hits...

I tried many different methods of selecting this point and none worked...

However, I never tried to find the closest point on the edge to a line, the way you described in your other post

After reading your other post and thinking about it some more, I wonder if maybe selecting the closest point on the edge to the path of the sphere would resolve the problems I had...

I wish I had more time this week to test out your idea on my old project

by the way... do I understand what you were saying correctly?: It looks like in the original code you posted you were using the plane intersection point to find the closest point on the triangle, but then in other posts you talked about modifying this so that it picks the point based on the object's path... is that correct?

This topic is closed to new replies.

Advertisement