Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

A object has a position and a speed vector. Usually only the position is used to check if two objects collide, this is problematic for very fast moving objects as it can happen that the object moves so fast that it is in front of the first object in the first collision check, and behind it in the second collision check.

BoundingBox Collision Fail

Now there is also line based collision checks, in which you only check if the movement vector of each object intersects with the bounding-box of the other one. This can be seen as a expansion of a point. This only works though if the fast moving object is really small.

Hexagon Collision Win

So my idea is, instead of expanding a point, why not expanding a rectangle? This results in a Hexagon.

Now, so far so good. But how do I actually check if two Hexagons of this kind intersect? Note that these are very specific Hexagon's.

Hexagon Specifications

Bonus Question: Is it possible to calculate where exactly (or rather after how much time) the collision happened? This could be very useful to detect what really happened, like where and with how much power and to simulate how they moved in the time between the collision and the end of the frame.

share|improve this question
    
for(lines in A) for (lines in B) if (lines cross) collision - except that doesn't cover A in B or B in A cases. Hm. =) –  Jari Komppa May 20 '13 at 16:01
4  
Are you committed to boxes? The boxes you drew can be represented by circles with minimal loss of accuracy but a comparatively easy collision algo. Search for swept circle collision detection. If your length/width ratio moves away from 1, the less attractive this would be though. –  Steve H May 20 '13 at 22:05
    
@SteveH I am looking for the most flexible solution, so the length/width ratio is a kinda big deal. –  API-Beast May 22 '13 at 16:25
1  
You must realize that just because the hexagons intersect doesn't mean the collision occurs. Even provided you could tell without mistake whether they do intersect, you would still have work to do to determine whether there is a collision, and, obviously, where and when it happens. So you can't jump to your bonus question just yet. –  jrsala May 23 '13 at 13:39
2  
I've not tried this before but it seems that instead of hexagons in 2d space, you can think of the movement in 2d as volumes in 3d space where one axis is time. You're then intersecting two 3d polyhedra with (x,y,t) coordinates. If the two solid objects intersect then you want to find the minimum t value. You might simplify a little bit by converting all of B's coordinates to be in A's reference frame. I haven't implemented this but that's where I'd start. –  amitp May 24 '13 at 20:27

6 Answers 6

up vote 28 down vote accepted
+200

The solution is actually simpler than expected. The trick is to use Minkowski subtraction before your hexagon technique.

Here are your rectangles A and B, with their velocities vA and vB. Note that vA and vB aren't actually velocities, they are the distance traveled during one frame.

step 1

Now replace rectangle B with a point P, and rectangle A with rectangle C = A+(-B), which has dimensions the sum of the dimensions of A and B. The Minkowski addition properties state that collision between the point and the new rectangle occur if and only if collision between the original two rectangles occur:

step 2

But if rectangle C moves along vector vA, and point P moves along vector vB, a simple change of reference frame tells us it is the same as if rectangle C was still, and point P moved along vector vB-vA:

step 3

You can then use a simple box-segment intersection formula to tell where the collision occurs in the new reference frame.

The last step is to move back to the proper reference frame. Just divide the distance traveled by the point until the circled intersection by the length of vector vB-vA and you will get a value s such that 0 < s < 1. The collision happens at time s * T where T is the duration of your frame.

Comment by madshogo:
One HUGE advantage of this technique over the one in Mr Beast's own answer is that if there's no rotation, then the "Minkowski subtraction" A+(-B) can be computed once for all the subsequent timesteps!

So the only algorithm that takes time in all this (Minkowski sum, complexity O(mn) where m is the number of vertices in A and n the number of vertices in B) can be used only once, effectively making collision detection a constant-time problem!

Later, you can throw the sum away once you know for sure that A and B are in different parts of your scene (of your quadtree?) and won't collide anymore.

In contrast, Mr Beast's method requires quite a lot of computations at each time step.

Also, for axis-aligned rectangles, A+(-B) can be computed much more simply than by actually computing all the sums, vertex by vertex. Just expand A by adding the height of B to its height and the width of B to its width (one half on each side).

But all this only works if neither A nor B is rotating and if both are convex. If rotation there is or if you use concave shapes then you must use swept volumes/areas.
end of comment

share|improve this answer
4  
Looks like a rather interesting approach, however, I don't grasp it 100% yet, what happens when the object is really small and is moving between the two lines? i.imgur.com/hRolvAF.png –  API-Beast May 22 '13 at 17:39
    
-1: This method does not in any way allow you to be sure collision happens. It only allows you to be sure it doesn't happen, in the case where the segment and the extruded volume do not intersect. But it is entirely possible that they intersect and yet that there is no collision. What's wrong is the "Now you can use [...] simple segment-segment intersection to decide where the collision occurred" part. –  jrsala May 22 '13 at 17:58
2  
@madshogo You're right. I assumed that the timestep was small enough compared to object sizes that this wouldn't be a problem, but it's certainly not very robust in the general case. I'll look into fixing it. –  Sam Hocevar May 23 '13 at 9:09
    
