Three body collisions

D.V.D

Make a wish
Reaction score
73
Hey guys I made a rigid body dynamics system but it suffers from major issues when theres more than 2 bodies colliding at once. The way it works is that it finds which objects are colliding with eachother and puts them into pairs. Each pair being 2 objects colliding with eachother but this doesn't seem to always work. When the three objects collide, they pass through eachother and the program starts to lag intensively because of calculations it does when objects are moving inside of eachother. I was wondering, since all my objects are boxes with a fixed radius, do I need to push the objects back a bit so that they aren't overlapping, and then do the momentum calculations? Whats the way of solving such a problem?

TestStack is a list of all the objects in my engine. TEST_COUNT is the number of objects in my engine. Ispointinbox is the function used to calculate if a point is in a box, I tested it around and it works since no rotation transformations are put on the box. If source code for this function is needed, Ill provide it.

Code:
colstack CollisionStack;
 
void PhysicsPipeline::update () {
    for ( int i=0; i < TEST_COUNT; i++ ) {
        // Update position of boxes
        TestStack[i].updatepos();
    }
    // For every object object in test count
    for ( int i=0; i < TEST_COUNT; i++ ) {
        // Check collision with every other object in collision
        for ( int j=0; j < TEST_COUNT; j++ ) {
            // If objects being checked aren't the same object
            if ( j != i ) {
                // Add to pair of collisions
                CollisionStack.add(TestStack[i], TestStack[j]);
            }
        }
    }
    for ( int i=0; i < CollisionStack.current-1; i++ ) {
        // Check for Collision of every vertice of the coliding boxe
        bool hascollided = false;
        if ( CollisionStack.pair1[i].BoundingBox.ispointinbox(CollisionStack.pair2[i].BoundingBox.NW) == true ) {
            collide(0,1);
            hascollided = true;
        }
        if ( CollisionStack.pair1[i].BoundingBox.ispointinbox(CollisionStack.pair2[i].BoundingBox.NE) == true && hascollided == false ) {
            collide(0,1);
            hascollided = true;
        }
        if ( CollisionStack.pair1[i].BoundingBox.ispointinbox(CollisionStack.pair2[i].BoundingBox.SW) == true && hascollided == false ) {
            collide(0,1);
            hascollided = true;
        }
        if ( CollisionStack.pair1[i].BoundingBox.ispointinbox(CollisionStack.pair2[i].BoundingBox.SE) == true && hascollided == false ) {
            collide(0,1);
            hascollided = true;
        }
    }
    CollisionStack.clear();
}

This is the collision function. It works by saying that the object with the most momentum in a collision will lose momentum while the object with the least momentum gains momentum. This is described with the proportion variables. The debug function simply prints a variable.

Code:
inline void collide (int i, int j) {
    //FIX LATER!!
    //if ( deb == true ) {
    Vector2f m1 = Vector2f(TestStack[i].mass * TestStack[i].vel.x, TestStack[i].mass * TestStack[i].vel.y);
    Vector2f m2 = Vector2f(TestStack[j].mass * TestStack[j].vel.x, TestStack[j].mass * TestStack[j].vel.y);
   
    cout << "m1: " << m1.x << ", " << m1.y << endl;
    cout << "m2: " << m2.x << ", " << m2.y << endl;
 
    double mag1 = sqrt( (m1.x*m1.x) + (m1.y*m1.y) );
    double mag2 = sqrt( (m2.x*m2.x) + (m2.y*m2.y) );
 
    debug("mag1",mag1);
    debug("mag2",mag2);
   
    double angle1 = radtodegree(atan(m1.y/m1.x));
    double angle2 = radtodegree(atan(m2.y/m2.x));
    if ( m1.x < 0 ) {
        angle1 -= 180.0f;
    }
    if ( m2.x < 0 ) {
        angle2 -= 180.0f;
    }
 
    debug("angle1",angle1);
    debug("angle2",angle2);
   
    double proportion1, proportion2;
   
    if ( mag1 > mag2 ) {
        proportion1 = mag2/mag1;
        proportion2 = 1.0f - proportion2;
    }
    if ( mag1 < mag2 ) {
        proportion2 = mag1/mag2;
        proportion1 = 1.0f - proportion2;
    }
    if ( mag1 == mag2 ) {
        proportion1 = 0.50f;
        proportion2 = 0.50f;
    }
 
    debug("proportion1",proportion1);
    debug("proportion2",proportion2);
   
    double mag1t = mag1*proportion1;
    double mag2t = mag2*proportion2;
 
    debug("mag1t",mag1t);
    debug("mag2t",mag2t);
   
    mag1 -= mag1t;
    mag2 -= mag2t;
    mag1 += mag2t;
    mag2 += mag1t;
   
    debug("mag1",mag1);
    debug("mag2",mag2);
 
    debug("a1",degreetorad(angle1));
    debug("a2",degreetorad(angle2));
 
    debug("Angle1C",cos(degreetorad(angle1)));
    debug("Angle1S",sin(degreetorad(angle1)));
    debug("Angle2C",cos(degreetorad(angle2)));
    debug("Angle2S",sin(degreetorad(angle2)));
 
    TestStack[i].vel.x = mag1 * cos(degreetorad(angle1)) * -1.0f / TestStack[i].mass;
    TestStack[i].vel.y = mag1 * sin(degreetorad(angle1)) * -1.0f / TestStack[i].mass;
    TestStack[j].vel.x = mag2 * cos(degreetorad(angle2)) * -1.0f / TestStack[j].mass;
    TestStack[j].vel.y = mag2 * sin(degreetorad(angle2)) * -1.0f / TestStack[j].mass;
 
    cout << "Ivel: " << TestStack[i].vel.x << ", " << TestStack[i].vel.y << endl;
    cout << "Jvel: " << TestStack[j].vel.x << ", " << TestStack[j].vel.y << endl;
    deb = false;
    //}
}
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
Whats the way of solving such a problem?

