Hello, I’m Glenn Fiedler and welcome to ** Virtual Go**, my project to simulate a Go board and stones.

In previous articles we mathematically defined the go stone, rendered it, determined how it moves and rotates, accelerated it by gravity and detected when it collides with the go board. We also discussed the inertia tensor and how it affects the movement of the go stone.

In this article we reach our first milestone: __a go stone bouncing and coming to rest on the go board__.

We do this using a technique called impulse-based collision response.

The concept is simple: apply an impulse at the point of collision to make the go stone bounce.

Exactly how to calculate and apply this impulse is rather complicated and interesting. __So read on!__

## Linear Collision Response

We now pick up where we left off at the end of the collision detection article.

We have a contact point and a contact normal for the collision.

Lets start by calculating a collision response impulse without rotation.

First, take the dot product of the linear momentum of the go stone with the contact normal. If this value is less than zero, continue; otherwise, the stone is moving away from the board and you should __not__ apply a collision impulse.

To calculate the impulse we need the concept of ‘elasticity’.

If the collision is perfectly elastic the go stone bounces off the board without losing any energy:

If the collision is perfectly inelastic, the go stone loses all its vertical motion post-collision and slides along the surface of the board:

What we want is something in between:

To support this we introduce a new concept called the ‘coefficient of restitution’. When this value is 1 the collision is perfectly elastic, when it is 0 the collision is inelastic. At 0.5, it’s halfway between.

This gives the following formula:

Where:

- j is the magnitude of the collision impulse
- e is the coefficient of restitution [0,1]
- p is the linear momentum of the go stone
- n in the contact normal for the collision

Note that the direction of the collision impulse is __always__ along the contact normal so to apply the impulse just multiply the contact normal by j and add it to the linear momentum vector.

Here is the code:

void ApplyLinearCollisionImpulse( StaticContact & contact, float e ) { const float mass = contact.rigidBody->mass; const float j = max( - ( 1 + e ) * dot( contact.rigidBody->linearMomentum, contact.normal ), 0 ); contact.rigidBody->linearMomentum += j * contact.normal; }

And here is the result:

## Collision Response With Rotation

Now lets calculate collision response with rotation.

To do this we will now calculate the velocity of the stone at the contact point, then take the dot product of this vs. the contact normal to check if the stone is moving towards the board. This is necessary because the stone is rotating so different points on the stone have different velocities.

Next we use the same basic strategy of applying an impulse along the contact normal with magnitude j except this impulse is now applied to the go stone at the contact point.

It’s actually quite tricky now to calculate the magnitude of this impulse such that the post-collision behavior matches the coefficient of restitution because the impulse at the contact point has both linear and angular effects, and the balance between them depends on the following factors:

- The point of application of the impulse
- The direction of the impulse relative to the center of the stone
- The inertia tensor of the go stone

Here is the general equation for calculating j of the collision response between two moving objects:

You can find an excellent derivation of this result on wikipedia.

Understandably this is quite complex, but in our case, the go board never moves, so we can simplify the equation by assigning zero velocity and infinite mass to the second body. This leads to the following, simpler, but still pretty complex equation:

Where:

- j is the magnitude of the collision impulse
- e is the coefficient of restitution [0,1]
- n in the contact normal for the collision
- v is the the go stone velocity at the contact point
- r is the contact point minus the center of the go stone
- I is the inertia tensor of the go stone
- m is the mass of the go stone

Which turns into the following code:

