Swept Sphere Collision?
by Richard Wilson · in Torque Game Engine · 09/01/2005 (5:43 pm) · 12 replies
Recently I've been charged with adding line swept sphere collision to a certain portion of Torque. I know this has been done on a number of occasions and in various games, such as Marble Blast. I'm fairly certain the troubles I've been having stem more from getting the geometry to the test than the actual swept sphere test itself. I thought I'd share a resource and inquire about others.
Jorrit Rouwe wrote an article on swept sphere collision and kindly provides sources FREE to anyone wishing to borrow them. Has anyone else borrowed this and gotten it working? http://www.three14.demon.nl/
I'd be very glad to hear of other code resources such as this. I'm well aware of MOST of the various collision systems available and they are far too 'heavy' for what I need at the moment.
For anyone who has already put something like this into the engine, I'd be glad to hear your pointers on how you did it, or various issues you had doing so. Thus far I've been using buildPolyList() on intersecting objects. I've noticed others doing similar things have gone this route, though I'm not convinced it's the best way yet.
So far, I've managed some very nice terrain collisions and bouncing off statics. However, I also have issues with collisions 'missing' certain areas of terrain.
Jorrit Rouwe wrote an article on swept sphere collision and kindly provides sources FREE to anyone wishing to borrow them. Has anyone else borrowed this and gotten it working? http://www.three14.demon.nl/
I'd be very glad to hear of other code resources such as this. I'm well aware of MOST of the various collision systems available and they are far too 'heavy' for what I need at the moment.
For anyone who has already put something like this into the engine, I'd be glad to hear your pointers on how you did it, or various issues you had doing so. Thus far I've been using buildPolyList() on intersecting objects. I've noticed others doing similar things have gone this route, though I'm not convinced it's the best way yet.
So far, I've managed some very nice terrain collisions and bouncing off statics. However, I also have issues with collisions 'missing' certain areas of terrain.
About the author
Recent Threads
#2
I'd considered going the route of convexes, but I'm in need of easily getting back essentially the visible geometry as I'd like to not be confined to convex polytopes. I've not looked at it enough to rule out the possability of having such information returned that route ... just knowing the main mechanism in Torque was gjk and convexes, kinda led me to stay away from that.
I seem to have it roughly working at the moment. Battling some 'Invalid query box' errors and issues with the sphere collisions getting 'stuck' to the poly's. My main concern is that either the sample code I'm using isn't numerically robust enough, or the way I've used it has led to such issues.
I've seen CollisionTest, but I might just have to go look it over again since you mention it. Any other suggestions would be greatly appreciated.
09/02/2005 (5:59 pm)
Specifically I've called getContainer()->findObjects(...) with a callback which does the object->buildPolyList(...).I'd considered going the route of convexes, but I'm in need of easily getting back essentially the visible geometry as I'd like to not be confined to convex polytopes. I've not looked at it enough to rule out the possability of having such information returned that route ... just knowing the main mechanism in Torque was gjk and convexes, kinda led me to stay away from that.
I seem to have it roughly working at the moment. Battling some 'Invalid query box' errors and issues with the sphere collisions getting 'stuck' to the poly's. My main concern is that either the sample code I'm using isn't numerically robust enough, or the way I've used it has led to such issues.
I've seen CollisionTest, but I might just have to go look it over again since you mention it. Any other suggestions would be greatly appreciated.
#3
Trust me on this; I've implemented a couple of poly soup systems in Torque. :)
The player is a good example here, as it treats everything as poly soup even though it uses the convex system.
09/03/2005 (6:23 pm)
The convex code can also be viewed as an indirect way of getting accurate collision meshes, since you need only grab the convexes, then call getPolyList from it. object->buildPolyList only gives geometry suitable for rendering shadows against, which can potentially be very very bad for the purposes of collision.Trust me on this; I've implemented a couple of poly soup systems in Torque. :)
The player is a good example here, as it treats everything as poly soup even though it uses the convex system.
#4
We have just about wrapped up our implementation of swept sphere collision. In the process we tried both Jorrit Rouwe's sample as well as Igor Kravtchenko's sample of very similar code. We got both working about equivalently though we've yet to really profile them. Neither was too difficult to integrate, as they both boiled down to a single function call treated similarly once appropriate geometry was retrieved.
For reference, Igor's sample is available over at flipcode http://www.flipcode.com/cgi-bin/fcarticles.cgi?show=64175
The only real challenge has been with getting geometry for the swept sphere tests. In particular most of the time we would like exactly the geometry that is rendered. So far, I've not noticed any direct way of doing this. I've plenty more comments / questions related to this work, though better suited to a different thread.
09/07/2005 (3:21 pm)
Thanks for your comments Ben, I appreciate them. Though, my task isn't quite over and thought I'd continue to share a bit so if anyone else want's to mess with this.We have just about wrapped up our implementation of swept sphere collision. In the process we tried both Jorrit Rouwe's sample as well as Igor Kravtchenko's sample of very similar code. We got both working about equivalently though we've yet to really profile them. Neither was too difficult to integrate, as they both boiled down to a single function call treated similarly once appropriate geometry was retrieved.
For reference, Igor's sample is available over at flipcode http://www.flipcode.com/cgi-bin/fcarticles.cgi?show=64175
The only real challenge has been with getting geometry for the swept sphere tests. In particular most of the time we would like exactly the geometry that is rendered. So far, I've not noticed any direct way of doing this. I've plenty more comments / questions related to this work, though better suited to a different thread.
#5
If you're using either of the swept sphere resources listed above, or even another solution where you need to get collision geometry fed into your solution then you might be interested in a related discussion continued at: www.garagegames.com/mg/forums/result.thread.php?qt=34262
09/07/2005 (5:13 pm)
Though no longer specifically about swept sphere, there are related issues people may or may not be interested in.If you're using either of the swept sphere resources listed above, or even another solution where you need to get collision geometry fed into your solution then you might be interested in a related discussion continued at: www.garagegames.com/mg/forums/result.thread.php?qt=34262
#6
09/07/2005 (10:14 pm)
It's worth noting that Marble Blast uses swept sphere collision, the player uses swept box collision, and both do just fine against the existing interfaces. Not to say that that's the best way, but it does work.
#7
09/08/2005 (9:30 am)
Yes, and if your requirements pair well with either then conforming would be great. Though collision against a .dts which is to have cavities you are to interact with will not function properly if you follow that path. (At least not without modifications as discussed in the linked to thread) 
#8
09/08/2005 (3:39 pm)
Both the Marble and the Player code collide just fine against concave collision meshes. The only implication to having a non-convex collision mesh is that raycasts won't work against them (the dts raycast code assumes the mesh is convex). This is fairly trivial to fix. It is important to note that the vehicle collision is gjk-based and *does* require you to have convex collision meshes.
#9
09/08/2005 (4:20 pm)
Sorry, but what's "gjk"?
#10
Pardon the 'nit picking' but just in case others miss construe the implications...
I don't believe Marble Blast used concave meshes at all. From their description they used entirely .dif objects, which from my understanding still use convex hulls. Granted, you can create concave geometry (like loop-the-loops) yet due to the way it's handled it's broken down for you already. Thus making it an excellent way to avoid the entire pain myself and a few others before me have had to deal with.
If we could use .dif's (interiors) for our collision needs, as we indeed have a mock up of, then the task is essentially done. However, being pretty much forced to .dts (TSStatic etc.) then you may very well have more work left in front of you. See [ulr]http://www.garagegames.com/mg/forums/result.thread.php?qt=34262[/url] for details.
Please correct me If I'm wrong Matt, I know you've been dealing with collision stuff far longer than myself.
09/08/2005 (4:20 pm)
Player will definitely interact properly if you simply have a concave collision mesh on an object.Pardon the 'nit picking' but just in case others miss construe the implications...
I don't believe Marble Blast used concave meshes at all. From their description they used entirely .dif objects, which from my understanding still use convex hulls. Granted, you can create concave geometry (like loop-the-loops) yet due to the way it's handled it's broken down for you already. Thus making it an excellent way to avoid the entire pain myself and a few others before me have had to deal with.
If we could use .dif's (interiors) for our collision needs, as we indeed have a mock up of, then the task is essentially done. However, being pretty much forced to .dts (TSStatic etc.) then you may very well have more work left in front of you. See [ulr]http://www.garagegames.com/mg/forums/result.thread.php?qt=34262[/url] for details.
Please correct me If I'm wrong Matt, I know you've been dealing with collision stuff far longer than myself.
#11
It's an algorithm for determining the distance between convex objects. This is very useful in detecting collision and is the primary mechanism in Torque.
Explore google for links to more info: www.google.com/search?hl=en&q=gjk+collision+algorithm&spell=1
09/08/2005 (4:31 pm)
Gjk stands for Gilbert-Johnson-Keerthi, the three originators of the algorithm.It's an algorithm for determining the distance between convex objects. This is very useful in detecting collision and is the primary mechanism in Torque.
Explore google for links to more info: www.google.com/search?hl=en&q=gjk+collision+algorithm&spell=1
#12
09/08/2005 (4:44 pm)
True, most of the art for Marble Blast is convex dif's (but not all of it). I have also used the same swept sphere collision code from it in BoomBall to interact with concave meshes. 
Associate Kyle Carter
Using buildPolyList on intersecting Convexes is in general the best way to go about this in Torque. If you cache the convexes it's nice and fast.
CollisionTest is a wildly useful bit of code for this sort of work; look in game/collisionTest.cc.