Summary
We have already known commonly how to check if the two axis-aligned rectangles collide at many ways about it: one to just use information about lengths and a distance of those, or to take typicalized and structured variables such as x-axis length and y-axis length. But when they start to rotate themselves randomly, the function to check it goes more complex and finally it needs to have functionality that can make the problem simpler like class as a language grammar, and/or the linear transformations I'll explain now.
Linear Transformation
Well, you might have doubt about why linear algebra's topic appears in this context, but this concept is surly significant for us who want to get advanced knowledge for collision detection. Here is a pivotal thesis that will lead us to all the following concepts.
Thesis 1. Any translation and linear transformation with its determinant as non-zero cannot affect whether arbitrary two points in a coordinate plane have the same position.
That means, for example, a point P(2, 3) and another Q(3, 6) are always different though they are transformed by a translation or linear transformation whose determinant is not 0; like (-3, 2) that indicates P and Q get changed to P'(-1, 5) and Q'(0, 8). And, why this is that important is from the presence of the following thesis (and now on, I will say both a translation and a linear transformation having the constraint for determinant a normal transformation).
Thesis 2. A count of intersections between two curves is equivalent whenever any normal transformation is applied to those.
The thesis 1 is true, and this second one can be induced from it. This thesis is too strong for every cases of two shapes to transform a complex question to a relatively simpler one. Let's take a look about it here:
I want to know if a rotated ellipse (represented by E1) and another (also F1) get intersected.
To make this ease, I apply an appropriate revolving transformation for this problem. And the origin of this plane is the center of E1.
E1 becomes an axis-aligned ellipse–E2 while transformed F1, F2 is yet an ellipse.
I also do a linear transformation to them to make E2 a circle–E3. Modified F2 is F3.
Since E3 is circular, it doesn't change for shape when I use any revolving transformation by them, so E3 is still E3, but F3 can be an axis-parallel ellipse if the transformation's angle value was the negative of the rotation angle of F3. Now it is F4.
-
A question for two rotated ellipses now goes the basically equal question for a circle and an unrotated ellipse. If E3 intersects F4, E1 collides with F1 because the thesis 2 is true.
Collision Detection for Closed Two Curves
Although two curves do not have any intersections, they can still collide with each other if all those are closed. And the cases are always specified as when one curve completely wraps the another. For intuition, here's an high quality example that appropriately explains it below:
As most video games do, the two curves deserve being judged to collide so that a detection function returns the true value in this situation. Then, what and how should we do to find out if they collide at this point? Fortunately, there is an easy and satisfactory way for it; to check a coordinate of any point in the inner curve and also the outer one. If one point in a curve is wrapped from the another, they intersect.
Of course, this method is only proper when they don't have any intersections, since some point in a curve can be either within the different one or out of that generally. But once we are confident that there is no intersection of them, the method is definitely able to be considered reliable.
Conclusion
So, we now have a universal way to judge whether two curves that may be closed get collided:
If they are all closed,
1: Find any existing intersections between them. When some point of two curves does, they intersect.
2: Else, find any point (almost a center) within a curve included by the other one. Importantly, try this to all the two curves, not uniquely the one. When a point is done, they intersect.
3: Unless they are applied to all cases above, they do not intersect.
If at least one of them is open,
1: Check whether some intersection with them exist. When it does, they intersect.
2: If not, they do not intersect.
Also, as we saw how to simplify the first question (to find intersections) through concepts from Linear Algebra, this series of questions is gently acceptable to resolve and calculate in factual programs. Thus, I will show you soon the methods that we can apply for this collision detection problem later. See you the next time!
a source of the cover image: https://blog.bladecreativebranding.com/design-matters-how-shapes-affect-your-brands-perception/
Top comments (0)