Sign in to follow this  
minionx

racing game collisions

Recommended Posts

minionx    133
Hi there, So i've got it in my head to put together a little 3d racing game, making use of my rigid body dynamics code for car physics. I've written a gjk implementation (nearly finished that is) for detecting collisions between convex bodies (the car bodies in this case), but now it occurs to me that i'll need to do collisions against the ground/track/whatever else, which may not necessarily be convex. Can I decompose my track/environment into convex pieces and still use GJK for collision detection, or will that be too costly? If its impractical, what *reliable* method could be used instead for convex-hull/poly-soup collision detection? Thanks, -Eric

Share this post


Link to post
Share on other sites
oliii    2196
I dont think you have much of a choice. Dealing with non convex geometry will be very hard to pull off. Detection isn't the problem, but it is to get a fluid, continuous response.

Share this post


Link to post
Share on other sites
sbroumley    283
Well I wouldn't say I'm a pro exactly but I do have convex hull versus poly soup (my world) collision working in my physics engine.

I actually use a swept SAT collision tests, but it could probably be adapted to use GJK or whatever you want.

Basically I simply perform an SAT test between my convex hull and each world triangle individually (broad phase culls out most of the world triangles so there's only a few to perform SAT tests on).

In order to get correct collision response, I pre-process my poly soup collision so that each triangle has a flag for each edge. This flag determines if an object can actually collide with the edge - it is only true for edges that face outwards (this can be easily determined by using the dot product of the 2 triangles that share the edge).

eg. think about the edges of a simple staircase - the external edges of each step can be collided with, but the internal edges between each stair cannot because you would hit the connected faces before the edge.

e = external edge
i = internal edge

_*e
*|_*e
i**|_*e
**i**|_
****i**|

(this is a side view, where e and i are edges that go into the screen of the 3d world - I hope my crappy ascii pic makes sense - I had to replace the spaces with * to keep the formatting)



Then all I did was modify the SAT test so that all the (convex hull edges cross triangle edges) are still used as a separating axis test, but the MTD (minimum translation distance) is only updated if the triangle edge is marked as collidable.

For swept sphere collision, I also extended the system so that each triangle has an additional 3 flags (1 for each vertex) to determine if a vertex should be considered during swept sphere versus triangle tests.

The same idea is also discussed by the novadex guys in Game-Programming-Gems4.

Let me know if this doesn't make sense or you have further questions,
Steve.

[Edited by - sbroumley on November 9, 2005 8:34:38 PM]

Share this post


Link to post
Share on other sites
oliii    2196
along similar lines, in the first commercial game I worked on, I computed smoothed normals at each of the vertices. When a collision with a vertex occured, I took the normal at the vertex, and not the MTD, for calculating the colliison response.

If it was an edge collision, I interpolated the normals at the edge vertices to where the contact point was found, and used that as my collision normal.

It's a bit nasty, but the problem is nasty. Even with swept SAT, and flagging edges-vertices, you can get unwanted 'hard' collisions, and smoothing them out will be a pain.

problems :

- the collision mesh has to be reasonably tessalated. Long edges will produce errors.
- need to store normals for vertices.
- Other problems I forgot about! (I's been 5 years :)).

Share this post


Link to post
Share on other sites

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