Jump to content
  • Advertisement
Sign in to follow this  
CaossTec

Where to find capsule-capsule swept collision code?

This topic is 4563 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 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
Advertisement
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
Yeah, i'm refering, to a boolean value as a result, sorry if this was to simplistic for what you wanted, i.e cirlces, points, and so on.

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
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!