# Problem with 3d impulse and collisions

1. Jun 23, 2010

### 1101

Ok so I'm writing a 3D game that uses impulse to determine how things behave when they collide. In this game I have two cubes. Now the shape of each cube is defined by 9 spheres, sort of like this:

http://mark.reid.name/images/figures/high-dim-3d.png

Though in my game the middle sphere is larger. I am using the equations found here:

http://www.euclideanspace.com/physics/dynamics/collision/threed/index.htm

So far everything works as it should except for one small detail. If I line the cubes up and place them as close as possible to each other, sort of like this:

http://static-p3.fotolia.com/jpg/00/11/43/92/400_F_11439295_zmVtzYajNbkN71oe6l6lThBQHhRWxkQm.jpg

(and btw these aren't from my game their just random pictures from the internet I thought might be helpful).

Anyways if I position the cubes as shown in that picture I am able to rotate them through each other, which is obviously not what would happen in real life. Basically If the cubes have only linear velocity or have linear velocity and angular velocity everything works. But if the cubes only have angular velocity and are next to each other like in the picture they will rotate through each other. Keep in mind this isn't due to the fact that the collision of the cubes is represented with spheres. I am able to see the spheres that compose the cubes and can clearly see them going through each other (I also tried this with rectangles where it became very obvious something was wrong).

I would think in this type of situation that one of two things should happen:
1) In the case they are perfectly lined up and the angular velocity is small then nothing should happen .
2) In the case that they are not perfectly lined up but are still close or when the angular velocity of one of them is really large they should turn each other like gears.

I have checked my code again and again and have found nothing wrong. I believe that the equation I found at the euclidean space site does not account for this type of motion. So does anyone know how to account for this type of motion and how I could incorporate it into my current equation?

2. Jun 23, 2010

### K^2

That's because formulae you are using are only good for collisions. You don't want to be using these when you slowly push the two cubes into each other.

There is a reason why people usually don't do collisions like that. Compute forces. Do simulation that way.

3. Jun 23, 2010

### 1101

So what should I be doing then? I don't know what you mean by computing the forces.

4. Jun 23, 2010

### K^2

For every step of the simulation, do the following:

1) Check for collisions.
2) For every collision pair, check how much the two objects overlap. Use Hook's law (or any monotonous law, really) compute repulsion force.
3) Combine forces from collision and any other forces you wish to add into net force and net torque.
4) Compute linear and angular accelerations.
5) Use finite time increment to compute $\Delta v = a * \Delta t$
6) Do the same to find change in position, angular velocity, and orientation matrix/quatternion.
7) Rinse, repeat.

This is how most modern game engines work, including Havok. The main differences from one engine to another are how they detect collisions, determine the forces from these, and how the velocity and position changes are interpolated. (You will notice that without any interpolation, this recipe results in poor energy-conservation in collisions. If you run into this problem, I can give you a few tips on resolving them.)

5. Jun 26, 2010

### 1101

I'm just not getting it. I've looked online and downloaded a few books about game physics. It just seems like no one knows how to do this. Most of the information and all the examples are obfuscated horribly and there aren't any simple clear concise tutorials anywhere.

6. Jun 26, 2010

### K^2

Heh. Yes. Because people who write books on game designs are programmer-writers. Finding someone who's a programmer-physicist-writer is near damn impossible. So your best bet is to try and ask someone who is a physicist, comfortable with programming, and have done that before and stepped on most of the rakes associated with the problem.

That's why I'm trying to help. :) Not that I've written anything super-complex, but definitely on the scope you're working with. Plus, I've worked with physics engines written by other people enough to know a little about how these work as well.

7. Jun 26, 2010

### 1101

Ok so assuming there aren't any other forces aside from the two objects colliding how should I be calculating net force and torque. Is the net force just the result I get from using hooke's law?

As for torque. Wiki says its r x F. The F just stands for force but I'm confused about r which is a "displacement vector". Would I just use the point of collision for this value?

Also for the displacement in hooke's law should I be using the volume of overlap between the spheres that represent the area of my rigid body or some kind of 1 dimensional linear value?

