Hello,
I've built my own 3D engine in AS3, and before making my first game, I need to develop a fast, solid per poly collision routine.
I have the broadphase working fine, as well as object to object collisions, it's just the per polygon collisions I need to do now.
I have Nettle's and Fauerby's papers, plus a couple of others I've found online.
I hear some criticisms of Nettle's method, so I'm assuming that Fauerby's is supposedly better (although on the demo supplied with the paper, I notice that although the routine generally works fine, you get stuck frequently).
Also, more so than just the vector maths involved in finding the intersection point (which I've implemented in a very basic way, just with the gravity vector, one poly at a time), I'm after a reference for the whole process, including efficient sorting of the potentially collidable polys, plus solid collision response with multiple polys etc.
Which paper or reference do you find to be the best for an all round solid and efficient routine?
Cheers,
RumbleSushi
Best reference for 3D Sphere to Triangle collisions?
Author
I'm surprised at the lack of replies, surely per poly collision detection is a very common part of developing a 3D engine? And not something that is particularly easy to get perfect either.
Quote:I'm surprised at the lack of replies, surely per poly collision detection is a very common part of developing a 3D engine? And not something that is particularly easy to get perfect either.That's probably why there haven't been any responses thus far; as you state, it's not a problem that's easily solved, and references that cover all of the details involved, if there are any, are probably few and far between.
I don't know what constraints you're working under, but my general recommendation would be to use an existing physics engine for this if at all possible.
If that's not possible, you might try searching the forum archives for terms such as 'sliding plane', 'sphere collision', 'ellipsoid collision', and so on, as the topic has been discussed quite a bit in the past.
The Fauerby paper is sound, I think, but I don't recall if or how it deals with collisions with multiple planes (hence the 'getting stuck' problems you referred to). At one point I coded up a version of that algorithm that dealt with these issues, but that was a long time ago and I couldn't tell you exactly what was involved. I can say in general though that if the sphere was found to collide with multiple connected triangles in the same step, the velocity vector was constrained so as to be parallel to the 'crease' vector between the two triangles (if there were only two), or set to zero (e.g. if the object was in a corner).
Another general approach is to represent the world geometry using a BSP tree (this approach is used by games like Quake, MDK, etc.). At one point there was an article floating around online about collision detection in the Quake games, but I can't remember if it addressed the issue of collisions with multiple surfaces.
Author
Quote:Original post by jykQuote:I'm surprised at the lack of replies, surely per poly collision detection is a very common part of developing a 3D engine? And not something that is particularly easy to get perfect either.That's probably why there haven't been any responses thus far; as you state, it's not a problem that's easily solved, and references that cover all of the details involved, if there are any, are probably few and far between.
I don't know what constraints you're working under, but my general recommendation would be to use an existing physics engine for this if at all possible.
If that's not possible, you might try searching the forum archives for terms such as 'sliding plane', 'sphere collision', 'ellipsoid collision', and so on, as the topic has been discussed quite a bit in the past.
The Fauerby paper is sound, I think, but I don't recall if or how it deals with collisions with multiple planes (hence the 'getting stuck' problems you referred to). At one point I coded up a version of that algorithm that dealt with these issues, but that was a long time ago and I couldn't tell you exactly what was involved. I can say in general though that if the sphere was found to collide with multiple connected triangles in the same step, the velocity vector was constrained so as to be parallel to the 'crease' vector between the two triangles (if there were only two), or set to zero (e.g. if the object was in a corner).
Another general approach is to represent the world geometry using a BSP tree (this approach is used by games like Quake, MDK, etc.). At one point there was an article floating around online about collision detection in the Quake games, but I can't remember if it addressed the issue of collisions with multiple surfaces.
Hey jyk, thanks for the reply.
As I've developed a browser based software renderer obviously performance is paramount, so I definitely don't want to use a public physics engine, they are far too slow. I've managed to get my 3D engine running faster than every other 3D engine in Flash by doing everything from scratch, and taking a dilligent speed first approach.
Luckily I've got the collision detection working now ;)
Just spheres to triangles so far, I'll add Ellipsoid collision later.
I'm not using a BSP tree, as I'm going to develop racing games and open world games, BSP trees are best suited to interiors and also moving objects have a big impact on performance with a BSP tree, having to rebuild parts of the tree etc for moving objects.
I'm actually just using a grid for the collision broadphase (for moving objects AND the environment). It's incredibly fast as I don't iterate through the grid at all, all the adding and removing is done by the objects themselves.
Here's an example of it in action with moving objects, press Space to pan the camera out and S to add a ship - http://rumblesushi.com/grid.html
I'm handling multiple collisions fine, just by sorting the array of potential collision polygons by facing distance, then using the remaining velocity as the new displacement to recurse through the others, up to 6 times.
By the way I find Fauerby and Ericson's papers to be the most useful.
Cheers,
RumbleSushi
If you don't mind paying real money for a physical copy, then I've found 'Real Time Collision Detection' by Christer Ericson to be a fantastic resource.
This is the companion website for the book: http://realtimecollisiondetection.net/
This is the companion website for the book: http://realtimecollisiondetection.net/
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
