Motivation
In WOF, we wanted characters to smoothly collide with the world (goal, advertisement banners, other characters, ...) and therefore 'slide' next to obstacles and not get blocked by them.
This might not be a necessity per se, since in a football game, the footballers have no business being outside the pitch, but this would be nice to have to reuse in other games, it was also something I had not done before so I wanted get my hands dirty with a more general solution then just character / character collision where bounding volumes could be used.
I decided to use the real polygon geometry of the obstacles, and not any specially prepared collision proxies, this meant the algorithm needed to handle colliding simultaneously with a number of objects / triangles and still making the best of it and sliding in the correct direction whenever it would be the right thing to do.
Results Video
A video of the nice results can be seen here:
http://www.youtube.com/watch?v=zBxg_Mp3md0
Usual Approach(es)
So as a first step of course, research, this was some time ago, so I will not post any links, you can search yourselves, but mostly people used nicely formed collision volumes such as spheres, capsules, cylinders. the advantages being per example being able to rotate in place without the collision volume changing, and therefore not causing collisions because of rotations.
This is important, because, if a character is moving, as in changing it's position, we know in which direction it moved, and we can therefore use that direction to make the collision response look credible, however for turning, things are a bit more complicated, and your usual collision tests help you by telling you how to translate volumes to resolve the collision, but not how to rotate, except if we search using bisection, which is expensive, and it seems there is no way around it for now.
This is again related to continuous collision detection (CCD), an active research topic, again linear is much easier than angular, and this of course makes sense, and has an explanation, but this is out of our scope right now, but as usual, the net is there for those who want to know more. A first search points to"Continuous Collision Detection Progress and Challenges" by 'Gino van der Bergen', who is known for his research in this area. The Bullet physics forums are probably also a good place for this topic, among many others.
Chosen Solution
Now our math library already had collision tests for many primitives, almost all a game would ever need, except capsules. I did not like the idea of using spheres because they would be too big, and we wanted the characters to be able to come very close before colliding. Of course, the spheres could be made smaller, which then has other disadvantages, basically, the sphere did not fit the real volume closely enough for my taste, (there are many collision detection tutorials / papers that discuss fitting properties of collision shapes). At the time, I chose to use Axis Aligned bounding boxes that do not change their volume when the footballers changes directions, additionally, OBB were being used for accelerating collision detection between the ball and the footballer's limbs using the physics engine, this means we have two types of bounding volumes for 2 different purposes.
Capsules would have been an equally good choice, or even a better one. But the 'technique' I used to resolve collision applies to both.
Plan of Attack
So what do we really want to achieve? we want the character to slide along obstacles and not be blocked by them when it makes sense.
When does it make sense? it makes sense when the obstacle does not directly oppose the direction the character is moving. so except if the obstacle directly opposes the movement direction, there is possibility to slide, this is the basic idea. Of course, we have more than one obstacle, and since we want to use the raw polygons of the obstacles, we will have more than 1 triangle per obstacle, additionally in WOF, obstacles can be volumes, so in the end, we will have a number of triangles and volumes to check against, and we will need to find a sliding direction giving the original movement direction and the triangles and volumes.
There is more than one way to solve this, but I will describe the final solution (and I think in WOF's context the best solution) that I came up with.
'Algorithm'
For all triangles and volumes, I used a swept volume collision detection to gather all the contact normals between the moving volume and the world's objects, for triangles I used only the face normals, this prevents the character from getting stuck because of slight penetrations of polygonal objects, as for cases where we really have a collision with a triangle edge, this works as well, assuming all triangles in an object are connected, whenever we have contact with an edge we also have contact with 2 or more triangle faces that meet at that edge, so we can get away with using triangle face normals and no edges (or points) assuming all triangles are connected, this way we happily slide along polygonal objects even if we hit edges because of slight penetrations and we will still be correct when we hit real edges because in that case more than 1 face normal will be taken into account. (some pictures at this point would be nice, but maybe I will do then later and update this post).
So as i said, I gather all contact normals as explained above, then I use quadratic programming to find a direction that satisfies the following constraint: has a non-zero negative dot product with all the gathered normals, or in other words a direction along which we can move freely without penetrating all current contacting obstacles. I take the resulting direction and if it is zero or if it has the same direction as the movement vector (solvedDir dot moveDir > 0), I block the moving object, sending it to where it was at the last step, I use a fixed step approach to physics, thus making this always look ok, otherwise I use the direction obtained from the solution as the new movement direction, optionally projecting the current movement translation onto it (thus reducing the movement speed), the new direction is not used 'after' the current movement is applied, the contacts are gathered during a 'check potential contacts using the current direction', so this means the new direction (translation) is used instead of the original direction.
Luckily, we have a Convex Quadraitc Prorgramming Problem at hand, this means it can be solved in reasonable time, I used the QuadProg++ library, (which uses the Goldfarb-Idnani dual method), but I modified it to optimize it's memory allocation behaviour
There are some more details to take into consideration, because in WOF per example, in some modes (tackling per example), we allow footballers to penetrate each other, so we need filters to specify which triangles / objects to use for collision detection, there are also issues about how to make swept collision detection behave nicely in all problematic cases, all those issues are solved and work well in WOF as one can see in the video, but the point here was using quadratic programming to solve for the 'sliding direction'. As for performance, there were no problems until now, I will spare you the profiling numbers though, they are only relevant for WOF.
No comments:
Post a Comment