This Collision Detection/Response Tutorial...

Member
Posts: 148
Joined: 2003.03
Post: #1
I was wondering if anyone has taken a look/stab at this tutorial: http://www.peroxide.dk/download/tutorial...tut10.html

I got the concept down pretty good, and I've got all of the code written. My collision detection works half-assedly (works sometimes), and my collision response doesn't appear to be correct; mainly due to the fact that the author of the tutorial conveniently left out (or perhaps I've missed) the relevant implementation details (from both the tutorial and the tutorial source code) that should be located somewhere near the end of the tutorial.

If anyone has any experience with this tutorial, I sure could use your help. Oh the frustration! Thanks.
Quote this message in a reply
Member
Posts: 446
Joined: 2002.09
Post: #2
Quote:Originally posted by MacFiend
My collision detection works half-assedly (works sometimes)
There's an update to that available here: http://www.peroxide.dk/tuts_c.shtml The update uses sweep tests so fast moving objects won't pass through polys (which may be the problem you're seeing), but it's definitely more complicated.

A more in-depth description of sweept shpere collision (with source) can be found here: http://www.three14.demon.nl/

Quote:Originally posted by MacFiend
...my collision response doesn't appear to be correct
The response seems a bit iffy at times (especially on multiple edges). If you use it as-is you have to be sure to apply gravity in a separate pass.

In all I found those papers to be informative but the result was too slow for my purposes (mostly because of the separate gravity step). I'm taking what I've learnt and trying to design a system that will hopefully minimize recursion - It's nowhere near finished though.
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #3
Quote:The update uses sweep tests so fast moving objects won't pass through polys (which may be the problem you're seeing)

I think this may be the case. Sometimes when I get close to a triangle, everything freezes for a second (recursion I assume), and then the position ends up on the other side of the triangle. Sometimes it freezes permanently. It's probably something I forgot to do (like normalize a vector). That new tutorial looks like a BEAST, but it looks like what I'm looking for.
Quote this message in a reply
Member
Posts: 446
Joined: 2002.09
Post: #4
Quote:Originally posted by MacFiend
Sometimes when I get close to a triangle, everything freezes for a second (recursion I assume), and then the position ends up on the other side of the triangle.

Are you checking for collisions on both sides of the triangle? I found it more stable (and much faster) to only test for collisions on the front. Whether or not this is an appropriate thing to do depends on how our level data is arranged though.
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #5
Quote:Originally posted by Frack C.Are you checking for collisions on both sides of the triangle? I found it more stable (and much faster) to only test for collisions on the front. Whether or not this is an appropriate thing to do depends on how our level data is arranged though.

I thought that might be a problem, so I tried just checking against triangles that have a normal facing the source's velocity. It still does the same thing, so I figure I must've goofed somewhere in the code.
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #6
A section from the newer version of the tutorial I was talking about as pointed out by Frank C.:

Quote:This updated version of the algorithm fixes in particular the problem where colliding against triangle edges could cause the original algorithm to fail resulting in the player being stuck or fall through the world geometry.

Ahhhhh....!!!
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #7
I went through the new tutorial, re-writing all my collision code. I have just a few questions...

1) In the tutorial PDF, in the collideWithWorld() function code (in the Appendix), it says "world->checkCollision()", which is an "application specific" function. This function should generally go through all triangles, convert them to ellipsoid-space, and call checkTriangle() with the current collisionPacket and eSpace-triangle, correct?

1a) When scaling a triangle to ellipsoid-space for the purpose of this collision detection, I should be scaling the triangle normal as well right?

2) This collideWithWorld(position,velocity) function should be called no matter what (ie, it doesn't matter if there is a collision or not), right?

2a) Afterwards, if collisionPacket.foundCollision is true, then I would continue on to calling collideAndSlide(), right?

3) For the collision response, isn't there supposed to be some vector that I'm supposed to apply to the object's velocity to get it to move parallel to the triangle?

