I'm in the process of making a 2D sprite-based game engine, and at the moment I'm working on making my collision detection scheme more realistic than simple bounding boxes/circles can provide. Specifically, I'm looking at using bounding polygons. I know that there are algorithms out there to test two convex polygons against each other, and I'm confident in my ability to partition an arbitrary polygon into a set of convex polygons (I'm also reasonably confident in my ability to generate a rough outline of a sprite given a black and white bitmask). However, I've heard tantalizing references of a collision detection scheme that works with concave polygons as well as convex polygons. These tantalizing references have turned up nothing for me on Google beyond some names: Lin and Canny. Does anyone know of an actual explanation of their algorithm that I could view (preferably, freely)? Am I better off just partitioning the polygons? Ultimately I want to have something more accurate than just bounding convex polygons, which is why I'm going to the trouble here. I've considered my other options and discarded them as either too inaccurate (bounding boxes, bounding spheres) or too expensive and simultaneously uninformative (per-pixel tests).

You don't really want the Lin-Canny algorithm. First, it doesn't deal with concave objects. Second, it has been superseded by V-Clip. However, that too would likely be overkill for your application.

The old-timer approach to performing "exact" 2D sprite collisions is to store a [minx, maxx] interval for each scanline of the sprite (and ditto [miny, maxy] interval for each, uh, "scancolumn") and then for the appropriate pairs of scanlines (and scancolumns) from each sprite see if the intervals overlap.

Note that this approach really represents the sprite as the sprite equivalent to a star-shaped polygon, so the interior cannot have holes with this approach, but that's generally what you want anyway. Overall, this solution is typically vastly better than the per-pixel test that is so overused for sprite collisions.

Lin-Canny works for convex polyhedrons.

Other schemes would be, to use a line intersection test + vertex-in-polygon. That would deal with non-convex geometry. That and a binary search time for the time of impact and accurate collision report.

Or use continuous collision detection, including angular motion.

Thanks for the input. The "scanline" approach sounds like it wouldn't give me surface normals, which is pretty much the entire reason I'm not using per-pixel detection (since at the moment, I'm after something that works before I'm after speed; "working" needs to give accurate collision information, though).

The line-intersection test method sounds good; I know how to test if lines intersect. I'm curious, though - how would you go about testing if a vertex is in a polygon? My thought was to find all lines that exist in the same vertical space as the vertex, then count the number of lines crossed to go from one (horizontal) side to that vertex. If it's even, then the vertex is outside, and vice versa. In other words:

For each vertex V_i = (x, y) in incoming sprite  For each line L_i = (v1, v2) in stationary sprite    If ((v1.y < y) and (v2.y > y)      If (L_i is to the left of V_i)        count++  if (count % 2)    V_i is outside polygon

This is potentially rather slow, though. Granted that I'll already be doing an N*M algorithm to test for line intersections (N and M being the number of lines in each polygon), tacking on an extra N*M for vertex containment seems excessively harsh. Then again, I did say that I'm going for accuracy over speed at the moment, and this seems the kind of thing that should be easily swapped out later on.

Thanks for the input, everyone!

Ah, how sneaky! You're adding additional problem constraints not present in your original post! BTW, I presume you meant you want a contact normal and not surface normals (like you wrote)?

At this point it would probably be a good idea if you were to fully describe the problem, without leaving any details out.

E.g. what do your sprite objects look like? Why are you determining that you need to represent them as concave polygon outlines? What are you intending to do once you have detected the collision of two objects? What information do you think you need for that? Do you think you need a continuous collision detection scheme, or are you planning on allowing objects to overlap, to resolve collisions later? Etc.

Interestingly, it is often the case that for a perfectly stated problem, the solution becomes obvious. At the very least, properly describing your problem is half the battle! (And it'll help us to help you.)

A good point on fully specifying the problem. I figured out many a baffling homework problem back in the day by writing out careful emails to my profs. Oftentimes I never needed to send the email! And by "surface normal" I mean the vector perpendicular to the edge that the sprite hit; I'm not sufficiently familiar with the terminology, I suppose.

Part of my problem is that I don't know how this engine is going to be used. I'm trying to write as fully general a 2D sprite engine as I can given my time constraints. So while I want the collision detection algorithm to be as fully general as possible, I can't know if my users will actually make use of the features that I'm making available. For myself, these are the features I want:

1) Accurate reflection of a ball that hits an arbitrarily-oriented surface.
2) Accurate handling of arbitrarily-shaped sprites.

The former requires that I be able to determine contact normals, and the latter requires something more rubust than a simple bounding polygon.

Once a collision is detected, I'll be moving the sprites so that they no longer intersect each other. This is a bit tricky on my end since I'll need to be able to figure out the behaviour of arbitrary scripted sprites, but it doesn't really enter into the specific problem here, beyond that I'll need to figure out some alpha such that (polygon_1 + alpha * velocity) no longer intersects polygon_2.

At the moment, I'm assuming a discretized collision detection scheme, but if there's a reasonable continuous one, that's fine too. My biggest problem at the moment is that I have a deadline in two weeks and several other things I'm working on at the same time. If worst comes to worst, though, I can just default to bounding box collisions; those satisfy neither of my desired features, but are sufficient for my advisor. If you hadn't figured it out yet, this is an independant-study project that's coming due in early May. Collision detection is the last big thing I need to implement.

If there's any more information I can provide, I'm more than happy to do so.

To be fair to Derakon, he already asked this before in the game programming forums, you probably missed the threads, but I kinda know what he is up to.

If you have such a tight deadline, you'll have to make compromises.

Discrete collision scheme would be fine for a sprite based engine. As for a compromise, I suggested you let the user decide what to do with overlapping pixels, probably using a simple callback function. THen the user will be able to say, average the overlapping pixels as a collison point approximation if he wished too, or do a 'step up' if the collision pixel is marked as a 'slope' pixel, ect...

If the collision area is too large, with too many overlaps, then the user should be clever enough to back-track the objects by himself and test again for a more accurate test. It's all his decision, not your problem.

If I was using a sprite based 2D engine, I would not expect anything more than just that. If people want a collision detection engine with physics, then they'll have to look elsewhere, since it's a completely different problem (per pixel collisions maybe not the best answers for a 2D rigid body engine).

then they can plug-in my stuff for convex body detection, and let them do the dirty work of calculating a suitable convex hull around the sprite.

I'm actually planning to automatically generate the hulls, by using an edge-detection filter run on a black and white bitmask, and then drawing the outline of that bitmask. I don't anticipate this being too much of an issue (I've done the edge-detection bit before, and I know conceptually how to draw outlines).

As far as the deadline goes, as I mentioned before I can always just settle for bounding-box collisions for the moment. These more detailed collisions are something I'm doing for myself. I'll implement them eventually; it'd just be nice to get them working inside of two weeks.

One idea that someone else came up with (in an entirely different community) was projecting the vertices of the polygon along the velocity vector of the sprite. This gives you a bunch of lines to test for intersection with the lines of the other polygon. Is there a particular reason why this wouldn't work?

Quote:Original post by oliii
Lin-Canny works for convex polyhedrons.

Other schemes would be, to use a line intersection test + vertex-in-polygon. That would deal with non-convex geometry. That and a binary search time for the time of impact and accurate collision report.

Or use continuous collision detection, including angular motion.

Now I'm curious here. I've been working away at the design I've currently decided on, and I discovered a way to avoid the binary search method you've suggested here. Here's a copy&paste from the brief writeup I did on the method I'm using. Check this out:



Here we see two intersecting lines, one moving at some velocity v. We can intuit that if one of these lines is going to slip off of the other line, then the last point of contact is going to be at a vertex. So what if we draw lines parallel to v and passing through one each of the vertices (call these vertices "anchors") and see how far it is from the anchor to the other line?


(The velocity lines were not meant to seem perpendicular to one of the line segments; it shouldn't matter)

Here we can see that the distance from two of the endpoints to the other lines are infinite, one has length a, and one has length b (where either the lengths have been scaled to fit v, or v is assumed to be a unit vector). In other words, if we add (a * v) to the endpoints of the line containing anchor 1, then said line will no longer intersect the long line. Or, if we add (b * v) to the endpoints of the line that contains anchor 2, then it will also not intersect. Equivalently, we could add (-b * v) to the line containing anchor 1 for the same effect (useful since we really only want to move one of the lines).

In the greater scheme of collision detection, we're testing a moving line against a stationary line. If the lines intersect, then we want to find the most negative fraction of v to add to the endpoints of the moving line to make it no longer intersect the stationary line. What's great about this is that we can just do tests over all lines, and only actually move the polygon when we've found the greatest possible fraction. There's no N*logN binary search time involved here. At least, assuming I didn't screw something up.

Is this basically the "continuous" detection scheme you mentioned in passing? Seems a lot easier than a binary search.

continuous would involve solving the equation of motions of the object using linear and angular velocity, so it's quite tricky and maths heavy. THe binary time search is an easier method to achieve the same thing (find the time of collision). Much easier to code, but less accurate.

for continuous collisions, think of vertices arcking towards edges. That could be reduced to a second degree equation. But then it gets a lot more complicated if both edges rotate in different directions and speed. You have to define a screwing motion, that involves root solving trigonometric equations, so quite nasty. You have to check out Stephan Redon's paper on continuous collision detection.

semi-continuous, with just the velocity would be roughly what you suggest. But you also have to remember that the objects rotate as well, and you can have overlaps (you can't guarantee a state where the objects are always separated or touching).

as for your idea, you can do something like that, in case lines intersect, find the minimum projection distance to separate lines along the velocity, and use that. When velocity is close to zero, you might have troubles though.

Also, in case of fast rotations, then it will all go potty, but that's always a problem, whatever method you choose.


but then, isn't all of that a bit OTT for a sprite engine?