Collision detection on polygon level: yay or nay
Author
I have been thinking about polygon level collision detection today and have found a number of tutorials/codebases for it, but I was wondering if it really should be used, as it looks quite calculation intensive. Ofcourse, before you go down to polygonal collision detection one should first do a bounding sphere detection, but still, if you have quite intensive MD2 models this might (will!) have a big impact.
Another thing:
How does one do collision detection on a terrain? Is sphere->plane detection the best solution here, or is poly->poly detection the best solution?
For non-terrain models, you could try BSP for collision detection see the MDK2 article in Gamasutra. That gives you polygon test and it relatively quick.
(After intial bounding sphere tests) I use a set of convex meshes which allows be to tune the volume of a body without needing the excessive polygon details which modern graphics demand. Of course this extra geometry costs me more memory (and more transformations).
The convex meshes are very low detail (well they can be as high as you want), but using them rather than a oriented boundary box saves you having to use millions of excess tests cause by fitting a set of boxes to something that is simple but not cube shaped like (ie cylinders or spheres)
I''ve yet to find a good method to uniformly deal with all types of collision (in particular the object vs terrain).The best I could come up with it to dynamically create collision meshes for the terrain as and when they are needed.
Surely you can''t do sphere->plane tests without then checking if the sphere intersects the terrains polygon.
(After intial bounding sphere tests) I use a set of convex meshes which allows be to tune the volume of a body without needing the excessive polygon details which modern graphics demand. Of course this extra geometry costs me more memory (and more transformations).
The convex meshes are very low detail (well they can be as high as you want), but using them rather than a oriented boundary box saves you having to use millions of excess tests cause by fitting a set of boxes to something that is simple but not cube shaped like (ie cylinders or spheres)
I''ve yet to find a good method to uniformly deal with all types of collision (in particular the object vs terrain).The best I could come up with it to dynamically create collision meshes for the terrain as and when they are needed.
Surely you can''t do sphere->plane tests without then checking if the sphere intersects the terrains polygon.
Although I''m prticularly interested in exact collision detection, for most purposes some kind of bounding box/sphere technique will do. WRT object-terrain collisions that is tricky. I haven''t researched this yet for my terrain engine, but I''d guess a first step would be to narrow the possible section of the terrain which could be involved down as much as possible. If the terrain is a 2-d array of points this it is trivial to find a bounding rectangle of vertices such that the object never went outside it. Typically I''d expect this to be maybe 10x10 - 30x30 depending on how big your object is, how high the terrain resolution is etc. Then I''d use a bounding box/sphere for the object and maybe test that on each polygon, with the dimensions here thats 100-1000 polys X2 as a quad has two triangles so 200-2000 polygons. I don''t know whether 2000 intersections is a lot or not, but you could also look at the normals to the polygons and compare it to the object''s velocity - if the collision would involve the object coming from inside the poly (i.e appearing through the terrain) then you should have caught it going into the terrain in the first place. Hence you can lower the number of polys to test dramatically.
Just a top-of-my-head approach, what does anyone think?
Read about my game, project #1
NEW (18th December)2 new screenshots, one from the engine and one from the level editor
John 3:16
Just a top-of-my-head approach, what does anyone think?
Read about my game, project #1
NEW (18th December)2 new screenshots, one from the engine and one from the level editor
John 3:16
A quadtree would dramatically reduce the number of polygons that you would test in a terrain, similar to how d000hg describes it. You can find the smallest node that the object is in and test only the polygons in that node, which should be small compared to the entire terrain. I actually use an octree for mine, which basically has the same principle behind it but you can apply it to other 3D levels/worlds/whatever.
As for the collisions themselves, I myself use bounding sphere->poly detection. I''d think that since only the bottom polygons of thr model would ever touch the terrain, checking every polygon in the MD2 model would be unnecssary.
''There''s something out there....something stupid...''
''I think I''m going to be ill. Is that a problem for you?''
''[You] overestimate my conscience by assuming that I have one.''
- Daria
DirectInput8 with the Keyboard , DirectInput8 with the Mouse , Using DirectX Audio 8
As for the collisions themselves, I myself use bounding sphere->poly detection. I''d think that since only the bottom polygons of thr model would ever touch the terrain, checking every polygon in the MD2 model would be unnecssary.
''There''s something out there....something stupid...''
''I think I''m going to be ill. Is that a problem for you?''
''[You] overestimate my conscience by assuming that I have one.''
- Daria
DirectInput8 with the Keyboard , DirectInput8 with the Mouse , Using DirectX Audio 8
If you are interested in exacting collision detection, detecting a hit is the easy part. Determining exactly when is the computationally-intensive part.
It''s simple to do CD with sphere''s, cylinders, and capsules (which are two half-sphere''s & a cylinder). The hard part is what happens while the volumes move through time. You have to consider the volume they swipe-out and do hit detection on that. A moving sphere (assuming linear motion) creates a capsule, which is also easy to test. If you do not assume linear motion between physics frames, the problem becomes considerably more complex with a minimal increase in precision.
The main problem with triangle-level CD, is that there''s so many of them to test. If you break the models into heirarchies as well, it''s not so bad.
"3D Game Engine Design" by David Eberly has several chapters on various collision detection shapes. From spheres to triangles, and static-static to dynamic-dynamic (e.g. a model to ground is dynamic-static, the model moves but the ground doesn''t, so there''s an optimization over the dynamic-dynamic case).
It''s simple to do CD with sphere''s, cylinders, and capsules (which are two half-sphere''s & a cylinder). The hard part is what happens while the volumes move through time. You have to consider the volume they swipe-out and do hit detection on that. A moving sphere (assuming linear motion) creates a capsule, which is also easy to test. If you do not assume linear motion between physics frames, the problem becomes considerably more complex with a minimal increase in precision.
The main problem with triangle-level CD, is that there''s so many of them to test. If you break the models into heirarchies as well, it''s not so bad.
"3D Game Engine Design" by David Eberly has several chapters on various collision detection shapes. From spheres to triangles, and static-static to dynamic-dynamic (e.g. a model to ground is dynamic-static, the model moves but the ground doesn''t, so there''s an optimization over the dynamic-dynamic case).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
