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.