2d line-to-line collision detection using vectors (Week 2: Vectors)

  • As we’ve seen in class, vectors can be used to represent several objects such as physical quantities like velocity or force; 2-dimensional images; and even the bag-of-words model.
  • In what other ways can we use vectors?
  • Give one sample application and describe/illustrate how the vector can be used.

While computers are good at calculating lots and lots of numbers that would be impossible for a human to do, amusingly some trivial things for humans are much more complex when it is done by a computer. One of these things is checking whether two lines intersect or not.

lines

At one glance it is easy for a human to check if two lines intersect or not, but how would you make a computer do it? This problem seems simple and doesn’t seem to be useful for anything, however it has its use in some areas like collision detection in video game development.

One way to do line-to-line collision is through the use of vectors. We can represent each line as a vector with one end as the the tail and the other head as a tail.

vectors

From here we can get the “projection” of each vector on a certain axis, like the x-axis. This can be easily done by getting the dot product of the vector and a unit vector in the same direction as the axis you want to project on. In this case since we will be projecting each vector to the x-axis, we will get the dot product of each vector with the (1,0) unit vector.

projection

Once the vectors are projected into an axis, it’s easier to compare whether the projection lines intersect or not (the details on how exactly would depend on what you are using). If the projections do not intersect, then we are sure that the original lines do not intersect.

This method does not handle all cases of collisions though, for example in case A below if we use the x-axis as a projection it would say that they intersect even though they aren’t. If we projected case A along the y-axis we would detect that indeed they aren’t intersecting. Case B passes both x and y axis tests even though they do not intersect. It seems testing for x and y axis isn’t sufficient.

other_cases

The correct axis to use is the two normal axis perpendicular to any of the two vectors. This check works for any case and is sufficient on its own (no need to check other axis). The image below shows a projection onto the axis perpendicular to the blue line. Note that if we project using the axis perpendicular to the red line it would seem that they are intersecting, that’s why it’s important to use the two normal axis for checking.

normal_axis

The use of vectors for collision detection can even be used on other things that aren’t two lines. For example, a 2d rectangle can be represented by a vector from the lower left corner to the upper right corner of the box. A 3d cube can also be represented by a vector in a similar manner. Vectors are useful in collision detection and game development in general.

 

Advertisements