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; >double dist = distRayPlane(Pos, velocity, pl.Normal, Dplane); >if(dist < distRayPlane(Pos, velocity, pl.Normal, Dplane)) dist is never going to be less ...

  1. #16
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >double dist = distRayPlane(Pos, velocity, pl.Normal, Dplane);
    >if(dist < distRayPlane(Pos, velocity, pl.Normal, Dplane))

    dist is never going to be less than itself

  2. #17
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    score 1 for perspective

    I was thinking about telling him that in class today.... but... I decided it was best he find out his silly mistake for himself

    No, I'm just kidding, I was just as oblivious as he was .
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  3. #18
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200
    Quote Originally Posted by Perspective
    >double dist = distRayPlane(Pos, velocity, pl.Normal, Dplane);
    >if(dist < distRayPlane(Pos, velocity, pl.Normal, Dplane))

    dist is never going to be less than itself
    I kinda figured out. So all i have to do is determine the distance from the Original position till the plane's normal. Also, i have to check to see if the Origin position is inside the triangle or not (it is easier checking a rectangle than a triangle). Do you think you can help me figure out what the problem is?
    Hello, testing testing. Everthing is running perfectly...for now

  4. #19
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    There is a ray-to-triangle intersection algo somewhere on this board. Bob and I talked about it extensively in several posts. I would recommend searching for posts either started by Bubba or by Bob.

  5. #20
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200
    Yes, finally i've made it work. This is how it goes:
    Code:
    bool checkPointTriangle(vect3 Point, vect3 Pa, vect3 Pb, vect3 Pc)
    {
    	double totalAngle = 0.0f;
    	vect3 v1 = Point - Pa;
    	vect3 v2 = Point - Pb;
    	vect3 v3 = Point - Pc;
    
    	NormalizeVect(v1);
    	NormalizeVect(v2);
    	NormalizeVect(v3);
    
    	totalAngle += acos(dot(v1, v2));
    	totalAngle += acos(dot(v2, v3));
    	totalAngle += acos(dot(v3, v1));
    
    	if(fabs(totalAngle - 2*PI) < 0.005)
    		return true;
    	else 
    		return false;
    }
    So, the Position of the object (a vector) will be check if it is going to be inside a triangle or not, then with a distance calculation from the position to the triangle's normal, collision will occur.

    Is there anything else i should add into my collision code to make it faster?

    EDIT:
    If i have a model with multiple triangles, what vector on the model should i check for the collide triangles? A point in a model's triangle or a point on its face?
    Last edited by hdragon; 01-17-2006 at 09:29 AM.
    Hello, testing testing. Everthing is running perfectly...for now

  6. #21
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    That acos() looks quite nasty. Anything you can do to get rid of it?

  7. #22

    Join Date
    May 2005
    Posts
    1,041
    If i have a model with multiple triangles, what vector on the model should i check for the collide triangles? A point in a model's triangle or a point on its face?
    Could you please explain what you mean by this question?

    I wrote this for determining if a point resides in a triangle...but this is also pretty nasty, and might actually be more expensive, but it works.

    Code:
    #include	"CollisionDetectionPrimitives.h"
    
    extern	std::ofstream	trace;
    
    #define	CCWPITDEBUG(x)	x
    
    //Fixme: investigate to see how vector length plays into uncertainty here
    //Normal x DiffVector = InwardVector
    //InwardVector Dot Point >= 0 or >= -.0001
    BOOL	CCWPointInTri(float	P1X,float	P1Y,float	P1Z,
    					  float	P2X,float	P2Y,float	P2Z,
    					  float	P3X,float	P3Y,float	P3Z,
    					  float	NormalX,float	NormalY,float	NormalZ,
    					  float	PointX,float PointY,float	PointZ)
    {
    	Vector3	Point1(P1X,P1Y,P1Z);	Vector3	Point2(P2X,P2Y,P2Z);	Vector3	Point3(P3X,P3Y,P3Z);
    	Vector3	Normal(NormalX,NormalY,NormalZ);
    	Vector3 Point(PointX,PointY,PointZ);
    
    	Vector3	LocalPoint = Point - Point1; //The point in local coordintes with respect to a vertex 
    
    	Vector3	DiffVector	=	Point2 - Point1;
    	Vector3	InwardVector(0,0,0);
    	InwardVector	=	CrossProduct(&Normal,&DiffVector);
    
    	if(DotProduct(&InwardVector,&LocalPoint) < -.0001f)
    	{
    		CCWPITDEBUG(	trace << "Returning on first point" << "\n";	)
    		return	FALSE;
    	}
    
    	LocalPoint	=	Point  - Point2;
    	DiffVector	=	Point3 - Point2;
    	InwardVector	=	CrossProduct(&Normal,&DiffVector);
    
    	if(DotProduct(&InwardVector,&LocalPoint) < -.0001f)
    	{
    		CCWPITDEBUG(	trace << "Returning on seconed point" << "\n";	)
    		return	FALSE;
    	}
    
    	LocalPoint	=	Point  - Point3;
    	DiffVector	=	Point1 - Point3;
    	InwardVector	=	CrossProduct(&Normal,&DiffVector);
    	if(DotProduct(&InwardVector,&LocalPoint)<-.0001f)
    	{
    		CCWPITDEBUG(	trace << "Returning on third point" << "\n";	)
    		return	FALSE;
    	}
    
    	return	TRUE;
    }
    I'm not immature, I'm refined in the opposite direction.

  8. #23
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    That doesn't look so nasty. It's only subtraction's and cross product's. Shouldn't hit too hard.

  9. #24
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    while we're all in the mood for posting ray-triangle intersection algo's, here's mine. (I was forced to use this prototype, thats why i set the u, v, t params by reference). Also, this scence always had one object, that's why i just grab objects[0]. A better implimentation would pass the triangle as a paramater.

    edit: oh btw: u and v are the "UV Coordinates" of the intersected triangle and t is the magnitude along the direction of the ray that the intersection takes place. So this algo doesn't just tell you if there is an intersection, it tells you the point on the triangle that the intersection takes place by setting the u,v, and t params (handy for phong shading or other types of lighting). Returns 0 if there is no intersection and 1 if there is.

    Code:
    // calculate ray - triangle intersection with backface culling
    int RayTracer::calcTriangleIntersection(const Ray& ray, const VertexList* face,
    					float *t, float *u, float *v) {
    
      Point3f vert1 = scene->objects[0].vertices[(face->vertex)-1];
      Point3f vert0 = scene->objects[0].vertices[(face->next->vertex)-1];
      Point3f vert2 = scene->objects[0].vertices[(face->next->next->vertex)-1];
    
      Vector3f 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 = ray.dir.cross(edge2);
      
      // if determinant is near zero, ray lies in plane of triangle
      det = edge1.dot(pvec);
    
      if (det < EPSILON)
        return 0;
    
      // calculate distance from vert0 to ray origin 
      tvec = ray.start - vert0;
    
      // calculate U parameter and test bounds 
      *u = tvec.dot(pvec);
      if (*u < -EPSILON || *u > det)
        return 0;
    
      // prepare to test V parameter 
      qvec = tvec.cross(edge1);
    
      // calculate V parameter and test bounds 
      *v = ray.dir.dot(qvec);
      if (*v < -EPSILON || (*u + *v) > det)
        return 0;
      
      // calculate t, scale parameters, ray intersects triangle 
      *t = -edge2.dot(qvec);
    
      inv_det = 1.0f / det;
      *t *= inv_det;
      *u *= inv_det;
      *v *= inv_det;
      
      return 1;
    }
    Last edited by Perspective; 01-18-2006 at 10:43 AM.

  10. #25
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200
    Quote Originally Posted by Bubba
    That acos() looks quite nasty. Anything you can do to get rid of it?
    Well, i can put it like this:
    Code:
    totalAngle += (acos(dot(v1, v2)) + acos(dot(v2, v3)) + acos(dot(v3, v1)));
    Anyway, i have to convert the decimal to degree to make a full 360* circle. Then minus 2 PI. I don't know how can you clean it up if you need the function.

    Quote Originally Posted by BobMcGee123
    Could you please explain what you mean by this question?
    I meant like this, I use a vector Pos, which i put in the glTranslatef() for testing. So all it does is check the Pos coordinate (x, y, z). Then i draw a triangle moved by the Pos coordinates. So, when i have more than one triangle, what point should i check so that all the triangle of the model can determine if it is inside/hit another objects.
    Last edited by hdragon; 01-18-2006 at 09:26 PM.
    Hello, testing testing. Everthing is running perfectly...for now

  11. #26
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >>
    I meant like this, I use a vector Pos, which i put in the glTranslatef() for testing. So all it does is check the Pos coordinate (x, y, z). Then i draw a triangle moved by the Pos coordinates. So, when i have more than one triangle, what point should i check so that all the triangle of the model can determine if it is inside/hit another objects.
    <<

    Well, I didn't post the question but anywho...

    You can ray trace against every triangle in the model, you can ray trace against a bounding volume of the model, or you can use a space partitioning algorithm to determine which triangles are in the same volume of space as your ray and test the triangles in that volume.

    Those 3 options range from easy to difficult while simultaniously ranging from innefficient to efficient

  12. #27
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200
    That was suppose to be Bob, i messed up.

    Anyway, if i ray trace every triangle of a model, it would be slow right?

    About the bounding volume, if my model is really complex (curve, rectangles, all kind of stuff that make it look complex), do i have to find the center of the model? If the model is an aircraft with 2 wings on the side, would the bounding volume will make it look realistic.

    The partitioning algorithm is something i have no idea, could you talk about it more.
    Hello, testing testing. Everthing is running perfectly...for now

  13. #28
    Absent Minded Programmer
    Join Date
    May 2005
    Posts
    964
    I think he means something along the lines of checking whether or not two objects are even close to each other whatsoever...

    If not they don't need to check collision between each other, saving valuable computation time .

    How to do it? You could just as well ask a monkey for the answer :d.
    Sometimes I forget what I am doing when I enter a room, actually, quite often.

  14. #29
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200
    Quote Originally Posted by Shamino
    I think he means something along the lines of checking whether or not two objects are even close to each other whatsoever...

    If not they don't need to check collision between each other, saving valuable computation time .

    How to do it? You could just as well ask a monkey for the answer :d.
    So by that, we can use the ray to determine if the object parallel to the others. Find the ray direction of the first object, and calculate. If it perpendicular to the other objects' normal, we have a parallel line and we don't have to run the calculation.
    Hello, testing testing. Everthing is running perfectly...for now

  15. #30
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    Well you could probably use an octree. Each leaf in the tree holds the vertices for that volume and each leaf is responsible for drawing itself. I'm not sure how to do this in a raytracer except that you wouldn't ray-intersect test any of the tri's in a leaf unless it passed certain tests.

    I have very little experience with pure ray-tracing but I'm very experienced with ray-casting and vertical ray coherence. However ray-tracing is a whole nuther ball game since you basically are tracing a ray of light through pixel at x,y to completion.

    I hope you get it working because I'm looking forward to seeing the final result.

    Also a curve is simply a ray-to-sphere intersection test and you would want to break down the geometry into vertices if the sphere passed the test. Again I'm pretty much in the dark here with little experience in ray-tracing.

Page 2 of 3 FirstFirst 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