Collision Test - 2D

This is a discussion on Collision Test - 2D within the Game Programming forums, part of the General Programming Boards category; So, the counterclockwise function tells whether points A, B, and C are in counterclockwise order. IE, if you graphed the ...

  1. #16
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    So, the counterclockwise function tells whether points A, B, and C are in counterclockwise order. IE, if you graphed the XY coordinates of times on a lock, the points found at 11, 5, and 3 would be counterclockwise, while the points found at 11, 3, and 5 would not.

    Based off the ordering of points relative to eachother, you can tell if lines intersect.

    To be honest, I found this algorithm on a mailing list posting or something years ago, and haven't thought about it too much since (aside from the fact that it works). It kind of hurts my brain a little.
    Programming Your Mom. http://www.dandongs.com/

  2. #17
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,334
    > If the asteroid is within the box, then it does circle collision test.
    If you're going for the full accuracy test as well, then I'd think I'd skip the circle test.

    The amount of space which is inside the bounding box isn't going to be that great. The amount of space which is inside the circle, but outside the polygon is going to be even less.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #18
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    Hmm, Thanks Norman, I'll work on it.

    Quote Originally Posted by Salem View Post
    > If the asteroid is within the box, then it does circle collision test.
    If you're going for the full accuracy test as well, then I'd think I'd skip the circle test.

    The amount of space which is inside the bounding box isn't going to be that great. The amount of space which is inside the circle, but outside the polygon is going to be even less.
    Yeah, the point of that was to avoid the distance formula as much as possible. Now though, I'm thinking maybe just do the box, then if the asteroid is within the box do line by line. No circle test at all. That's what you were thinking, right?

    EDIT: Didn't see the line directly under the quote =P. Thanks though
    Last edited by IdioticCreation; 05-21-2007 at 07:47 PM.

  4. #19
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    Quote Originally Posted by Salem View Post
    Code:
    if ( ship.right < roid.left || ship.left > roid.right ||
          ship.top < roid.bottom || ship.bottom > roid.top ) {
      // no overlap
    } else {
      // overlap
    }
    Why omit the circle test and not omit the box test? With the above method, each frame you execute, for example, this for the collision test:

    Code:
    ship.right = shipX + 0.6f;
    ship.left = shipX - 0.6f;
    ship.top = shipY - 0.6f;
    ship.bottom = shipY + 0.6f;
    roid.right = roidX + 0.8f;
    roid.left = roidX - 0.8f;
    roid.top = roidY - 0.8f;
    roid.bottom = roidY + 0.8f;
    
    if ( ship.right < roid.left || ship.left > roid.right ||
          ship.top < roid.bottom || ship.bottom > roid.top ) {
      // no overlap
    } else {
      // overlap
    }
    in which you do 8 additions/subtractions, 4 comparisions, and 3 logical operations.
    If you use the optimized circle test, your code would be like this:
    Code:
    dx = roidX - shipX;
    dx *= dx;
    dy = roidY - shipY;
    dy *= dy;
    if( dx + dy - shipConstant - roidConstant)
    {
      //overlap
    }
    in which you need 5 additions/subtractions, 2 multiplications and 1 comparision.
    Now what would be faster?

  5. #20
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,584
    Because when a circle test is off, it's way off. A box normally can contain the object much better than a circle. A circle or sphere test is usually used for a very quick trivial rejection test because it's simple and quick.

  6. #21
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,334
    > Why omit the circle test and not omit the box test?
    For roughly the same amount of geometric space, the box test is far more efficient (each comparison eliminates ~25&#37; of possible objects). After just 4 comparisons, there isn't much left to deal with.

    Besides, if your box is rectangular, there's no difference in performance, but if you were to implement a true elliptical test, then that gets much more interesting in a hurry.

    > in which you do 8 additions/subtractions, 4 comparisions, and 3 logical operations.
    In any reasonable implementation, the bounding box of the ship would be calculated just once.

    Plus, as you should know, the logical operations will short-circuit, so there is less than 4 compares and 3 logical ops per test on average.

    Since you can re-use the bounding box of an asteroid to work out say whether to bother drawing it at all, even that may be a freebie as well, in which case the amount of work boils down to a couple of compares on average.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #22
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    So you also think that circle test is quicker.
    >> A box normally can contain the object much better than a circle.
    But this guy is testing collisions between asteroids and a triangle, and circles are more accurate for that, if you look at his program.
    Don't call me stupid.

  8. #23
    Registered User pronecracker's Avatar
    Join Date
    Oct 2006
    Location
    netherlands
    Posts
    158
    Quote Originally Posted by Salem View Post
    In any reasonable implementation, the bounding box of the ship would be calculated just once.
    As the x and y change every frame, the bounding box must also be recalculated, as the above code does.
    Also, those asteroids are closer to circles than to rectangles.

    Quote Originally Posted by Salem View Post
    Plus, as you should know, the logical operations will short-circuit, so there is less than 4 compares and 3 logical ops per test on average.
    Sorry, I never heard about this.

    Edit: I think I know what you mean, I just didn't recognize the word "short-circuit".
    Last edited by pronecracker; 05-25-2007 at 10:25 AM.
    Don't call me stupid.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 2D in directX
    By fighter92 in forum Game Programming
    Replies: 6
    Last Post: 01-25-2009, 10:23 AM
  2. Integer Emulation
    By Elysia in forum C++ Programming
    Replies: 31
    Last Post: 03-18-2008, 01:03 PM
  3. Newbie needs help..
    By xpress urself in forum C++ Programming
    Replies: 3
    Last Post: 07-26-2007, 07:22 PM
  4. collision detection
    By DavidP in forum Game Programming
    Replies: 2
    Last Post: 05-11-2002, 01:31 PM
  5. Replies: 4
    Last Post: 05-03-2002, 09:40 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21