how to detect collision between point and triangle in a mesh?

Started by
6 comments, last by Buckeye 9 years, 5 months ago

Hi

I know algorithm how to detect if point is inside triangle (in details - at plane created by vertices of triangle and bounded to triangle area). Here is my implementation:


bool isPointInTriangle(D3DXVECTOR3 P, D3DXVECTOR3 A, D3DXVECTOR3 B, D3DXVECTOR3 C)
{       
D3DXVECTOR3 v0 = C - A;
D3DXVECTOR3 v1 = B - A;
D3DXVECTOR3 v2 = P - A;


float dot00 = D3DXVec3Dot(&v0, &v0);
float dot01 = D3DXVec3Dot(&v0, &v1);
float dot02 = D3DXVec3Dot(&v0, &v2);
float dot11 = D3DXVec3Dot(&v1, &v1);
float dot12 = D3DXVec3Dot(&v1, &v2);


// Compute barycentric coordinates
float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
float v = (dot00 * dot12 - dot01 * dot02) * invDenom;


// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v < 1);
}

However I don't know how to use it in order to detect collision, because if You make collision algorithm You are in fact not interested if point is in triangle. You are in fact interested if point is on positive half space of triangle - none collision. If point is in negative half of space or in triangle then we have collision.

Here is my implementation of half space test:


Collision::PlaneSide Collision::HalfSpaceTest(const D3DXVECTOR3& vecTestPoint, const D3DXVECTOR3& vecNormal, const D3DXVECTOR3& vecPointOnPlane, const float offset)
{
    //n o v = |n||v|cosL = 1|v|cosL = distance


//Calculate a vector from the point on the plane to our test point
    D3DXVECTOR3 vecTemp(vecTestPoint - vecPointOnPlane);


    //Calculate the distance: dot product of the new vector with the plane's normal
    float dist(D3DXVec3Dot(&vecTemp, &vecNormal) - offset);


    if(dist > COLLISION_EPSILON)
    {
        //Point is in front of the plane
        return FRONT_PLANE;
}
else if(dist < -COLLISION_EPSILON)
{
//Point is behind the plane
return BEHIND_PLANE;
}
//If neither of these were true, then the point is on the plane
    return ON_PLANE;
}

And I have a problem how to connect those two algorithms. I suppose firstly I have to execute half space test. And if half space test returns that point is BEHIND_PLANE (negative half space) or ON_PLANE then I need to detect somehow if point come through this part of space which belongs to this specific triangle.

Could somebody help me to clear it?

Advertisement

You haven't described your variables or whether you're casting a ray, or whether you're only trying to determine the closest point in the triangle to the test point closer than "offset."

IF you're only trying to determine the closest point closer than a given offset (or radius? a sphere-triangle intersection, for instance) -

You can calculate the point-in-plane as:


// vecNormal must be normalized. I.e., a unit vector
// if you're not interested in the distance to the point, remove the use of float* out_distance
bool PointCloserThanOffset( D3DXVECTOR3 vecTestPoint, D3DXVECTOR3 vecPointOnPlane, D3DXVECTOR3 vecNormal, float offset,
   float *out_distance, D3DXVECTOR3 *out_pointInPlane)
{
   // create a vector from the test point to any point in the plane
   D3DXVECTOR3 vecTemp(vecTestPoint - vecPointOnPlane);
   // calculate the distance from the test point to the plane
   float distance = D3DXVec3Dot(&vecTemp, &vecNormal);
   if( distance > offset ) return false;
   *out_distance = distance;
   *out_pointInPlane = vecTestPoint + vecNormal * distance;
   return true;
}
...
// use the function
float distance;
D3DXVECTOR3 pointInPlane;
if( PointCloserThanOffset( vecTestPoint, vecPointOnPlane, vecNormal, offset, &distance, &pointInPlane )
{
   // if desired, make further tests on "distance." Not sure what the intent of your collision test is.
   // do your barycentric coord test here using D3DXVECTOR3 pointInPlane
}


If desired, you can add to the PointCloserThanOffset function:


if( fabs(distance) < EPSILON) distance = 0;

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

Hi

My aim is to calculate if a point P(x,y,z) collide with a traingle described by A(x,y,z),B(x,y,z) and C(x,y,z). It collide with the traingle when

1.) it is on the triangle plane in area ABC

or

2.) it is on negative half space of triangle plane and line from point perpendicular to triangle plane is inside area ABC

OK, so firstly I have to execute PointCloserThanOffset(...) and then if results is true I have to execute isPointInTriangle(...)

Do You know less cost algorithm?

For ray triangle intersection (I combine plane and triangle intersection) I use an implementation of the Moller-Trumbore algorithm which uses two cross-products. Many algorithms use 3 cross-products, so M-B may be slightly faster in that regard.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

ok and what is really "ray direction"? I don't have any "ray direction" attributable to any object. So this Moller-Trumbore algorithm cannot be used for mesh collision when You don't have "ray direction" variable attached to vertex?


It collide with the traingle when
1.) it is on the triangle plane in area ABC
or
2.) it is on negative half space of triangle plane and line from point perpendicular to triangle plane is inside area ABC


I don't have any "ray direction" attributable to any object.

You mention "line from point perpendicular to triangle plane." Is that not a direction? Your collision criteria 2) is a ray-cast from the point to the plane parallel to the plane normal. If I understand your intent - if distance is <=0, the direction is the plane normal.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

"line from point perpendicular to triangle plane." - no it is not direction. It is just the closest distance from point to the mesh face.

it is not ray direction because between two frames the movement direction might be not perpendicular to the triangle plane. I mean in frame N point is on positive half space, in frame N+1 on negative half space, so we have collision and ray direction might not be perpendicular to triangle face.

So in order to have ray direction I should remember position of point in frame N and then in frame N+1 I should calculate ray as = P(N+1) - P(N) and then normalize it. And this value I should introduce into "D" parameter, am I right??? This is the way You do when using Moller-Trumbole algorithm? Or You determine ray direction in other way?

int triangle_intersection( const Vec3 V1, // Triangle vertices

const Vec3 V2,
const Vec3 V3,
const Vec3 O, //Ray origin
const Vec3 D, //Ray direction
float* out )

You previously posted your criteria for a collision.

Hi

My aim is to calculate if a point P(x,y,z) collide with a traingle described by A(x,y,z),B(x,y,z) and C(x,y,z). It collide with the traingle when

1.) it is on the triangle plane in area ABC

or

2.) it is on negative half space of triangle plane and line from point perpendicular to triangle plane is inside area ABC

Is that, in fact, your criteria? If it is, then, along with the distance calc posted above, casting a ray from the point in the direction of the triangle normal will provide you with results to determine 1) and 2).


it is not ray direction because between two frames the movement direction might be not perpendicular to the triangle plane. ... between two frames the movement direction ... And this value I should introduce into "D" parameter, am I right???

Movement of what?? You've said nothing previously about "frames" or a moving object. If what you previously posted is NOT your criteria for collision, and you're asking for help with something, you'll have to clearly describe the problem you're trying to solve.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

This topic is closed to new replies.

Advertisement