8. Jun 26, 2010

### K^2

Exactly.

r is the vector to pivot point. If you have a free-rigid body, the pivot is the center of mass. So r is the vector from center of mass to the point where force is applied.

I'd use linear distance. If you can compute it, it's easier to work with. For spheres, it's very straight forward. The overlap depth is just distance - R1 - R2.

Part of the reason why linear distance works well is because you know that for the time of collision, it's going to essentially work as an oscillator. That might help you with debugging.

One thing you can do to save yourself trouble. Instead of computing force from just current positions, take average of this frame and previous frame. The reason for that is if you integrate Hook's Law in discrete steps, you consistently over-integrate. If you average it like above, the average error is zero.

Also, make sure that your Hook's constant is appropriate for the time step you are using. If you make it too stiff, the collision will happen in too few steps, and you'll have large error. If it's too soft, the objects will visibly overlap.

9. Jun 26, 2010

### 1101

Wait you saying overlap depth = - R1 - R1;
I'm assuming R1 and R2 are the respective radii of each sphere? Shouldn't the location of the spheres be incorporated into that? What I tried doing was finding the vector from the center of one sphere to the other, then multiplying it by each of their respective radii (keeping in mind that the radii would not necessarily be the same for each sphere) and find the distance between these two points. But that wouldn't work in the case the sphere's were perfectly overlapped since I'd have to normalize the distance vector (which would cause division by zero).

So is there a way to calculate overlap depth between two spheres without dividing by distance?

10. Jun 26, 2010

### K^2

I guess that sentence is a bit ambiguous. Depth = (distance - R1 - R2). And yes, these are radii.

If the two centers meet, you have other problems, such as, which way is the force pointing. You should set your Hook's constant to be high enough to avoid this scenario.

11. Jun 26, 2010

### 1101

Okay then but how do I convert that 1D value into a vector for force? I tried taking the distance of each component, ie

x_force = abs(x1 - x2) - radius1 - radius2;
y_force = abs(y1 - y2) - radius1 - radius2;
z_force = abs(z1 - z2) - radius1 - radius2;

where abs returns the absolute value

But that didn't work out too well. Would I have to calculate the normal of the collision and then multiply this by the magnitude of the force? If so how should I be calculating the normal?

12. Jun 26, 2010

### K^2

I think this is going to be easier.

Code (Text):
//Returns force experienced by sphere 1 at x1 due to sphere 2 at x2.
void getForce(float f[3], float x1[3], float x2[3], float r1, float r2, float k)
{
float dir[3],d;
int i;

for(i=0;i<3;i++)dir[i]=x1[i]-x2[i]; //Compute displacement vector between centers.
d=sqrt(dir[0]*dir[0]+dir[1]*dir[1]+dir[2]*dir[2]); //Compute norm of displacement.

if(d<r1+r2) //No collision.
{
for(i=0;i<3;i++)f[i]=0.0;
return;
}

//Computes force otherwise.
//Note: dir[i]/d is unit direction vector. (d-r1-r2)=depth.
for(i=0;i<3;i++)f[i]=k*(d-r1-r2)*dir[i]/d;
}

13. Jun 26, 2010

### 1101

For the most part everything is working but there's a couple of problems:

1) The cubes are still rotating through each other (which was my problem with the other method).

2) I've been arbitrarily assigning k. Right now the cubes collide properly unless I accelerate one of them really fast. Is there some proper way to calculate k based on velocity/acceleration?

I'm thinking with the rotation it might be due to a lack of friction (isn't that what causes gear-like rotation in the first place?). Just to clarify I'm calculating the change in angular velocity to be the torque multiplied by the inverse inertia_tensor. I'm pretty certain I'm calculating the tensor correctly.

14. Jun 26, 2010

### K^2

1) Do you treat the entire cube as a rigid body? Id est, do you compute the inertia tensor for the entire cube out of sphere contributions? Or how do you handle torque on cubes?

2) The value of k should depend on the time step, and that also limits velocities the simulation can handle. A really advanced engine may scale the time step depending on complexity of the situation, but that can cause lags.

