Advertisement

Ray and Poly collision

Started by June 20, 2002 02:17 PM
3 comments, last by Kern 22 years, 7 months ago
Hi, i'm trying to make a Ray to polygon collision detection, when the first(closest to the start) colision point on the ray I reflect the remaining part of the ray and loop through all polygons until I have a ray that does not collide with any polygon. The problem is that for some unknown reason it goes through sometimes, I think it's at the intersection of 2 polygons. Has anyone here ever succeded at such a system, if you did could you please help me out, I can post more code if necessary. I will start with the ray to poly colision detection functions.
    bool IntersectedPolygon2(const D3DXVECTOR3 vPoly[3], const D3DXVECTOR3 vLine[2], const D3DXVECTOR3 &vNormal, D3DXVECTOR3 &vIntersection) {
	float fDistance = 0;

	// First, make sure our line intersects the plane

	if(!IntersectedPlane2(vPoly, vLine, vNormal, fDistance)) {
		return false;
	}

	// Now that we have our normal and distance passed back from IntersectedPlane(),

	// we can use it to calculate the intersection point.

	int iClass = IntersectionPoint2(vIntersection, vNormal, vLine, fDistance);
	if(iClass == PARALEL) {
		// More complex way to determin the point of intersection

		if(PointInTriangle2(vLine[0], vPoly, vNormal)) {
			vIntersection = vLine[0];
		}
		else {
/* I don't know how to find the first point in the ray that is inside the polygon yet, but I tested if this was the problem and it wasent. */
		}
	}

	// Now that we have the intersection point, we need to test if it's inside the polygon.

	if(PointInTriangle2(vIntersection, vPoly, vNormal)) {
		// We collided!	  Return success

		return true;
	}

	// There was no collision, so return false

	return false;
}

bool IntersectedPlane2(const D3DXVECTOR3 vPoly[3], const D3DXVECTOR3 vLine[2], const D3DXVECTOR3 &vNormal, float &originDistance) {
	// The distances from the 2 points of the line from the plane

//	int iClass1, iClass2;

	float fDist1, fDist2;

//	iClass1 = ClassifyPoint(vPoly[0], vNormal, vLine[0], fDist1);

//	iClass2 = ClassifyPoint(vPoly[0], vNormal, vLine[1], fDist2);


	originDistance = PlaneOriginDistance(vNormal, vPoly[0]);
	fDist1 = PlanePointDistance(vPoly[0], vNormal, vLine[0]);
	fDist2 = PlanePointDistance(vPoly[0], vNormal, vLine[1]);

	// Now that we have 2 distances from the plane, if we times them together we either

	// get a positive or negative number.  If it's a negative number, that means we collided!

	// This is because the 2 points must be on either side of the plane (IE. -1 * 1 = -1).


	// Check to see if both point's distances are both negative or both positive

	if(fDist1 * fDist2 > 0)
	   return false;	// Return false if each point has the same sign.  -1 and 1 would mean each point is on either side of the plane.  -1 -2 or 3 4 wouldn't...


	// The line intersected the plane, Return TRUE

	return true;
}

int IntersectionPoint2(D3DXVECTOR3 &vIntersection, const D3DXVECTOR3 &vNormal, const D3DXVECTOR3 vLine[2], double distance) {
	// Variables to hold the point and the line's direction

	D3DXVECTOR3 vPoint, vTemp, vLineDir;
	double Numerator = 0.0, Denominator = 0.0, dist = 0.0;

	// 1)  First we need to get the vector of our line, Then normalize it so it's a length of 1

	// Get the Vector of the line

	vTemp = vLine[1] - vLine[0];
	// Normalize the lines vector

	D3DXVec3Normalize(&vLineDir, &vTemp);


	// 2) Use the plane equation (distance = Ax + By + Cz + D) to find the 

	// distance from one of our points to the plane.

	// Use the plane equation with the normal and the line

	Numerator = - (vNormal.x * vLine[0].x +
				   vNormal.y * vLine[0].y +
				   vNormal.z * vLine[0].z + distance);

	// 3) If we take the dot product between our line vector and the normal of the polygon,

	// Get the dot product of the line's vector and the normal of the plane

	Denominator = D3DXVec3Dot(&vNormal, &vLineDir);
				  
	// Since we are using division, we need to make sure we don't get a divide by zero error

	// If we do get a 0, that means that there are INFINATE points because the the line is

	// on the plane (the normal is perpendicular to the line - (Normal.Vector = 0)).  

	// In this case, we should just return any point on the line.


	// Check so we don't divide by zero

	if(Denominator == 0.0) {
		// Return an arbitrary point on the line

		return PARALEL;
	}

	// Divide to get the multiplying (percentage) factor

	dist = Numerator/Denominator;
	
	// Now, like we said above, we times the dist by the vector, then add our arbitrary point.

	vPoint.x = (float)(vLine[0].x + (vLineDir.x * dist));
	vPoint.y = (float)(vLine[0].y + (vLineDir.y * dist));
	vPoint.z = (float)(vLine[0].z + (vLineDir.z * dist));

	// Return the intersection point

	vIntersection = vPoint;
	return INTERSECT;
}