There are lots of methods of resolving collisions. However, the more correct ways (calculating the exact collision times in chronological order and performing collision resolution) aren't always practical ways.

First off: If you have bodies that can't move (e.g. the walls of a level), you have to accept the possibility that there is no solution to resolve a collision.

One method that works if all objects CAN move, is to perform your pair-wise collision resolution in a while loop, until there are no collisions. However, this can be slow (such as in the classic example of a tower of boxes stacked on top of each other, especially if the top box collisions are resolved before the bottom ones). Note that if you have bodies that can't move, this method could potentially result in an infinite loop.

Another method would be to allow intersections of objects after collision, and instead of moving objects, simply change each object's velocity so that each object will bounce away from the other object. By making this velocity proportional (e.g. square of the distance from the penetrating point to the edge) to how far the object has penetrated the other, this naturally provides a force to repel objects (objects moving fast will penetrate further, thus repelling the two objects with greater velocity). In addition it is realistic, in that objects in nature work more like springs than truly rigid objects.
 

D.V.D

Make a wish
Reaction score
73
Why would there be cases where you can't resolve a collision? What would be such a case?

Hmm, I want to add the penetration but if you have a object such as a circle, how exactly would you find the exact or close point of intersection (where the object began penetrating the other object)? Would you need to step back your object or is there some kind of formula to do this that people have developed?

And I've stumbled upon a formula that Im using and I got it working but its a little odd. Since its a square root, you have plus and minus. When exactly do you use plus and when minus? (Second post) http://www.sciforums.com/showthread.php?96101-Momentum-loss-in-an-elastic-collision
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
Why would there be cases where you can't resolve a collision? What would be such a case?

Actually, I take back the constraint I gave, that it's possible to not be able to solve when you have immobile objects. It's still quite easy to get a scenario that cannot be solved:

xtq9s.png


This adds constraints (objects cannot be colliding when they are created, for one, or objects cannot be rigid). Even if the bottom side of the rectangle is gone, you would have to do several iterations of the blue and orange ball pushing each other horizontally and partially vertically for the orange ball to finally have enough room, which is again, slow.

Hmm, I want to add the penetration but if you have a object such as a circle, how exactly would you find the exact or close point of intersection (where the object began penetrating the other object)? Would you need to step back your object or is there some kind of formula to do this that people have developed?

It's very similar to stepping back (you have to perform calculations to find out 'how far'). Essentially, if you use the relative velocity V (treat object A as 'not moving' and subtract its velocity from object B's velocity to get the relative velocity V), you simply have to find what distance D to move object B back in direction -V for object B to no longer be colliding (depending on what kind of objects you have you use a formula). Note that you do not actually move the objects, you only find out how far they have already penetrated.

Without moving This distance D is the value you use in a formula to find out how much force to apply to each object (on object A this force is applied in direction V, and on object B it is applied in direction -V).

And I've stumbled upon a formula that Im using and I got it working but its a little odd. Since its a square root, you have plus and minus. When exactly do you use plus and when minus? (Second post) http://www.sciforums.com/showthread.php?96101-Momentum-loss-in-an-elastic-collision

I don't have time right now to go and analyze the formula (10m late as it is). However, you can derive the formula if you know the physics for conservation of momentum.
 

D.V.D

Make a wish
Reaction score
73
Ohh I see but the impossible situation is more of a error because your creating objects of certain radius in a area where they cannot fit.

Yes but what would the formula to find the distance D be? Is there a site that shows a tutorial for this kind of stuff because I've been having trouble finding some of this stuff online.

