Sign in to follow this  
Numsgil

Multibody collisions

Recommended Posts

Numsgil    501
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;
    end
    
    def x
      @x
    end
    
    def y
      @y
    end
      
    def to_s
        "<#@x,#@y>"
    end
      
    def -(other)
        Vector.new(@x-other.x, @y-other.y)
      end
      
    def +(other)
        Vector.new(@x + other.x, @y + other.y)
      end
      
    def dot(other)
        @x*other.x + @y*other.y
      end
    def *(other)
          Vector.new(@x*other, @y*other)
        end
        
    
    def /(other)
          Vector.new(@x/other, @y/other)
        end
        
    def length()
      Math.sqrt(@x*@x + @y*@y)
    end
    
  end
  
  class Body
    def mass
      @mass
    end
    
    def mass=(val)
      @mass = val
    end
    
    def vel
      @vel
    end
    
    def vel=(val)
      @vel = val
    end
    
    def pos
      @pos
    end
    
    def pos=(val)
      @pos = val
    end
    
    def initialize()
      @mass = 1
      @vel = Vector.new(0,0)
      @pos = Vector.new(0,0)
    end
    
    def applyImpulse(j, normal)
      @vel = @vel + j / @mass * normal
    end
  end
  

def findCollisionImpulse(normal, a, b)
    ((a.vel - b.vel).dot(normal)) /
    (normal.dot(normal) * (1.0 / a.mass + 1.0 / b.mass))
  end
  
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)
end

def abs(a)
  Math.sqrt(a*a)
end
  
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)
  end
  
  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
  
  
end

main()

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
Pheonixx1980    270
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
Numsgil    501
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
Numsgil    501
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this