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.**