jump to navigation

Line Segment Intersection (Update) February 23, 2010

Posted by Jesse in : Game Development , trackback

I’m not sure why, but lately there’s been a lot of interest in the post I wrote about line segment intersection. I get emails about it pretty regularly, and that post has the most comments of anything I’ve written here. Today, a comment was posted explaining that there’s a flaw in my code. The code cannot tell when two line segments are coincident, but not overlapping. There’s a post on Stack Overflow which demonstrates a solution to this problem.

However, since I’m mostly interested in game development, I think we can do better. In most games, we’re not often interested in the intersection between simple line segments. I’d think that line segments would be a less common case than the collision and intersection of polygons. And if our solution for polygons also happens to work for the more rare case where we’re interested in line segments, awesome!

The method I use relies on the separating axis theorem. The separating axis theorem states that if there exists a line that upon which the projection of two convex polygons do not overlap, then they are not intersecting. This basically boils down to the idea that if you can draw a line between two objects, then they don’t intersect. (Which seems pretty obvious, really.)

I’m not going to dig into explaining the math behind SAT, but I’ve written a simple demo showing that this works for line segments (even coincident lines) as well as polygons. The code is copied from some of my old test code, and is mostly untested and completely unoptimized. It might be useful for some experimentation, though. You’re free to use it in any way you wish. Download here. (The included project requires XNA Framework version 3.1.)

If you’d like to learn more about SAT, here are a few links to get you started:
SAT on Wikipedia
Metanet’s N Tutorials
David Eberly’s Paper on SAT

A few screens from my test app. Blue background indicates no collision, while red shows there is a collision.





Comments»

no comments yet - be the first?