search

dimforge / ncollide

2 and 3-dimensional collision detection library in Rust.
https://ncollide.org
Apache License 2.0
921 stars 105 forks source link

RayIntersection precision question #3

Closed brandonw closed 10 years ago

brandonw commented 10 years ago

A little while ago, I spoke briefly with you in the rust-gamedev irc channel, and you recommended using a MinkowskiSum to test for a time of impact between a ball and a rectangle.

That is proven extremely effective, and I am using ncollide now just as you said. However, I have a scenario that plays out where a RayIntersection that is returned ends up computing the ball's position to be precisely adjacent to the block. For example, if the block's leftmost edge is at x = 0, and the ball's radius is 5, the RayIntersection will give me a time of impact such that the ball's updated position computes x to be precisely -5.

This causes the next update call to immediately detect an intersection with a very small time of impact, and the same normal as the previous intersection. The ball then "bounces" along the side of the block, as it repeatedly updates the ball's position to be directly adjacent to the block, and then moves it slightly away while updating the velocity to point back towards the block again.

ncollide is doing exactly what it is supposed to do, but I'm not sure exactly what the standard procedure is for dealing with this scenario. Is there a specific mechanism in ncollide that already handles this? Or should I be doing something differently?

sebcrozet commented 10 years ago

No there is nothing on ncollide to handle this.

I don't know if there is a "standard" method to deal with this but, here are some pointers. I am assuming that you have some kind of integrator, and you are using the time of impact (TOI) information to prevent the so-called "tunnelling effect" using "motion clamping" (i-e teleporting the ball at the exact position it should have had at a given TOI):

  1. You can see this problem as a ray-casting precision issue (i-e the ray-cast erroneously intersects the new Minkowski Sum with a very small TOI because they are very close). This also causes the so-called "surface acne" problem that is well known in the computer graphics community that works with ray-based rendering. One easy "solution" is to move your ball slightly in the direction of its velocity, then perform the TOI computation. This might work very well if you don't have extremely small objects.
  2. Another way of dealing with this, assuming you have a constraint-based integrator, is to ignore any TOI that is smaller than a given threshold. Then, for each TOI that is ignored, perform an exact distance computation between your ball and your rectangle, and use this information to setup a new constraint on your integrator. Some articles call this a pessimistic collision detection.

I hope this will help you to find some ideas to solve your problem.

brandonw commented 10 years ago

You are exactly correct re: how I am using raycasting to prevent the tunneling effect.Thanks for the tips, I will try them out, and thanks for the great work on this library!