If anyone could help, I would greatly appreciate it!
2D AABB to moving circle collision detection and response
Author
I am currently attempting to write AABB to moving circle collision detection and response in 2D. There is a single moving circle, which most likely has a changing velocity each update, and there are multiple AABBs which the circle is not allowed to move through.
The code checks for collision between the moving circle and all of the AABBs that surround it (up to 8). If a collision is detected, the time of collision is calculated using an extended AABB with rounded corners and a ray from the circle's starting position to where it ends up. The circle is moved along the ray to the time of intersection.
However, this collision detection system is flawed because the circle is now at the time of intersection which means that it is still intersecting the AABB. So the circle is moved back by an additional 1 pixel (not circular, meaning the magnitude of the vector the circle is additionally moved back by might not be 1). Even this system does not work correctly though.
If the circle's movement vector is parallel to an edge/face (this is 2D, so I am unsure which term to use) of the AABB, the circle could be within 1 pixel of the AABB and not be pushed back.
To make the response code a bit cleaner, the movement vector that is used is extended by 1 block pixel. This way the "additional" move-back is not required as it is part of being pushed to the point of intersection. This does not solve the previously mention problem however.
Here is a graph showing the problem:
If anyone could help, I would greatly appreciate it!
If anyone could help, I would greatly appreciate it!
Author
After further research, there seems to be 2 options for handling the collision detection and response.
The first option is to consider any intersection as a collision which needs to be resolved. This is the option I described in my previous post. This option requires the circle to be completely pushed out of the AABB, which I was doing by pushing it back by an additional pixel. This causes the problem I described earlier; you need to somehow keep a 1 pixel thick border around the AABB without actually making it part of the AABB.
The second option is to consider intersection at "time 0" to be non-intersecting, and simply resting on each other's borders. However, this means that the circle and the AABB will be sharing a point. Resolving this collision is a little easier since you simply move the circle back along it's movement vector to the point of intersection. The drawback to this is that the circle will remain stuck on the edge of the AABB, since even if it tries to move away from the AABB, it will still intersect it at time 0. To fix this, I believe you would need to somehow check if the circle is moving away from the AABB, and disregard any intersection with the AABB if that is the case.
Is all of that correct, or am I wrong? Could someone please explain exactly how this is supposed to work?
Edit: After trying to figure out a method to find out if a circle is moving towards or away from an AABB, I have come to the conclusion that it is probably not possible to do so if the circle is sharing an edge with the AABB... If someone knows how, please let me know!
The first option is to consider any intersection as a collision which needs to be resolved. This is the option I described in my previous post. This option requires the circle to be completely pushed out of the AABB, which I was doing by pushing it back by an additional pixel. This causes the problem I described earlier; you need to somehow keep a 1 pixel thick border around the AABB without actually making it part of the AABB.
The second option is to consider intersection at "time 0" to be non-intersecting, and simply resting on each other's borders. However, this means that the circle and the AABB will be sharing a point. Resolving this collision is a little easier since you simply move the circle back along it's movement vector to the point of intersection. The drawback to this is that the circle will remain stuck on the edge of the AABB, since even if it tries to move away from the AABB, it will still intersect it at time 0. To fix this, I believe you would need to somehow check if the circle is moving away from the AABB, and disregard any intersection with the AABB if that is the case.
Is all of that correct, or am I wrong? Could someone please explain exactly how this is supposed to work?
Edit: After trying to figure out a method to find out if a circle is moving towards or away from an AABB, I have come to the conclusion that it is probably not possible to do so if the circle is sharing an edge with the AABB... If someone knows how, please let me know!
I didn't quite follow the details of the problem you've presented, so I don't have a definite answer, but I will offer one idea to consider.
When I've done this sort of thing in the past, I haven't used any sort of buffer or epsilon, and instead have used both static and dynamic tests.
Basically, I set up my collision detection functions to return a 'package' of information that indicates whether the intersection is static (that is, the objects are already intersecting and possibly penetrating) or dynamic (intersection at t > 0).
If the intersection is static, the minimum translational vector and contact points corresponding to the object configuration after the penetration is resolved are returned. If the intersection is dynamic, the time of intersection and the contact points corresponding to the object configuration at the time of intersection is returned.
The idea is that instead of using epsilons, thresholds, or buffers, you simply handle each type of intersection - static or dynamic - as appropriate.
Disclaimer: I created some 'sandbox' applications using this approach, but I don't think I really ever gave it a thorough workout, so I can't say with certainty that it's the best approach overall.
There are other options you could consider as well (and maybe already have). For example, if the per-update displacement of the circle will always be less than its radius, you could use a static/discrete test only. This approach is *much* simpler to implement than the dynamic version, and gives you nice sliding collision response essentially for free.
When I've done this sort of thing in the past, I haven't used any sort of buffer or epsilon, and instead have used both static and dynamic tests.
Basically, I set up my collision detection functions to return a 'package' of information that indicates whether the intersection is static (that is, the objects are already intersecting and possibly penetrating) or dynamic (intersection at t > 0).
If the intersection is static, the minimum translational vector and contact points corresponding to the object configuration after the penetration is resolved are returned. If the intersection is dynamic, the time of intersection and the contact points corresponding to the object configuration at the time of intersection is returned.
The idea is that instead of using epsilons, thresholds, or buffers, you simply handle each type of intersection - static or dynamic - as appropriate.
Disclaimer: I created some 'sandbox' applications using this approach, but I don't think I really ever gave it a thorough workout, so I can't say with certainty that it's the best approach overall.
There are other options you could consider as well (and maybe already have). For example, if the per-update displacement of the circle will always be less than its radius, you could use a static/discrete test only. This approach is *much* simpler to implement than the dynamic version, and gives you nice sliding collision response essentially for free.
Author
Unfortunately, the circle's movement vector magnitude could be (and usually is) greater than the circle's radius, so I have to handle the "dynamic" situation.
Thanks for the reply, but the problem mostly lies with resolving the collision. Lets say a dynamic collision is detected. How is this collision corrected? Do you move the circle back to the point of intersection (option #2 in my previous post), or move the circle back to the point of intersection and a little further (option #1)?
I am fairly new to this form of collision detection/response, so I could be going about this the wrong way. I've got this far mostly based off of what I have read and results I have gathered from numerous tests...
Thanks for the reply, but the problem mostly lies with resolving the collision. Lets say a dynamic collision is detected. How is this collision corrected? Do you move the circle back to the point of intersection (option #2 in my previous post), or move the circle back to the point of intersection and a little further (option #1)?
I am fairly new to this form of collision detection/response, so I could be going about this the wrong way. I've got this far mostly based off of what I have read and results I have gathered from numerous tests...
Quote:Thanks for the reply, but the problem mostly lies with resolving the collision. Lets say a dynamic collision is detected. How is this collision corrected? Do you move the circle back to the point of intersection (option #2 in my previous post), or move the circle back to the point of intersection and a little further (option #1)?What do you want to happen when the circle collides with a box? Should it slide? Bounce? Or just come to a stop?
Author
The eventual goal is to make the circle slide. However, from what I understand of sliding techniques, the first step is to resolve the collision. So right now I just want to make the circle stop. I'll add the sliding technique after that is working correctly.
The sliding technique I'm planning on using is described here, if you are interested: http://www.peroxide.dk/download/tutorials/tut10/pxdtut10.html
The sliding technique I'm planning on using is described here, if you are interested: http://www.peroxide.dk/download/tutorials/tut10/pxdtut10.html
What if you try to maintain the contact info (each object has a list of objects it currently touches)? This is something you probably need anyway (so you can detect player standing on a moving elevator in a platformer game, for instance).
Collision queries could also return 3 states: intersecting, touching and no collision. If a collision status is intersecting, you handle that first and move the object(s) to unpenetrate (collision validation), then change collision status to touching. Once that done (or if collision is already touching), apply forces to both objects (collision response).
The "touching" state would be caused by the smallest separation distance being less than 2 pixels - I guess - since it's a 2D game.
One last thing you can try is using a combination of sweep test and sampling test somehow. Sampling test is when you choose a fixed step size (let's say 1/2 if your cicle's radius) and then figure out how much time must pass during that step, based on relative speeds. Then sample over a certain time span with that time increment - each time the collision detection would be 100% static, so do need to worry about dynamic collision. I know you said dynamic collisions are not the problem, but I thought I would mention this to give you more tools, in case you don't already know.
Collision queries could also return 3 states: intersecting, touching and no collision. If a collision status is intersecting, you handle that first and move the object(s) to unpenetrate (collision validation), then change collision status to touching. Once that done (or if collision is already touching), apply forces to both objects (collision response).
The "touching" state would be caused by the smallest separation distance being less than 2 pixels - I guess - since it's a 2D game.
One last thing you can try is using a combination of sweep test and sampling test somehow. Sampling test is when you choose a fixed step size (let's say 1/2 if your cicle's radius) and then figure out how much time must pass during that step, based on relative speeds. Then sample over a certain time span with that time increment - each time the collision detection would be 100% static, so do need to worry about dynamic collision. I know you said dynamic collisions are not the problem, but I thought I would mention this to give you more tools, in case you don't already know.
Author
Thanks for the suggestions, but your solution is basically what I already do. If the circle is intersecting the AABB, it is moved back to the intersection point + 1 pixel. However, this causes the problem I mentioned in the first post.
if that's any help to you, I have some 2D swept sphere - polygon collision code.
The method is more complicated than what's explained in the doc you provided, however I believe the algorithm presented there is flawed.
The method is more complicated than what's explained in the doc you provided, however I believe the algorithm presented there is flawed.
Are you doing this in the integers, or with floating point math?
You are talking about pixels, but still you use spheres, that don't seem to be approximated by pixels.
You are talking about pixels, but still you use spheres, that don't seem to be approximated by pixels.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
