Emulating Billiard Ball Behaviour

[Dr Memory]

I've been working on a Snooker game (I use "billiard ball" as a generic term for pool-balls, snooker balls, etc).

I was determined to learn as much as I could before asking for help - that point has now arrived!

A summary of my setup:

• The game space has zero-gravity, so we need a substitute for table friction - the balls need to slow down, after all. This is done by damping (0.5 seems to be a reasonable emulation)

• Rail (cushion) sections are composed of static segments

• Balls have their MoI set to infinity, to suppress 2D rotation, which is an undesired effect. At this stage I am deferring the delicate topic of cue-ball spin, which is of course a 3D attribute. I think I can implement basic top-spin and back-spin by simple collision callbacks, but that's for later on.

• Because there are so few moving objects (max 22) I can run the engine with very small timesteps (eg: 1 msec). Chipmunk is really fast, even with this setting, so I don't really need to implement swept collisions.

My first real problem comes with a ball rebounding off a cushion. Balls have elasticity of 1. With cushions also having elasticity 1 I get accurate rebounds. But if I reduce rail elasticity to emulate cushion speed (e.g 0.5 = slow, say) then the rebound angles are affected, quite a lot in fact. (I now understand why this so, see PS below)

Is there another way to implement my cushion speed setting without affecting rebound angles?

Or do I need to just bite the bullet and put in a collision callback to reduce the velocity myself?

PS: I have found Scott's explanation of how elasticity affects rebound, which is explained here

[Dr Memory]

Is there another way to implement my cushion speed setting without affecting rebound angles?

Or do I need to just bite the bullet and put in a collision callback to reduce the velocity myself?

Well, I bit the bullet, and figured out how to operate the callback feature. I'm happy with this simple approach, which is to apply a specific rail damping factor to a ball that collides with a rail.

So I'll move on to the next phase, which needs callbacks in any case. That is, to simulate, as far as possible, the effect of cue-ball played with top-spin. When it makes its first impact with another ball, both its velocity and direction have to be varied according to the degree of top-spin.

If I understand things correctly, this would involve the callback function:

• Converting existing cue-ball velocity vector CV, to polar form (ie: direction, angle)

• Adjusting direction/speed by some yet-to-be determined formula

• Converting CV back to (x, y) form to pass to cpBodySetPosition

Does that make sense?

[Dr Memory]

I have learned that even emulating simple cue-ball follow (top spin) and draw (back spin) is beyond the capabilities of a collision callback alone.

The cue-ball deviation from the cut angle is at first parabolic, before it becomes linear. Emulating this would require the game software to monitor the cue-ball post-collision, making continuous adjustments until the linear stage is reached.

Fortunately this parabolic stage is relatively small, so my 2D game will have to be content with simulating draw and follow, by making one-off velocity vector adjustments.

Perhaps the callback function can make an educated guess about the mean deviation for the parabolic stage, and the time for which this applies, and the game software can apply the 2nd deviation at the right time, i.e. a dog-leg trajectory as a slightly better solution than a linear one.

[Dr Memory]

Fortunately this parabolic stage is relatively small, so my 2D game will have to be content with simulating draw and follow, by making one-off velocity vector adjustments.

Oh dear, my lack of physics understanding is showing already. The model presented above means that every shot I play is a stun shot. In reality all "natural" shots will have follow (top spin), and the parabolic phase of post-impact trajectory is by no means insignificant.

The attached screenshot is from the rather excellent Cue Club 2 game. I have overlaid this with the results of my cue-ball tracking function to trace the location of the cue-ball.

The cue ball has been played from the left, and the blue ball was potted bottom-right.

The shot was played with 30% force (the CC2 default) and "natural" spin (ie. cue impact at dead center). The cue-ball postimpact follows a parabolic trajectory for approx .75s, then straightens.

Dave Alciatore has an excellent series of technical articles on Billiard Ball Physics, see http://billiards.colostate.edu.

The parabolic-then-linear effect is documented in detail in http://billiards.colostate.edu/technica ... TP_A-4.pdf.

[Dr Memory]

Ok, I have researched the heck out of this topic, and I can report on what is needed for a truly realistic snooker/pool emulator.

You definitely need 3D motion (2D vector for position, but 3D vectors for velocity and spin). And you need to keep track of 3D states SLIDING and ROLLING (either both can apply at any given time).

As shown above, particularly with the cue ball, you have to apply one set of motion equations for post-collision when the cue ball slides, and another set for when it stabilises (and starts rolling in a straight line).

