Friday, April 24, 2009

Quick 'n Dirty Point-Plane Collision Detection

A couple weeks ago I was in a frenzy to implement collision detection in my SkyCop demo. Sure, I planned to go back and study it in more detail at some point, but for the moment I just wanted to get something done so I could avoid flying through enemy ships and start blowing them up. After a few days of searching, I quickly realized that collision detection is no trivial task; it's a field of study all on its own! I started with this flipcode article that served as a good introduction but left me a bit confused. After more research and trial-and-error I had a working example function that I would like to share with anyone needing to feed that same primal urge to get something working quickly.

The function, written in C++ for Direct3D 9, determines if a single point will cross a triangular plane (parameters vP1-vP3 specified in clockwise order). Parameter prevPos is the initial position your character/camera/object moves from and curPos is the position to which it will be moved. For example, if you want to detect if an FPS player will collide with a wall, you would call this function with the camera's initial position as prevPos and its predicted next position [prevPos + (speed * direction)] as curPos. Submit a comment if you have any questions, and keep in mind I will discuss the code in detail in a future post.

Btw, I'm sure there are engines that handle all this stuff for you, but since I haven't gotten into those yet it was a nice exercise for me. And I do apologize for the ugly formatting. I'll work on making code selections look better in future posts!

enum PlanePosition
{
   PlaneFront,
   PlaneBack,
   OnPlane
};

bool IntersectsTriangle(D3DXVECTOR3 prevPos, D3DXVECTOR3 curPos, 
          D3DXVECTOR3 vP1, D3DXVECTOR3 vP2, D3DXVECTOR3 vP3)
{
    float p, d, t, thetaSum;
    PlanePosition prevLoc, curLoc;
    D3DXVECTOR3 ray, v1, v2, v3, vNormal, intersect;
 
    // Compute normal vector for the plane
    v1 = (vP2 - vP1);
    v2 = (vP3 - vP2);
    D3DXVec3Cross(&vNormal, &v1, &v2);
    D3DXVec3Normalize(&vNormal, &vNormal);

    
    // Compute plane distance
    d = - D3DXVec3Dot(&vP1, &vNormal);

    
    // Classify positions using planar equation
    p = (D3DXVec3Dot(&vNormal, &prevPos) + d);
    if ( p > 0.0f ) prevLoc = PlaneFront;
    else if ( p < 0.0f ) prevLoc = PlaneBack;
    else prevLoc = OnPlane;

    
    p = (D3DXVec3Dot(&vNormal, &curPos) + d);
    if( p > 0.0f ) curLoc = PlaneFront;
    else if (p < 0.0f ) curLoc = PlaneBack;
    else curLoc = OnPlane;
        
    if (prevLoc == curLoc) return false;
   
    // Crossed the plane, did intersect occur inside triangle?
    // Get normalized ray
    ray = curPos - prevPos;
    D3DXVec3Normalize(&ray, &ray);

    
    // t = point along ray where intersection occurs
    t = - (d + D3DXVec3Dot(&vNormal, &prevPos)) 
        / D3DXVec3Dot(&vNormal, &ray);

    
    // Get intersection point on the plane
    intersect = prevPos + (ray * t);

    
    // Determine if intersection is within triangle plane
    // Angles around intersection should total 360 degrees (2 PI) 
    v1 = intersect - vP1;
    v2 = intersect - vP2;
    v3 = intersect - vP3;
    D3DXVec3Normalize(&v1, &v1);
    D3DXVec3Normalize(&v2, &v2);
    D3DXVec3Normalize(&v3, &v3);
 
    thetaSum = acos(D3DXVec3Dot(&v1, &v2)) 
             + acos(D3DXVec3Dot(&v2, &v3)) 
             + acos(D3DXVec3Dot(&v3, &v1));

    
    // If sum == 2PI we have an intersection!
    if ((thetaSum >= ((2 * D3DX_PI) - 0.1)) && 
        (thetaSum <= ((2 * D3DX_PI) + 0.1)))
    {
        return true;
    }

    
    return false;
}

3 comments:

  1. Can you put this code in java? i tried but coud not get to work.

    thanks

    ReplyDelete
  2. I would like to do that at some point, but unfortunately I can't guarantee it will be anytime soon. Perhaps someone better versed in Java will be able to comment to help you.

    Realize that D3DXVec3Dot returns a dot product of the two input vectors; D3DXVec3Normalize normalizes its second input vector storing the result in the first input parameter; and D3DXVec3Cross takes the cross product of the second and third parameters and stores the result in the first parameter. Hopefully understanding how those functions work can help you convert this to Java.

    Also I've read that using the sum of angles (last part of the code) to determine if an intersection occurred is not the best approach. Do a search for "point in triangle detection" and "barycentric" to see what I mean.

    ReplyDelete
  3. Hi Thank you for replying !

    I build your code using java, using vector class and as you said to find intersection is a difficult part in java, and confused with ray, how to determined. The game I build a plane crash in to the wall and all I know is plane start point and its current moving point.

    I got to work to this point

    // Classify positions using planar equation

    I could not get to work from

    // Crossed the plane, did intersect occur inside triangle?

    I will search what you suggest :)

    Thanks

    ReplyDelete