Collision Detection (Point-Polygon)

Member
Posts: 148
Joined: 2003.03
Post: #1
I am rendering a simple triangle

[sourcecode]
my_object.vertices[0].x = 0.0;
my_object.vertices[0].y = 0.0;
my_object.vertices[0].z = 0.0;

my_object.vertices[1].x = 0.0;
my_object.vertices[1].y = 1.0;
my_object.vertices[1].z = -1.0;

my_object.vertices[2].x = 1.0;
my_object.vertices[2].y = 1.0;
my_object.vertices[2].z = -1.0;
[/sourcecode]

and I want to tell if my camera collides with the triangle. So far, I am able to tell if my camera collides with the triangle's plane, using this code

[sourcecode]
vertex u,v,n,n_normalized;
float n_length,d,solution;
u.x = my_object.vertices[2].x-my_object.vertices[0].x;
u.y = my_object.vertices[2].y-my_object.vertices[0].y;
u.z = my_object.vertices[2].z-my_object.vertices[0].z;
v.x = my_object.vertices[2].x-my_object.vertices[1].x;
v.y = my_object.vertices[2].y-my_object.vertices[1].y;
v.z = my_object.vertices[2].z-my_object.vertices[1].z;

n.x = u.y*v.z - u.z*v.y;
n.y = u.z*v.x - u.x*v.z;
n.z = u.x*v.y - u.y*v.x;

n_length = sqrt(n.x*n.x + n.y*n.y + n.z*n.z);

n_normalized.x = n.x/n_length;
n_normalized.y = n.y/n_length;
n_normalized.z = n.z/n_length;

d = n_normalized.x*my_object.vertices[0].x + n_normalized.y*my_object.vertices[0].y + n_normalized.z*my_object.vertices[0].z;
solution = (n_normalized.x*camera.position.x + n_normalized.y*camera.position.y + n_normalized.z*camera.position.z)-d;
[/sourcecode]

If anyone understands what I am doing (I hope someone does), if solution is zero (or near zero), then the camera has collided with the plane on which my_object (the triangle) lies. Although this is a step forward, now I need to figure out of the camera actually collides with the polygon itself, and not just the plane on which it lies. Anyone have any clues as to what step I should take next? Thanks in advance.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
You could use the planes through the pairs of vertices of the triangle that are perpendicular to the triangle's plane, and check if the camera is in front of each of those planes to check whether it's within the triangle...

There may be better methods, of course, that's just off the top of my head. I'd try Google Rasp
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #3
Seems like it would work. Thanks.
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #4
take the vectors between the 3 vertices, V12, V13, V23, and the point and the vertices V1P, V2P, V3P

The point on the plane of the triangle is in the triangle
if V12.V13 > V12.V1P and V12.V1P > 0
and if -V23.V12 > V23.V2P and V23.V2P > 0
and if -V23.V13 > -V13.V2P and -V13.V2P > 0

This should be largely correct, the concept is that the angle of any pair of the edge vectors should be larger than the angle between one of the edge vectors and the vector to the point which originates from the common point of the edge pair in question.
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #5
i'm not sure if i understand you completely DoooG, but then again, i don't necessarily understand vector math all that well Grin.

Quote:take the vectors between the 3 vertices, V12, V13, V23, and the point and the vertices V1P, V2P, V3P

how would i get the vectors between the 3 vertices V12, V13, V23?

when you say the point, you are talking about the camera position, correct?

and the vertices V1P, V2P, V3P are the vertices of the triangle, right? ie: my_object.vertices[] (from my code above)