vec3f GetVelocityAtWorldPoint( const RigidBody & rigidBody, vec3f point ) const { vec3f angularVelocity = transformVector( rigidBody.inverseInertiaTensor, rigidBody.angularMomentum ); return linearVelocity + cross( angularVelocity, point - rigidBody.position ); } void ApplyCollisionImpulse( StaticContact & contact, float e ) { RigidBody & rigidBody = *contact.rigidBody; vec3f velocityAtPoint = GetVelocityAtWorldPoint( rigidBody, contact.point ); const float vn = min( 0, dot( velocityAtPoint, contact.normal ) ); // calculate inverse inertia tensor in world space mat4f rotation; rigidBody.orientation.toMatrix( rotation ); mat4f transposeRotation = transpose( rotation ); mat4f i = rotation * rigidBody.inverseInertiaTensor * transposeRotation; // apply collision impulse const vec3f r = contact.point - rigidBody.position; const float k = rigidBody.inverseMass + dot( cross( r, contact.normal ), transformVector( i, cross( r, contact.normal ) ) ); const float j = - ( 1 + e ) * vn / k; rigidBody.linearMomentum += j * contact.normal; rigidBody.angularMomentum += j * cross( r, contact.normal ); }

And here is the result:

## Coulomb Friction

We don’t often get to see frictionless collisions in the real world so the previous result looks a bit strange.

In order to get realistic behavior out of the go stone, we need to add friction.

We’ll model sliding friction between the go stone and the board using the Coulomb friction model.

In this model the friction impulse is proportional the magnitude of the normal impulse ‘j’ and limited by a friction cone defined by the coefficient of friction ‘u’:

Lower friction coefficient values mean less friction, higher values mean more friction. Typical values for the coefficient of friction are in the range [0,1].

Calculation of the Coulomb friction impulse is performed much like the calculation of the normal impulse except this time the impulse is in the tangent direction against the direction of sliding.

Here is the formula for calculating the magnitude of the friction impulse:

Where:

- j
_{t}is the magnitude of the friction impulse (pre-cone limit) - u is the coefficient of friction [0,1]
- t in the tangent vector in the direction of sliding
- v is the the go stone velocity at the contact point
- r is the contact point minus the center of the go stone
- I is the inertia tensor of the go stone
- m is the mass of the go stone

Which turns into this code:

void ApplyCollisionImpulseWithFriction( StaticContact & contact, float e, float u ) { RigidBody & rigidBody = *contact.rigidBody; vec3f velocityAtPoint = GetVelocityAtWorldPoint( rigidBody, contact.point ); const float vn = min( 0, velocityAtPoint, contact.normal ); // calculate inverse inertia tensor in world space mat4f rotation; rigidBody.orientation.toMatrix( rotation ); mat4f transposeRotation = transpose( rotation ); mat4f i = rotation * rigidBody.inverseInertiaTensor * transposeRotation; // apply collision impulse const vec3f r = contact.point - rigidBody.position; const float k = rigidBody.inverseMass + dot( cross( r, contact.normal ), transformVector( i, cross( r, contact.normal ) ) ); const float j = - ( 1 + e ) * vn / k; rigidBody.linearMomentum += j * contact.normal; rigidBody.angularMomentum += j * cross( r, contact.normal ); // apply friction impulse velocityAtPoint = rigidBody.GetVelocityAtWorldPoint( contact.point ); vec3f tangentVelocity = velocityAtPoint - contact.normal * dot( velocityAtPoint, contact.normal ); if ( length_squared( tangentVelocity ) > 0.001f * 0.001f ) { vec3f tangent = normalize( tangentVelocity ); const float vt = dot( velocityAtPoint, tangent ); const float kt = rigidBody.inverseMass + dot( cross( r, tangent ), transformVector( i, cross( r, tangent ) ) ); const float jt = clamp( -vt / kt, -u * j, u * j ); rigidBody.linearMomentum += jt * tangent; rigidBody.angularMomentum += jt * cross( r, tangent ); } }

And gives the following result:

## Rolling Friction

This looks really good but there is one small problem remaining.

Due to its shape, the go stone really prefers to rotate about axes on the xz plane. This means that if you you attempt to spin up around the y axis it stands up and spins on its side like a coin:

This is kinda cool. The problem is that it spins like this __forever__.

Why? Shouldn’t coulomb friction handle this for us?

No. Coulomb friction only handles friction when the two surfaces are sliding relative to each other.

Sliding friction is just one type of friction and there are many others.

What we have here specifically is combination of rolling and spinning friction.

At this point I have very little patience so I came up with my own hack approximation of spinning and rolling friction that gives me the result that I want: vibrant motion at high energies but slightly damped so the stone slows down, collapses from spinning, wobbles a bit and come to rest.

Here is my horrible code that does this:

// this is a *massive* hack to approximate rolling/spinning // friction and it is completely made up and not accurate at all! if ( collided ) { float momentum = length( stone.rigidBody.angularMomentum ); const float factor_a = DecayFactor( 0.9925f, dt ); const float factor_b = DecayFactor( 0.9995f, dt ); const float a = 0.0f; const float b = 1.0f; if ( momentum >= b || appliedSpin ) { stone.rigidBody.angularMomentum *= factor_b; } else if ( momentum <= a ) { stone.rigidBody.angularMomentum *= factor_a; } else { const float alpha = ( momentum - a ) / ( b - a ); const float factor = factor_a * ( 1 - alpha ) + factor_b * alpha; stone.rigidBody.angularMomentum *= factor; } } // apply damping const float factor = DecayFactor( 0.99999f, dt ); stone.rigidBody.linearMomentum *= factor; stone.rigidBody.angularMomentum *= factor;

And here is the end result:

If you enjoyed this article series please donate.

__Donations offset hosting costs and encourage me to write more articles!__

Great to see such good progress with this project. The stone bounce looks a bit too elastic – the first bounce at 1:10 seems high.

Thanks! Yeah I have tuned the elasticity up pretty high. I want really dynamic stone motion so when they drop they do a lot of tumbling.

Obviously, the elasticity really doesn’t come into play much when placing a stone on the board so I’m taking a bit of creative licence with this one

Also, the amount of bounce depends heavily on the angle of hit. Sometimes you get extra high bounces!

Nice article.

float clamp(float x, float min, float max)

{

if(x > max)

return max;

else if(x < min)

return min;

else

return x;

}

correct?

I sure hope so

Thanks! I’ve already sent you another question but i’m going to delete and ask here… If we do not apply damping in a rolling ball in the plane, it will be moving forever?

Yes without damping or rolling friction it will roll forever

(Of course some damping/error will accumulate over time — if your integrator loses energy rather than add it may come to rest very slowly on its own)

If we do not apply damping in a rolling ball in the plane, it will be moving forever?

Yes if you don’t apply damping or rolling friction it will roll forever

Hi. What approximation could be a good damping value for a euler-symplectic simulation?

Try the simplest thing you can get away with that gives the effect you want.

Absolutely fantastic work. Keep it up! The go community needs more people doing things like this. Can’t wait to see what this culminates in.

Thanks!

I’ve actually been quite busy since writing these articles.

Here is the latest screenshot:

If you have an iPad you can join the beta testing group here: http://tflig.ht/Zy3J8Y

Wow… Awesome articles! One question – The second call to getVelocityAtWorldPoint() uses the updated angularMomentum to compute angularVelocity, but doesn’t recompute linearVelocity (assuming these methods have the same behavior), is this correct?

velocityAtPoint = getVelocityAtWorldPoint(rigidBody, contact.point);

// …

// collision impulse applied to rigidBody linear & angular momentum.

// …

velocityAtPoint = rigidBody.getVelocityAtWorldPoint(contact.point);

The velocity at a function is a combination of linear and angular velocity, and the point itself.

So the correct behavior of the GetLinearVelocityAtPoint function in to recalculate both the linear and angular velocities from momentum, then use that to calculate the velocity at the point.

cheers

I love this project. I can’t follow the math or programming (past a certain point), but I love the idea and effort you’ve put in so far to make a physically accurate playable go board. I’ve been playing go for quite a few years, and I have to agree that the tactile experience is as rewarding as the intellectual endeavor. I was given a full-size floor board by my father-in-law, and the click of the stones (with wobble) is wonderful. It’s interesting, from a physics-simulation-development standpoint, that you have to start with modeling all the aspects of falling, friction, etc, even though they’ll probably only apply slightly to a stone which is placed on the board, not dropped. Although this led me to think about the times that stones do drop on the board, which is usually when the stone has stuck slightly to your finger as you lift it up, causing the stone to fall a few millimeters. So are you going to model each stone’s potential drop height as a function of fingertip skin-stickiness? One other question – I understand not accounting for the bevel when calculating the bouncing and rotation of the stone, but won’t that (admittedly small) difference in diameter affect the jostling of adjacent stones on the board? Each stone is only very slightly larger than the distance between the lines on the board, and it would seem if you ignore the bevel in your collision detection, it would make the size wrong enough to notice that two adjacent stones are not touching (separated by the distance of two bevels), yet pushing against each other. Just curious. Thanks again for undertaking this great project.

Nice catch with the bevel, you are right that it creates invisible space between go stones on the board. To fix this I apply special treatment in stone vs. stone collision which “chops off” the extra biconvex edge where the bevel should be, in effect creating an approximation that allows the stones to rest precisely next to each other from top down.

Cheers

I hope there is an index for all articles.

There is, it’s at the top of the page.

Thanks for the articles, they are very interesting and well written! I did not know there is so much behind some ‘simple’ physics!

Yeah it’s kind of crazy just how much work it takes!

Hello from Australia!

I have thoroughly enjoyed all of your articles and am looking forward to the next one. Thanks for providing me with such a great read! I have enjoyed reading your articles even more than some best selling books – if you had a book published I would read the shit out of it.

Keep up the great work Glenn! Really interested in reading your future articles

Thank you very much!

Hello,

I discovered this project about one year ago and was very interesting about it. Especially because I’m a Go player who learned a bit about 3d modelisation … Your explanations are really good and make things “easy” to understand.

So I was here again to see how it evolved and was bit deceived there’s no update.

Anyway I’m sure you’re busy because of another projects, work, etc. But I’m interested to know if you will continue that project ? (Or at least think you’re trying to)

I will still keep an eye on your website, hoping for some updates.

Take care and good continuation !

Thanks!

I worked on the project for about 1-2 months after the end of my last project at Sony.

Now I’m working at Respawn Entertainment on “Titanfall”

I have to concentrate on the paying projects for now, but do hope to return to virtual go in the future.

This is a really good article

last year I wrote a chunk of FEM-based sound synthesis code/toolchain that i thought would perfectly fit your project. i even made it work on bullet physics before getting burglarized o_o

Like many, I’ve been eagerly awaiting Titanfall’s release. But for sure I have one more reason than most for such anticipation: that you get a chance to resume this excellent project-blog around virtual go. Congratulations on both counts; please keep this project going.

Thank you