2
$\begingroup$

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:

Rectangles

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 ?

$\endgroup$
  • $\begingroup$ Are the rectangles axis-aligned, as in the image? $\endgroup$ – Nominal Animal Jun 6 '17 at 20:28
  • $\begingroup$ @NominalAnimal Yes they are, sorry, forgot to mention. $\endgroup$ – Winter Jun 7 '17 at 14:21
  • 1
    $\begingroup$ Anything else that you might try to do to infer which sides are going to touch is going to be at least as expensive to compute—and likely more so—than a few additions and four divisions and range checks. Seems like doing something “smart” but less efficient is actually the “stupid” way. $\endgroup$ – amd Jun 7 '17 at 20:15
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't really understand what you are trying to do with $t$. If I need to plug in the time at which they collide, this is impossible for me. I don't know at what time they will collide. (I only know it later, when I already know from which side they collide) Plus, I feel like it shouldn't be needed. If both shapes are moving along a linear vector, do I really need to move them to know from which side they will collide ? I added more information to my question, sorry if I was misleading. $\endgroup$ – Winter Jun 7 '17 at 18:27
  • $\begingroup$ @Winter You solve for the parameter $t$ (now $\lambda$) in the four equations that I gave you, effectively computing potential collision times. That gives up to four potential points at which the rectangles collide, and you then test each one for an actual collision. I”m sure that with a lot of work you could come up with another way to do this using relative angles and such, but this way is very simple and very fast. $\endgroup$ – amd Jun 7 '17 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.