Hmm I see, well the formula already conserves momentum and energy its just that it creates a quadratic function which you solve for using the quadratic formula. However, I think I found another site that has a more programmer friendly way of calculating impulses from collisions so I'll check that out.
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
Ohh I see but the impossible situation is more of a error because your creating objects of certain radius in a area where they cannot fit.

True. However, in some situations where there IS room (but just barely), be prepared for the possibility of extremely long loops (this is the point I was trying to make in the paragraph after the image). The point is that even if the chance is small to get in situations where there is barely enough room, there is still the possibility (in worst case scenarios) that your physics engine could take seconds, even minutes to resolve all collisions in a single frame. The amount of time required to resolve all collisions between N objects isn't constant, unlike in the other method of collision resolution, where it is O(N^2).

Yes but what would the formula to find the distance D be? Is there a site that shows a tutorial for this kind of stuff because I've been having trouble finding some of this stuff online.

Again, this depends on how you're representing the two objects (are they circles? AABB? polygons? rotated bounding boxes? etc).

Example 1: If they are both circles, it is as simple as solving for the time when the distance between the two circles is A_r + B_r (radius of A + radius of B). Look up circle-circle collision.

Example 2: If they are both axis aligned bounding boxes (AABB), you have a similar calculation, though you must do it in both horizontal and vertical direction (to find out which side was 'hit' first). Try looking up AABB collision resolution/response.

Example 3: If they are both convex polygons, you can detect collisions with Separating Axis Theorem, and find the distance D by projecting A's vertices inside B's polygon onto the various lines making up B's edges, and find the longest time
 

D.V.D

Make a wish
Reaction score
73
Hmm okay I seem to get it then. I just went through exactly what my code does because its for my physics project in grade 12 and I realized how ridiculously inefficient it is :p Although I really wanna do the overlapping implementation, I still got to fix my collision detection which is complete shit as of now haha.

Great links, I kind of skimmed through them and I sorta get what they're saying. Really appreciate the links btw, ill update this post once I fix up a bit of the current problems with the efficiency as I found a really good site for simple collision calculations that actually worked this time :) So the code works, just hogs too much resources and isn't exactly dynamic.
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
Glad I was able to help some, physics engines are no simple task, and I've spent many hours on them. :p I have a project where I attempted to have 'perfect' a-priori (predictive) collision detection and objects being represented as a list of connected vertices (even less restrictive than concave polygons!). Feel free to ask more questions sometime! :)

While I was able to resolve collisions, predict them, and simulate objects bouncing around, the engine was far from fast (written in python), and its method of collision resolution resulted in severe lag/crashes any time objects came to rest upon other objects.

The more accurate engines tend to be a lot slower. The engines written for games like Super Mario Bros. tend to have lots of hacks in them to increase speed (through approximation), and are far from being realistic.
 

D.V.D

Make a wish
Reaction score
73
Oh man, I can imagine the troubles of writing such a program. Predicting collisions is quite a complex task especially if you have walls and such in the way, atleast in my mind.

With collisions that get more accurate like your, since 1 CPU core won't cut it, I think its better to either use a quad core or write the code in CUDA/OpenCL to make everything run quicker. It does complicate things but it can be a way to make your code more real time while still being accurate.
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
Oh man, I can imagine the troubles of writing such a program. Predicting collisions is quite a complex task especially if you have walls and such in the way, atleast in my mind.

With collisions that get more accurate like your, since 1 CPU core won't cut it, I think its better to either use a quad core or write the code in CUDA/OpenCL to make everything run quicker. It does complicate things but it can be a way to make your code more real time while still being accurate.


Technically, once you get the math in there, all you have to do is find the time-to-FIRST-collision. Finding this is essentially just finding all collision times, and then choosing the smallest non-negative collision time. There's loads of room here for optimization, such as parallelization, space partitioning, using AABB for rough approximations of collisions, etc. Note that most of these optimizations are applicable for any type of collision detection.

Making it parallel is usually pretty simple, as it's just a bunch of math (a simple math function is a pure function, making it trivially parallelizable).

For my system it's just a bunch of math to find out the time when a point R with relative velocity V intersects with a line defined by points P and Q:

W8v0P.png


Disclaimer: I am very proud of the fact that I derived this equation myself. :p However, it is expensive, as those are all cross products (for 3d, each is 6 multiplications and 3 subtractions, for 2d it is still 2 multiplications and 1 subtraction (
gif.latex
)), and this will be performed for every point on each object, for every line on the other object.
 

D.V.D

Make a wish
Reaction score
73
Haha its funny, I mentioned this to my brother whos taking physics and math 3rd year in university and he explained to me how he imagined it being done and it was something similar to this. I think it was applying a matrix that gave a similar result like your equation for t but that stuffs still way too complicated for me, I haven't even started calculus in high school :p

That seems like a real cool way of doing things, although expensive but I guess if you don't have too many objects colliding and for some reason want perfect collision then its the way to go :p