Thanks btw, I feel I am getting really close to finally getting past this.
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #6
Code:
// the following is based on code from [url]http://www.ce.chalmers.se/staff/tomasm/raytri/[/url]
// by Tomas Moller, May 2000  
// modified by Ian Rickard, July 2002
static bool intersect_triangle(const Point3f &orig, const Point3f &dir,
        const Point3f &vert0, const Point3f &vert1, const Point3f &vert2,
        bool backface = true, float *t=NULL) {
    Point3f edge1, edge2, tvec, pvec, qvec;
    float det , inv_det;

    // find vectors for two edges sharing vert0
    edge1 = vert1 -vert0;
    edge2 = vert2 -vert0;

    // begin calculating determinant - also used to calculate U parameter
    pvec.MakeCross(dir, edge2);

    // if determinant is near zero, ray lies in plane of triangle
    det = edge1.Dot(pvec);

    if (det > 0) { // IFR: don't care about the coplanar case
        if (t)
            inv_det = 1.0 / det;

        // calculate distance from vert0 to ray origin
        tvec = orig - vert0;
        
        // calculate U parameter and test bounds
        float u = tvec.Dot(pvec);
        
        if (u < 0.0 || u > det)
            return false;

        // prepare to test V parameter
        qvec.MakeCross(tvec, edge1);

        // calculate V parameter and test bounds
        float v = dir.Dot(qvec);
        
        if (v < 0.0 || u + v > det)
            return false;

    } else {
        if (!backface) return false;
        
        if (t)
            inv_det = 1.0 / det;
        
        tvec = orig - vert0;
        
        float u = tvec.Dot(pvec);
        
        if (u > 0.0 || u < det)
            return false;

        qvec.MakeCross(tvec, edge1);

        float v = dir.Dot(qvec);
        
        if (v > 0.0 || u + v < det)
            return false;
    }

    if(t)
        *t = edge2.Dot(qvec) * inv_det;

    return true;
}

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #7
Quote:Originally posted by MacFiend
i'm not sure if i understand you completely DoooG, but then again, i don't necessarily understand vector math all that well Grin.



how would i get the vectors between the 3 vertices V12, V13, V23?

when you say the point, you are talking about the camera position, correct?

and the vertices V1P, V2P, V3P are the vertices of the triangle, right? ie: my_object.vertices[] (from my code above)

Thanks btw, I feel I am getting really close to finally getting past this.


You can get the vectors between the vertices, assuming they are numbered 1, 2, 3, by taking their coordinates and substracting them, so V12 = V2 - V1, and so on.

P is the camera's position mapped to the triangle and V1P = P - V1, etc.

You can project any point P0 to a plane if you know its normal, N, and a point on the plane, V. Simply project V-P0 onto N, and you get the vector pointing to the closest point on the plane. The procedure in my prev. post comes after this. You should check also that proj(V - P0, N).N is positive, in which case P0 is behind the triangle.
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #8
Quote:You can project any point P0 to a plane if you know its normal, N, and a point on the plane, V. Simply project V-P0 onto N, and you get the vector pointing to the closest point on the plane. The procedure in my prev. post comes after this. You should check also that proj(V - P0, N).N is positive, in which case P0 is behind the triangle

OK, DoooG, so should I be using the code I used in my first post in conjunction with the math in your 1st and 2nd post, or is the math in the quote above supposed to replace my code?

I initially tried your method in your 1st post along with my original code, and it doesn't appear to work. Here is what I am trying...

[sourcecode]
...code from my first post...

