Question:
Imagine I have $2$ axis aligned rectangles both moving along a vector. They can't overlap with each other so on collision, they will be stopped. Both shapes goes at the same speed relative to their vector meaning that $A$ takes the same time to reach the end of his vector than $B$ does, even if his vector is longer.
Example:
In that case for rectangle $A$, the normal of the side in contact with rectangle $B$ is $(1, 0)$. (And for $B$ it's $(-1, 0)$)
If I have the coordinates for both rectangles, their size and their movement vector, how can I get on which side rectangle $A$ will touch rectangle $B$?
I need a solution that works even if they are not touching and even if they are already overlapping. In those 2 cases, the vector can be extended to infinity or to negative infinity (in the other direction) but the length of the vector still indicates the relative movement of the shapes.
Background:
I have a physics engine with a continuous collision detection that works for a single side of a rectangle. (In other words, it checks if 2 segments will collide with their vector). It already works and I do not want to touch this algorithm. For the AABB vs AABB continuous collision detection, I do 4 detections for all of their sides which is stupid and inefficient. What I would like is to be able to know on which side perform the collision detection. Is it possible to get that with a simple formula ?
The computations involved are fairly simple and inexpensive, so I think it’s easiest to tackle this in stages, generating potential solutions and then discarding them as you go along.
Let $\mathbf a_0$ and $\mathbf b_0$ be the starting points of the centers of the two rectangles and $\mathbf d_A$ and $\mathbf d_B$, respectively, their movement vectors. The locations of the two centers along their respective line segments are then $$\mathbf a(\lambda)=\mathbf a_0+\lambda\,\mathbf d_A\\\mathbf b(\lambda)=\mathbf b_0+\lambda\,\mathbf d_B.$$ for $0\le\lambda\le1$. It’s also convenient to work with the half-widths and half-heights to eliminate stray factors of two from the formulas. I’ll also assume that at start, the rectangles aren’t overlapping.
If and when the moving rectangles collide, there will be some pair of opposite edges of the two rectangles that are aligned. So, start by finding the four locations at which this occurs, that is, solve for the values of $\lambda$ that satisfy one of the four equations $$x_{\mathbf a_0}+\lambda x_{\mathbf d_A}\pm w_A = x_{\mathbf b_0}+\lambda x_{\mathbf d_B}\mp w_B \\ y_{\mathbf a_0}+\lambda y_{\mathbf d_A}\pm h_A = y_{\mathbf b_0}+\lambda y_{\mathbf d_B}\mp h_B$$ giving $$\lambda={(x_{\mathbf b_0}-x_{\mathbf a_0})\pm(w_A+w_B)\over x_{\mathbf d_A}-x_{\mathbf d_B}} \\ \lambda={(y_{\mathbf b_0}-y_{\mathbf a_0})\pm(h_A+h_B)\over y_{\mathbf d_A}-y_{\mathbf d_B}}.$$ The first two equations represent vertical edges coinciding, the second two horizontal edges. Discard any solutions that are not in the interval $[0,1]$. The remaining candidates represent actual collisions if the aligned edges overlap, which can be tested for by a range check of the appropriate edges. That is, for vertical sides overlapping, check that the intervals $[y_{\mathbf a}(\lambda)-h_A,y_{\mathbf a}(\lambda)+h_A]$ and $[y_{\mathbf b}(\lambda)-h_B,y_{\mathbf b}(\lambda)+h_B]$ overlap, and similarly for horizontal edges. The least of the parameter values that correspond to collisions is the first contact, and the corresponding edges are the ones that collide.