Acceleration Collision Detection

Question

I am writing a physics engine / simulator that includes three-dimensional space flight, planetary / stellar gravity, ship propulsion and relativistic effects. So far, everything is going well, but I need help with the math of the collision detection algorithm.

The iterative motion simulation that I use basically looks like this:

(Note. 3D vectors are ALL COPIES.)

For each obj obj.ACC = Sum(all acceleration influences) obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2 (*EQ.2*) obj.VEL = obj.VEL + (obj.ACC * dT) Next 

Where to:

 obj.ACC is the acceleration vector of the object obj.POS is the position or location vector of the object obj.VEL is the velocity vector of the object obj.Radius is the radius (scalar) of the object dT is the time delta or increment 

Basically, I need to find an effective formula that is derived from (EQ.2) above for two objects (obj1, obj2) and say if they ever collide, and if so, at what time. I need the exact time so that I can determine if it is in this particular time increment (because the acceleration will differ with different time increments), and also so that I can determine the exact position (which I know how to do, given time)

For this engine, I model all objects as spheres, all that needs to be done to this formula / algorithm is to find out at what points:

 (obj1.POS - obj2.POS).Distance = (obj1.Radius + obj2.Radius) 

where .Distance is a positive scalar value. (You can also enclose a square in both directions, if it's easier, to avoid the square root function implicit in the .Distance calculation).

(yes, I am aware of many, many other issues of collision detection, however, it seems that their solutions are very specific to their engine and assumptions, and none of them matches my conditions: 3D, spheres and acceleration applied with the modeling step Give let me know if I'm wrong.)

---

Some clarifications:

1) It is not enough for me to check the intersection of two spheres before and after an increase in time. In many cases, their speeds and changes in position will far exceed their radii.

2) RE: efficiency, I do not need help (at this stage in any case) with regard to identifying likely candidates for collisions, I think I have covered it.

---

Another refinement that seems to be a lot:

3) My equation (EQ.2) of incremental motion is a quadratic equation that applies both speed and acceleration:

 obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2 

In the physical engines I've seen (and, of course, in every game engine I've ever heard of), there are only linear equations of incremental motion that apply only speed:

 obj.POS = obj.POS + (obj.VEL * dT) 

That's why I can't use the publicly available collision detection solutions found on StackOverflow, Wikipedia, and the entire Internet, such as finding the intersection / closest approach of two segments. My simulation deals with variable accelerations, which are fundamental to the results, so I need the intersection / closest approach of the two parabolic segments.

Answer 1

The AShelley-linked web page has developed the "Nearest Approach Point" method for the case of two objects moving at a constant speed. However, I believe that the same vector calculation method can be used to obtain the result in the case of two objects moving with constant non-zero acceleration (quadratic time dependence).

In this case, the time derivative of the function of the square of the distance is 3rd order (cubic) instead of 1st order. Therefore, there will be 3 solutions for the time of the closest approach, which is not surprising, since the path of both objects is curved, so multiple intersections are possible. For this application, you probably want to use the earliest value of t, which is within the interval defined by the current simulation stage (if such a time exists).

I developed a derivative equation that should give the time of the closest approach:

0 = |D_ACC|^2 * t^3 + 3 * dot(D_ACC, D_VEL) * t^2 + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ] * t + 2 * dot(D_POS, D_VEL)

Where:

D_ACC = ob1.ACC-obj2.ACC

D_VEL = ob1.VEL-obj2.VEL (before updating)

D_POS = ob1.POS-obj2.POS (also before the update)

and dot(A, B) = Ax*Bx + Ay*By + Az*Bz

(Note that the square of |A|^2 can be calculated using dot(A, A) )

To solve this problem for t , you probably have to use formulas such as those found on Wikipedia .

Of course, this will only give you a moment of approach. At this point you will need to check the distance (using something like equation 2). If it is larger than (obj1.Radius + obj2.Radius) , it can be neglected (i.e. No collision). However, if the distance is shorter, this means that the spheres collide up to this point. You can then use an iterative search to check the distance in earlier times. It may also be possible to come up with one more (even more complicated) conclusion that takes into account the size or may find some other analytical solution without resorting to an iterative solution.

Edit : due to the higher order, some of the solutions of the equation are actually moments of the farthest separation. I believe that in all cases one of the 3 solutions or 2 of the 3 solutions will be a time of more complete separation. You can analytically check whether you are at min or max, evaluating the second derivative with respect to time (for the values ​​of t that you found by setting the first derivative to zero):

D''(t) = 3 * |D_ACC|^2 * t^2 + 6 * dot(D_ACC, D_VEL) * t + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ]

If the second derivative estimates a positive number, then you know that the distance is minimum, not maximum, for a given time t.

Answer 2

Draw a line between the starting location and the ending location of each sphere. If the resulting line segments intersect with balls definitely colliding at some point, and some clever math can find what time the collision occurred. Also make sure that the minimum distance between segments (if they do not intersect) is always less than a radius of 2 *. This will also indicate a collision.

