Capsule-Capsule Detection

Irrespective of whether the rest of the code is correct (it may or may not be), I'm not sure how this is supposed to work:

diff = abs( close_d - (2*S_RADIUS) )
if(diff <= epsilon):
    return True
else:
    return False

If the distance is less than twice the radius, then 'close_d - (2*S_RADIUS)' will be some negative value, and 'abs( close_d - (2*S_RADIUS) )' will be some positive value that's likely > epsilon, therefore the function will (incorrectly) return false.

Am I missing something there? (I may be.)

Too late to edit my previous post, but that code seems to test for whether the capsules are just touching, whereas I'm guessing you want to know if they're intersecting at all. For that, you only need check that the distance is < or <= twice the radius (or you can do a squared distance check and save some math).

It looks like the source you're using as reference already addresses numerical problems. If there's some other issue you're trying to address via an epsilon, maybe you could clarify what it is.

This should be helpful: https://www.geometrictools.com/Samples/Geometrics.html#DistanceSegments3

IIRC, it uses an epsilon only once to tell if the lines are parallel. (But i see the code has been updated and there is nmore efford on precision issues now.)

4 hours ago, Zakwayda said:

Am I missing something there? (I may be.)

A simple test like this can only safely tell there is no intersection because the capsules are too far apart. It can not tell if there is intersection if they are close to each other.

5 hours ago, JoeJ said:

A simple test like this can only safely tell there is no intersection because the capsules are too far apart. It can not tell if there is intersection if they are close to each other.

I'm not exactly sure what you mean, but that doesn't sound correct to me. The test under discussion (implemented correctly) should detect any and all intersections.

If that sounds wrong to you, maybe you could elaborate (I may just be misunderstanding what you said).

33 minutes ago, Zakwayda said:

If that sounds wrong to you, maybe you could elaborate (I may just be misunderstanding what you said).

Ah, sorry - i did only quickly read over your post and did not notice your snippet is a small section from the inital post.

Accidently i though you would propose to check bounding spheres of both capsules for a quick seperation test and leave it at this.

So i totally missed your point. My bad - i was in a rush.

Looking more closely i see you have answered the question already and my reply was just noise.

6 hours ago, JoeJ said:

IRC, it uses an epsilon only once to tell if the lines are parallel

I was wrong with this too.

Also he OP code seems an exact copy of Eberlys code that i have linked to, just for Python.

Hi Zakwayda,

When you said "you only need check that the distance is < or <= twice the radius (or you can do a squared distance check and save some math).", doesn't distance <= twice the radius already include distance < twice the radius? Also, what do you mean by a squared distance check? Can you be more explicit?

When I try to run my code, it doesn't find all the collisions.

Thanks for all the help!

1 minute ago, ThinkSmall98 said:

Hi Zakwayda,

When you said "you only need check that the distance is < or <= twice the radius (or you can do a squared distance check and save some math).", doesn't distance <= twice the radius already include distance < twice the radius? Also, what do you mean by a squared distance check? Can you be more explicit?

Thanks for all the help!

Sorry, '< or <=' was probably a little confusing. What I meant is that you can use either < or <=, as you prefer. In other words, it's your choice which to use. Conceptually, whether you choose < or <= depends on whether you want to count 'just touching' as an intersection (<= will count 'just touching', < won't). Both in theory and in practice, the 'just touching' case is probably unlikely to occur (except in contrived cases), so which comparison you use may not matter much.

As for squared distance, in this context comparing squared distances is equivalent to comparing distances, so you can save some math (in particular a square root) by comparing squared distances instead.

Untested pseudocode, but here's how you might perform the test once you've computed the pair of closest points:

return squaredDistance(closestPoint0, closestPoint1) <= square(2 * radius)

Thanks for the tip! I've implemented the squared distances, which made my program much faster, but one problem is that the collision detection doesn't seem to work that well. Sometimes collided particles still go through the algorithm, which shouldn't happen. I tried to figure out why by researching and the only thing people have said is that it is probably due to a floating point error, which is why I tried implementing epsilon in the first place. Here's a picture of one collision after I ran my edited code:

Here's a blog that talks about it: http://realtimecollisiondetection.net/blog/?p=89

49 minutes ago, ThinkSmall98 said:

Sometimes collided particles still go through the algorithm, which shouldn't happen.

Can you clarify what you mean by particles 'going through the algorithm'?

Quote

...the only thing people have said is that it is probably due to a floating point error...

I wouldn't just assume it's due to floating-point error unless you have a specific reason to think that's the culprit. If the people who suggested it was floating-point error also told you why/how floating-point error might be an issue, that would be worth considering. But absent that information I'm not sure the suggestion that it's 'floating-point error' is particularly useful.

Can you clarify where the problem in your image is? I can see that two capsules are intersecting. Is the problem that that intersection (or others like it) isn't being detected by the algorithm?

Yes, that's exactly the problem. Some intersections aren't being detected by the algorithm.

3 minutes ago, ThinkSmall98 said:

Yes, that's exactly the problem. Some intersections aren't being detected by the algorithm.

I suggest finding a configuration for which the algorithm returns a false negative, and then testing the algorithm in isolation using that configuration as input. If you have a debugger available, you can step through in the debugger. And/or, you can add log messages to track the algorithm's progress.

The algorithm itself isn't particularly intuitive, so even under that kind of examination it may not be obvious what's going wrong. In case you get stuck, here are some more suggestions:

- Post your current code and the input for which the algorithm fails so we can take a look.

- There are a lot of opportunities for typos or copy-paste errors there, so you could double-check your code again against the reference you're using to check for obvious mistakes.

- I don't know much about Python, and maybe you're inlining all the operations for performance reasons. Otherwise though, writing functions for common operations like vector dot product, addition, etc. will make your code cleaner, easier to read, and less bug-prone. (Again though, I understand that you may be inlining on purpose.) Also, on the topic of performance I notice you're doing a lot of squaring via exponentiation. I don't know what the performance characteristics of the exponential operator are in Python (maybe simple cases are optimized), but in some languages/environments, simply multiplying a value by itself can be faster. Anyway, something to consider if you're encountering performance issues. (There's some discussion of the cost of the exponential operator here.)

On 10/17/2019 at 2:54 AM, ThinkSmall98 said:

if D**2 < small_num: # checks if SCs are parallel

Because D is already a result of squares, i think this should be just: if D < small_num

But htat's unlikely the reason or a big problem at all. In your picture the intersecting capsules seem more normal than parallel to each other and the test should not fail in any case (except the scale of the scene is super tiny).

So i would try to get data from the guys who detect the issue - maybe they can log capsule positions instead making a screenshot.

Otherwise it's helpful to have some visualization yourself, and the ability to set up capsule positions intercatively from some GUI. This way it becomes easy to detect failure cases yourself and to debug them.

On 10/17/2019 at 2:54 AM, ThinkSmall98 said:

p0 = particle1.get_p1_position() #P0

Can it be this returns the center of the capsule, while the algorithm assumes it to be one of its end points?

No, this returns one of the end points.

On 10/17/2019 at 2:54 AM, ThinkSmall98 said:

u = particle1.get_s()

And this is the same as particle1.get_p2_position() - particle1.get_p1_position()?

I guess yes, but just to be sure.

And changing the last lines to:

if (close_d < (2*S_RADIUS)) return true
else return false

... not using an epsilon, is likley what you had initially (before introducing the 'touching'-bug with the epsilon, which is not necessary).

That said just to confirm i do not see any other thing that could be wrong with your code.

Maybe the users of your code use a broad phase to detect potential colliding pairs? Some acceleration structure?

I'd bet the bug is on their side then, or their visualization is off.