2D Math library for simple primitives

Discussion in 'Game Development (Technical)' started by zoombapup, Sep 27, 2006.

  1. zoombapup

    Moderator Original Member

    Joined:
    Nov 25, 2004
    Messages:
    2,890
    Likes Received:
    0
    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?
     
  2. KatieL

    Original Member

    Joined:
    Nov 2, 2005
    Messages:
    44
    Likes Received:
    0
    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...
     
  3. zoombapup

    Moderator Original Member

    Joined:
    Nov 25, 2004
    Messages:
    2,890
    Likes Received:
    0
    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.
     
  4. jetro

    Original Member

    Joined:
    Jan 21, 2005
    Messages:
    130
    Likes Received:
    0
  5. stiill

    Original Member

    Joined:
    Feb 13, 2006
    Messages:
    108
    Likes Received:
    0
    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.
     
  6. HairyTroll

    Original Member

    Joined:
    Jul 29, 2004
    Messages:
    583
    Likes Received:
    0
    There are the tutorials over at Metanet. They give an overview of how they did their physics and collision detection for 'N'.

    - Luke
     
  7. Applewood

    Moderator Original Member Indie Author

    Joined:
    Jul 29, 2004
    Messages:
    3,859
    Likes Received:
    2
  8. HairyTroll

    Original Member

    Joined:
    Jul 29, 2004
    Messages:
    583
    Likes Received:
    0
    Seems not. However this mirror seems OK. Not sure how much of the original content is mirrored however.
     
  9. Applewood

    Moderator Original Member Indie Author

    Joined:
    Jul 29, 2004
    Messages:
    3,859
    Likes Received:
    2
    Good catch!

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

    Moderator Original Member

    Joined:
    Nov 25, 2004
    Messages:
    2,890
    Likes Received:
    0
    Thanks guys.. I completely forgot I had that Erikson book.. I'll have a go through that.
     
  11. Bad Sector

    Original Member

    Joined:
    May 28, 2005
    Messages:
    2,742
    Likes Received:
    3
    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.
     
  12. svero

    Moderator Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    3,393
    Likes Received:
    5
    Arbitrary polygon collision in 2d is actually very tricky stuff. Its non-trivial.
     
  13. Bad Sector

    Original Member

    Joined:
    May 28, 2005
    Messages:
    2,742
    Likes Received:
    3
    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 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...).
     
  14. svero

    Moderator Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    3,393
    Likes Received:
    5
    I guess it depends what you mean by trivial. But compared to things like circle plane and circle circle collisions its a bit tricky.
     
  15. jankoM

    Indie Author

    Joined:
    Feb 17, 2005
    Messages:
    1,003
    Likes Received:
    0
    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.
     
  16. esmelon

    esmelon New Member

    Joined:
    Aug 28, 2006
    Messages:
    98
    Likes Received:
    0
  17. Dan MacDonald

    Moderator Original Member Indie Author

    Joined:
    Jul 26, 2004
    Messages:
    1,424
    Likes Received:
    0
    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.
     
  18. soniCron

    Indie Author

    Joined:
    May 4, 2005
    Messages:
    3,664
    Likes Received:
    0
    I don't think anybody's debating that, Dan. ;)
     
  19. Enimeny22

    Enimeny22 New Member

    Joined:
    Thursday
    Messages:
    1
    Likes Received:
    0
    I here because of the same question. It is important for my homework.
     

Share This Page

  • About Indie Gamer

    When the original Dexterity Forums closed in 2004, Indie Gamer was born and a diverse community has grown out of a passion for creating great games. Here you will find over 10 years of in-depth discussion on game design, the business of game development, and marketing/sales. Indie Gamer also provides a friendly place to meet up with other Developers, Artists, Composers and Writers.
  • Buy us a beer!

    Indie Gamer is delicately held together by a single poor bastard who thankfully gets help from various community volunteers. If you frequent this site or have found value in something you've learned here, help keep the site running by donating a few dollars (for beer of course)!

    Sure, I'll Buy You a Beer