Haha, what a waste (collision detection)
I'm sure most of you guys have probably been through something similar at some point time time while developing your first engine:
Anyway, for the past few days I was trying to write down on paper a formal specification for how collision detection would be handled in my game. I covered one test case after another, constantly honing the algorithms accuracy and efficiency. Suddenly I noticed a test case I missed, and for the life of me could not wrap my brain around a solution.
Finally I gave up (about a half hour ago ) and just wrote in a section about the standard "binary search" type algorithm that just subdivides the distance between the player's old and new positions a few times until there are no longer any collisions. With an effective culling algorithm the difference in execution time will be negligible, plus it automatically solves all the problems I was expecting with the old algorithm requiring the floats to be more precise than they are (it called for a lot of fudging the numbers by 0.0001, which is incredibly ugly and prone to errors).
Now I just need to rewrite the relevant parts of the algorithm to work with a subdivide function and I should be good to go... hopefully.
Anyway, for the past few days I was trying to write down on paper a formal specification for how collision detection would be handled in my game. I covered one test case after another, constantly honing the algorithms accuracy and efficiency. Suddenly I noticed a test case I missed, and for the life of me could not wrap my brain around a solution.
Finally I gave up (about a half hour ago ) and just wrote in a section about the standard "binary search" type algorithm that just subdivides the distance between the player's old and new positions a few times until there are no longer any collisions. With an effective culling algorithm the difference in execution time will be negligible, plus it automatically solves all the problems I was expecting with the old algorithm requiring the floats to be more precise than they are (it called for a lot of fudging the numbers by 0.0001, which is incredibly ugly and prone to errors).
Now I just need to rewrite the relevant parts of the algorithm to work with a subdivide function and I should be good to go... hopefully.
Heh, I just had another "duh" moment, although these things are never really obvious until after the fact.
I still had three nagging issues related to the collision detection, all of which were notsocoincidentally centered on the cylindershaped bounding box I was designing the system around. The main issue is that when a collision takes place, I needed to generate the plane tangent to the surface of the bounding box, but the right angles at the top and bottom of the cylinder made this mathematically impossible.
After toying with a few ideas, I realized using an ellipsoid make a LOT more sense in terms of computation, plus it fixes all three issues in one fell swoop. I'm finally feeling confident about being able to cobble this thing together.
I still had three nagging issues related to the collision detection, all of which were notsocoincidentally centered on the cylindershaped bounding box I was designing the system around. The main issue is that when a collision takes place, I needed to generate the plane tangent to the surface of the bounding box, but the right angles at the top and bottom of the cylinder made this mathematically impossible.
After toying with a few ideas, I realized using an ellipsoid make a LOT more sense in terms of computation, plus it fixes all three issues in one fell swoop. I'm finally feeling confident about being able to cobble this thing together.
Cool! So what kind of game are you building with it?
(If this gets here twice, sorry... I think some error ate my first post, or if it gets here double then it's the noobfilter).
Cylinder is pretty complex collision primitive indeed. I would recommend a capsule instead of ellipsoid. If sphere is point with radius, the capsule is line segment with radius. It is really easy to check capsulecapsule and capsule triangle collisions. I have tried ellipsoids too, but since you need nonuniform scaling at some point sometimes it is not as straight forward. Especially the collision response part.
I one of my recent prototype projects' I used capsules againts trimesh collision detection. It was simple to implement. For the collision response I first tried the usual bounce vector calculation but that always failed in some cases. Could have been my epsilons and floating point precision, since the problems usually occured while sliding really slowly.
I finally settled to verlet integration. The character was simulated simply using one particle anyway. The cool thing about verlet integration is that you can just push the collider out of the object, and it will slide automatically. It also works nicely if the objects in the scene are moving.
I did not use binary search, but moved the capsule in small bits if the movement delta got big. I think I used 0.45*r as maximum step size. Worked really well, but it can miss a sharp corner (I never observed this problem).
I recommend Christer Ericson's book Realtime Collision detection. It helped me a lot. After reading that book I after implementing a simple AABB tree to speed up the collision i noticed that collision detection is not so much about calculating the collisions, but trying to avoid that calculation For example my brute force code took around 7ms at start most time spent in tricapsule tests, and the optimised version took less than 1ms 90% time spent on traversing the tree.
Cylinder is pretty complex collision primitive indeed. I would recommend a capsule instead of ellipsoid. If sphere is point with radius, the capsule is line segment with radius. It is really easy to check capsulecapsule and capsule triangle collisions. I have tried ellipsoids too, but since you need nonuniform scaling at some point sometimes it is not as straight forward. Especially the collision response part.
I one of my recent prototype projects' I used capsules againts trimesh collision detection. It was simple to implement. For the collision response I first tried the usual bounce vector calculation but that always failed in some cases. Could have been my epsilons and floating point precision, since the problems usually occured while sliding really slowly.
I finally settled to verlet integration. The character was simulated simply using one particle anyway. The cool thing about verlet integration is that you can just push the collider out of the object, and it will slide automatically. It also works nicely if the objects in the scene are moving.
I did not use binary search, but moved the capsule in small bits if the movement delta got big. I think I used 0.45*r as maximum step size. Worked really well, but it can miss a sharp corner (I never observed this problem).
I recommend Christer Ericson's book Realtime Collision detection. It helped me a lot. After reading that book I after implementing a simple AABB tree to speed up the collision i noticed that collision detection is not so much about calculating the collisions, but trying to avoid that calculation For example my brute force code took around 7ms at start most time spent in tricapsule tests, and the optimised version took less than 1ms 90% time spent on traversing the tree.
I chose an ellipsoid after working through some other designs and realizing that a simple matrix transform can turn the ellipsoid into a unit sphere, giving the equations some nice simplifications. I already worked through all the math for the collision detection and response, and it should work great. I don't even need a binary search for the ellipsis anymore, since I was planning that as a stopgap measures for the problems associated with the cylinder collision response.
codemattic Wrote:Cool! So what kind of game are you building with it?Platformer. The game engine originally started out very similar to Ninja Gaiden Black, but the more I work out the gameplay details, the more the engine starts to play like Donkey Kong 64. It turns out the Ninja Gaiden engine is perfect for handtohand combat but not so good at general platforming. The engine will still have elements from NG, such as wall runs and wall jumps, but most of the engine will use elements from DK's gameplay style.
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
Optimize the collision detection  alaslipknot  1  5,153 
May 12, 2013 08:02 PM Last Post: SethWillits 

Collision detection tutorial  ThemsAllTook  7  26,333 
Nov 5, 2011 05:20 PM Last Post: SethWillits 

Help with Collision Detection..(i'm almost there)  carmine  1  6,100 
Jun 29, 2011 12:33 PM Last Post: ThemsAllTook 

Time Delta, collision detection  mk12  19  20,998 
Sep 8, 2010 06:40 PM Last Post: AnotherJake 

Collision detection for pinball game  johncmurphy  0  5,758 
Sep 6, 2009 02:46 PM Last Post: johncmurphy 