Hi all, I've been reading Real-Time Collision Detection (RTCD) for quite a while now (great book, explained very well), along with some other books that discuss collision detection. I've noticed there are parts that discuss collision detection for moving bodies, both in RTCD and in Eberly's "3D Game Engine Design", which present algorithms for moving objects. Mostly it has been one of two choices: 1. Use a bisection algorithm to find the first time of contact in a time interval. 2. Use the generalization of the separating axis method for moving objects, which tends to be more complex that the original. Now, I understand both methods. With the first, there is a recursion and a logarithmic complexity of the search for the collision. What I'm wondering is if there is no collision, there are going to be many queries. How will that work in real time ?? And as for the separating axes method, it is more complicated than the original and probably contains more pathological cases. How feasable is it to implement these algorithms ? What are full fledged game engines do when it comes for collision detection for dynamic objects ?? What is a good direction to take the engine to ?

Quote:Original post by voguemaster
With the first, there is a recursion and a logarithmic complexity of the search for the collision. What I'm wondering is if there is no collision, there are going to be many queries. How will that work in real time ??

You only need to divide a time segment when at the start of that segment there is no intersection but at the end there is, disgard any time segment for which the intersection status is the same at both ends. Hence when there is no collision over the physics time step there will be no interection reported at either end of your first time segment and so there is no need to split it and recurse.

Quote:Original post by voguemaster
And as for the separating axes method, it is more complicated than the original and probably contains more pathological cases. How feasable is it to implement these algorithms ?

Very feasable. In fact S.A.T. is without doubt one of the most popular intersection testing methods because the code is simple, its fairly fast, very easy to optimise, and its possible to extract other needed information out of the tests without much fuss.

Quote:Original post by voguemaster
What are full fledged game engines do when it comes for collision detection for dynamic objects ??

Most engines I've seen and also those I've written myself dont even try to detect the first time of intersection under most circumstances since to try and create an engine that stops, starts, rewinds, restarts etc to resolve collisions in exact time correct order becomes extremely complicated and inefficient very quickly and so isn't well suited to games. Instead its common to move all your objects to the end of the time step and perform the collision detection only once at that point. For very fast objects or collisions with very thin surfaces you might want to combine this with a ray test to be sure objects dont pass through each other or fall out of the game world however.

To maintain non-penetration you can modify the standard S.A.T. fairly easily to return minimum penetration axes and depths of intersecting objects and use this to physicaly seperate the objects. Exactly how you implement this depends on your game. For something like a space game then simply pushing each object back along the penetration axis by half the depth should be sufficient. However if you want to create stackable objects you'll have to be more clever and build up intersection groups with each member in the group sorted by height and seperate objects from the bottom up.

There's really a lot of complications and subtleties to this subject, and as most people who've tried this before will tell you 'its as much of an art form as a science'. The best advice I can give you is to read as many papers on the subject as possible to avoid common pitfalls (I recommend anything by Baraff) and then just experiment for yourself.

Good luck

I don't understand something. You said you only need to divide a time segment if there is an intersection at the end of the segment, but what happens when you don't have intersection at the beginning and at the end of the time segment the object has completely passed through another object (wall for example) ?

In that case, there is no intersection at the end of the segment as well, but there is an intersection sometime in the middle of the time segment.

I know one way to deal with it is to somehow use swept volumes, although I gather that you can get away with a few rays..


One other thing: You said something about intersection groups for stackable objects. Can you elaborate a bit more ? I know a stack of objects is tricky but I haven't yet gotten to that part.


What you're saying is to sort them by height ? why ? In any case, if you have a data structure that contains all your scene objects, having special intersection groups sorted by some specific way (which differs from the normal spatial sorting of the scene) will complicate things, am I right ?


What is a good way to store scene objects ? An octree ? BSP tree ? graph ? an assortment of collision groups ? After all, the spatial sorting you do greatly depends on the underlying data structures.

For me this is also an interesting dilemma.

Quote:Original post by voguemaster
I don't understand something. You said you only need to divide a time segment if there is an intersection at the end of the segment, but what happens when you don't have intersection at the beginning and at the end of the time segment the object has completely passed through another object (wall for example) ?

In that case, there is no intersection at the end of the segment as well, but there is an intersection sometime in the middle of the time segment.

This is true for any non-predictive collision method. If you really really must have objects which are small enough and travel fast enough to pass through each other and they must collide then you'll have to use a predictive collision method like swept volumes. I've never seen this be a problem though since any small and fast enough objects can be intersected with larger objects and terrain via rays and it really isn't too noticeable if two objects of this size and speed pass through each other (think of things like small shrapnel chunks from an explosion).

Quote:Original post by voguemaster
One other thing: You said something about intersection groups for stackable objects. Can you elaborate a bit more ? I know a stack of objects is tricky but I haven't yet gotten to that part.