4) I'm using time-based movement for this, so should I scale the velocity and(/or) position (that I pass to collideWithWorld() ) to the current time increment?

[EDIT]
I just noticed that I forgot to update my isPointInTriangle() function to match the one in the tutorial (I'm sure mine works fine, this is for ease of mind).

Code:
typedef unsigned int uint32;
#define in(a) ((uint32&) a)
bool checkPointInTriangle(...)
{
   ... ... ...
   return (( in(z)& ~(in(x)|in(y)) ) & 0x80000000;
}

I get 3 "parse error before '&' token" errors. [EDIT 2] When I change uint32& to uint32, it works fine. So now my question for this edit is, what's the difference between the 2 (if any?)
Quote this message in a reply
Member
Posts: 446
Joined: 2002.09
Post: #8
First I'll say I haven't read through the new PDF yet so take this advice with a grain of salt...

Quote:Originally posted by MacFiend
1) In the tutorial PDF, in the collideWithWorld() function code (in the Appendix), it says "world->checkCollision()", which is an "application specific" function. This function should generally go through all triangles, convert them to ellipsoid-space, and call checkTriangle() with the current collisionPacket and eSpace-triangle, correct?
Yes.

Quote:Originally posted by MacFiend
1a) When scaling a triangle to ellipsoid-space for the purpose of this collision detection, I should be scaling the triangle normal as well right?

Yes - the normal defines the triangle's plane, and must be transformed into ellipsoid space.

Quote:Originally posted by MacFiend
2) This collideWithWorld(position,velocity) function should be called no matter what (ie, it doesn't matter if there is a collision or not), right?
Yes, unless you have some early-out code in place (say you've partitioned the world, and the object is in an empty node for example).

Quote:Originally posted by MacFiend
2a) Afterwards, if collisionPacket.foundCollision is true, then I would continue on to calling collideAndSlide(), right?

Yes.

Quote:Originally posted by MacFiend
3) For the collision response, isn't there supposed to be some vector that I'm supposed to apply to the object's velocity to get it to move parallel to the triangle?

You have to calculate the sliding plane, and the velocity of the move along that plane, which is then added to your next move (this should be in the PDF).

Quote:Originally posted by MacFiend
4) I'm using time-based movement for this, so should I scale the velocity and(/or) position (that I pass to collideWithWorld() ) to the current time increment?

