Im working on collision detection for my game, and need some advice. I looked into a bunch of different collision detecion algorithms, and finally decided to be ambitious and use GJK. But now that i looked more into it, im not sure if its the best choice for my requirements. So GJK is really fast for just detecting collisions. But I need the colliding objects to physically respond to the collision. For this, i need to know exactly which polygon hit where on which polygon. But it seems that calculating the point of collision requires explicitly finding the whole CSO, which would take n^2 time to find the verticies, and then even more time to build the hull. So now im not sure. Given these requirements, would GJK still be the best choice in terms of speed? Thanks. EDIT: Oh, another thing i need to find is the penetration depth in the direction of the 2 object's relative velocity. If i do build the hull of the whole CSO, i can find this fairly easily.. i think? Alternatively, if i use another algo, i could do a binary search through space. Please take this into consideration when answering my questions above. Thanks.

Building the CSO explicitly isn't really practical, for two reasons:

1. Too slow (as you noted)
2. Not necessarily feasible when curved objects are involved

The point of GJK is to work with the CSO not by building it explicitly, but rather by sampling it through a support function. Ray intersection (for raytracing or swept tests), closest point to the origin (for distance and static intersection) and penetration direction and depth (via the expanding polytope algorithm) all work with the CSO through a single support function.

I don't want to be discouraging, and just because I find GJK hard to implement doesn't mean it would be hard for you. But, I would say that your choice of the word 'ambitious' is not inappropriate.

Perhaps you could give us a little more information, specifically:

1. Whether you need swept tests, or only static (with penetration info)
2. What shapes you want to support (boxes, cylinders, capsules, etc.)

I ask because for many pairs of shapes there are solutions which are far easier to implement than GJK. If you can tell us more about your needs, we can probably recommend some alternatives.

Mmmm i see. Thanks for your reply.

1. The game is quite dynamic and realtime, so i would need swept tests.

2. Im need to do collision detection on pretty much anything you can find in a 3D rpg game. That would include simple boxes and cylinders for things like walls and trees, and also more complex things such as character/creature models (which i probably will split into several convex polytopes).

This is all IMHO, but here's what I'd do. Collision detection and response in general is difficult, so if I were you I'd simplify things as much as possible. Here are a few ideas for how you can restrict the problem domain:

1. Cylinders in general are hard to do collision detection with, but if they're all aligned to the same axis, it reduces to a 2d problem, which is easy. In your case, for example, characters, trees, and anything else that is more or less upright could be represented as a cylinder.

2. For arbitrary orientation, an alternative that is a little easier to work with is a capsule, which is basically a cylinder with hemispherical caps on the end (all points equidistant from a line segment).

3. If you can get away with it, represent characters with one simple convex shape rather than multiple polytopes. For special cases, such as determining where a projectile strikes a character, you can use raytracing.

4. Perhaps consider using a combination of swept and static tests. I can't imagine characters will be moving through trees in one timestep, and solving static intersection between such objects can be done simply and robustly.

Again, this is just advice which you can take or leave (and may be wrong), but I'd forget about GJK for the moment. My guess is it would be overkill for this sort of environment, and that trying to code it would just bog you down. Even getting simple collision detection right is hard, so a good rule of thumb is don't make it any more complex than it needs to be to get the job done :)

Quote:
1. Cylinders in general are hard to do collision detection with, but if they're all aligned to the same axis, it reduces to a 2d problem, which is easy. In your case, for example, characters, trees, and anything else that is more or less upright could be represented as a cylinder.

2. For arbitrary orientation, an alternative that is a little easier to work with is a capsule, which is basically a cylinder with hemispherical caps on the end (all points equidistant from a line segment).

3. If you can get away with it, represent characters with one simple convex shape rather than multiple polytopes. For special cases, such as determining where a projectile strikes a character, you can use raytracing.