What you're saying is to sort them by height ? why ? In any case, if you have a data structure that contains all your scene objects, having special intersection groups sorted by some specific way (which differs from the normal spatial sorting of the scene) will complicate things, am I right ?

You are right, things do get more complicated, but if you want a robust and realistic collision and physics system it isn't simple. The reason for the height ordered seperation is because if you seperate your collision groups in any old order you'll end up with a stack of objects which dont maintain non-penetration constraints which is needed for stacking stability and is also often a pre-requisite of starting your next physics step. I've drawn a little example so you can see this for yourself:



As you can see, if the green box is seperated before the orange box, then when the orange box is seperated from the terrain it will re-prenetrate the green box violating your non-penetration constraint at the end of the frame. If however this group was seperated in height order with the lowest box moving first you'd form a perfect non-penetrating stack. These contact groups and height orderings can also be used for other things such as impulse propagation through the stacks which will also greatly increase the realism of the simulation.

Quote:Original post by voguemaster
What is a good way to store scene objects ? An octree ? BSP tree ? graph ? an assortment of collision groups ? After all, the spatial sorting you do greatly depends on the underlying data structures.

This really depends on what sort of game world you have. Personally I find octrees and quadtrees to be suitable in a wide range of environments so maybe give one of these a go. The only thing to be aware of using these kind of recursive spacial partitioning techniques is that objects which intersect the boundaries of nodes high up the tree will be involved in much more collision testing than they really need since they will be stored in one of the larger partitions. This can lead to unpredictable and stuttering frame rates which is very undesirable so once you get the hang of these techniques you might want to do some research and modify your trees to be loose trees instead. With regards to collision groups, this is a step that would be taken in addition to your partitioning method. For example, in one frame you detect that object A and object B intersect and that also object B and object C intersect. These would be combined together to form the collision group ABC.

Quote:Original post by voguemaster
I've been reading Real-Time Collision Detection (RTCD) for quite a while now (great book, explained very well) [...]

Thank you!

Quote:Mostly it has been one of two choices:

1. Use a bisection algorithm to find the first time of contact in a time interval.
2. Use the generalization of the separating axis method for moving objects, which tends to be more complex that the original.

For simpler objects and simple motions there's also the option of solving the problem analytically. There are also various hacky solutions involving e.g. testing the object for intersection at start and end only, and using some simpler query to do an approximate test for the motion inbetween (such as a ray test or a swept-sphere test).

Quote:What I'm wondering is if [with a bisection approach] there is no collision, there are going to be many queries. How will that work in real time ??

The worst case happens in near-miss scenarios. The frequency with which such cases occur depends very much on the nature of your game. Usually you would avoid bisection if e.g. swept SAT would be sufficient for the problem at hand. However, if the object motion is sufficiently complex (non-linear translational movement, object rotating during motion, etc) then you typically end up stuck with something like bisection (and e.g. interval arithmetic to bound the objects over their motion).

Quote:And as for the separating axes method, it is more complicated than the original and probably contains more pathological cases. How feasable is it to implement these algorithms ?

The swept SAT involves marginally more code than the non-swept version. It's eminently feasible.

Personally I strongly recommend you steer clear of the bi-section method for games for quite a lot of reasons:

-> Unlike swept S.A.T. or non-predictive methods which run in almost constant time, the simulation time for bi-section methods vary quite a lot between frames since the number of iterations depends on the configuration of objects which changes each simulation update. If you're unprepared for this then you'll find your game dropping a lot of frames or you'll find the framerate changing constantly, both of which are visualy very undesirable.

-> If you do prepare for the worse simulation case to prevent the above framerate issues then you'll find it runs very slow compared to simulators based around swept or non-predictive methods since it has to cope with the possibility of having to run many collision iterations per object. (In fact bi-section is going to be slower any way you look at it since it runs several collision steps per object rather than just the one. If preparing for the worst case though the drop in performance is going to be large)

-> Bi-section is still no garauntee to catch all collisions for a capped number of iteration steps so why bother at all. Like I tried to explain in my previous post, its rare to get situations in games were objects are small and fast enough to pass through each other and for this to be unacceptable behaviour. Also when it comes to colliding small fast objects with large objects or terrain were collision detection is important, these situations can be handled with rays. Bi-section methods might catch the odd glancing hit that other methods may miss but failing to detect such narrow collisions is also generaly visually acceptable.

-> Since bi-section collision detection allows inter-penetration just like non-predictive methods you still have to do the 'hacky' seperation so its not solving this issue for you either. If the above point holds true then you'll be detecting all collisions you're actualy interested in responding too with either methods, and after seperation you'll end up with the same final result for these detected collision either way, so why bother with the more expensive and complicated method?

See what I'm getting at? Bi-section has only one advantage, the fact that it will sometimes detect glancing collision that other methods will miss but which you aren't so bothered about anyway. This is far far outweighed by all its downfalls though. If you want accuracy at the expense of cost go for a swept S.A.T. approach, else just keep it fast and simple with plane old non-predictive methods.