I'm going to say yes, but I'm not sure I understand the question... Your move should equal the translation from where the object is this frame, to where it should be next frame (if you're time based then this should already be done by the time you reach the collision step).

Quote:Originally posted by MacFiend
(uint32&)

That looks like a typo.
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #9
Quote:You have to calculate the sliding plane, and the velocity of the move along that plane, which is then added to your next move (this should be in the PDF).

I think this may be the problem. If I collide with a triangle, I get moved to where I should be...but this move is very rough...because the velocity of the "entity" isn't being changed at all, just its position. I don't see anything about this anywhere in the old or new tutorials (or again, maybe I'm missing it). I see "finalPosition"...shouldn't there be a "finalVelocity" to go along with this?

Anyway it turns out theres a post on another forum concerning this tutorial: http://pub137.ezboard.com/fmrgamemakerfr...3610.topic

It looks as if a lot of people are (were?) having similar problems with this tutorial. I'm sure it's some super small detail, the only problem there are so many different things it could be! Blink

[EDIT]
Am I supposed to be dividing the position/velocity vector that I pass to collideWithWorld() by ellipsoid radius, and then multiply by ellipsoid radius afterwards?

[EDIT 2]
To give you more of an idea of what I mean: if the entity pass through a triangle at a high speed, there is a collision, but the collision response really does nothing as the high speed velocity is still being applied in the next collision check (because it hasn't been changed). It seems the entity's velocity should be multiplied by some factor of the sliding plane's normal (or it's length, or length squared...i dunno), to get it to travel parallel to the triangle but in its same general direction (NSEW)...or something along those lines.
Quote this message in a reply
Member
Posts: 446
Joined: 2002.09
Post: #10
Quote:Originally posted by MacFiend
Am I supposed to be dividing the position/velocity vector that I pass to collideWithWorld() by ellipsoid radius, and then multiply by ellipsoid radius afterwards?
I don't think so - once the world is in ellipsoid space everything is relative to a unit sphere and it should "just work"...

Quote:Originally posted by MacFiend
To give you more of an idea of what I mean: if the entity pass through a triangle at a high speed, there is a collision, but the collision response really does nothing as the high speed velocity is still being applied in the next collision check (because it hasn't been changed).

But it is changed - adding the slide velocity should negate and deflect some of the original move (or at least that's what I gathered from the papers).

I actually don't use the sliding plane so I can't say it if works or not as is - I ended up pushing the object back along it's move vector as well as the triangle plane, until it's no longer colliding - which works, but has other problems (which is why I'm rewriting it). This is a common approach when you need the penetration depth, but can't really be done with a sweep test, since that gives you a position just before the actual collision.
Quote this message in a reply
w_reade
Unregistered
 
Post: #11
I've only given the tutorial the most cursory look, but what about just setting the position to the closest point where it isn't colliding and projecting the velocity onto the sliding plane? If you want it to bounce, reflect the velocity in the sliding plane and scale the perpendicular component down a bit...
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #12
Quote:But it is changed - adding the slide velocity should negate and deflect some of the original move (or at least that's what I gathered from the papers).

Then for some other reason, it's letting the entity pass through the triangles...

The actual velocity isn't being changed, it just moves the entity according to its velocity and the slide plane. So it'll collide with the triangle a couple of times, then it'll eventually pass through the triangle, unless the entity is moving slow.

As w_reade said: if, when I get a collision, I were to move the entity to the closest point possible without colliding, and send the entity in a direction that's perpendicular to the sliding plane, then it'll just collide with the triangle once, and continue in it's path until it hits another triangle (or it stops). I'm not exactly sure on how to do this (projection that is).

[EDIT]
Right now, when I get a collision, I collideAndSlide() the entity with the world, and I zero the entity's velocity afterwards. Doing so causes it to "slide" to an extent, but it's not really sliding...it's just moving and stopping. If you understand this, then you get what I mean. Smile

Thanks for all your help guys, I really appreciate it.
Quote this message in a reply
w_reade
Unregistered
 
Post: #13
Projecting a line onto a plane:

The way that immediately comes to mind is a change of basis, but I can't be bothered to dredge that out of the depths of my memory, so you could just do this:

take the collision point Pc and the velocity U of the moving thing and add them together to make a point Pe = Pc + U. Find the closest point to Pe that lies on the sliding plane, call it Pp, and set your new velocity V = Pp - Pc.

For bonus points, make them bounce by actually setting your velocity to W = V + r * (Pp - Pe) where r is the coefficient of restitution (between 0 and 1, unless you want things to act weird).

I think this is right, ask if you have any questions.

[edit: bugger, wrong variable names. Should be fixed]
Quote this message in a reply
Member
Posts: 148
Joined: 2003.03
Post: #14
Thanks w_reade. It appears to work perfectly if the geometry is flat, and A LOT better when the geometry isn't flat, but there's still something wrong. I've contacted that author of the tutorial for further help, as I'm sure the problem lies in one of the "application specific" functions he describes.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Response to Elphaba arekkusu 6 3,005 Aug 27, 2009 02:24 AM
Last Post: Ingemar
  2D Pixel Collision Detection using OCCLUSION Elphaba 0 3,319 Jun 8, 2009 06:30 AM
Last Post: Elphaba
  the best way to do collision detection ghettotek 26 10,260 Jun 4, 2009 02:30 PM
Last Post: AnotherJake
  Hierarchy, gluProject and collision detection lemtoo 3 4,661 Nov 30, 2007 09:26 AM
Last Post: lemtoo
  multi-level collision detection alert 0 1,736 Apr 7, 2005 10:27 AM
Last Post: alert