Sign in to follow this  
CaossTec

Where to find capsule-capsule swept collision code?

Recommended Posts

I had already done capsule-capsule collision. But I want that two very fast capsules be detected. I had done that by using several iterations. However it is possible to perform a swept collision test and only performing one iteration. As far as I see the test can be done using a combination of distance of two planes and then between segments, by just extending the capsule test to the swept test. As I don't want to reinvent the weel I'm looking if that code is already in the internet, so far I didn't had luck with google. Do any of you know were can I get a function to perform capsule-capsule swept test?

Share this post


Link to post
Share on other sites
I think you could turn it into four Capsules and an OBB, but i don't really know much abouts this.

Quote:

Do any of you know were can I get a function to perform capsule-capsule swept test?


against what? I happen to have abook that has a lot different collision code snippets

Share this post


Link to post
Share on other sites
Quote:
Original post by TheC00L1
against what? I happen to have abook that has a lot different collision code snippets
I think he means testing two moving capsules against one another.

I'm not aware of any straightforward algorithms or online code samples for swept capsule-capsule intersection. I'd be interested to know if there is such a thing though.

The only thing that comes to mind at the moment is GJK, which doesn't fall into the 'straightforward' category. I imagine a special-case CSO-based implementation could be devised though. I've written a swept capsule-triangle test using this method, and it seemed to work (although I didn't test it rigorously). The capsule-capsule test should be similar; the CSO would be, I think, a swept-sphere solid whose medial structure is a parallelogram. This structure could then be raytraced to find the time of intersection.

There may be other ways to go about it, but nothing particularly easy, I don't think. In any case, you might want to consider using a friendlier bounding volume (with regard to this particular test at least), such as OBBs.

Share this post


Link to post
Share on other sites
Or your could just generate two flat triangles per capsule sweep(make a quad), and find the closest points(maybe infinite) of one pair of triangles against the other pair. then determine if the distances are past of a certain length.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheC00L1
Or your could just generate two flat triangles per capsule sweep(make a quad), and find the closest points(maybe infinite) of one pair of triangles against the other pair. then determine if the distances are past of a certain length.
It sounds like you're refering to the boolean swept test here. Just to be clear, my previous post was in reference to the swept test with time of intersection; if only a boolean result is needed, the problem is indeed more manageable.

Share this post


Link to post
Share on other sites
If you're able to aproximate the capsule as a convex-hull, you could perform the "seperating axis theorem" on 2 convex hulls. Google has a lot of information on the algorithm.

I know there are algorithms for swept capsule-capsule, but the added complexity of them may be more than the effort its worth.

Share this post


Link to post
Share on other sites
I assume your capsules are moving during the time step with constant linear velocity. In this case, the center segment of a capsule sweeps out a parallelogram *or* a longer segment (when the velocity is parallel to the center segment). For a Boolean test, you need to compute the distance between the swept regions and compare it to the sum of the capsule radii. That means you need algorithms for distance between two parallelograms, a segment and a parallelogram, and two segments.

Share this post


Link to post
Share on other sites
I had continue searching the web, and had no lucky yet. As it has being pointed, the boolean test will imply computing distances between two parallelograms. It's relatively fast but the disadvantage of just computing that distance is that the point of contact for each capsule could be reached at different time frames. So a more precise test should involve performing maybe a binary search with the boolean operation.
I think that could be efficient to manage collision missed because of the capsule passing the contact point at different times. First to apply boolean test with the complete movement of both capsules, and then if a possible collision is detected, perform a binary search until the contact point has being located with in a permited error.

I wonder if there is some other approach to avoid doing the binary search?

Btw, I guess that computing the distance between two parallelograms involve computing the distance between the segments that bound the figure and then the plane were the figures are in. Are there any other faster way?

Share this post


Link to post
Share on other sites
Quote:
Original post by CaossTec
I had continue searching the web, and had no lucky yet. As it has being pointed, the boolean test will imply computing distances between two parallelograms. It's relatively fast but the disadvantage of just computing that distance is that the point of contact for each capsule could be reached at different time frames. So a more precise test should involve performing maybe a binary search with the boolean operation.
I think that could be efficient to manage collision missed because of the capsule passing the contact point at different times. First to apply boolean test with the complete movement of both capsules, and then if a possible collision is detected, perform a binary search until the contact point has being located with in a permited error.

I wonder if there is some other approach to avoid doing the binary search?


There is a common misconception that closed-form solutions are "better" than an iterative algorithm. Whether one approach is better than the other just depends. In this problem, computing the distance between two parallelograms is going to be relatively expensive.

An iterative scheme is reasonable when you have constant linear velocities during the time step. Consider the function F(t) = sqrDist(seg0(t),seg1(t))/(rad0+rad1)-1, where seg0(t) and seg1(t) are the capsule segments (vary with time due to the velocities) and where rad0 and rad1 are the capsule radii. Initially, the capsules are separated, so F(t) > 0. You want to compute the first time tmin for which F(tmin) = 0 but F(t) > 0 for t < tmin. The function F is "convex" (graph looks like a parabola that opens upward). These are good for applying Newton's method or the Secant method for root finding. You do not have to use a slower bisection method.

Quote:

Btw, I guess that computing the distance between two parallelograms involve computing the distance between the segments that bound the figure and then the plane were the figures are in. Are there any other faster way?


I believe you can reduce parallelogram-parallelogram distance computations to segment-parallelogram distance computations. These in turn are reduced to point-parallelogram distance computations and segment-segment distance computations. Alternatively, the squared-distance function for two parallelograms is a quadratic function of four variables. You can apply methods of calculus to compute the minimum.

Share this post


Link to post
Share on other sites
I don't think there is source code on the web for swept-capsule collision. I wrote one a long time ago, and a swept-capsule forms a lozenge shape. You may want to try googling for that shape intersection.

If you've written capsule-capsule collision then extending it to a lozenge isn't a huge undertaking to write.

Of course, it's my opinion that an iterative solution is better.

- Dave

Share this post


Link to post
Share on other sites
Finally I create the swept capsule-capsule code using the iterative approach as sugested. However, I used a linear solution instead of a faster bisection method.

t = 0
for each dt between 0..1
check if collision between the two capsules
if not, move both capsules
if a collision is detected, return the t value
t += dt
end for

Most bisection methods (Binary search, Newton Secant, etc) as far as I know, allows finding the solution faster, but need a parabolic function. As I see it, the function that describe the distance between the two capsules, most of the times, has a parabolic shape, but due to the fact that the capsules can not just be moving but also rotating, then some local minimums will appear. Using the newton method of most other, it's easy to fall into one of those local minimums.
Is it possible to avoid falling on the local minimums? So I can use a faster bisection method

Share this post


Link to post
Share on other sites
Quote:
Original post by CaossTec
Most bisection methods (Binary search, Newton Secant, etc) as far as I know, allows finding the solution faster, but need a parabolic function. As I see it, the function that describe the distance between the two capsules, most of the times, has a parabolic shape, but due to the fact that the capsules can not just be moving but also rotating, then some local minimums will appear. Using the newton method of most other, it's easy to fall into one of those local minimums.
Is it possible to avoid falling on the local minimums? So I can use a faster bisection method


Once you allow for arbitrary motion, you have a very general root-finding problem to solve. You either use some general iterative scheme or you try to take advantage of information you know about the motion. For example, the assumption of constant linear velocity and no angular velocity gives you the "parabolic shape" for your function (what I called "convex function" and is the correct nomenclature).

If you have constant angular velocity (in addition to constant linear velocity), you might be able to get an upper bound on the number of roots for a specified time interval. This bound will depend on the relationship between the angular speeds of the capsules. The function I mentioned in an earlier post is the one you want to find its roots. This function will involve sinusoidals whose frequencies are determined by the angular speeds. There is no chance of obtaining a closed-form solution for the roots but you can get an idea of how many roots there might be. Still, what you have now is a difficult numerical problem.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this