Jump to content
  • Advertisement
Sign in to follow this  
Moe

Collision detection... (in 3D)

This topic is 4723 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, Lately I have been doing a bit of thinking about collision detection and response. This is something that I have never really done before, and I am a bit nervious about trying to implement it in some form (in a 3D environment). The most that I have ever done is simply putting a limit on the range of the camera for a peticlar scene. I am fairly familiar with the theory of the different methods (bounding spheres, OBB and AABB, using the cross product, BSP trees and convex shapes) but I am still really nervious about trying to code something that actually works. Has anyone here actually implemented a decent collision detection system (in 3D)? How hard was it?

Share this post


Link to post
Share on other sites
Advertisement
I'm still working on that aspect. However, for player-world collision I'd recommend reading "Improved collision detection and response" by Kasper Fauerby. It provides a very interesting system using ellipsoids.

Share this post


Link to post
Share on other sites
I have implemented a few different systems (capsule, cylinder, swept-AABB and swept-sphere). Some advice:

* Use some form of swept method, either sweeping a primitive (sphere, ellipsoid, box etc) against your geometry or expanding your geometry quake-style and doing line segment queries. Trying to use a discrete method introduces a lot of problems and will almost certainly have robustness issues

* Use simplified collision geometry, done either manually or via preprocess. This is not only for the collision detection or performance, but also for the collision response - it is very easy for arbitrary geometry to stick sliding code unnecessarily (assuming you want to slide on contact)

* Be wary of float precision, this applies not only to the detection but also the response, where it is important to try to keep yourself some minimum distance away (depending on your world units) from the geometry rather than right up next to it

That said, swept-spheres are quite widely used and probably a good method to start with, the ellipsoid version mentioned above is an extension of this.

Share this post


Link to post
Share on other sites
I can't say I am really too familiar with sweeping algorithms. Would anyone happen to have any favorite links handy?

Share this post


Link to post
Share on other sites
Quote:
I can't say I am really too familiar with sweeping algorithms. Would anyone happen to have any favorite links handy?
Too lazy to track down the links at the moment, but the aforementioned paper by Kasper Fauerby is good. Also, check out the collision detection articles here on gamedev - there's one that covers swept circles/spheres and swept AABBs.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
I can't say I am really too familiar with sweeping algorithms. Would anyone happen to have any favorite links handy?
Too lazy to track down the links at the moment, but the aforementioned paper by Kasper Fauerby is good. Also, check out the collision detection articles here on gamedev - there's one that covers swept circles/spheres and swept AABBs.

I will have to check it out. Too bad its bedtime.[rolleyes]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Most swept tests are based on one or a combination of the following three techniques:

* The dynamic version of the Separating Axis Theorem (google this, dynamic version is sometimes abbreviated to DSAT). The basic version of SAT applies to static objects but it can be extended for objects undergoing translational motion

* "Reversing" the test to ask the same question the other way round - for example, testing a swept sphere against a box is equivalent to testing a line segment against the box "expanded" by the sphere. Often the equivalent is easier to work out

* Decomposing the original test into a number of simpler tests. This is often used with the technique above. For example, testing a swept sphere vs triangle can be reversed to testing a line segment vs the triangle expanded by the sphere. This can be decomposed into testing the line segment vs 3 "fat" edges and vs 3 spheres and picking the closest intersection (some of the tests can be optimised away in certain situations but you get the idea)

Some links in addition to the Fauerby one: (err don't know how to do links here :P)

http://www.gamasutra.com/features/20000330/bobic_01.htm
A bit of intro to some collision detection issues

http://sourceforge.net/mailarchive/forum.php?forum=gdalgorithms-list
The archives of the Game Development Algorithms mailing list, collision has been discussed a lot

http://www.realtimerendering.com/int
A big list of static and dynamic intersection tests

http://www.gamasutra.com/features/19991018/Gomez_1.htm
A number of static and dynamic intersection tests

http://www.gamasutra.com/features/20010324/melax_01.htm
This describes the cylinder-based method used for avatar collision in MDK2

Also looking through the player collision routines in the quake 2 source might be helpful.

Hope some of that helps!

Share this post


Link to post
Share on other sites
Sweet, thanks a bunch! It looks like I will have to do some readinig now...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!