@SamHocevar If you could revise the answer that would be great. –  API-Beast May 24 '13 at 14:39
1  
@LuisAlves yes and no… all the logic works, but you’ll have to replace vB-vA with g(t)-f(t) where f and g are A and B’s positions over time. Since this is no longer a straight line, you’ll have to solve a box — parametric curve intersection problem. –  Sam Hocevar Oct 26 at 12:22

First of all, in the case of axis-aligned rectangles, Kevin Reid's answer is the best and the algorithm is the fastest.

Second, for simple shapes, use relative velocities (as seen below) and the separating axis theorem for collision detection. It will tell you whether a collision happens in the case of linear motion (no rotation). And if there's rotation, you need a small timestep for it to be precise. Now, to answer the question:


How to tell in the general case whether two convex shapes intersect?

I'll give you an algorithm that works for all convex shapes and not just hexagons.

Suppose X and Y are two convex shapes. They intersect if and only if they have a point in common, i.e. there is a point x X and a point y ∈ Y such that x = y. If you regard the space as a vector space, then this amounts to saying x - y = 0. And now we get to this Minkowski business:

The Minkowski sum of X and Y is the set of all x + y for x ∈ X and y ∈ Y.


An example for X and Y


X, Y and their Minkowski sum, X+Y

Supposing (-Y) is the set of all -y for y ∈ Y, then given the previous paragraph, X and Y intersect if and only if X + (-Y) contains 0, that is, the origin.

Side remark: why do I write X + (-Y) instead of X - Y ? Well, because in mathematics, there is an operation called the Minkowski difference of A and B which is sometimes written X - Y yet has nothing to do with the set of all x - y for x ∈ X and y ∈ Y (the real Minkowski difference is a little more complex).

So we'd like to compute the Minkowski sum of X and -Y and to find whether it contains the origin. The origin is not special compared to any other point, so that to find whether the origin is within a certain domain, we use an algorithm that could tell us whether any given point belongs to that domain.

The Minkowski sum of X and Y has a cool property, which is that if X and Y are convex, then X+Y is too. And finding whether a point belongs to a convex set is much easier than if that set were not (known to be) convex.

We can't possibly compute all of the x - y for x ∈ X and y ∈ Y because there are an infinity of such points x and y, so hopefully, since X, Y and X + Y are convex, we can just use the "outermost" points defining the shapes X and Y, which are their vertices, and we'll get the outermost points of X + Y, and also some more.

These additional points are "surrounded" by the outermost ones of X + Y so that they do not contribute to defining the newly obtained convex shape. We say that they don't define the "convex hull" of the set of points. So what we do is that we get rid of them in preparation for the final algorithm that tells us whether the origin is within the convex hull.


The convex hull of X+Y. We have removed the "inside" vertices.

We therefore get

A first, naive algorithm

boolean intersect(Shape X, Shape Y) {

  SetOfVertices minkowski = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      minkowski.addVertice(x-y);
    }
  }
  return contains(convexHull(minkowski), Vector2D(0,0));

}

The loops obviously have complexity O(mn) where m and n are the number of vertices of each shape. The minkoswki set contains mn elements at most. The convexHull algorithm has a complexity that depends on the algorithm you used, and you can aim for O(k log(k)) where k is the size of the set of points, so in our case we get O(mn log(mn)). The contains algorithm has a complexity that is linear with the number of edges (in 2D) or faces (in 3D) of the convex hull, so it really depends on your starting shapes, but it won't be greater than O(mn).

I'll let you google for the contains algorithm for convex shapes, it's a pretty common one. I may put it here if I have the time.


But it's collision detection we're doing, so we can optimize that a lot

We originally had two bodies A and B moving without rotation during a timestep dt (from what I can tell by looking at your pictures). Let's call vA and vB the respective speeds of A and B, which are constant during our timestep of duration dt. We get the following:

and, as you point out in your pictures, these bodies do sweep through areas (or volumes, in 3D) as they move:

and they end up as A' and B' after the timestep.

To apply our naive algorithm here, we would only have to compute the swept volumes. But we're not doing this.

In the reference frame of B, B doesn't move (duh!). And A has a certain velocity with respect to B that you get by computing vA - vB (you can do the converse, compute the relative velocity of B in the reference frame of A).

Relative motion

From left to right: velocities in the base reference frame; relative velocities; computing relative velocities.

By regarding B as immobile in its own reference frame, you only have to compute the volume that A sweeps through as it moves during dt with its relative velocity vA - vB.

This decreases the number of vertices to be used in the Minkowski sum computation (sometimes greatly).

