View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Mesh - Elipse Collision Detection and Response Problem

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

2 replies to this topic

### #1BlueSpud  Members

Posted 05 February 2014 - 03:27 PM

Hi,
So for hours Ive been working on collision detection with triangle meshes and ellipses. The paper I've been using for reference can be found here:
http://www.peroxide.dk/papers/collision/collision.pdf

There a big problem with my system that I can't seem to work out. I've recoded the function about 10 times now, and its still not quite working. Here is the function that I have written as well as the relevant supporting code:

bool physicsObject::onSameSide(glm::vec3 point, glm::vec3 p1, glm::vec3 p2, glm::vec3 p3)
{
glm::vec3 cross1 = glm::cross(p3-p2, point-p2);
glm::vec3 cross2 = glm::cross(p3-p2, p1-p2);
if (glm::dot(cross1, cross2) >= 0.0)
return  true;
else return false;

}
collisionResponsePacket physicsObject::checkTriangle(unsigned int i)
{
collisionResponsePacket packetToReturn;
glm::vec3 velocity = ( playerESpace.vecInElipsoidSpace(glm::vec3(-camx,-camy,-camz))-playerESpace.vecInElipsoidSpace(glm::vec3(-lcamx,-lcamy,-lcamz)));
glm::vec3 basePos = playerESpace.vecInElipsoidSpace(glm::vec3(-lcamx,-lcamy,-lcamz));

//for now, we're just going to check the one triangle.
//.obj stores vertexes in counter-clockwise order, so we're going to swap the positions.
glm::vec3 p1 =playerESpace.vecInElipsoidSpace( (glm::vec3(ModelRegistry.models[model].m.obj[i].x3,ModelRegistry.models[model].m.obj[i].y3,ModelRegistry.models[model].m.obj[i].z3)));
glm::vec3 p2 = playerESpace.vecInElipsoidSpace((glm::vec3(ModelRegistry.models[model].m.obj[i].x2,ModelRegistry.models[model].m.obj[i].y2,ModelRegistry.models[model].m.obj[i].z2)));
glm::vec3 p3 = playerESpace.vecInElipsoidSpace((glm::vec3(ModelRegistry.models[model].m.obj[i].x1,ModelRegistry.models[model].m.obj[i].y1,ModelRegistry.models[model].m.obj[i].z1)));

//get the normal
glm::vec3 normal  = glm::normalize(glm::cross(p2-p1, p3-p1));

//get signed distance
double distance = glm::dot(normal, basePos) - glm::normalize(((normal.x*p1.x)+(normal.y*p1.y)+(normal.z*p1.z)));
double nvd = glm::dot(normal, velocity);

//if its equal to zero, the elipse is traveling parallel to the triangle
if (nvd != 0.0)
{
//figure out what time the sphere would intersect with the collision plane, it doesn't nessesarily have to
double time0,time1;
time0 = (1.0-distance)/nvd;
time1 = (-1.0-distance)/nvd;

if (time0 > time1)
{
double temp = time1;
time1 = time0;
time0 = temp;
}
//check if there can actually be a collision
if (time0 > 1.0 || time1 < 0.0)
return packetToReturn;
else
{
//fix thew times if there was a possible collision
if (time0 < 0.0) time0 = 0.0;
if (time1 < 0.0) time1 = 0.0;
if (time0 > 1.0) time0 = 1.0;
if (time1 > 1.0) time1 = 1.0;

//continue to look for a collision
glm::vec3 planeIntersectionPoint = (basePos - normal) + ((float)time0*velocity);
//now we have where the elipsoide will collide with the trangle, now we check if it is an actual collision
if (onSameSide(planeIntersectionPoint, p1, p2, p3) && onSameSide(planeIntersectionPoint, p2, p1, p3) && onSameSide(planeIntersectionPoint, p3, p1, p2))
{
//there was a collision here so we give the packet the proper information
packetToReturn.intersectionPoint = planeIntersectionPoint;
packetToReturn.time0 =  time0;
packetToReturn.time1 = time1;
packetToReturn.collided = true;
}
else return packetToReturn;
}

} else return packetToReturn;

return packetToReturn;
}

