# Finding time of intersection in SAT between dynamic and dynamic intersection

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

## Recommended Posts

I had a little time and implemented a version of SAT that properly detects collision between two dynamic objects by transforming the problem to a dynamic vs static object collision detection one. My question is: how can i detect the time t0 and t1 for each object with respect to their velocities where the objects must stop and are only "touching" themselves, effectively repositioning and stopping them in the path of collision?

##### Share on other sites
The time of first intersection will be the same for both objects, so all you need to do is update the object's positions using the computed time of intersection and the original unaltered displacement vectors. (If that's what you're asking...)

##### Share on other sites
Quote:
 Original post by jykThe time of first intersection will be the same for both objects, so all you need to do is update the object's positions using the computed time of intersection and the original unaltered displacement vectors. (If that's what you're asking...)

Yes, that is what i am asking but obviously i am doing something wrong, because doing the calculations like so does not present the correct results. Here's the relevant code:

bool SAT::testCollision(const std::vector<Vector3>& poly1,						const Vector3& pos1,				        const std::vector<Vector3>& poly2,						const Vector3& pos2,						const Vector3& vel1,						const Vector3& vel2,						Vector3& pos1New,						Vector3& pos2New){	std::vector<Vector3> axes;		Vector3 relativeVel = vel1-vel2;		// first check axes perpendicular to poly1 edges	unsigned int i;	//printf("poly1:\n");	for (i=0; i<poly1.size(); i++)	{	//	printf("%f %f\n", poly1.x, poly1.y);		// calculate edge vector		Vector3 edgeVector = poly1[(i + 1) % poly1.size()] - poly1;		// this returns a perpendicular vector onto the edge		Vector3 axis = Vector3(-edgeVector.y, edgeVector.x, 0.0f);		axis.normalize();		axes.push_back(axis);	}	// next check axes perpendicular tu poly2 edges	//printf("poly2:\n");		for (i=0; i<poly2.size(); i++)	{	//	printf("%f %f\n", poly2.x, poly2.y);				// calculate edge vector		Vector3 edgeVector = poly2[(i + 1) % poly2.size()] - poly2;		// this returns a perpendicular vector onto the edge		Vector3 axis = Vector3(-edgeVector.y, edgeVector.x, 0.0f);				axis.normalize();				axes.push_back(axis);	}		// now check all axes for projection overlap - ALL of the projection intervals for each axis	// should overlap in case of collision between the two objects		for (i=0; i<axes.size(); i++)	{		float min1,max1,min2,max2,overlapMin,overlapMax;		getProjectionInterval(poly1, pos1, axes, min1, max1);		getProjectionInterval(poly2, pos2, axes, min2, max2);	}		float t0 = 0;	float t1 = 1000000.0f;					float tMax = 1.0f;		for (i=0; i<axes.size(); i++)	{		float min1,max1,min2,max2,overlapMin,overlapMax;		getProjectionInterval(poly1, pos1, axes, min1, max1);		getProjectionInterval(poly2, pos2, axes, min2, max2);		float speed = dot(axes, relativeVel);		//printf("speed is: %f %d axis is: %f %f relativeVel is: %f %f min1=%f max1=%f min2=%f max2=%f\n", speed, axes.size(), axes.x, axes.y, relativeVel.x, relativeVel.y,		//			min1, max1, min2, max2);				if ( max1 < min2 ) 		{ 			if (speed<=0.0f)				return false;						//printf("max1 min2 %d\n", i);			float t = (min2 - max1) / speed;			t0 = MAX(t, t0);						if (t0 > tMax)				return false;						t = (max2 - min1) / speed;			t1 = MIN(t, t1);						//printf("%f %f\n", t0, t1);						if (t0 > t1)				return false;		}else		if ( max2 < min1 ) 		{ 			if (speed>=0.0f)			 return false;			 			// printf("max2 min1 %d - max2=%f min1=%f speed=%f\n", i,max2,min1,speed);			 float t = (max2 - min1) / speed;			 t0 = MAX(t, t0);			 			 if (t0 > tMax)			 return false;						 			 t = (-max1 + min2) / speed;			 t1 = MIN(t, t1);			 			 if (t0 > t1)			 return false;			 			// printf("t0=%f t1=%f\n", t0, t1);					}							else		{			if ( speed > 0 ) 			{ 				float t = (max2 - min1)/speed; 				t1 = MIN(t, t1);								if (t0 > t1)				{					//printf("overlap return false > 0 t0=%f t1=%f - %f %f i=%d %f %f\n", t0, t1,axes.x, axes.y, i,					//	   pos2.x+relativeVel.x, pos2.y+relativeVel.y);					return false;				}							} 			else if ( speed < 0 ) 			{ 				float t = (min2 - max1)/speed;								t1 = MIN(t, t1);								if (t0 > t1)				{					//printf("overlap return false < 0 t0=%f t1=%f - %f %f i=%d %f %f\n", t0, t1,axes.x, axes.y, i,					//	pos2.x+relativeVel.x, pos2.y+relativeVel.y);					return false;								}			}				}	}		pos1New = pos1 + vel1*t0;	pos2New = pos2 + vel2*t0;		// we have a collision so, return true	return true;}

The last few lines of code show the calculation of the new positions. This does not result in the positions i am seeking though. The objects are drawed with the same center, on their respective velocity directions.

[Edited by - Deliverance on December 6, 2009 6:01:31 PM]

##### Share on other sites
does it report false positives, false negatives, or just that the time is wrong?

##### Share on other sites
Quote:
 Original post by oliiidoes it report false positives, false negatives, or just that the time is wrong?

The time reported is correct for the transformed problem(and also no false positives or negatives). So we have problem P that represents determining the collision between dynamic object o1 and dynamic object o2. We transform this problem intro P' which represents finding collision between dynamic object o1 and static object o2 using a relative velocity. The time returned by the algorithm is correct with respect to problem P' but how do i map this value to the problem P? After executing the code above here's how it looks like:

The dark blue objects are rendered using pos1New and pos2New.

[Edited by - Deliverance on December 7, 2009 4:08:12 AM]

##### Share on other sites
well, if your time t0 is correct, that should just work. I don't really see how P' is shown to be working. Seems to go straight through?

I would guess you may have a problem with your calculations of the projection intervals.

##### Share on other sites
Quote:
 Original post by oliiiwell, if your time t0 is correct, that should just work. I don't really see how P' is shown to be working. Seems to go straight through? I would guess you may have a problem with your calculations of the projection intervals.

I did not stop the swept volume when there is a collision in P', neither rendered the "resting" position of the circle to the ellipse, but

I found the problem! The problem was not in the actual function(which works just fine) i provided but when rendering the objects. Now the results look just okay,check this out:

##### Share on other sites
yeah that's more like it.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634090
• Total Posts
3015434
×