   Collision Detection Issues
  Hey everyone!This summer, as an exercise in learning C++ (and getting better with OpenGL), I've been creating an engine for what will probably be a crappy game.  Anyways, I'm on the collision detection step.  I did some research and cobbled together my form of collision detection.  This system checks for collisions between a unit sphere, and a trianglized mesh loaded from an OBJ file. Right now, this method checks all polygons in the 'polygon soup', but once I get collision working properly, I will try to use more efficent methods.  Sometimes it works fine, but other times, the sphere gets embedded in walls or falls through the terrain completely.Now, I would like to know if the problems with my collision detection are theory-based or coding-based.  So, to show you the ideas behind my system, I've provided some very simplified psuedo-code.if (distance to travel &lt; EPSILON) returnfor (every polygon in terrain){  find and take note of polygons where: -the starting position and the ending position (position + velocity) lie  on different sides of the hyperplane containing the polygon -a unit sphere would be embedded in the plane @ the destination point}if (no polygons match the description){  perform the move   return}for (each potential colliding polygon){  set sphere collision point to be the point on the sphere which would makefirst contact with the poly (i.e., sphereCenter - polyNormal) find the point of intersection between the velocity vector (starting atthe sphere collision point) and the hyperplane containing the polygon   if (the point of intersection lies within or on the edge of the polygon)   {   we have found a collision!    compute the distance to this collision    if (this distance is smaller than any other distance)  {   take note of this distance, the current polygon, and   the point of intersection  }   }}if (we have found a collision){  new position := currentPosition + velocity w/length set to closest distance}else{  new position := currentPosition + velocity}update the sphereAre my ideas behind collision detection sound?  Or is there a fundamental issue with the logic that is causing my mistakes?Thanks!PS:  I don't know the proper tags to use for codes, so sorry if the formatting is a little screwy.[Edited by - jrod2032 on June 8, 2009 2:14:17 PM]
  The tags you're looking for are [source][/source].I noticed two things right off:1. The start and end points lying on opposite sides of the supporting plane of the triangle is not a necessary condition for intersection to occur, so it's incorrect to use this as an early out.2. If the computed intersection point falls outside of the triangle, the sphere may still collide with one of the triangle edges.You might search the archives for 'sphere triangle intersection'; you should be able to find some good references explaining the algorithm, and maybe source code as well.[Edit: It looks like you're addressing item 1 with the 'embedded' test, so maybe it's just item 2 that's causing the problem.]   ;  I edited the original post to use the source tags.Thanks for the advice, I'll definitely do some searching around for sphere triangle intersection topics/papers/algorithms in order to handle the second case you mentioned.I knew that the code just seemed too easy to be true!   ;  Okay, this stuff is driving me crazy.I've done a good bit of research on collision detection, and changed my algorithm accordingly.  Now, it is still behaving crazily (not recognizing obvious hits, etc).Now, I'd like to make sure that this algorithm is sound before trying to double and triple check all the maths in my code (which will definitely make me cry).  Below is the updated algorithm (just the collision detection part):for (each triangle in the mesh){  find the point that the sphere will intersect the triangle first(i.e., sphereCenter - polyNormal) if (a ray starting from the sphere collision point in the direction of  the velocity vector makes contact with the hyperplane)   {   if (the distance to the plane collision point is within themaximum moving distance for this time step) { if (the current triangle contains the plane collision point)    {    if (the distance to this collision is smaller than the closest colliding distance detected so far)  {  collision detected w/in the polygondo whatever's needed  }    }    else    {    for (each bounding vertex of the polygon)  {  find the earliest time (if any) when the center of the swept  sphere is the radius' length away from the vertexif (a valid time value is obtained above){take note of the value if it is earlier than any othertime value calculated}  }  for (each edge of the polygon)  {find the earliest time (if any) when the center of the swept  sphere is the radius' length away from the edgeif (a valid time value is obtained above){take note of the value if it is earlier than any othertime value calculated}  }  if (any valid time values were obtained previously)  {  collision detected with a vertex or an edge of the polydo whatever's needed  }    } }   } }Now, is there anything wrong with the algorithm as I presented?Thanks for the help![Edited by - jrod2032 on June 13, 2009 5:13:13 PM];  There are some optimizations that could be made at the algorithmic level, but based on a quick read-through, I would say that what you have looks correct. (Unfortunately though, implementing this test correctly can be tricky, as there are quite a few details that have to be gotten right.)   ;  Yeah, that's what I was afraid of.But, I spent today slaving over the code and everything seems to be working alright now.Thanks again for your help, and sorry if I was asking extremely noobish questions.BTW the debugging/breakpoint functionality of Visual Studio rocks.   ;Quote:Original post by jrod2032BTW the debugging/breakpoint functionality of Visual Studio rocks.amen to that   ;  This is probably not what you want to hear since you've gone ahead and written a good deal of code, but Kasper Fauerby has a good PDF on the web about Swept-Sphere collision detection in ellipsoid space. You model the collider as an ellipsoid, then flatten potential collidees from R3 space to Ellipsoid space and run a swept-sphere algorithm to see at what time [t] a collision might occur, then you perform some simple sliding vector adjustment and repeat until there is no collision.I've implemented and it works nicely for all arbitrary collision geometry (aside from some jitteriness that is likely my own doing).   