Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

DMINATOR

Intersection problem

This topic is 5142 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was trying to implement picking system with projecting ray , but come to many problems . First of all the methods i have found on the net are not working with my code , producing strange result like here It some how doesn't select the correct triangle. Here is my source code (with Debug build i get some results but in Release nothing is selected (strange) ) I am really don't know what is the problem here is the algorithm i use for checking ray-tri intersection :

bool MollerTrumbore_IntersectRayTri(VERTEX r_o,VERTEX r_d,VERTEX v1,VERTEX v2,VERTEX v3)
{ 
	VERTEX e2;
	SUB(e2,v3,v1);       // second edge


	VERTEX e1;
	SUB(e2,v2,v1);    // first edge


	VERTEX r; 
	CROSS(r,r_d,e2);  // (d X e2) is used two times in the formula

	// so we store it in an appropriate vector

	VERTEX s = r_o ;//-v1;       // translated ray origin

	float a = DOT(e1,r);    // a=(d X e2)*e1

	float f=1/a;           // slow division*

	VERTEX q;
	CROSS(q,s,e1);
	float u = DOT(s,r);
	if ( a > EPSILON)            // eps is the machine fpu epsilon (precision), 

		// or a very small number :)

	{ // Front facing triangle...

		if ((u<0)||(u>a)) return false;
		float v = DOT(r_d,q);
		if ((v<0)||(u+v>a)) return false;
	}
	else if (a < -EPSILON)
	{ // Back facing triangle...

		if ((u>0)||(u<a)) return false;
		float v= DOT(r_d,q);
		if ((v>0)||(u+v<a)) return false;
	} 
	else return false; // Ray parallel to triangle plane

	
	float t= f* DOT(e2,q);

	return true;
}

My Structures are :
   
typedef struct tagVERTEX
{
	float  x, y, z;
	float  u, v;

     tagVERTEX operator + (tagVERTEX);
	tagVERTEX operator - (tagVERTEX);
	tagVERTEX operator * (tagVERTEX);

} VERTEX;

typedef struct tagTRIANGLE
{
   VERTEX *vertex;

} TRIANGLE;


As ray i use mouse with direction
   
	VERTEX line_from;   //beginning of line

	VERTEX line_dir;    // direction of line


    line_from.x = posx;
	line_from.y = posy;
	line_from.z = 0;
    
	// line is pointing into the screen


	line_dir.x = posx;
	line_dir.y = posy;
	line_dir.z = -2;

For triangle array i use :

     TRIANGLE *Gesture;
   // LEFT SIDE

      Gesture[0].vertex[0].x = -1;
	Gesture[0].vertex[0].y = -1;
	Gesture[0].vertex[0].z = -0.5;

	Gesture[0].vertex[1].x = -1;
	Gesture[0].vertex[1].y = 1;
	Gesture[0].vertex[1].z = -0.5;

	Gesture[0].vertex[2].x = 0;
	Gesture[0].vertex[2].y = 0;
	Gesture[0].vertex[2].z = -0.5;
  // DOWN SIDE

	Gesture[1].vertex[0].x = -1;
	Gesture[1].vertex[0].y = -1;
	Gesture[1].vertex[0].z = -0.5;

	Gesture[1].vertex[1].x = 1;
	Gesture[1].vertex[1].y = -1;
	Gesture[1].vertex[1].z = -0.5;

	Gesture[1].vertex[2].x = 0;
	Gesture[1].vertex[2].y = 0;
	Gesture[1].vertex[2].z = -0.5;

  // TOP SIDE

	Gesture[2].vertex[0].x = -1;
	Gesture[2].vertex[0].y = 1;
	Gesture[2].vertex[0].z = -0.5;

	Gesture[2].vertex[1].x = 1;
	Gesture[2].vertex[1].y = 1;
	Gesture[2].vertex[1].z = -0.5;

	Gesture[2].vertex[2].x = 0;
	Gesture[2].vertex[2].y = 0;
	Gesture[2].vertex[2].z = -0.5;
	 // RIGHT SIDE

    Gesture[3].vertex[0].x = 1;
	Gesture[3].vertex[0].y = -1;
	Gesture[3].vertex[0].z = -0.5;

	Gesture[3].vertex[1].x = 1;
	Gesture[3].vertex[1].y = 1;
	Gesture[3].vertex[1].z = -0.5;

	Gesture[3].vertex[2].x = 0;
	Gesture[3].vertex[2].y = 0;
	Gesture[3].vertex[2].z = -0.5;
All other info may be found from source : picktest.zip [edited by - DMINATOR on May 26, 2004 5:58:36 AM]

Share this post


Link to post
Share on other sites
Advertisement
K i have found a solution it seems that 2 methods i used earlier didn''t work correctly , maybe i have changed them and added some bugs , but i have used different method from Tomas Moller (with division at the end in the code ):


/* code rewritten to do tests on the sign of the determinant */
/* the division is at the end in the code */
int intersect_triangle1(double orig[3], double dir[3],
double vert0[3], double vert1[3], double vert2[3],
double *t, double *u, double *v)
{
double edge1[3], edge2[3], tvec[3], pvec[3], qvec[3];
double det,inv_det;

/* find vectors for two edges sharing vert0 */
SUB(edge1, vert1, vert0);
SUB(edge2, vert2, vert0);

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

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

if (det > EPSILON)
{
/* calculate distance from vert0 to ray origin */
SUB(tvec, orig, vert0);

/* calculate U parameter and test bounds */
*u = DOT(tvec, pvec);
if (*u < 0.0 || *u > det)
return 0;

/* prepare to test V parameter */
CROSS(qvec, tvec, edge1);

/* calculate V parameter and test bounds */
*v = DOT(dir, qvec);
if (*v < 0.0 || *u + *v > det)
return 0;

}
else if(det < -EPSILON)
{
/* calculate distance from vert0 to ray origin */
SUB(tvec, orig, vert0);

/* calculate U parameter and test bounds */
*u = DOT(tvec, pvec);
/* printf("*u=%f\n",(float)*u); */
/* printf("det=%f\n",det); */
if (*u > 0.0 || *u < det)
return 0;

/* prepare to test V parameter */
CROSS(qvec, tvec, edge1);

/* calculate V parameter and test bounds */
*v = DOT(dir, qvec) ;
if (*v > 0.0 || *u + *v < det)
return 0;
}
else return 0; /* ray is parallell to the plane of the triangle */


inv_det = 1.0 / det;

/* calculate t, ray intersects triangle */
*t = DOT(edge2, qvec) * inv_det;
(*u) *= inv_det;
(*v) *= inv_det;

return 1;
}


And here is the correct behaviour of my program :

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!