Jump to content
  • Advertisement
Sign in to follow this  
Deliverance

Finding time of intersection in SAT between dynamic and dynamic intersection

This topic is 3173 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 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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
Quote:
Original post by jyk
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...)


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 this post


Link to post
Share on other sites
Quote:
Original post by oliii
does 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:

Loading...

The dark blue objects are rendered using pos1New and pos2New.

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

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by oliii
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.


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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!