Ray tracer and collision detection

This is a discussion on Ray tracer and collision detection within the Game Programming forums, part of the General Programming Boards category; Ray tracing and collision detection are...well, kinda messy. I've read some of the tutorials online and always asked myself: where ...

  1. #1
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200

    Ray tracer and collision detection

    Ray tracing and collision detection are...well, kinda messy. I've read some of the tutorials online and always asked myself: where and when the heck ray tracing is going to start? and how do they know which direction it will go. After a little digging and sticking my brain into the computer's monitor, i've finally understand something.

    This is basically what i understand. If it is not a good way to do it, please give advice.

    So the ray will have a start point and end point. The start point will be the position of the tangible object, and the end point will be where it goes to. To determine the direction of the ray, the object's velocity will be add to the object's position:
    Code:
    Vector3d startPoint, endPoint, velocity(1, 1, 1);
    endPoint = startPoint + velocity;
    With this kind of calculation, every step (or frame) the object moves, it will calculates if the end point will hit anything when the velocity added to the object's position. (i don't know if this is a good idea to do it, but it is pretty simple).

    Well, ray tracing will be useful for collision detection in 3d space. My problem is (i forgot some of the stuff from geometry) determine the plane in 3d space. I've been looking all over the place and found out: the plane's equation is
    Code:
    Ax + By + Cz + D = 0
    It looks simple but what the heck is it mean. I know the x, y, z stands for the coordinate but what is 'D' stand for? Can anyone please tell me how does the plane works in 3d space? Thanks
    Hello, testing testing. Everthing is running perfectly...for now

  2. #2
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    But for computer graphics you will want this:

    Ax + By + Cz=D

    So that D's sign is not flipped.


    Ray tracing is a bit more than that. It basically traces a ray of light that goes through pixel x,y at a set angle. It then calculates what, if anything, the ray hits and how much it's light properties are affected. By knowing the materials of the objects it hits, you can gradually change the light properties of the ray using color equations.

    There are several types of intersections to test for but the basics will give you a complex scene since most scenes are just large collections of simple objects

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    I think someone here has coded a raytracer program. They traced a cool looking pic of a teddy bear or something. I'm not sure if was Perspective or not.

    You might want to do a search.

  4. #4
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    hdragon is working on raytracing for a collision method in our engine.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  5. #5

    Join Date
    May 2005
    Posts
    1,041
    >>stands for the coordinate but what is 'D' stand for?

    The closest distance from the origin to the plane.

    The dotproduct between a point and a plane normal, minus 'D' gives the distance from the point in question to the plane.

    If this value is > 0, the point is in front of the plane, if this value is < 0 the point is behind the plane.

    If this value for the start point is > 0, and the value for the end point is < 0, then the ray intersects the plane.

    You can find the point of intersection by using the ratio of the start distance to the total distance (absolute values) as a linear interpolation factor to determine the XYZ of where the ray hits the plane.

    Code:
    Vector3d startPoint, endPoint, velocity(1, 1, 1);
    endPoint = startPoint + velocity;
    
    float startdist = dotproduct(plane.normal,startPoint) - plane.D;
    float enddist = dotproduct(plane.normal,endPoint) - plane.D;
    
    if(startdist > 0 && enddist < 0)
    {
       vector hitpoint;
       startdist = fabs(startdist);
       enddist = fabs(enddist);
       float iTotalDist  =  1 / (startdist + enddist); //inverse total distance
       float InterpValue = startdist * iTotalDist; //otherwise we'd just divide here, startdist / TotalDist
      hitpoint = startPoint + (endPoint - StartPoint) * InterpValue;
    }
    else
    {
     ;//doesn't cross plane
    }
    I'm not immature, I'm refined in the opposite direction.

  6. #6
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by BobMcGee123
    >>stands for the coordinate but what is 'D' stand for?

    The closest distance from the origin to the plane.
    No. Consider the plane

    2x + y + 2 = 0

    What is its closest distance to the origin? It's not 2. The point (-1,0,0) is on the plane and its distance to the origin is 1. The smallest distance is less than that (draw a figure).


    EDIT: perhaps I should add that the closest distance to the origin is

    D / sqrt(A^2 + B^2 +C^2)

    so for normalized (A,B,C) your statement is true.
    Last edited by Sang-drax; 01-05-2006 at 12:42 PM.

  7. #7

    Join Date
    May 2005
    Posts
    1,041

    Question

    >>so for normalized (A,B,C) your statement is true.

    And, plane normals are always normalized in the paradigm of game programming, that's a safe assumption you can always make...therefore in this context what I said is correct. Whatever source he referenced from is describing what I said, and you are crossing some useless crap from a university text book with game programming.

    The equation he described is the dotproduct between the normalized plane normal and some point on that plane, which will *always* give the closest distance from the origin to the plane. Always.

    And the next time you suggest I draw a diagram I am going to kill you.
    Last edited by BobMcGee123; 01-05-2006 at 06:15 PM.
    I'm not immature, I'm refined in the opposite direction.

  8. #8
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200
    Ok, i think i'm being dumb here. What i don't understand is the Plane normal. So if i say like this:
    Code:
    plane.normal(-1, 0, 0);
    What does it mean?

    So the plane normal only contain 1, 0, and -1. This is the plane normal code i found on nehe.gamedev.net about the plane's normal and its position:
    Code:
    struct Plane
    {
    	        TVector _Position;
    	       TVector _Normal;
    };
    Plane pl1,pl2,pl3,pl4,pl5;
    
    void InitVars()
    {
    	 //create palnes
    	pl1._Position=TVector(0,-300,0);
    	pl1._Normal=TVector(0,1,0);
    	pl2._Position=TVector(300,0,0);
    	pl2._Normal=TVector(-1,0,0);
    	pl3._Position=TVector(-300,0,0);
    	pl3._Normal=TVector(1,0,0);
    	pl4._Position=TVector(0,0,300);
    	pl4._Normal=TVector(0,0,-1);
    	pl5._Position=TVector(0,0,-300);
    	pl5._Normal=TVector(0,0,1);
    }
    could you explaine for me more about the plane normal?
    Hello, testing testing. Everthing is running perfectly...for now

  9. #9
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    University? We're still in high school!
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  10. #10
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    Lol, i hate Geometry Bad Teacher. Good luck with your project! I have a quick question perhaps someone could PM me or just make a quick post, i dont want to interrupt How do you go about using 3D objects in programming code? You make them in 3D programs im sure but how do you go about bringing them into the code? I have done a few little 3D things in Blender 3D, with the Yafray Raytracer. Perhaps if you could find the source code fo the raytracer implemented in that program it could help? I dont know, just offering a possibility, and a question. Good luck and thanks!

  11. #11
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    Well to bring 3d models into your code you simply have to set up all the data structures that the model file (.3ds) has in it already, and basically you copy all information from the file into memory (your new storage structures..)

    We're using MS3D Models in our project...
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  12. #12
    Registered User
    Join Date
    Nov 2004
    Location
    Pennsylvania
    Posts
    434
    Thanks, and good luck!

  13. #13
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    In Bob's defense there is nothing wrong with what he said as it relates to game programming. It may not be accurate for classroom math, but plane normals are ALWAYS normalized in 3D graphics. Storing them any other way would bring the system to a crawl as it attempted to re-normalize every frame. D3D does do a re-normalization but I think somehow the hardware plays a role in it and I'm sure it does not re-normalize every normal in the game per frame.

    Sometimes the normals do get out of wack and end up pointing the wrong direction, thus making then abnormal (no pun intended). So re-normalizing them fixes this. There are a lot of calculations and transformations going on and sometimes the underlying data gets hosed to the point it's not useable after a few hundred or a few thousand iterations. Floating point creep and the like all contribute to the problem.

    But what Bob said is completely accurate. The statement about the dot product is the exact same process that Direct3D uses to determine camera-facing triangles as opposed to those not facing the camera.

    And notice this:
    hitpoint = startPoint + (endPoint - StartPoint) * InterpValue
    Is what I've been talking about in a great many threads here.

    LIvalue=value1+value_interp*(value2-value1)

    or

    hitpoint=startPoint+InterpValue*(endPoint-startPoint);

    They yield the same result.

    Code:
    fld [endPoint]
    fsub [startPoint]
    fmul [InterpValue]
    fadd [startPoint]
    This is a fast linear interpolation in assembly using only the FPU.
    This can also be done in modern pixel shaders although I would probably only do it in a vertex shader.
    Last edited by VirtualAce; 01-06-2006 at 12:21 AM.

  14. #14

    Join Date
    May 2005
    Posts
    1,041
    >> What does it mean?

    Normalis, latin, literally means perpendicular...a plane normal is the vector that is perpendicular to the plane.

    >>So the plane normal only contain 1, 0, and -1

    Except that the vector <1, 0, -1> doesn't have a length of 1...the unit vector in that direction would be <.7071, 0, -.7071>

    >>could you explaine for me more about the plane normal?

    I think you need to access more resources about basic 3D math. Why not start here:

    http://chortle.ccsu.ctstateu.edu/Vec...ctorIndex.html

    You can do a google or amazon search and quickly find an assload of material on the subject. I suggest reading some rudimentary sources but then come back to our explanations as they relate to game programming (eventually the light will turn on, I promise).

    >>University? We're still in high school!

    The school of high people.

    How do you go about using 3D objects in programming code? You make them in 3D programs im sure but how do you go about bringing them into the code? I have done a few little 3D things in Blender 3D, with the Yafray Raytracer. Perhaps if you could find the source code fo the raytracer implemented in that program it could help? I dont know, just offering a possibility, and a question. Good luck and thanks!
    I have written code for just a couple of formats: MS3D models and quake3 BSPs. You need to write code that loads a model from a file (or just use loading code from one of the many tutorials online). You need to know how to use the data.

    Well to bring 3d models into your code you simply have to set up all the data structures that the model file (.3ds) has in it already, and basically you copy all information from the file into memory (your new storage structures..)

    We're using MS3D Models in our project...
    Yeah


    It may not be accurate for classroom math, but plane normals are ALWAYS normalized in 3D graphics
    Yeah

    D3D does do a re-normalization but I think somehow the hardware plays a role in it and I'm sure it does not re-normalize every normal in the game per frame.
    Yeah, I'm pretty sure you can turn this on and off, at least you can in OpenGL. You only really need forced renormalization in some pretty arcane scenarios, i.e using a scalaing matrix to modify a mesh before sending it to the rendering API. Incidentally this is the first thing described in OpenGL.org's 16 common pitfalls to OpenGL programming.
    http://opengl.org/resources/features...es/oglpitfall/

    You really do like assembly don't you bubba? I wish I had gotten more masterful with it. Have you used any old/arcane instruction sets (something other than x86 or the x87 FPU inst. set?)
    I'm not immature, I'm refined in the opposite direction.

  15. #15
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200
    Ok, after a while, i figured out the theory about collision detection/ray tracing.

    For each triangle, i set a plane normal for it and declared 3 vector points.
    Then i create an object vector3d point, as well as velocity.

    so this is how it goes:
    Code:
    struct Plane
    {
          vect3 Normal;
    }
    Plane pl;
    
    vect3 Pos, velocity;   //position and velocity of player object
    vect3 IP; //intersection point;
    vect3 p1, p2, p3;   //3 points for the triangle
    double Dplane;
    Then I calculate the distance of the vector to the plane (which will be the triangle i created using p1, p2, p3)

    Code:
    double DistRayPlane(vect3& Origin, vect3& velocity, vect3& PlaneNormal, double& D)
    {
       double Delta;
       double cosAlpha = dot(velocity, PlaneNormal);
       
    if(cosAlpha == 0) return -1.0;  //when it is parallel, do nothing
       
       Delta = D - (dot(Origin, PlaneNormal));
    return (Delta/cosAlpha);
    }

    After that, here will be another function to determine if the Pos vector will be inside the triangle (p1, p2, p3) at the IP point.

    Code:
    bool PointInTriangle(vect3& Point, vect3& v1, vect3& v2, vect3& v3)
    {
    double Angle;
    vect3 vt1 = NormalizeVect(Point - v1);
    vect3 vt2 = NormalizeVect(Point - v2);
    vect3 vt3 = NormalizeVect(Point - v3);
    
    Angle = (acos(dot(vt1, vt2))+ acos(dot(vt2, vt3)) + acos(dot(vt3, vt1)));
    
    if(fabs(Angle - 2*PI) < EPSILON)
         return true;
    else 
        return false;
    }
    So this is all set...I think. All i have to do is calculate the direction of the object, then check to see if it is inside the triangle or not when the IP hit the plane.

    in the InitGL i set the value for the vectors
    Code:
    pl.Normal = vect3(-1, 0, 0);
    
    Pos = vect3(0, 0, -50);
    velocity = vect3(1, 0, 0);
    
    p1 = vect3(0, 10, -45);
    p2 = vect3(0, -10, -40);
    p3 = vect3(0, -10, -50);
    
    Dplane = 1;

    Then, in the draw function i set up the triangle and set normal for everything i needed to.

    Code:
                    glLoadIdentity();
    	glTranslatef(10, 0, 0);
    	glBegin(GL_TRIANGLES);
    		glColor3f(1, 1, 1);
    		glNormal3f(-1, 0, 0);
    		glVertex3d(p1.x, p1.y, p1.z);
    		glVertex3d(p2.x, p2.y, p2.z);
    		glVertex3d(p3.x, p3.y, p3.z);
    	glEnd();
    //then draw the rectangle
    
    	glLoadIdentity();
    	glTranslated(Pos.x, Pos.y, Pos.z);
    	glBegin(GL_QUADS);
    		glColor3f(1, 0, 0);
    		glVertex3f(1, 1, 0);
    		glVertex3f(-1, 1, 0);
    		glVertex3f(-1, -1, 0);
    		glVertex3f(1, -1, 0);
    	glEnd();
    
    double dist = distRayPlane(Pos, velocity, pl.Normal, Dplane);
    
    
          if(dist > 0)
          {
             if(dist < distRayPlane(Pos, velocity, pl.Normal, Dplane))
             {
    	IP = Pos + velocity*dist;
    	         if(VertexTriangle(IP, p1, p2, p3))
                             {
    	               //collision 
                             }
              }
           }
    So when the distance is bigger than 0 and the distance is still smaller than the distance the object has to travel, the Intersection point will be add in. And when the IP point is inside the triangle, collision will occurs.


    Well, the problem is it did not work. The object goes right through the triangle. Did i do something wrong or my calculation is wrong?
    Last edited by hdragon; 01-10-2006 at 12:15 PM.
    Hello, testing testing. Everthing is running perfectly...for now

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21