Unfortunately, this can only be done by integrating the motion and collision detection fairly tightly, so Chipmunk 2D is going to need some work at the internals level, simply using the callback features won't really cut it.

One option would be to ask Scott to consider implementing SPHERE as a collision shape, ie "Chipmunk 2.25D"?

Another option is to lay your hands on a "Pool Physics" engine, and I will tell you right now they are as scarce as hen's teeth. But I have finally stumbled across one, after a week of searching.

So here are two invaluable links for this purpose:

• a paper by Leckie & Greenspan called An Event-Based Pool Physics Simulator. It will cost you 25 Euros for a copy, sorry about that, that's Springer for you. But well worth it, IMHO.

• a more-or-less open-source (yes!) implementation of this in C++: http://web.stanford.edu/group/billiards/index.html. Read about why they built it (to use as a common platform for comparison of pool-playing agent strategies for a competition). Follow the links to get the library source code.

The engine is embedded in a class-structure that supports the competition, but at the heart of it is the engine described in the paper. Because this model simply uses the math to predict the exact timing of collision and motion-state change events, it needs to be modified if you want to tie it to a graphical interface, which of course you will most likely wish to do. That's just a fairly straight forward exercise in interpolation.

A bit of grunt and lots of coffee and hey, presto, a Pool Physics engine!

[Dr Memory]

Unfortunately, this can only be done by integrating the motion and collision detection fairly tightly, so Chipmunk 2D is going to need some work at the internals level, simply using the callback features won't really cut it.

I really hadn't thought that through sufficiently! (the story of my life ...)

We can implement the curved trajectory phase (aka the "Slide Zone") by simply making per-timestep adjustments to the cue-ball's velocity vector. Since these adjustments are minor, it works pretty well seamlessly, and with only a single callback:

• when the cue ball first collides with another ball, we calculate the expected slide time (from Leckie & Greenspan Eqn 13) and set a CUE_BALL_SLIDING flag

• in our Update loop, every time we call cpSpaceStep, if the CUE_BALL_SLIDING flag is set we use L & G equations 8 and 9 to determine the correct velocity setting, call cpBodySetVelocity to make the correction, and decrement the slide time counter

• we clear the CUE_BALL_SLIDING flag when the slide time counter reaches zero, OR the cue ball has another collision, with either a rail (cushion) or another ball

• we don't need to use the L & G equations for cue ball rolling, since this is our default state, emulated by having zero-gravity and velocity damping on the Chipmunk space.

One pleasing result of this approach is that it allows me to overcome a significant drawback of the FastFiz library (ie. the Stanford implementation of L & G's Pool Engine design). While handling the complexity of cue ball slide & spin admirably, it assumes the table has simple straight-line pockets. Any collision with a rail that corresponds to these simple line sections is regarded as a pot.

My Chipmunk table emulates the curvature of the pockets (see image above) via poly-line segments that reflect this curvature accurately, and handles the rebound angles automatically for me.

Go Chipmunk!!

[Dr Memory]

This is turning into a blog ...

Ok, in the week since my last post, I found myself wrestling somewhat with the finer points of the math involved, and decided to delve into the Stanford code in an attempt to understand how it hangs together.

When I had done that for a few days, I realised that it was possible to teach this library (which I have now renamed SnookerFiz since I've done a heap of work on it) about pocket geometry, which I had pointed out earlier as a major drawback.

I started by implementing straight-line gates, and through learning how to do that I got a better understanding of the physics/maths handling, and was considering returning to my Chipmunk2D model when the penny dropped.

The tools for TCPE (aka "True Curvature Pocket Entrances") are in fact available. A snooker table has curved pocket entrances, and these are essentially arcs of a circle (see image above). Since SnookerFiz already predicts exactly when balls collide, I can use that same method to predict intersections with my curved "gates". This involves solving quartic equations, but the solvers are already provided, to support the ball-to-ball collision predictions, so its essentially a cut-and-paste job.

That changes everything wrt my ultimate objective - I can have the smarts of the predictive model, and not have to do any more math other than the curved rail section intersection stuff, which I have now largely done. The library can be married to a rendering interface (by generating simple interpolation data regarding balls in motion), and can also be used for its original purpose, ie computationally efficient modelling of alternative shots/strategy/etc.

I doubt now that I'll ever get around to evolving the Chipmunk model further, not because it can't be done, but because SnookerFiz offers so many nice features.