Problem with 3d impulse and collisions

  • Thread starter 1101
  • Start date
  • #1
23
0
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?
 

Answers and Replies

  • #2
K^2
Science Advisor
2,469
29
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
23
0
So what should I be doing then? I don't know what you mean by computing the forces.
 
  • #4
K^2
Science Advisor
2,469
29
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 [itex]\Delta v = a * \Delta t[/itex]
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
23
0
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
K^2
Science Advisor
2,469
29
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
23
0
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
K^2
Science Advisor
2,469
29
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?
Exactly.

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?
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.

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?
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
23
0
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
K^2
Science Advisor
2,469
29
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
23
0
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
K^2
Science Advisor
2,469
29
I think this is going to be easier.

Code:
//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
23
0
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
K^2
Science Advisor
2,469
29
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
23
0
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
K^2
Science Advisor
2,469
29
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
23
0
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:
//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
K^2
Science Advisor
2,469
29
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
23
0
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:
  • #20
K^2
Science Advisor
2,469
29
When it rotates through, does it push off the other cube at all? Or just passes through freely?
 
  • #21
23
0
It passes through it freely. It does not move it even the tiniest bit. I can rotate the cube so fast that it appears to not move at all and still it will not budge. I think I know why too. It's because with sphere's collision point and the direction of force are always going to be the same (so the cross product between the two, which would give torque, is going to be 0).

I think I really need to somehow incorporate friction into the torque though I'm still trying to figure out how.
 
Last edited:
  • #22
K^2
Science Advisor
2,469
29
No, that's not it. The direction of force is along sphere-sphere center line. The cross product is with a vector going to cube center. These directions will not be the same, generally in cube-cube collision.

Besides, even if torque was zero, there should still be a force pushing them apart in this collision.

First thing I'd do is check your spheres. Do they have correct coordinates assigned to them? It would help if you can render these along with the cube to see what's going on.

And I'll re-check the code and see if there is anything off.

Edit:
Code:
rax = ((rt1*xt1 + rt2*xt2)/(rt1 + rt2));
Should be:
Code:
rax = ((rt2*xt1 + rt1*xt2)/(rt1 + rt2));
Because the center will be closer to the smaller sphere. But I'm guessing you use spheres of equal radius, which won't make a difference here.
 
  • #23
K^2
Science Advisor
2,469
29
Ok, here is another one. This will mess up the forces, allowing spheres to pass through each other under certain conditions.

Code:
                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;
You can't decompose overlap in this manner. You should have something like:

Code:
                OVERLAP = r1+r2 - sqrt(sqr(xt1-xt2)+sqr(yt1-yt2)+sqr(zt1-zt2));
                //...
                xf = -OVERLAP*x_normal/M;      x_FORCE += xf;
                yf = -OVERLAP*y_normal/M;      y_FORCE += yf;
                zf = -OVERLAP*z_normal/M;      z_FORCE += zf;
The sign error is my own fault, I think. I think I had it the wrong way earlier too.
 
  • #24
23
0
I made those changes (tnx btw) but it's still rotating through it. I know the spheres are being placed right because I am rendering them (I can swap between seeing the cube model or seeing the sphere's that compose it). They all look to be correctly placed and the way I'm drawing them wouldn't work if they weren't. I know that the cube is not rotating at all (even the tiniest bit) because I am drawing the inertia tensor matrix of both cubes on the screen. When I rotate one cube it's tensor changes but the other doesn't despite colliding. Also even if I am calculating the tensor wrong (I don't think I am) it always has at least three non zero values in the matrix so some kind of rotation should occur upon collision (even if it is incorrect). I've checked several times now through all the code in the game (at this point there isn't a whole lot) and can find nothing that would interfere with the interactions of the cubes in a way that wouldn't be very obvious.

I'm thinking the problem has to be in how I'm calculating the collision normal, the point of the collision, and or the overlap but can't see anything wrong with any of them.

I mentioned before that I might need some kind of friction in place but realized that you were right, the direction of force is from the center of each sphere but the normal is the direction from the point of collision to the center of the cube. This would result in a nonzero cross product for all but 1 of the spheres.

What really bothers me is that I can see the sphere's overlapping and the presence of any type of overlap shouldn't be tolerated. But for some reason in the lack of linear velocity nothing happens, despite the fact that linear velocity isn't even a factor in the collision response.
 
  • #25
K^2
Science Advisor
2,469
29
Oooooo. I think I found it. Coordinates of the spheres. These are just fixed relative to cube, right? So when you take xt1 = x + SCALER*L(LIST_1,0); this is going to give you the same number regardless of orientation of the cube, isn't it? When you render the spheres, you probably just call a transform, so you still make calls to render spheres as if no rotation happened, and the rotation matrix in place takes care of it. But not in physics. So your spheres end up moving on the screen, but not from perspective of simulation.

You need to add a transform that depends on current orientation matrix. So the xt1 will depend on all 3 of the sphere's coordinates, and same goes for yt1 and zt1.

Unless I'm completely wrong and your SPHERE_LIST is already adjusted for rotation, but then you'd probably have origins shifted too, so I'm guessing that's not the case.

Plus, it explains perfectly why there is no collision unless cubes move.
 

Related Threads on Problem with 3d impulse and collisions

  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
2
Views
5K
Replies
1
Views
1K
  • Last Post
Replies
4
Views
6K
Replies
1
Views
12K
Replies
5
Views
2K
Replies
1
Views
7K
Top