if(solution<0.18)
{
vertex v12, v13, v23;
vertex v1p, v2p, v3p;

v12.x = my_object.vertices[1].x-my_object.vertices[0].x;
v12.y = my_object.vertices[1].y-my_object.vertices[0].y;
v12.z = my_object.vertices[1].z-my_object.vertices[0].z;

v13.x = my_object.vertices[2].x-my_object.vertices[0].x;
v13.y = my_object.vertices[2].y-my_object.vertices[0].y;
v13.z = my_object.vertices[2].z-my_object.vertices[0].z;

v23.x = my_object.vertices[2].x-my_object.vertices[1].x;
v23.y = my_object.vertices[2].y-my_object.vertices[1].y;
v23.z = my_object.vertices[2].z-my_object.vertices[1].z;

v1p.x = camera.position.x-my_object.vertices[0].x;
v1p.y = camera.position.y-my_object.vertices[0].y;
v1p.z = camera.position.z-my_object.vertices[0].z;

v2p.x = camera.position.x-my_object.vertices[1].x;
v2p.y = camera.position.y-my_object.vertices[1].y;
v2p.z = camera.position.z-my_object.vertices[1].z;

v3p.x = camera.position.x-my_object.vertices[2].x;
v3p.y = camera.position.y-my_object.vertices[2].y;
v3p.z = camera.position.z-my_object.vertices[2].z;

float dot_v12_v13, dot_v12_v1p, dot_v23_v12, dot_v23_v2p, dot_v23_v13, dot_v13_v2p;

dot_v12_v13 = (v12.x*v13.x) + (v12.y*v13.y) + (v12.z*v13.z);
dot_v12_v1p = (v12.x*v1p.x) + (v12.y*v1p.y) + (v12.z*v1p.z);
dot_v23_v12 = (v23.x*v12.x) + (v23.y*v12.y) + (v23.z*v12.z);
dot_v23_v2p = (v23.x*v2p.x) + (v23.y*v2p.y) + (v23.z*v2p.z);
dot_v23_v13 = (v23.x*v13.x) + (v23.y*v13.y) + (v23.z*v13.z);
dot_v13_v2p = (v13.x*v2p.x) + (v13.y*v2p.y) + (v13.z*v2p.z);

if(dot_v12_v13>dot_v12_v1p && dot_v12_v1p>0 && -dot_v23_v12>dot_v23_v2p && dot_v23_v2p>0 &&
-dot_v23_v13>-dot_v13_v2p && -dot_v13_v2p>0)
{
NSLog(@"Collision!");
}
}
[/sourcecode]

Oh yea, I'm assuming when you use "V12.V1P", the "." is supposed to represent Dot-Product, right?

It doesn't work possibly because dot_v12_v1p is negative for some reason, but then again, I probably just have something mixed up. Does your method take into account approximations? The way I am doing this doesn't actually place the camera position exactly on the plane of the triangle, just really close to it. Any ideas?

Inio, I am going to try your example once I make sense of all of it Wow .

OneSadCookie:

Quote:You could use the planes through the pairs of vertices of the triangle that are perpendicular to the triangle's plane, and check if the camera is in front of each of those planes to check whether it's within the triangle...

Would I use cross-products to find triangles perpendicular to the plane? Sorry I keep asking all these questions, I failed Math 3 Rasp .

Thanks everyone.
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #9
Quote:Originally posted by MacFiend
Inio, I am going to try your example once I make sense of all of it Wow .

Here's the source for Point3f:

Code:
struct Point3f {
    GLfloat x,y,z;
    
    void set(Float ix, Float iy, Float iz){x=ix;y=iy;z=iz;}
    Point3f(){}
    Point3f(Float ix, Float iy, Float iz){set(ix,iy,iz);}
    Point3f(const Point3f &v){*this = v;}
    Point3f operator +(const Point3f &t) const {return Point3f(x+t.x, y+t.y, z+t.z);}
    Point3f operator -(const Point3f &t) const {return Point3f(x-t.x, y-t.y, z-t.z);}
    Point3f operator +=(const Point3f &t) {return Point3f(x+=t.x, y+=t.y, z+=t.z);}
    Point3f operator -=(const Point3f &t) {return Point3f(x-=t.x, y-=t.y, z-=t.z);}
    Point3f operator* (Float t) const {return Point3f(x*t, y*t, z*t);}
    Point3f operator*= (Float t) {return Point3f(x*=t, y*=t, z*=t);}
    Float Dot(const Point3f &t) const {float result =  x*t.x+y*t.y+z*t.z; return result;}
    void MakeCross(const Point3f &a, const Point3f &b) {x = a.y*b.z-a.z*b.y; y = a.z*b.x-a.x*b.z; z = a.x*b.y-a.y*b.x;}
    void Normalize() {float inv = FastSqrtRecip(x*x+y*y+z*z); x*=inv; y*=inv; z*=inv;}
    operator GLfloat*() {return &x;}
    operator const GLfloat*() const {return &x;}
    Float Length() const {return FastSqrt(x*x+y*y+z*z);}
    Float Length2() const {return x*x+y*y+z*z;}
    Point3f ProjectOntoNorm(const Point3f &onto) {return onto*Dot(onto);}
    Point3f ProjectOnto(const Point3f &onto) {return (onto*Dot(onto))*(__fres(onto.Length2()));}
    Float& operator[](int index) {return (&x)[index];}
};
inline Float Length(const Point3f &i) {return FastSqrt(i.x*i.x+i.y*i.y+i.z*i.z);}