Another possible optimization is at the point where you compute the volume swept by one of the bodies, let's say A. You don't have to translate all of the vertices making up A. Only those that belong to edges (faces in 3D) whose outer normal "face" the direction of the sweeping. Surely you had noticed that already when you computed your swept areas for the squares. You can tell whether a normal is towards the sweeping direction using its dot product with the sweeping direction, which has to be positive.

The last optimization, that has nothing to do with your question regarding intersections, is really useful in our case. It uses those relative velocities we mentioned and the so-called separating axis method. Surely you know about it already.

Suppose you know the radii of A and B with respect to their centers of mass (that is to say, the distance between the center of mass and the vertex farthest from it), like this:

A collision can occur only if it is possible that the bounding circle of A meet that of B. We see here that it won't, and the way to tell the computer that is to compute the distance from CB to I as in the following picture and make sure it's bigger than the sum of the radii of A and B. If it's bigger, no collision. If it's smaller, then collision.

This doesn't work very well with shapes that are rather long, but in the case of squares or other such shapes, it's a very good heuristic to rule out collision.

The separating axis theorem applied to B and the volume swept by A, however, does tell you whether the collision happens. The complexity of the associated algorithm is linear with the sum of the numbers of vertices of each convex shape, but it is less magical when comes the time to actually handle the collision.

Our new, better algorithm that uses intersections to help detect collisions, but still not as good as the separating axis theorem for actually telling whether a collision happens

boolean mayCollide(Body A, Body B) {

  Vector2D relativeVelocity = A.velocity - B.velocity;
  if (radiiHeuristic(A, B, relativeVelocity)) {
    return false; // there is a separating axis between them
  }

  Volume sweptA = sweptVolume(A, relativeVelocity);
  return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));

}

boolean radiiHeuristic(A, B, relativeVelocity)) {
  // the code here
}

Volume convexHull(SetOfVertices s) {
  // the code here
}

boolean contains(Volume v, Vector2D p) {
  // the code here
}

SetOfVertices minkowskiMinus(Body X, Body Y) {

  SetOfVertices result = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      result.addVertice(x-y);
    }
  }
  return result;

}
share|improve this answer

I don't think using the 'hexagon' is all that helpful. Here's a sketch of a way to get exact collisions for axis-aligned rectangles:

Two axis-aligned rectangles overlap if and only if their X coordinate ranges overlap and their Y coordinate ranges overlap. (This can be seen as a special case of the separating axis theorem.) That is, if you project the rectangles onto the X and Y axes you have reduced the problem to two line-line intersections.

Compute the time interval over which the two lines on one axis intersect (e.g. it starts at time (current separation of objects / relative approaching velocity of objects)), and do the same for the other axis. If those time intervals overlap, then the earliest time within the overlap is the time of collision.

share|improve this answer
3  
You forgot your sketch. –  Byte56 May 20 '13 at 17:31
2  
@Byte56 No, I mean it's a sketch of an algorithm, not even pseudocode. –  Kevin Reid May 20 '13 at 23:57
    
Oh... I see. My mistake. –  Byte56 May 21 '13 at 0:34
    
This is actually the easiest method. I added the corresponding code to implement it. –  Pasha S May 22 '13 at 17:21

I don't think there is an easy way to calculate the collision of polygons with more sides than a rectangle. I would break it down into primitive shapes like lines and squares:

function objectsWillCollide(object1,object2) {
    var lineA, lineB, lineC, lineD;
    //get projected paths of objects and store them in the 'line' variables

    var AC = lineCollision(lineA,lineC);
    var AD = lineCollision(lineA,lineD);
    var BC = lineCollision(lineB,lineC);
    var BD = lineCollision(lineB,lineD);
    var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle());

    return (AC || AD || BC || BD || objectToObjectCollision);
}

illustration of objects' paths and end-states

Note how I ignore the start-state of each object as that should have been checked during the previous calculation.

share|improve this answer
3  
Problem with this is that if the sizes of the objects are a lot different, the smaller object can move inside the path of the large object without triggering a collision. –  API-Beast May 20 '13 at 15:53

Seperate Axis Theorem

The Seperate Axis Theorem says "If we can find a axis on which two convex shapes don't intersect then the two shapes are not intersecting" or more practicable for IT:

"Two convex shapes only intersect if they intersect on all possible axes."

For axis aligned rectangles there are exactly 2 possible axes: x and y. But the theorem isn't limited to rectangles, it can applied to any convex shape by just adding the other axes on which the shapes could intersect. For more details on the topic check out this tutorial by the developer of N: http://www.metanetsoftware.com/technique/tutorialA.html#section1

Implemented it looks like this:

axes = [... possible axes ...];
collision = true;
for every index i of axes
{
  range1[i] = shape1.getRangeOnAxis(axes[i]);
  range2[i] = shape2.getRangeOnAxis(axes[i]);
  rangeIntersection[i] = range1[i].intersectionWith(range2[i]);
  if(rangeIntersection[i].length() <= 0)
  {
    collision = false;
    break;
  }
}

