2D Math library for simple primitives

[zoombapup]

Hey guys.. I am sure someone has come across this before.

I'm looking for a library for simple 2D primitives (line, circle, point, polygon) intersection tests.

I was about to roll my own, but I thought I'd set an example and see if anyone knew of a good quality one already.

I'm mainly after a few key things:


Circle/Line intersection (returns collision point, time and normal)
Line/Line intersection (same)
Swept circle/line
Point in/out/on line/poly test


I think thats about it. Basically its a mixture of tests for doing really simple 2D scenes. Oh, forgot poly/poly intersection test I guess.. and maybe swept versions of same.

Anyone seen such a beast?

[KatieL]

Have a flick through some of the "Maths for Games Developers" type books; there's at least one which has a 2D maths chapter that includes most of the tests you've mentioned {I could be more specific if my entire library weren't in storage 90 miles away...}.

I think "3D Game Engine Design" by Eberly might have 2D versions as well.

They're not really something that needs a whole library -- the routines are pretty short and you can type them in out of the books...

[zoombapup]

I always found many of those books to be a little bit stale.. but yeah, I've got those so I'll dig through them.

I'll likely just write my own library for my students if there isnt an existing one out there.

[jetro]

I definitely recommend the Real-Time Collision Detection (http://www.realtimecollisiondetection.net/) book by Christer Ericson.

[stiill]

I just rolled my own collision handling system last week.

Right now it's only swept circle vs. swept circle, because that's all I need. The hardest bit was handling the results of the collisions: I allow slippery collisions, and plan to add elastic and inelastic as well. If it were just a collision detection system, it would have been significantly easier.

The first system took me a day to code. That was enough to help me figure out where all of my assumptions were wrong, then I rewrote it in two days following. It's not optimized, though, so I will probably end up spending more time on it with help from a book or two. I also do contract work, so these weren't full work days.

Obviously, it's going to be better to find an existing, optimized system rather than roll your own. If you do get stuck rolling your own, though, it's not so bad.

My code's not as clean as I'd like, and like I said it's strikingly non-optimal, but I can send the code your way if you want to take a look. I'm planning on writing up some of my learnings on my blog soon.

[HairyTroll]

There are the tutorials over at Metanet (http://www.harveycartel.org/metanet/tutorials.html). They give an overview of how they did their physics and collision detection for 'N'.

- Luke

[Applewood]

ftp://x2ftp.oulu.fi

There's some great old stuff on there. Assuming it's still alive.

[HairyTroll]

ftp://x2ftp.oulu.fi

There's some great old stuff on there. Assuming it's still alive.

Seems not. However this mirror (http://ftp.lanet.lv/ftp/mirror/x2ftp/) seems OK. Not sure how much of the original content is mirrored however.

[Applewood]

Good catch!

I'm just downloading the index again. Brings back good memories :D

[zoombapup]

Thanks guys.. I completely forgot I had that Erikson book.. I'll have a go through that.

[Bad Sector]

I think "3D Game Engine Design" by Eberly might have 2D versions as well.

Nope, it's all 3D (i have that book) and unless you have some high degree in maths or time and patience to learn the required math before reading the first (okay, i'm exaggerating, the second) page of this book, don't. I know, i had to put that book on my bookshelf for around a year before being able to read it :-/.

But doing circle, line, polygon, etc tests in 2D are very easy to do.

[svero]

But doing circle, line, polygon, etc tests in 2D are very easy to do.

Arbitrary polygon collision in 2d is actually very tricky stuff. Its non-trivial.

[Bad Sector]

Arbitrary polygon collision in 2d is actually very tricky stuff. Its non-trivial.

I'm not sure what you mean with "collision" here, but i don't think that figuring out if two arbitrary polygons collide is that hard. All you have to do is to check if the polygon edges of one polygon intersect with the edges of the other or the one polygon points lie inside the other. If you need contact points, in the first case the points are the intersection points and in the second case, the points are the inner polygon's points.

I can't think of any other "polygon collision" case and the above cases are trivial and very documented.

Yet, of course, if you don't know where to find information about that and/or how it's done it seems trivial. I didn't knew, but it took my sister (who has only high school level math knowledge - i also supposed to have, but while i was at school i never was interested in math :-P) only five minutes to explain me (and if you don't have a sister which is good in math, you can always ask Google about algebra or visit PurpleMath (http://www.purplemath.com/) and read the articles there).

But when you learn, you'll see that it wasn't that hard (if i only paid some attention to those math classes...).

[svero]

I guess it depends what you mean by trivial. But compared to things like circle plane and circle circle collisions its a bit tricky.

[jankoM]

There is a bunch of code in form of about 10 tutorials from basic collision testing to 2d rigid bodies physics somewhere... search under polycoly or something like that.

[esmelon]

Look at http://ggt.sourceforge.net

[Dan MacDonald]

Circle Circle collisions? you mean like adding up the length of the raidus from each circle and then seeing if it's greater then the distance between the centers of both circles?

I always found that to be one of the more trivial collision tests.

[soniCron]

I don't think anybody's debating that, Dan. ;)