Hi, 

I used the 3D shortest distance between two line segments algorithm at this website: http://geomalgorithms.com/a07-_distance.html#dist3D_Segment_to_Segment

This function in Python is checking if two capsules intersect. I checked the algorithm from the website and it seems to work. I tried implementing an epsilon to help with floating point error, but I don't think I did it correctly. Help would be much appreciated. 

def check_intersection(particle1,particle2):
    decimal.getcontext().prec = 100
    epsilon = 2**-52 #implement epsilon
    small_num = 0.00000001 #number to check if they're closely parallel
    u = particle1.get_s() #s1
    v = particle2.get_s() #s2
    p0 = particle1.get_p1_position() #P0
    q0 = particle2.get_p1_position() #Q0
    w = np.array([p0[0]-q0[0], p0[1]-q0[1], p0[2]-q0[2]])  #distance from 2 particles from their p1's

    a = u[0]**2 + u[1]**2 + u[2]**2 #dot product of u*u. Always >=0
    b = u[0]*v[0] + u[1]*v[1] + u[2]*v[2] #dot product of u*v.
    c = v[0]**2 + v[1]**2 + v[2]**2 #dot product of v*v. Always >=0
    d = u[0]*w[0] + u[1]*w[1] + u[2]*w[2] #dot product of u*w
    e = v[0]*w[0] + v[1]*w[1] + v[2]*w[2] #dot product of v*w
    D = (a*c)-b**2 #always >=0

    #Set all to defaults
    sc = sN = sD = D #sc = sN / sD, default sD = D >= 0
    tc = tN = tD = D #tc = tN / tD, default tD = D >= 0
    if D**2 < small_num:  # checks if SCs are parallel
        sN = 0.0  # force using point P0 on segment S1
        sD = 1.0  # to prevent possible division by 0.0 later
        tN = e
        tD = c
    else:  # get the closest points on the infinite lines
        sN = (b * e) - (c * d)
        tN = (a * e) -(b * d)
        if sN < 0.0:
            sN = 0.0
            tN = e
            tD = c
        elif sN > sD:  # sc > 1  => the s=1 edge is visible
            sN = sD
            tN = (e + b)
            tD = c
    if tN < 0.0:  # tc < 0 => the t=0 edge is visible
        tN = 0.0
        # recompute sc for this edge
        if -d < 0.0:
            sN = 0.0
        elif -d > a:
            sN = sD
        else:
            sN = -d
            sD = a
    elif tN > tD:  # tc > 1  => the t=1 edge is visible
        tN = tD
        # recompute sc for this edge
        if (-d + b) < 0.0:
            sN = 0.0
        elif (-d + b) > a:
            sN = sD
        else:
            sN = (-d + b)
            sD = a
    # division to get sc and tc
    if abs(sN) < small_num:
        sc = 0.0
    else:
        sc = sN / sD
    if abs(tN) < small_num:
        tc = 0.0
    else:
        tc = tN / tD
    # difference of 2 closest points
    dP = np.array( [w[0] + (sc * u[0]) - (tc * v[0]), w[1] + (sc * u[1]) - (tc * v[1]), w[2] + (sc * u[2]) - (tc * v[2])] )
    # dP = w + np.multiply(sc,u) - np.multiply(tc,v) #S1(sc) - S2(tc)
    close_d = (math.sqrt(dP[0] ** 2 + dP[1] ** 2 + dP[2] ** 2) ) # closest distance b/w 2 lines
    # check if distance <= radius * 2, if so, INTERSECTION!
    diff = abs( close_d - (2*S_RADIUS) )
    if(diff <= epsilon):
        return True
    else:
        return False

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?