That should help you understand what it's doing. Also backface is to turn off collision checks against backface (points rotate clockwise around ray).

In general, how you would use this is set the start point to the position of the location of the camera in the previous frame, and the direction to the difference between the previous and current frame. If the value returned in t is in 0..1 (and the function returned true) then the movement of the camera passed through the triangle.

oh, and you probably want to take the "static" off the function, I forgot to delete that. (the codes as pasted is used as part of a larger mangle of bsp collision code, so static is appropriate.)

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #10
Well, I am not quite sure with the signs, but if you note, I did put some negative signs in my previous equations.

The pseudocode should be something like this:

if distance from point to plane < min_distance
if the point projected on the plane lies inside the triangle (by the dot product tests)
return true
else return false

I have just noticed I have not implemented this piece of code before, I will do it and test it to make sure, but I am sure the algorithm works, even if I made some sign mistakes.

Another thing is that it does matter which way the normal points. If it points the wrong way, eg. to the back of the tri, the test will obviously not work. And it should work even with an approximate projection to the triangle plane.
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #11
Quote:Originally posted by DoooG
if distance from point to plane < min_distance
if the point projected on the plane lies inside the triangle (by the dot product tests)
return true
else return false
Two problems with that:
1. what if the camera moves more then 2*min_distance units in a single frame?
2. what about convex seams?

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #12
Quote:Originally posted by inio
Two problems with that:
1. what if the camera moves more then 2*min_distance units in a single frame?
2. what about convex seams?

Convex seams? A triangle? I am lost Blink

You have to consider the camera's position in the previous frame, draw a line segment to the current pos, find the intersection. If there is any, the camera collided, if there is none, it didn't. Additionally, you can test the end position, too.
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #13
Do you think you could possibly post an example using this method? I've tried several variations to it, but it doesn't seem to work properly. I can get it to sort of recognize a collision, but it's still not correct.
Quote this message in a reply
Member
Posts: 145
Joined: 2002.06
Post: #14
Quote:Originally posted by DoooG
Convex seams? A triangle? I am lost Blink
You aren't testing against a single triangle, you're testing against a mesh of triangles. where two triangles meet is called a seam. each seam can be classified as convex, concave, or planar depending on whether the triangles face away from each other, towards each other, or are coplanar. Your method works OK for situations where they're coplanar or face towards each other, but if the triangles face away from each other there's a sliver between the two triangles where you can get stuck.

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Quote this message in a reply
DoG
Moderator
Posts: 869
Joined: 2003.01
Post: #15
Quote:Originally posted by inio
You aren't testing against a single triangle, you're testing against a mesh of triangles. where two triangles meet is called a seam. each seam can be classified as convex, concave, or planar depending on whether the triangles face away from each other, towards each other, or are coplanar. Your method works OK for situations where they're coplanar or face towards each other, but if the triangles face away from each other there's a sliver between the two triangles where you can get stuck.


The method works for a single triangle, yes, that was asked, ircc. For a mesh, you obviously have to make some more assumptions, for example that the mesh is regular (a single surface). With a regular mesh, and allowing collisions with multiple triangles at the same time, things should work out just fine, since the proposed algorithm correctly determines collision with each individual triangle. Right? (i think)
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Polygon budgets Kerome 1 2,830 Mar 7, 2010 04:55 AM
Last Post: mikey
  glut polygon winding strangeness OptimisticMonkey 2 3,005 Sep 7, 2009 06:27 PM
Last Post: OptimisticMonkey
  2D Pixel Collision Detection using OCCLUSION Elphaba 0 3,286 Jun 8, 2009 06:30 AM
Last Post: Elphaba
  the best way to do collision detection ghettotek 26 10,176 Jun 4, 2009 02:30 PM
Last Post: AnotherJake
  Getting the Normal for a polygon. Jaden 3 5,671 May 1, 2009 01:47 PM
Last Post: Nosredna