Archived

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

DMINATOR

Intersection problem

Recommended Posts

DMINATOR    240
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
DMINATOR    240
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