Jump to content
  • Advertisement
Sign in to follow this  

Collsion response involving multiple polygon collsions

This topic is 679 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been working on adding collision detection to my directx 11 engine. Its designed for a first person game, and takes place largely outdoors, so the main things the player will collide with are organic meshes like trees, rocks, etc.


I'm  using the DirectXCollision library for the actual collisions (mostly sphere-triangle intersections), so I've go the detections part working fine. The problem then is handling the collision response once one or more collisions have been detected. I should note that that sometimes what works for simple flat walls doesn't always work well when you are dealing with weird organic meshes. I mitigate this somewhat by using simplified collision meshes.


The main issue I'm dealing with now is player movement and collision response. Right now I'm using a simple bounding sphere, and do a triangle intersect test on all objects nearby. So sometimes you will get multiple collsions at the same time. Everything I try seems to work in "most" cases... but sometimes you can get sucked around, or bounced or end up inside a mesh or whatnot...


Here is my basic method so far:


1) loop through all nearby objects and do a sphere-box test to see there is a possible collision. Then for each potential object, I loop through each triangle and store each collision in an array, along with the normal of the triangle I collide with.


2) I can then calculate the response for each collision in another loop. I do something like this:


normal = XMVector3Normalize(normal);
direction = XMVector3Normalize(playerPosition - temppos); //where playerPosition is current pos, and temppos is where we would end if there is no collision
invNormal = -normal;
invNormal = invNormal * XMVector3Length(direction * normal);
wallDir = direction - invNormal;
playerPosition +=  wallDir;
I do this for each collision that occurs, and hope that the player ends up in a decent place at the end....usually it works, but not always.
This code basically I guess is trying to find the distance to "knock back" player based on the length of movement direction * the normal
It sort of works, but i'm not sure I've got it quite right...I am wondering is the vectors are actually the right ones...
Sorry if this a long and meandering question, but its' a complex problem... the two main questions  are:
1) is it valid to calculate in sequence each response for each collision?
2) is my collision response code really right? Could it be better?










Share this post

Link to post
Share on other sites

Basically you change your collision detection to a search in time method - this means, you take your delta position (current position - last position) and find a percentage when the player collides - this is basically a line segment vs polygon test raycast, which can be simplified a lot by converting it into a minkowski sum to change it to a point vs polygon test.

You repeat that search until you either have no more collisions to check or your percentage drops to 0 - of course you initialize your current percentage at start of iteration to one. This iteration should be limited by some amount, you mostly have 8 collisions at max at the same time or something... After that is is simply, removing the percentage of the delta position from the current position and decrease the current percentage.


But using just the position you cannot glide along the wall, which you may want.

To support gliding you require a velocity/speed for your player and remove all speed against the collision normal (No restitution impulse).

This can be combined with the search in time technique. Done.


Btw. this works great if you dont want to use a generic physics system ;)

Share this post

Link to post
Share on other sites

There are a few thing you need to be aware off. From what I gather, you're not doing continuous collision detection, which is detecting collision along the sphere's path and solving at what time it starts intersecting. This means that you can pass objects if you move fast enough (imagine starting position before a wall and an ending position behind it, you'll never detect the wall). This is called tunneling. To combat this without doing continuous collision detection, you can chop up your movement into smaller segments so that you're less likely to miss an intersection. As for responding to intersection, you'll probably want to push out of the triangle with the largest penetration first and then do another detection round, only if when you're clear from intersections do you allow to move further (e.g. sliding along the wall). If you keep intersecting after x iterations, the move is invalid and you position the sphere at the last valid position.

Share this post

Link to post
Share on other sites

After some fiddling I think I have sort of got something like what you are guys are talking about...basically I set up a loop where I lerp between end position and start position and check the collision subset at each point, and finally when there are no more collisions or we reach startpos, then doing some bounce back...so now we basically don't go  into meshes anymore, but I'm having a hard time figuring out the "gliding" part..


"To support gliding you require a velocity/speed for your player and remove all speed against the collision normal (No restitution impulse)."

can you clarify how you get this? I assume you mean direction* distance to travel ... but I'm not sure of the math to do what you are saying.. I'm not exactly too swift in this department though I am trying to learn...


something like this sort of works...playerPosition =newPos+( direction - normal)*2.0f;

Edited by Matt_Aufderheide

Share this post

Link to post
Share on other sites

Basically the distance that you'd travel without hitting any obstructions is the maximum amount of distance you're allowed to travel. Say you have the vectors start and velocity, your destination is end = start + velocity, the direction your moving in is direction = normalize(velocity) and the maximum travel distance is magnitude(velocity). Because you're detecting in intervals your intermediate destination becomes:

intermediate = start + direction * min(remainingDistance, 0.2)

remainingDistance is initialized as magnitude(velocity) and the 0.2 is just an arbitrary number for the maximum distance you can move before detecting collision. Every time you move the player to a new valid location, you subtract the moved distance from remainingDistance (make sure to not go negative), when remainingDistance hits 0 or you've reached the maximum amount of iterations for finding a valid position you're done.


Whenever you collide you change the direction to move along the intersected plane. Here's an archived article on sliding sphere collision which explains this in much more detail, it describes the continuous collision detection case, but the idea for the response is the same. Note however that the sphere intersection point calculation in that article is flawed. There are follow up articles that try and fix some of the flaws, but the proposed solutions are flawed as well, you can read some discussion on that here. If you're interested in all the different intricacies and robust collision detection I can highly recommend Christer Ericson's Real-Time Collision Detection. Yes, collision detection can be hard :<.


That might be overkill for you and you might not need perfect collision detection or exact sliding so it's okay if you cut some corners (pun intended :ph34r:), but I'm just putting it out there in case you or anyone else is interested.

Share this post

Link to post
Share on other sites

Thanks a lot for the responses! I'm getting it work pretty well right now with your help.. I also realized one of the issues i was having is that I wasnt transforming my normals properly, so there was some wierdness happening...(one of the cords needed to be flipped)


Basically I am trying to do it as simply as possible... so here is what I'm am doing case anyone wants to know:


1) first get height above the "floor" by casting some rays downward and apply gravity (if you are below the floor we get negative gravity) and get the potential end position

2) then start with maximum allowed distance and work backwards, test the collision subset every time.. stop when you  reach the end or there are no more collisions....then glide along the normal.. seems to be working ok for even some weird meshes with lots of concavities...


obviously you need to have some decent scene management to do this kind of triangle testing and not lose too many frames...

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!