Jump to content
  • Advertisement
Sign in to follow this  

Multibody collisions

This topic is 4001 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to find an equation for predicting the outcome velocities of a group of 3 objects, all touching each other, as the first step in a more general solution. The first has a velocity, the others are at rest. By positioning the other objects (spheres) at different angles relative to each other, I can change the resultant velocities of the objects. I'm colliding the first and second object, then the second and third, pairwise and iteratively, until the solution converges to an arbitrary exactness. The idea is that if the objects' velocities were integrated, there would be no penetration between any of the three objects. Obviously a generalized solution to this problem would be very useful in a physics engine. Here's my test source (Ruby script)
class Vector
    def initialize(x, y)
        @x = x; @y = y;
    def x
    def y
    def to_s
    def -(other)
        Vector.new(@x-other.x, @y-other.y)
    def +(other)
        Vector.new(@x + other.x, @y + other.y)
    def dot(other)
        @x*other.x + @y*other.y
    def *(other)
          Vector.new(@x*other, @y*other)
    def /(other)
          Vector.new(@x/other, @y/other)
    def length()
      Math.sqrt(@x*@x + @y*@y)
  class Body
    def mass
    def mass=(val)
      @mass = val
    def vel
    def vel=(val)
      @vel = val
    def pos
    def pos=(val)
      @pos = val
    def initialize()
      @mass = 1
      @vel = Vector.new(0,0)
      @pos = Vector.new(0,0)
    def applyImpulse(j, normal)
      @vel = @vel + j / @mass * normal

def findCollisionImpulse(normal, a, b)
    ((a.vel - b.vel).dot(normal)) /
    (normal.dot(normal) * (1.0 / a.mass + 1.0 / b.mass))
def collide(normal, a, b)
  impulse = findCollisionImpulse(normal, a, b)
  puts impulse
  a.vel = a.vel - normal * (impulse / a.mass)
  b.vel = b.vel  + normal * (impulse / b.mass)

def abs(a)
def main()
  bodyA = Body.new()
  bodyB = Body.new()
  bodyC = Body.new()
  bodyA.mass = 1
  bodyA.vel = Vector.new(100,0)
  bodyA.pos = Vector.new(0,0)
  bodyB.mass = 1
  bodyB.vel = Vector.new(0,0)
  bodyB.pos = Vector.new(1, 1)
  bodyC.mass = 1
  bodyC.vel = Vector.new(0,0)
  bodyC.pos = Vector.new(2, 1)
  epsilon = 1e-10
  normalAB = bodyB.pos - bodyA.pos
  normalBC = bodyC.pos - bodyB.pos  
  counter = 0
  while(abs((bodyB.vel - bodyA.vel).dot(normalAB)) > epsilon ||
           abs((bodyC.vel - bodyB.vel).dot(normalBC)) > epsilon)
    counter = counter + 1
    puts "Iterating..."
    puts abs((bodyB.vel - bodyA.vel).dot(normalAB))
    collide(normalAB, bodyA, bodyB)
    collide(normalBC, bodyB, bodyC)
  puts counter.to_s + " iterations"
  puts "Body A:\n\tpos: " + bodyA.pos.to_s
  puts "\tvel: " + bodyA.vel.to_s
  puts "Body B:\n\tpos: " + bodyB.pos.to_s
  puts "\tvel: " + bodyB.vel.to_s
  puts "Body C:\n\tpos: " + bodyC.pos.to_s
  puts "\tvel: " + bodyC.vel.to_s


The previous source code produces this result: (objects are assumed to be spheres, the length of the vector between objects' position doesn't matter).
14 iterations
Body A:
        pos: <0,0>
        vel: <71.4285714285779,-28.5714285714221>
Body B:
        pos: <1,1>
        vel: <14.285714285711,28.5714285714221>
Body C:
        pos: <2,1>
        vel: <14.285714285711,0.0>
Clearly there's some sort of series work involved here, but I slept through series in Calc ;). I Would be greatly appreciative if someone could point me in the right direction.

Share this post

Link to post
Share on other sites
Here's my stab at it, perhaps it will work, or at least give you an idea.

*assuming a completely reflective relationship with no deformation, diffusion, absorption, or bonding*
have all objects move.
find which objects have collided.
for each group of objects add all masses, and add all forces.
resultant total force is applied to all masses in that group.
check each vector for penetration (if it is going to be moving faster in a way that would cause a second collision before the next frame)
perform sub group collisions if such a case exists.
once all vectors can occur without penetration, group has been solved.
after all groups have been calculated, next frame.

Share this post

Link to post
Share on other sites
I'm working on that last bit, resolving collisions. My idea is to resolve collisions before I integrate to change positions, so that large stacks of items resting on top of each other won't interpenetrate and cause problems for the collision solver in the next step.

We're talking about inelastic collisions for this prestep. The above ruby code is a simulation so I can try different configurations to see the end result.

I'm trying a system of equations approach at the moment, I'll see if it'll pan out. But I still think there's probably a reasonable way to distribute the momentum through the group to achieve the same result.

I'll try to upload a picture a bit later.

Share this post

Link to post
Share on other sites
Here's a picture of the above situation:

I'm able to get a generalized solution for the case of any 3 spheres colliding using a system of equations, but the result isn't in vector form and so is extremely unwieldly.

Basically, there are 6 equations and 6 unknowns (2 components for each vector):

(v2 - v1) * ab = 0 //balls do not move towards each other
(v3 - v2) * bc = 0 //ditto
m1 * (v1 - v1i) + m2 * (v2 - v2i) + m3 * (v3 - v3i) = <0, 0> //conservation of momentum
v1 cross ab = v1i cross ab //collisions do not effect tangent velocities
v3 cross bc = v3i cross bc //ditto

The result is over a page long in Maple, but shows promising signs that there is a better way to condense it. Does anyone have a vector friendly way of solving these equations in terms of dot products, cross products, and norms?

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!