I think i can easily get away with using simple convex shapes like aligned cylinders, spheres, and the such for static objects like rocks and trees, but my main problem is with characters. In my current game design, the character models will be jumping and flipping and flaying their arms all over the place, so im not quite sure how to use a simple convex shape. A cylinder/capsule might work for the body, but then arms and legs (or worse, long weapens such as spears) would penetrate through walls.

Currently, what im doing is this: Split the character model into smaller parts (ie. 2 for each arm, 2 for each leg, etc.). When a character C and an object O collide, check which parts of C have bounding spheres (i may change this to capsules later, since they fit bodyparts much more tightly) overlapping with the bounding sphere of O, and then loop through those parts with a more accurate method (originally was going to be GJK) to see which ones are actually colliding. I cant think of any other way to keep limbs from penetrating other objects without being super-conservative (like keeping everything at arms-length away).

Quote:
4. Perhaps consider using a combination of swept and static tests. I can't imagine characters will be moving through trees in one timestep, and solving static intersection between such objects can be done simply and robustly.

Oh yes, i wont be using swept tests for everything. Im thinking about doing something like only using swept tests if the distance of the object's movement in that one timestep is more than 2/3 of the radius of its bounding sphere, or something like htat.

Quote:
Again, this is just advice which you can take or leave (and may be wrong), but I'd forget about GJK for the moment. My guess is it would be overkill for this sort of environment, and that trying to code it would just bog you down. Even getting simple collision detection right is hard, so a good rule of thumb is don't make it any more complex than it needs to be to get the job done :)

Hmmm.. so what is it about GJK that makes it so difficult? The only problem ive heard (er.. read) about is some problems with floating point precision, but in Gino van den Bergen's paper titled "A Fast and Robust GJK Implementation for Collision Detection of Convex Objects" (forgot where i downloaded it from.. i think from the SOLID website), he talks about several ways (all of which seem fairly simple) to solve these problems, and claims that after he implemented these fixes, his GJK implementation passed all of his tests with no problems.

hmm, for some reason it wont let me edit my post. Anyway, by the way, do you know of any good resources about collision detection with raytracing?

Quote:Hmmm.. so what is it about GJK that makes it so difficult? The only problem ive heard (er.. read) about is some problems with floating point precision, but in Gino van den Bergen's paper titled "A Fast and Robust GJK Implementation for Collision Detection of Convex Objects" (forgot where i downloaded it from.. i think from the SOLID website), he talks about several ways (all of which seem fairly simple) to solve these problems, and claims that after he implemented these fixes, his GJK implementation passed all of his tests with no problems.

I'll just say that my own goal is to implement GJK robustly, with raytracing, swept tests, and the expanding polytope algorithm for penetration, and I'm finding it to be a big project. For others, it may not be difficult at all.

Quote:Anyway, by the way, do you know of any good resources about collision detection with raytracing?

What exactly do you mean by collision detection with raytracing?

As for the character collision problem, I think your method of breaking into a few simple primitives seems reasonable. For example, let's say you have a more or less humanoid character with a long spear held outward, moving against a wall. Do one capsule/plane test for the character, resolve the collision if any, then do the same for the spear. That way he can back all the way against the wall, but would be stopped by the spear if approaching it from the front.

I'm sure there are other ways of handling it, but that sounds reasonable.

Quote:What exactly do you mean by collision detection with raytracing?

i dont know much about raytracing, so... im not sure, haha. I was referring to whatever you were referring to in your #3 in your last last post.

Quote:i dont know much about raytracing, so... im not sure, haha. I was referring to whatever you were referring to in your #3 in your last last post.

Ah, got it. By that I meant that when one of the objects can be represented as a moving point (which is often the case with projectiles), you can treat intersection testing as a raytracing problem. There are standard solutions for intersecting a ray with just about any object, including all the standard bounding volumes, convex meshes, and arbitrary meshes. So for things like determining damage based on where a character has been hit, you can do very detailed collision detection using raytracing if need be.

mmm ic. So if i dont use GJK, what alternatives would you suggest for the accurate test of body parts after the bounding volumes test?