Collision Detection in twitch games

[DangerCode]

I was wondering is some of you guys out there had a favorite paper that explains a good collision detection scheme. Basically I'm looking for a way of knowing if any two (possibly concave) polygons collide.

I'm also a bit concerned about fast moving particles during a slow frame refresh, where the particle didn't hit between refreshes yet would have had the update been continuous. (perhaps I just have to guarentee a solid frame rate in this case?)

[milo]

There are a few different ways of doing polygon interference detection - octrees, axis-aligned bounding-boxes, and object-aligned bounding-boxes are probably the three most common (unless someone has come up with something really cool in the last few years). There are quite a few papers and open source implementations of each algorithm, so it's hard for me to recommend a favorite. You should do a google search and read at least one paper for each method before deciding which suits your needs best. Either that, or just punt and pick up one of the open source libraries and not worry about how it is implemented.

For particle collision, you don't want to just check the particle location on each frame. You will need to compute the line segment that the particle has traversed since the last frame, and determine the closest point on the line segment to the test object. If the closest point is within the bounding sphere of the test object, then you can perform a piercing test for the line segment through each of the polygons on the test object. Of course, this is all assuming that the target is moving much slower than the particle, as in the case for a bullet or laser blast versus a human or vehicular target.

--milo
http://www.starshatter.com

[hh10k]

If you're just interested in testing whether two primitives intersect, you might want to check out these pages:

3D Object Intersection (http://www.realtimerendering.com/int/)
Paul Bourke (http://astronomy.swin.edu.au/~pbourke/)
Magic Software (http://www.magic-software.com/)

They should cover pretty much all the basic geometry testing you'll ever need, but you may want to try Opcode (http://www.codercorner.com/Opcode.htm) for testing whether two models intersect each other. Note that if you're dealing with concave polygons (or even maybe convex) you'll want to split them up into triangles to make the intersection tests easy.

[Siebharinn]

"3D Game Engine Design" by David Eberly goes into mind-numbing detail on how to do collisions. Lots of other good stuff in it as well.

[Cartman]

Also, don't forget the Graphic Gems series of books. They have all of these algorithms in them for collision detections between differing objects.

[DangerCode]

Thanks for the good suggestions guys. I have found what I'm looking for. (someone tell Bono)

[C_Coder]

I never did this myself but I know of a technique that you can use a lower quality mesh of the object that you are checking for collision detection. This will reduce the number of polygons to check for collision. Obviously before beginning to do the polygon collision check, check if the object's bounding boxes collide first or else you will make computations for nothing.

I hope this helps! :)

[ogracian]

Hi,

You could check the OPCODE (http://www.codercorner.com/Opcode.htm)collision detection lib, it is a very clean and robust lib, and best of all is FREE and comes with full SRC CODE, it contains a fast Triangle - Triangle routine (a LOT other good things too) which could help you.

Regards,
Oscar

[milo]

Is anybody here actually using OPCODE?

I just downloaded and compiled the library, only to find name collisions with my own game engine. The author went to the trouble of putting all of his stuff in namespaces, but then the main include file contains "using namespace" statements that re-ambiguate all of the common foundation class names (like Point and Plane). :-P

--milo
http://www.starshatter.com

[hh10k]

We use OPCODE for Cellblock Squadrons. I was just lucky that I named all my math classes things like Vector3f, Matrix3x3f, Plane3f, etc :)

Of course, the solution to your problem is good ol' search-and-replace 'Point' for 'IcePoint' :)

[tentons]

Are there any good libraries for 2d collision detection?

I'm probably going to write something from scratch since I don't know of any, but I'm looking for something using 2d polygon collision detection (separation of axis theorem (http://www.magic-software.com/Documentation/MethodOfSeparatingAxes.pdf)) since it offers many benefits over bounding box and pixel perfect techniques.

[Mike Boeh]

Way back when I was coding Bugatron, I came upon this problem, and at the time, there weren't any polygon collision libraries. So I came up with an interesting hack that may work for others.

Internally, bugatron runs at 1000 fps, and just renders out at whatever speed the computer can handle. So my first advantage is that I had a lot of samples. Secondly, all collisions take place at a Z value of zero, because while the game is 3d, it really only plays in a 2d area.

So using these two things, I was able to simply take 3 random line segments from each of the two models, and run an XY line collision check on them, completely ignoring the Z value. The result was seemingly flawless polygon collision in a fraction of the time a "true" 3d polygon collision check would take! :-) Of course, I had special circumstances that I could take advantage of- but isn't that what game coding is all about?

[milo]

Of course, the solution to your problem is good ol' search-and-replace 'Point' for 'IcePoint' :)
OK, yeah that works. Annoying, but it works.

So now that the whole mess compiles, I'm trying to figure out how to use it. The docs are for version 1.2 and he seems to have changed things quite a bit in version 1.3. I'm sure I'll figure it out eventually, but it would go faster if there were some sample code available for actually using the library. Are there any samples on the Internet anywhere or am I on my own?

Thanks,

--milo
http://www.starshatter.com

[impossible]

Metanet has some great tutorials about how collision detection in N was done (with SAT.) http://www.harveycartel.org/metanet/tutorials.html.

This is also good http://www.pfirth.co.uk/collision.html.

[Jim Buck]

I used the separating plane method for colliding cars in 3d in Twisted Metal 4 (PS1):

http://www.gamasutra.com/features/20000203/lander_pfv.htm

(The beginning of the articles talks about axis-aligned, but he address arbitrarily-aligned toward the end of the article.)