15. Jun 27, 2010

### 1101

Okay so I am calculating the inertia tensor based on the entire cube (ie the eight points that make it up). I calculate the overlap and point of intersection based on the individual spheres but I calculate the force and torque based on the average overlap and the 'average' point of intersection. So lets say that the two faces of the cube are lined up and intersect. There would be five points of interaction between ten spheres but the average point of intersection would be the middle of the cube.

So in short Inertia is based on the entire cube and torque is based on the average point of intersection and the total force. The total force being calculated based on the average overlap.

16. Jun 27, 2010

### K^2

Don't average them. Just make each sphere-sphere collision generate its own force. Add forces from all spheres that belong to a cube to get total force, and add all torques from each rxF to get total torque.

I think, that might be the problem. If the two spheres on opposite sides touch, if you just average point of force application, there is no net torque when cubes try to rotate through each other. If you compute torques first, then add them, the side that overlaps more will be the one providing dominant torque, and that should help.

17. Jun 27, 2010

### 1101

Alright well I did that and didn't see any change in behavior. The linear part works and the angular part works if there is some linear velocity but if there is only angular velocity the cubes can still be rotated through each other.

Here's my actual code if you want to take a look, it's in GML so it might be a little strange. It's basically like c++ though.

Code (Text):

//the with statement makes the first cube cycle through all the instances of the other cube (there's only 1 so it doesn't really matter)
//just remember that when you see the prefix other. it means it is pulling or applying a variable to the other cube.
with (OBJECT_moving_box)
{
x_FORCE = 0;    x_torque = 0;
y_FORCE = 0;    y_torque = 0;
z_FORCE = 0;    z_torque = 0;
for(i = 0; i < ds_list_size(SPHERE_LIST); i += 1;) //cycles through all the spheres in the first cube
{
LIST_1 = L(SPHERE_LIST,i);      //That capital L is a function. Basically a list is like a vector, the function L
xt1 = x + SCALER*L(LIST_1,0);   //reads the value of the list at that location
yt1 = y + SCALER*L(LIST_1,1);   //Here 0,1,2 denote the x,y,z location of the sphere relative to the body and 3
zt1 = z + SCALER*L(LIST_1,2);   //denotes the radius
rt1 = SCALER*L(LIST_1,3);
for(ii = 0; ii < ds_list_size(SPHERE_LIST); ii += 1;) //cycles through all the spheres in the second cube
{
LIST_2 = L(other.SPHERE_LIST,ii);           //same setup as above but with the other cube
xt2 = other.x + other.SCALER*L(LIST_2,0);
yt2 = other.y + other.SCALER*L(LIST_2,1);
zt2 = other.z + other.SCALER*L(LIST_2,2);
rt2 = other.SCALER*L(LIST_2,3);
if sqrt(sqr(xt1 - xt2) + sqr(yt1 - yt2) + sqr(zt1 - zt2)) <= rt1 + rt2 //checks for intersection
{
rax = ((rt1*xt1 + rt2*xt2)/(rt1 + rt2));    rax -= x; //rax,ray, and raz is the point of interesction of the sphere
ray = ((rt1*yt1 + rt2*yt2)/(rt1 + rt2));    ray -= y;
raz = ((rt1*zt1 + rt2*zt2)/(rt1 + rt2));    raz -= z;
x_normal = xt2 - xt1;
y_normal = yt2 - yt1;
z_normal = zt2 - zt1;
x_OVERLAP = abs(xt1 - xt2) - rt1 - rt2;
y_OVERLAP = abs(yt1 - yt2) - rt1 - rt2;
z_OVERLAP = abs(zt1 - zt2) - rt1 - rt2;
M = sqrt(x_normal*x_normal + y_normal*y_normal + z_normal*z_normal);
xf = -x_OVERLAP*x_normal/M;      x_FORCE += xf;
yf = -y_OVERLAP*y_normal/M;      y_FORCE += yf;
zf = -z_OVERLAP*z_normal/M;      z_FORCE += zf;
x_torque += ray*zf - raz*yf;
y_torque += raz*xf - rax*zf;
z_torque += rax*yf - ray*xf;
}
}
}
x_speed -= x_FORCE/MASS;     other.x_speed += x_FORCE/other.MASS;
y_speed -= y_FORCE/MASS;     other.y_speed += y_FORCE/other.MASS;
z_speed -= z_FORCE/MASS;     other.z_speed += z_FORCE/other.MASS;

x_angular_velocity += INERTIA_TENSOR[1,1]*x_torque + INERTIA_TENSOR[1,2]*y_torque + INERTIA_TENSOR[1,3]*z_torque;
y_angular_velocity += INERTIA_TENSOR[2,1]*x_torque + INERTIA_TENSOR[2,2]*y_torque + INERTIA_TENSOR[2,3]*z_torque;
z_angular_velocity += INERTIA_TENSOR[3,1]*x_torque + INERTIA_TENSOR[3,2]*y_torque + INERTIA_TENSOR[3,3]*z_torque;

other.x_angular_velocity -= other.INERTIA_TENSOR[1,1]*x_torque + other.INERTIA_TENSOR[1,2]*y_torque + other.INERTIA_TENSOR[1,3]*z_torque;
other.y_angular_velocity -= other.INERTIA_TENSOR[2,1]*x_torque + other.INERTIA_TENSOR[2,2]*y_torque + other.INERTIA_TENSOR[2,3]*z_torque;
other.z_angular_velocity -= other.INERTIA_TENSOR[3,1]*x_torque + other.INERTIA_TENSOR[3,2]*y_torque + other.INERTIA_TENSOR[3,3]*z_torque;
}

