Figuring Collisions Between Lines and Faces/Planes

Sage
Posts: 1,066
Joined: 2004.07
Post: #1
I would like to have some people assist me in understanding this sort of math. I've looked at page after page of 3d math equations but all I can pull from it are obscure Greek symbols and confusion.

With my own setup, I have a beginning point and a directional vector for the line. I have coordinates of vertices of the faces I wish to check it against. I also have the normals for the faces so I could theoretically check the line against an infinitely large plane and get the coordinates and check those against the face.

Can anyone assist me at all? Sample code? Words of advice? Good websites? Prayers LOL?
Quote this message in a reply
Member
Posts: 320
Joined: 2003.06
Post: #2
if at all possible, use ODE or something similar. Working it all out yourself is no fun IMHO, and someone else has already done it Wink

Otherwise, check out http://nehe.gamedev.net/data/lessons/les...?lesson=30 and have a look at the text and code snippet on that page in the paragraph Ray - Plane Intersection Detection. Worked for me with a little trial and error.

David

Chopper, iSight Screensavers, DuckDuckDuck: http://majicjungle.com
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #3
I though about ODE but couldn't find the Mac "version". I remember some one here posting about it but I can't find it (searching for ODE doesn't work). I'd love to at least try it.

I'll give NeHe a look sometime as well. Thanks.
Quote this message in a reply
Member
Posts: 320
Joined: 2003.06
Post: #4
http://ode.org/

you will need to build the library by following the instructions in INSTALL. Then find some example code that does something similar to what you want, copy and paste, #include <ode/ode.h> and you're away laughing.

Chopper, iSight Screensavers, DuckDuckDuck: http://majicjungle.com
Quote this message in a reply
MarkJ
Unregistered
 
Post: #5
This is a very nice ray/triangle intersection algorithm, and it is what I have been using for collision detection in my latest game.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #6
Here's something I found online about this:
Code:
Intersection Between a Line and a Plane
This occurs at the point which satisfies both the line and the plane equations.
Line equation: p = org + u * dir                             (1)
Plane equation: p * normal - k = 0.                          (2)
Substituting (1) into (2) and rearranging we get:
(org + u * dir) * normal - k = 0
ie  u * dir * normal = k - org * normal
ie  u = (k - org * normal) / (dir * normal)
If (d * normal) = 0 then the line runs parrallel to the plane and no intersection occurs.
The exact point at which intersection does occurr can be found by plugging u back into the line equation in (1)
Now I'm thinking that the u * dir is actually scalar multiplication and dir * normal and org * normal are actually dot products but I don't know for sure. Can anyone verify this for me?
Quote this message in a reply
MarkJ
Unregistered
 
Post: #7
Nick, did you look at that Trumbore97 algorithm? The C implementation for it is right here. All you need to do is split the poly faces you want to check against into triangles Then you pass in the coordinates of the triangle vertices, the point you want to check against, and its normal. The function will give you back the distance from the point to the triangle, so it makes collision detection very simple.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #8
Unfortunately I need to test the line because I have a seemingly infinite amount of points to check. I don't have a point to check against the triangle. I have a line 1000 units in length (I had to assign a number to help make some things work, i.e. I couldn't just have a origin and direction making a line 1 unit in length) so checking points along the line is a daunting task. That is why I'm working on something like this.

I do, however, have a new idea for checking collisions that should be interesting if I can get it to work properly.
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #9
Here's my setup after looking at two websites and NeHe for ideas on collisions. I just wrote this up but it doesn't quite work as it should. The comments should help explain everything. Technically I left out the part that sees if the point of collision is simply on the plane or actually on the face of the box but I just wanted to see the collisions with the planes work but it doesn't. I'm not sure why. Any ideas or suggestions (besides using someone else's code)?

Code:
bool CheckCollision(Mesh mesh, Bullet bullet, Vector &vertex)
{
    bool collision = false;                        //the function's return variable set to assume no collision
    if(bullet.GetActive())                        //if the bullet is actively in use
    {
        Box        b = mesh.GetBounds();            //the mesh's bounding box (axis aligned)
        Vector    o = bullet.GetPosition();        //the origin of the bullet's ray
        Vector    d = bullet.GetDirection();        //the direction of the bullet
        Vector    n;                                //to store the normal of the plane    
        Vector    colPoint[6];                    //stores 6 points of impact (one for each plane of the box)
        float    distance[6];                    //stores the 6 distances from the bullet's origin to the collision points
        float    theDistance = 1000.0;            //sets a total distance for comparison when finding closest collision
        bool    onBox[6];                        //tells whether the 6 collision points are on the bounding box or not
        int        face;                            //stores which face is ultimately hit by the bullet
        
        //find all plane collisions and see if they are in or on the box
        for(int i=0; i<6; i++)                                        //count through each face
        {
            n = b.GetFace(i).GetFN();                                //get the current face's normal
            if(DotProduct(d,n)>0)                                    //prevent a divide by 0 error (if 0, the plane and line are parallel)
            {
                distance[i] = (DotProduct(o,n)) / DotProduct(d,n);    //get the distance along the ray until the ray and plane collide
                if(distance[i]>0)                                    //if the collision is positive along the ray (in front of player)
                {
                    colPoint[i] = o + (d * distance[i]);            //set our collision point using the ray equation and distance
                    onBox[i] = true;                                //for starters, just assume we're on the box (just to try and get results)
                }
            }
        }
        //find the closest point on the mesh and assign it to the vertex
        for(int i=0; i<6; i++)                        //count through each face
        {
            if(onBox[i])                            //if the face had a collision on it
            {
                if(distance[i]<theDistance)            //if the collision on face i is closer than theDistance
                {
                    collision = true;                //set the overall return variable to true
                    face = i;                        //make i the face of collision
                    theDistance = distance[i];        //set theDistance to the new distance for later comparison
                }
            }
        }
        vertex = colPoint[face];                    //set the vertex parameter to the closest collision point for drawing
    }
    return collision;                                //return our collision variable
}
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Camera Collisions Nick 4 3,667 Mar 9, 2005 08:57 AM
Last Post: Puzzler183