As a side note, I looked at Doom 3's source code and it had its own section on rigid body dynamics which I wanted to check out. Although its a bit complicated since you don't exactly know what each variable does, its a nice way to see how big companies solve such problems even if it was 5 years ago.
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
Haha its funny, I mentioned this to my brother whos taking physics and math 3rd year in university and he explained to me how he imagined it being done and it was something similar to this. I think it was applying a matrix that gave a similar result like your equation for t but that stuffs still way too complicated for me, I haven't even started calculus in high school :p

Never too early to start (as long as you start with the easy stuff ;) ). Technically that equation is derived entirely from trigonometry (using the equations for a line and a parabola to find where they intersect).

That seems like a real cool way of doing things, although expensive but I guess if you don't have too many objects colliding and for some reason want perfect collision then its the way to go :p

As a side note, I looked at Doom 3's source code and it had its own section on rigid body dynamics which I wanted to check out. Although its a bit complicated since you don't exactly know what each variable does, its a nice way to see how big companies solve such problems even if it was 5 years ago.

Looking at other games' source code is unfortunately not on the list of things I have done (and should probably go on my 'to-do' list). On a somewhat related topic, Valve published a document describing their AI systems in Left 4 Dead, which was very interesting!
 

D.V.D

Make a wish
Reaction score
73
Never too early to start (as long as you start with the easy stuff ;) ). Technically that equation is derived entirely from trigonometry (using the equations for a line and a parabola to find where they intersect).

Hmm, thats interesting. Kinda cool how you take a simple concept of intersecting lines and extrapolate it to use as a means of finding colliding objects.

Looking at other games' source code is unfortunately not on the list of things I have done (and should probably go on my 'to-do' list). On a somewhat related topic, Valve published a document describing their AI systems in Left 4 Dead, which was very interesting!

Oh man, don't even get me started. I have papers on so many different graphic features. A good 3 - 4 gigs of pdfs/word documents from companies like AMD, Nvidia, Crytek, Unreal, Valve, Wolfire, ID, Guirella, some guy from the God of War team, etc. The one thing that bothers me is nintendo never releases any sort of PDF's but Im dying to know how some of their engines work just cause I like the games so much :p Back to the topic, although AI is very cool, it hasn't grabbed me so much like physics and rendering has. I spent a lot more time researching stuff from GPU Gems on God Rays or Voxel-Based Enviorments as well as water rendering. One cool thing I saw was a PDF talking about how you can increase AI counts with Spatial Hasing, here Ill send the link: http://www.cs.ucf.edu/~jmesit/publications/scsc 2005.pdf

Another cool thing I noticed is that Doom 3's source code has certain code that they say specifically runs on the SIMD or sends info to cache memory which I really want to know more about cause that can optimize your program a lot!
 

Slapshot136

Divide et impera
Reaction score
471
I don't think Nintendo ever went for a "realistic" physics system in any of their games, just cartoon physics
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
I don't think Nintendo ever went for a "realistic" physics system in any of their games, just cartoon physics

Physics don't have to be realistic to be interesting and/or complicated. Sometimes small tweaks can make things more/less realistic. Haven't you ever wondered what sorts of systems they used in Super Mario Galaxy? Or Super Mario Bros?
 

D.V.D

Make a wish
Reaction score
73
Physics don't have to be realistic to be interesting and/or complicated. Sometimes small tweaks can make things more/less realistic. Haven't you ever wondered what sorts of systems they used in Super Mario Galaxy? Or Super Mario Bros?

Exactly, I always wondered how they handled pathing in Super Mario Galaxy, plus if they used deferred or forward rendering. Same question for Zelda Wii U Tech Demo, I wonder if they use traditional SSAO and local reflections or if they follow some other interesting way of doing things.
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615

D.V.D

Make a wish
Reaction score
73
If I recall, a few people found secret levels in the game and took the gravity properties of one map and attached it to that level to make it playable. The game seems to have a region probably created from simple geometry that once you enter creates a force of gravity in a certain direction or towards a object ( a planet ). Then after finding the characters rotation, if the character is standing in refrence to the surface, he will land safely and be able to walk on the planet. If not, then its just a collision. Usually, the character walks but there are cases in the game where you collide and simply move away or have the hurt animation played. This is a guess of how the engine works but I think its a good approximation on creating the weird gravity movement and full 3D pathing. Now on to programming it, thats the tough part haha.

Other games use a similar feature just without the gravity. Games like shadow of the collossus and god of war have scenarios where you can climb a enemy (boss) and have the fight centered around getting onto him and killing him in some fashion. They also have the 3D pathing but the gravity features are removed and instead, if your character is upside down you have hair or something to climb through. Even so, having 3D pathing is very useful for emmursive and large boss battles and is on my to do list after rigid bodies :))
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Staff online

      Members online

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top