void physicsObject::testCollisionMeshWithElipsoid(double time)
{
//some of the vectors we require for the response
glm::vec3 velocity = playerESpace.vecInElipsoidSpace( glm::vec3(-camx,-camy,-camz)-glm::vec3(-lcamx,-lcamy,-lcamz));
std::vector<collisionResponsePacket>results;

for (int i = 0; i < ModelRegistry.models[model].m.obj.size(); i++)
//we chech each triangle
results.push_back(checkTriangle(i));

float closest = 0;
int triangle = 0;
bool initial = false;
//now we find which one we are going to respond against, then do it
for (int i = 0; i < results.size(); i++)
{
if (results[i].collided == true)
{

//get the distance to the collision
float distanceToCollision = results[0].time0*glm::length(velocity);
if (initial == false || distanceToCollision < closest )
{
//this one was less than the previos one
initial = true;
closest = distanceToCollision;
triangle = i;
}

}
}
//we store the information for the closest collision here
closestResults.i = triangle;
closestResults.distance = closest;
closestResults.packet = results[triangle];
results.clear();

}


And the function that handles the 'response'

void physics::collisions()
{
if (pysObjs.size() > 0)
{
//here we're going to test all the collision objects and apply the collision response to the nearest collision
glm::vec3 velocity = ( playerESpace.vecInElipsoidSpace(glm::vec3(-camx,-camy,-camz))-playerESpace.vecInElipsoidSpace(glm::vec3(-lcamx,-lcamy,-lcamz)));
glm::vec3 basePos = playerESpace.vecInElipsoidSpace(glm::vec3(-lcamx,-lcamy,-lcamz));
glm::vec3 destination = playerESpace.vecInElipsoidSpace(glm::vec3(-camx,-camy,-camz));
int object = 0;
float distance = 0;
bool initial = false;
std::vector<collisionResultsPacket>results;
for (int i = 0; i < pysObjs.size(); i++)
{
//we need to test each mesh and see which is the closest triangle from all the meshes
pysObjs[i].testCollisionMeshWithElipsoid(0);
//we just got the closest result for that mesh
//now we test if that is closer than the one we already have
if (initial == false || pysObjs[i].closestResults.distance < distance )
{
initial = true;
distance = pysObjs[i].closestResults.distance;
object = i;
}
}

//now we have the colsest collision point and we can calculate the collision response properly
if (pysObjs[object].closestResults.packet.collided == true)
{
//do collision response
//std::cout << "There was a collision somewhere\n";
glm::vec3 collisionPointInWorldSpace = -(pysObjs[object].closestResults.packet.intersectionPoint * glm::inverse(playerESpace.CBM));
camx = collisionPointInWorldSpace.x;
camy = collisionPointInWorldSpace.y;
camz = collisionPointInWorldSpace.z;
}

}
}



If it is not apparent, I've actually just set up the response so that it sets the camera position to the collision point. Heres the problem: When I get close to the triangle, everything is fine. When it finally does find a collision, for some reason the intersection point is further back from the triangle than the camera already was. I have absolutely no idea what is wrong. I can't see this being a problem of conversion between ellipsoid and world space. I've multiplied the position by the inverse change in basis matrix, just like the paper detailed. I've tried just about everything at this point and I need a second option on what could possibly be wrong. Thanks for any help or input.

Edited by BlueSpud, 03 April 2014 - 03:55 PM.

### #2BlueSpud  Members

Posted 03 April 2014 - 03:55 PM

bump.

### #3BlueSpud  Members

Posted 14 April 2014 - 12:35 PM

I feel really dumb XD and I've solved my problem. I set the camera's point to the intersection point. Something in my brain just didn't register right and I thought the intersection point is the point the camera is at when it intersects the triangle. This causes the strange backward motion I was experiencing. After changing the code to set it to the velocity*time0 + basePos the problem was solved.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.