From there, you can return to your delta time to happen precisely in a collision so that you can correctly calculate the forces.

Have you considered using a physics library that is already doing this job? Many libraries use much more advanced and more stable (better integrators) systems to solve the systems of equations with which you work. Bullet Physics comes to mind.

Answer 3

Looks like you want the closest approach point (CPA) . If it is less than the sum of the radii, you have a collision. The link has a sample code. You can calculate each frame at the current speed and check if the CPA time is shorter than the size of your checkmark. You can even cache cpa time and only update when acceleration has been applied to any element.

Answer 4

op asked for a collision time. A slightly different approach will figure it out for sure ...

Remember that the equation of projection of position:

NEW_POS=POS+VEL*t+(ACC*t^2)/2

If we replace POS with D_POS=POS_A-POS_B , VEL with D_VEL=VEL_A-VEL_B and ACC=ACC_A-ACC_B for objects A and B we get:

$D_NEW_POS=D_POS+D_VEL*t+(D_ACC*t^2)/2

This is the formula for the vector distance between objects. To get the square scalar distance between them, we can take the square of this equation, which after expansion looks like this:

distsq(t) = D_POS^2+2*dot(D_POS,D_VEL)*t + (dot(D_POS, D_ACC)+D_VEL^2)*t^2 + dot(D_VEL,D_ACC)*t^3 + D_ACC^2*t^4/4

To find the time when the collision occurs, we can set the equation equal to the square of the sum of the radii and solve for t :

0 = D_POS^2-(r_A+r_B)^2 + 2*dot(D_POS,D_VEL)*t + (dot(D_POS, D_ACC)+D_VEL^2)*t^2 + dot(D_VEL,D_ACC)*t^3 + D_ACC^2*t^4/4

Now we can solve for the equation using the quartic formula .

The quartic formula will give 4 roots, but we are only interested in real roots. If there is a double real root, then two objects touch the edges at exactly one moment in time. If there are two real roots, then the objects continuously overlap between root 1 and root 2 (i.e., root 1 is the time the collision started, and root 2 is the time the collision ended). Four real roots mean that objects collide twice, continuously between pairs of roots 1,2 and 3,4.

In R, I used polyroot() to solve as follows:

 # initial positions POS_A=matrix(c(0,0),2,1) POS_B=matrix(c(2,0),2,1) # initial velocities VEL_A=matrix(c(sqrt(2)/2,sqrt(2)/2),2,1) VEL_B=matrix(c(-sqrt(2)/2,sqrt(2)/2),2,1) # acceleration ACC_A=matrix(c(sqrt(2)/2,sqrt(2)/2),2,1) ACC_B=matrix(c(0,0),2,1) # radii r_A=.25 r_B=.25 # deltas D_POS=POS_B-POS_A D_VEL=VEL_B-VEL_A D_ACC=ACC_B-ACC_A # quartic coefficients z=c(t(D_POS)%*%D_POS-r*r, 2*t(D_POS)%*%D_VEL, t(D_VEL)%*%D_VEL+t(D_POS)%*%D_ACC, t(D_ACC)%*%D_VEL, .25*(t(D_ACC)%*%D_ACC)) # get roots roots=polyroot(z) # In this case there are only two real roots... root1=as.numeric(roots[1]) root2=as.numeric(roots[2]) # trajectory over time pos=function(p,v,a,t){ T=t(matrix(t,length(t),2)) return(t(matrix(p,2,length(t))+matrix(v,2,length(t))*T+.5*matrix(a,2,length(t))*T*T)) } # plot A in red and B in blue t=seq(0,2,by=.1) # from 0 to 2 seconds. a1=pos(POS_A,VEL_A,ACC_A,t) a2=pos(POS_B,VEL_B,ACC_B,t) plot(a1,type='o',col='red') lines(a2,type='o',col='blue') # points of a circle with center 'p' and radius 'r' circle=function(p,r,s=36){ e=matrix(0,s+1,2) for(i in 1:s){ e[i,1]=cos(2*pi*(1/s)*i)*r+p[1] e[i,2]=sin(2*pi*(1/s)*i)*r+p[2] } e[s+1,]=e[1,] return(e) } # plot circles with radius r_A and r_B at time of collision start in black lines(circle(pos(POS_A,VEL_A,ACC_A,root1),r_A)) lines(circle(pos(POS_B,VEL_B,ACC_B,root1),r_B)) # plot circles with radius r_A and r_B at time of collision stop in gray lines(circle(pos(POS_A,VEL_A,ACC_A,root2),r_A),col='gray') lines(circle(pos(POS_B,VEL_B,ACC_B,root2),r_B),col='gray') 

Object A follows the red path from the lower left to the upper right. Object B follows the blue path from the lower right to the upper left. Two objects continuously collide between time 0.9194381 and time 1.167549. The two black circles simply touch each other, showing the beginning of the overlay - and the overlay continues in time until the objects reach the location of the gray circles.