Axes can be as represented as normalized vectors.

A range is a 1-Dimensional line. The start should be set to the smallest projected point, the end to the largest projected point.

Applying it to the "sweeped" Rectangle

The hexagon in the question is produced by "sweeping" the AABB of the object. Sweeping adds exactly one possible collision axis to any shape: the movement vector.

shape1 = sweep(originalShape1, movementVectorOfShape1);
shape2 = sweep(originalShape2, movementVectorOfShape2);

axes[0] = vector2f(1.0, 0.0); // X-Axis
axes[1] = vector2f(0.0, 1.0); // Y-Axis
axes[2] = movementVectorOfShape1.normalized();
axes[3] = movementVectorOfShape2.normalized();

So far so good, now we can already check if the two hexagon's intersect. But it get's even better.

This solution will work for any convex shapes (for example triangles) and any sweeped convex shapes (for example sweeped octagons). However the more complex the shape the less effective it will be.


Bonus: Where the magic happens.

As I said the only additional axes are the movement vectors. The movement is time multiplied by speed, so in a sense they aren't just space axes, they are time-space axes.

This means we can derive the time in which the collision could have happened from these two axes. For this we need to find the intersection between the two intersections on the movement axes. Before we can do this we need to normalize both ranges though, so we can actually compare them.

shapeRange1 = originalShape1.getRangeOnAxis(axes[2]);
shapeRange2 = originalShape2.getRangeOnAxis(axes[3]);
// Project them on a scale from 0-1 so we can compare the time ranges
timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]);
timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]);
timeIntersection = timeFrame1.intersectionWith(timeFrame2);

When I asked this question I kinda already accepted the compromise that there will be a few rare false positives with this method. But I was wrong, by checking this time intersection we can test if the collision "actually" happened and we can sort those false positives out with it:

if(collision)
{
  [... timeIntersection = see above ...]
  if(timeIntersection.length() <= 0)
    collision = false;
  else
    collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame
}

If you notice any errors in the code examples let me know, I haven't implemented it yet and thus was not able to test it.

share|improve this answer
1  
Congratulations on your finding a solution! But as I said before: just because the hexagons intersect doesn't mean there will be a collision. You can use your method to compute the collision time all you want, if there's no collision, it's not very useful. Second, you can use relative speeds so as to only have to compute 1 swept volume, and to simplify the computations when using the SAT. Finally, I have only a rough idea of how your "intersection time" trick works, because maybe you got your indices mixed up, seeing as shapeRange1 == shapeRange2 with your code, isn't it? –  jrsala May 24 '13 at 19:00
    
@madshogo Should make more sense now. –  API-Beast May 24 '13 at 19:03
    
I still don't understand how the range normalization thing works, but I guess that's because I need a picture. I hope it works for you. –  jrsala May 24 '13 at 20:21

As long as the swept areas are both closed (no gaps in the boundary formed by the edge-lines), the following will work (just reduce your collision tests to line-line and point-rect/point-tri):

  1. Do their edges touch?(line-line collisions) Check whether any edge-line of a swept area intersects with any edge-line of the other swept area. Each swept area has 6-sides.

  2. Is the small one inside the big one? (Use axis aligned shapes (point-rect & point-tri)) Re-orient (rotate) the swept-areas so that the larger one is axis-aligned and test whether the smaller one is internal (by testing whether any corner points (should be all or none) are within the axis-aligned swept area). This is done be decomposing your hex into tris and rects.

Which test you do first depends on the likelihood of each (do the most commonly occurring one first).

You may find it easier to use a swept bounding circle (capsule rather than hex) because it's easier to split it into two half-circles and a rect when it is axis-aligned. ..I'll let you draw the solution

share|improve this answer
    
Doesn't work if one of the rectangles is really tiny and moves within the space between two edge lines. –  jrsala May 22 '13 at 23:32
    
@madshogo I've just added to my response. Should be a complete solution now. –  axon May 22 '13 at 23:46
1  
"Use axis aligned shapes (point-rect & point-tri)": How do you even align a triangle or a "point-triangle" (whatever that means) with the axes? "so that the larger one is axis-aligned": how can you tell which one is larger than the other? Do you compute their areas? "This is done be decomposing your hex into tris and rects.": which hex? There are two. "(or upvote this response if you want me to illustrate it for you)": Are you serious?? –  jrsala May 23 '13 at 10:45
    
"How do you even align a triangle with the axes?" A: Align the path of the obj making the swept area. Pick an edge and use trig. "how can you tell which one is larger than the other?" A: For example, use the distance between two diagonally opposite points of the rect (middle of the hex). "which hex?" A: The big one. –  axon May 23 '13 at 22:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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