Thread: Collision detection improvements

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    1

    Collision detection improvements

    <<< Split from dead thread Programming Collision Detection - see the rules please >>>
    Does anybody know about other methods to reduce the number of collision test? What are the common methods to detect collision precisely and implement a realistic collision response which can handle point-pint interaction forces or surface friction forces.

  2. #2
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Hey, I'm about to start a 2d simulation program...and thought of solving the said problem in this way..
    1.Calculate the vector distance between the CM s of the objects in question....say x
    2.Let the extents of either body in *that direction be a & b
    3. if(x<=(a+b) <collision occurs>
    ....Any comments about how feasible it is?...I thought that it'd have accurate results ...But would it be too expensive?
    Last edited by manasij7479; 05-16-2011 at 08:50 AM.

  3. #3
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Quote Originally Posted by Sunbel View Post
    Does anybody know about other methods to reduce the number of collision test? What are the common methods to detect collision precisely and implement a realistic collision response which can handle point-pint interaction forces or surface friction forces.
    Split level into sectors (if that's what you mean). For example, if your map's size is, lets say, 20000x10000 points, you can create 100x50 square sectors (each of 200x200 points). If an object A occupies 2 sectors (10;10) and (10;11) and another object B occupies also 2 sectors (10;11) and (11;11), there is a possibility that they collide in the sector (10;11). Access to sector is O(1). You pick only these objects, which are likely to collide, no matter how many objects are on the other edges of the map.

    The problem might appear when your map grows/shrinks dynamically.

  4. #4
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    There are several optimizations you can do when collision testing to eliminate the need for an O(n^2) list. One of them is to separate the world into static and dynamic objects. Only test dynamic objects against other static objects. The list of dynamic objects is sure to be less than the number of static objects. Combine this with the aforementioned sectorized approach and/or a BSP or Quad-tree spatial data structure (depending on the type and usage of the world) as well as the common trivial rejection tests like sphere, AABB, OOBB, swept sphere, swept AABB (separating axis theorem) and you should be able to get good results.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Collision detection
    By jack_carver in forum C Programming
    Replies: 5
    Last Post: 02-08-2010, 06:52 AM
  2. Collision Detection
    By Grantyt3 in forum C++ Programming
    Replies: 3
    Last Post: 09-30-2005, 03:21 PM
  3. Collision Detection
    By cboard_member in forum Game Programming
    Replies: 2
    Last Post: 08-06-2005, 12:14 PM
  4. Collision Detection.
    By zergdeath1 in forum C++ Programming
    Replies: 5
    Last Post: 11-21-2004, 05:28 PM
  5. collision detection
    By tHaPuTeR in forum Game Programming
    Replies: 11
    Last Post: 09-22-2001, 10:53 AM