   Where to find capsule-capsule swept collision code?
  I had already done capsule-capsule collision. But I want that two very fastcapsules 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?   
  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   ;Quote:Original post by TheC00L1against what? I happen to have abook that has a lot different collision code snippetsI 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.   ;  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.   ;Quote:Original post by TheC00L1Or 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.   ;  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.   ;  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.   ;  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.;  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?   ;Quote:Original post by CaossTecI 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.