Sign in to follow this  

Collision Detection Issues

This topic is 3096 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

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 < EPSILON) return

for (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 make
     first contact with the poly (i.e., sphereCenter - polyNormal)
   
   find the point of intersection between the velocity vector (starting at
     the 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 sphere

Are 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]

Share this post


Link to post
Share on other sites
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.]

Share this post


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

Share this post


Link to post
Share on other sites
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 the
maximum 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 polygon
do 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 vertex

if (a valid time value is obtained above)
{
take note of the value if it is earlier than any other
time 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 edge

if (a valid time value is obtained above)
{
take note of the value if it is earlier than any other
time value calculated
}
}

if (any valid time values were obtained previously)
{
collision detected with a vertex or an edge of the poly
do 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]

Share this post


Link to post
Share on other sites
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.)

Share this post


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

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites

This topic is 3096 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this