Also you might notice there's no time step calculation. Basically when you see something like
a += d it means that d will be added to the current value of a every time step (which is 1/120th of a second at the moment). Though don't get confused, when I do this in the for loop it is only added to the current value once. For instance when you see x_FORCE += xf; it means that xf is added to the current value of x_FORCE once per iteration of the for loop.

18. Jun 27, 2010

### K^2

I don't know if this is a cause of your problem or not, but I haven't found any other issues yet.

Forces are equal-and-opposite on the two boxes. So you can compute force on both in one go. But that's not true for torques. The torques are only equal-and-opposite around common origin. But torque around center of mass of one cube will not be equal to minus the torque around the center of the other, because you just changed the origin around which torque is measured. It's a relative quantity.

Anyways, a better way to handle this, and it might be a good idea in case you decide to have more objects later, is to make this call for each cube, and compute forces and torques for current cube only.

Alternatively, you can try to figure out the torque on the second cube within your code, but you'll need to create x/y/z_torque2 from rax/y/z crossed with -x/y/z_FORCE, where rax/y/z are redefined relative to other.x/y/z.

I can only venture a guess that at your chosen location, the torque around first cube's center is zero, but not around second cube's, and that might be the reason they rotate through each other.

But it might be something else. I'll take another look through the code to see if I find anything else.

19. Jun 27, 2010

### 1101

Okay so I changed it so that the torque is calculated independently. Basically the first cube's torque is the cross product of the vector from the point of intersection to its center of mass with the positive force and the other is the cross product of the vector from the point of intersection with it's own center of mass and the negative force. Still the same...

Just to be super clear here's whats happening. If the cubes are lined up and strike each other the velocity of the one that is doing the striking is transferred to the one that's staying still. If the cubes are not lined up and strike each other the velocity is transferred and both cubes will spin a little bit. But if the cubes are placed close to each other and one of them starts spinning it will spin through the other one. I even scaled one of the cubes 50x and it will literally engulf the other one as it spins (i thought for a while that maybe the spheres that make them weren't really touching or something). I should also mention I can see the spheres that compose them and can clearly see them intersecting when I spin them. Another problem is that if I start spinning a cube and then make it collide with the other, they will react in the same way as if the cube had struck it in the same location without any spin.

Last edited: Jun 27, 2010
20. Jun 27, 2010

### K^2

When it rotates through, does it push off the other cube at all? Or just passes through freely?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook