 # ThinkSmall98

Member

5

1 Neutral

• Rank
Newbie

• Role
Student
• Interests
Design
Programming

## Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

1. No, this returns one of the end points.
2. Yes, that's exactly the problem. Some intersections aren't being detected by the algorithm.
3. 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
4. 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!
5. 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-q0, p0-q0, p0-q0]) #distance from 2 particles from their p1's a = u**2 + u**2 + u**2 #dot product of u*u. Always >=0 b = u*v + u*v + u*v #dot product of u*v. c = v**2 + v**2 + v**2 #dot product of v*v. Always >=0 d = u*w + u*w + u*w #dot product of u*w e = v*w + v*w + v*w #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 + (sc * u) - (tc * v), w + (sc * u) - (tc * v), w + (sc * u) - (tc * v)] ) # dP = w + np.multiply(sc,u) - np.multiply(tc,v) #S1(sc) - S2(tc) close_d = (math.sqrt(dP ** 2 + dP ** 2 + dP ** 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