Hi all,

Thanks for the great replies, you've helped me understand some important aspects of the bigger picture here.

I still don't have a full understanding of what happens with stackable objects but I suspect I have enough to keep me busy for a while.

I found the physics portion of the engine to be easier to understand and implement than sorting out the myriad of techniques involved in collision detection. That might be due to my background in physics (as opposed to computational geometry etc.)


In any case, thanks for the info :)

Quote:Original post by Motorherp
Bi-section is still no garauntee to catch all collisions for a capped number of iteration steps so why bother at all. [...] See what I'm getting at? Bi-section has only one advantage, the fact that it will sometimes detect glancing collision that other methods will miss but which you aren't so bothered about anyway.

I think you got this backwards. The standard bisection approach is to repeat (with smaller motion subinterval) until you either (a) can definitely rule out a collision, or (b) reach some preset limit of number of iterations. In the latter case, because you have not been able to rule out a collision, the customary action is to assume there is a collision. This makes the method conservative with respect to reporting collisions (i.e. it will always detect a collision when there is one, but in some near-miss scenarios you will have false positives).

Hmm... I just realized that what I'm assuming is that "bisection" means that you perform a swept test for each interval, and therefore are guaranteed to detect collisions. It seems you are talking about simple repeated static testing at each sample point, and are therefore still subject to possibly missed collisions. I guess the latter is a form of bisection too, but not what I would typically call by that name. To me the latter is just sampled motion.

The accuracy of the bisection method (as I use the term) is rarely, if ever, needed for games. However, for serious simulations, where you need to simulate the actual full motion of objects and not just their linear-translational movement (as is typically done in games), bisection is often your only option.

Quote:Original post by Christer Ericson
Hmm... I just realized that what I'm assuming is that "bisection" means that you perform a swept test for each interval, and therefore are guaranteed to detect collisions. It seems you are talking about simple repeated static testing at each sample point, and are therefore still subject to possibly missed collisions.

Yes this is what I mean by bi-section testing. Sorry I just assumed this would be the case since predictive bi-section is well outside the performance requirements and needs for a game.

I'm afraid I havn't read your book so I'm sorry if I've been playing devil's advocate here a bit in maybe contradicting the advice you give. However I usualy find that the methods descibed in these types of books, although mathematicly sound, accurate, and robust, are usualy fairly impractible when it comes to actualy using them in a game with limited resources rather than a dedicated simulation. I've just been wanting to make sure that when people new to the subject are trying to create their own implementations that they dont make the same mistakes I did, ie: get so tied up with the details of making their simulation mathematicly accurate that they end up with something unusable when they have to start dealing with large game worlds, many game objects, maintaining high constant framerates, and sharing resources with graphics and AI systems etc. Its important to realise from the earliest stages in design of your physics engine that the aim is to create something as visualy pleasing as possible and that the way to acheive this is to find ways of doing things which, although might seem a bit hacky, will give the best balance between perceived accuracy and performance. I think thats the key here is the difference between perceived accuracy and actual mathematical accuracy.

I think I'm probably over bias towards one end of the scale though since I'm used to creating simulations for console games which have comparitively very limited resources which are usualy mostly taken up by the graphics since thats what goes on the back of the box and sell the games. Perhaps if you try to write your simulator in a modular fashion this will make it easier for you to experiment with different conifgurations of methods to determine what is best for your target applications and hardware.

[Edited by - Motorherp on July 5, 2006 4:28:18 AM]

Quote:Original post by Motorherp
I'm afraid I havn't read your book so I'm sorry if I've been playing devil's advocate here a bit in maybe contradicting the advice you give. However I usualy find that the methods descibed in these types of books, although mathematicly sound, accurate, and robust, are usualy fairly impractible when it comes to actualy using them in a game with limited resources rather than a dedicated simulation.

Every algorithm and data structure I cover in my book is fast enough for games, with one or two exceptions (thus the "real-time" in the title). However, it is not a book exclusively for game programmers but for anyone requiring collision detection (or spatial partitioning, etc) so also for people in VR, simulation, CAD/CAM, visualization, GIS, modeling, etc. Also, a few methods are described as a background for another method. All in all, there are some approaches described that, while you could certainly use them in a game, you typically wouldn't use them in a game. Bisection testing pretty much falls in that category (in that few games need to worry about handling rotational motion during a timestep, unlike, say, engineering simulations).

Quote:I think I'm probably over bias towards one end of the scale though since I'm used to creating simulations for console games which have comparitively very limited resources which are usualy mostly taken up by the graphics since thats what goes on the back of the box and sell the games.

Well, if anything, my bias is also that of console games because that's my day job (as you can see from my profile) and has been for a long time. Your profile doesn't say, but in that you're in the UK and implied working on Formula One in one of your posts elsewhere, I'm thinking we're actually colleagues!