4

I'm so used to working just with rectangles for collision detection that I'm a bit stumped right now. I'm working with diamond-like shapes, and for the past few hours, have been trying to figure out how to check for collision.

I tried checking to see if the first objects four points are inside the points of the second object, but that just makes a box (I think)

The reason why I feel like I'm having difficulty with this is because of the angles.

Gareth Rees
  • 64,967
  • 9
  • 133
  • 163
  • You can check to see if the line between two points in one shape intersects with the line between two points in the other shape. You can iterate through all adjacent nodes in the shapes. This will give the most accurate collision detection, unless the shapes are around. – bhavinp Nov 19 '10 at 15:23
  • @bhavinp I see; I need to figure out what would be the best way to check for line collision then. I'm assuming I'd have to use a slope of sorts? –  Nov 19 '10 at 15:41
  • @Robert Fratto Make a function to create a line segment using two points. Then make another function to test whether those line segments intersect. This should be simple linear algebra or you can probably find online resources to help with this. Then you just have to test adjacent points for each vertex for both shapes. – bhavinp Nov 19 '10 at 21:06
  • @Robert Fratto Note: One method I can think of is to create a line using the two points and then solving using a matrix. If you can find an API for matrix calculations, that would be helpful. Then if there is a solution to the matrix (there is an intersection), just check whether that intersection point is in the box. – bhavinp Nov 19 '10 at 21:10
  • Doing line-line intersection tests for all pairs of line segments is (a) inefficient and (b) it doesn't work in general: if one polygon is entirely contained in the other, then the polygons intersect without any of their line segments intersecting. – Gareth Rees Nov 19 '10 at 21:13
  • However, if you insist on solving this by line/line intersection, then [see this question](http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/). – Gareth Rees Nov 19 '10 at 21:14
  • While checking out some things in the game, I'll only need to check collisions from one side of the object. To check this, I used a slope between two points on the second line, and see if it matches up on the slope. (I also have it so that the slope is only between the two points on the second line) –  Nov 20 '10 at 01:47

1 Answers1

11

You're trying to collide a moving convex polygon (your "diamond") with another moving convex polygon, is that right? Something like this:

two moving diamonds

Your first step should be to transform the problem to an equivalent one in which one of the polygons is stationary:

one diamond moving with difference of velocities, other diamond stationary

Then you can transform the moving polygon into a "shaft" that covers the area swept by the moving polygon. This is straightforward to do: if the original polygon has n sides, then the shaft has n + 2 sides, with the extra two sides being the same length and direction as the movement vector. You find where to insert these new sides by sorting the vertices according to their component that's orthogonal to the movement vector, and inserting new sides at the maxima.

the moving polygon transformed to a shaft

Now you've reduced the problem to static polygon against static polygon. Taking a look at the handy table of collision algorithms courtesy of realtimerendering.com, and following the references, we can see that we need to use the separating axis test, for example as described in section 3 of this paper by David Eberly.

In two dimensions, two convex polygons fail to intersect if we can find a separating axis, a line such that one polygon falls on one side of the line, and the other polygon on the other:

two convex polygons and an axis that separates them

If we are given a direction, we can easily discover if there exists a separating axis that runs in that direction, by projecting the two polygons onto a line running perpendicular to that direction, and looking to see whether the projections are disjoint:

two convex polygons projected onto a line are disjoint, showing the existence of a separating axis

How do we know which direction the separating axis will run in? Well, if any separating axis exists, then there's one that runs parallel to one of the sides of one of the convex polygons (see Eberly, page 3). So there's only a small set of directions to check, and if you've checked them all without finding a separating axis, then the two polygons intersect (and hence the original moving objects collide).

There are lots of refinements and optimizations you can make, certainly not limited to these:

  1. Before doing the full moving polygon/polygon test, do a simpler test like circle/circle so that you can reject easy cases quickly.
  2. Use some kind of spatial partitioning scheme like quadtrees so that you only test objects that are close enough that they might collide.
  3. "Caching witnesses" — if a line separates two objects at time t, it's likely that it continues to separate them at time t + δ, so it can pay to remember the separating axis you found and try it first next time (see Rabbitz, "Fast Collision Detection of Moving Convex Polyhedra" in Graphics Gems IV).

But don't worry too much about optimizing: get it right first in the confidence that you'll be able to speed it up later.

Gareth Rees
  • 64,967
  • 9
  • 133
  • 163