inline bool PointInTriangle2(const D3DXVECTOR3 &vP, const D3DXVECTOR3 vPoly[3], const D3DXVECTOR3 vNormal) {
	return (SameSide2(vP, vPoly[0], vPoly[1], vNormal) && SameSide2(vP, vPoly[1], vPoly[2], vNormal) && SameSide2(vP, vPoly[2], vPoly[0], vNormal));
}

bool SameSide2(const D3DXVECTOR3 &vP, const D3DXVECTOR3 &vA, const D3DXVECTOR3 &vB, const D3DXVECTOR3 &vN) {
	D3DXVECTOR3 vCp, vNormal;
	D3DXVec3Cross(&vCp, &(vB-vA), &vN);
	D3DXVec3Normalize(&vNormal, &vCp);
	if(D3DXVec3Dot(&vNormal, &(vP-vA)) <= 0.0f) {
		return true;
	}
	return false;
}    
[edited by - Kern on June 20, 2002 3:19:30 PM]
this is an interesting topic, it would also help me, because i might have to do such thing myself later on.

---
shurcool
my project
Advertisement
There are two points I want to object to:

In IntersectionPoint2:

  if(Denominator == 0.0) {			// Return an arbitrary point on the line		        return PARALEL;	}  

You don''t test floatng point values on equality, because of Computational inaccuracy. And don''t tell me you''ll just use a type with higher accuracy. Square the result ( to make it positive and smaller ) and test if it lies below, say 1e-8

And probably solving your problem:

In SameSide2 you again do a too strict check

  if(D3DXVec3Dot(&vNormal, &(vP-vA)) <= 0.0f) {		return true;	}return false;  

give your app some liberty by adding a check if the value is big enough to be of relevance. If the value if very small the point is lying sufficiently much on the line.

  float dst = D3DXVec3Dot(&vNormal, &(vP-vA)) ;if( dst <= 0.0f || ((dst*dst) < 1e-8f)) {		return true;	}return false;  

or just a little shorter

  float dst = D3DXVec3Dot(&vNormal, &(vP-vA)) ;return ( dst <= 0.0f || ((dst*dst) < 1e-8f));  


If this didn''t solve your problem, or if I misunderstood your problem, just come back

cu Dreamforger


---------------------------
I may be getting older, but I refuse to grow up
I may be getting older, but I refuse to grow up
I jsut spent amonth on a system like that, on a landscape grid. I wanted to make everything mathematically perfect. But I got into lots of infinite loops, and it also fell through sometimes.

Eventually I realized I should accept defeat, and use a more inaccurate method that never lets it fall through.

My new code was a loop that went over every tri during the time of update, it only took a few pages. My old code was this:

h = height_at( x, z )

if y < h
y = h
// reflect velocity

that''s all.

Now I can move on to other things.... and I can''t even tell the difference in accuracy.
I know it''s hard to accept not using a 100% precise system, but now i''m ok with it
Thanks alot Dreamforger for pointing that out.

The problem is solved now, with the preceding corrections the vehicle bounces at slow, medium and fast speed.

Thank you for your help.

[edited by - Kern on June 25, 2002 10:07:14 AM]

This topic is closed to new replies.

Advertisement