BEHIND THE MAGIC EIGHT BALL AT SHARP SHARKEY'S GRITTY LITTLE POOL HALL README

Richard Bragg (rwbragg@stanford.edu)

For some screenshots, see my webpage at www.stanford.edu/~rwbragg/magic8.html
Feel free to link to this from the class page.

1.  What is it?
---------------
Behind the Magic Eight Ball is a realistic 3d pool game that allows a player to practice his shots to perfect his game or to challenge an opponent to a head-to-head duel.  The incredibly realistic ball dynamics allow the user to do anything he would be able to do in a real game including applying different spins to the cue ball, shoot with varying amounts of power and spin, or even jump over other balls.  The winner of a two-player game even gets a chance to visit the mysterious "Magic Eight Ball" room, where Sharp Sharkey's Magic Eight Ball holds the answers to all of life's questions.

In short, my attempt was to create a pool game that was realistic as possible, so that someone who played pool would enjoy the game as much as playing pool for real.  Since I am not a very good pool player mainly due to the fact that I can't control the stick as much as I would like it to, this was my chance to create a pool simulator where I could make the stick do exactly what I asked of it, and then see if I really understood the game...  I feel I have accomplished that goal, and now have a very fun game that I can play without leaving the computer.

2. Running the game
-------------------
The source code should compile on Linux, just by running the included Makefile.  I'm not exactly sure what the minimum graphics requirements are, but the game runs perfectly well using the Geforce3 cards in the graphics labs, but runs much too slow on my computer with a lesser graphics card.
The executable included (pool3d) is for Linux and has already been compiled - it should work as is if you don't change any of the existing directory structure.

3. How to play
---------------
The controls of the game are as follows:

In all the scenes:
	-Left/right arrow keys: rotate the view
	-Up/down arrow keys: move the view up or down 
	-S/X: zoom in/out

Irrelevant to game play - but might help performance on slow systems:
	-P: toggle between solid and wireframe modes
	-T: toggle texture mapping
	-L: toggle lighting

Shooting (also shown on the screen just in case):
	-Left/right arrow keys: position the direction of your shot
	-CTRL + arrow keys: move the cue stick offset from the center of the ball - this can be used to apply topspin, backspin, or sidespin to your shot
	-A/Z: increase/decrease the cue angle, large angles here will actually cause the ball to "jump"
	-Spacebar: hold down to increase power, release to shoot
	
Shortcuts:
	-8: jump directly to the Magic Eight Ball room
	-N: stop all the balls where they are, ending a turn

4. Required Functionality
--------------------------
- 3d Viewing and Objects:
	Clearly this was done - everything in the game is 3d in both appearance and behavior.  Most of the objects you see in the game were found on the web (see section 10), but the pool table that I used was modified a great deal.  The model I originally found had holes in the model, it wasn't broken down into any groups, not all of the surfaces were flat, and the mesh was very poorly done, with many skinny triangles that made any interesting lighting effects useless.  While I did use the basic features and dimensions of that model, I made so many modifications to it that I must take some of the credit for that.

- User Input
	Nothing happens without the user hitting the ball, and there are many ways to do this.  See above for details on the controls.  Once the ball is hit, you can still move the view around, but the action on the table is at the mercy of the laws of physics!

- Lighting and Smooth Shading
	I actually went to great lengths to make the two lamps above the pool table create circular spotlights on the pool table, and for the pool balls' prominent specular reflections to be resulting only from those lights.  These are both built-in OpenGL features but it took awhile (including retooling the table's mesh as mentioned above) to get exactly the look I was going for.

- Texture Mapping
	Most of the scene is texture mapped.  Notice the changes in the wood grain at the corners of the table, and the fact that the green felt wraps completely to the bottom surface of the bumpers.  Since the pool table model that I found on the web was all one object, I actually had to manually break the model into its constituent parts in order to apply the texture map in a desirable way.  The texture maps on the balls I made myself from scratch!  Most of the other textures were obtained on the web (see Section 10).

5. Advanced Features (N=1 -> 2*N = 2)
-------------------------------------
- Simulated dynamics
- Collision detection
	Since the dynamics and collision detection are obviously intimately related, I will discuss them both at once here.  I must first say that I got most of my ideas from Chris Hecker's great articles on game physics (see References), which are a must for anyone trying to do accurate dynamic modeling.  I also got some great ideas for pool specifically from Jeff Hacker's article (and its associated source code).  I did my best to include all of the physics phenomena I could to make this as realistic as possible.
	First of all, the balls move according to all the laws of physics.  Each ball keeps track of its position, velocity, orientation, and angular velocity at all times.  External forces and torques can be applied to the balls either from friction, collisions, or striking a ball with the cue stick.  For each time step, the position and orientation are updated from the velocity and angular velocity, which are updated from any external forces and torques, which all together creates realistic motion.  A maximum time step is specified to make sure that the motion appears to be continuous.
	There is a lot more to shooting pool than these simple equations, though.  Obviously collision with a wall is different than collision with another ball, and is even different than a collision with the table surface.  Friction between these surfaces is also different.  Each type of collision/contact was characterized by the two objects in collision (ball-wall, ball-ball, ball-table, ball-floor, etc.) and each type of collision had its own relevant parameters, as follows:
- Coefficient of restitution: this measures the elasticity of a collision
- Coefficient of friction: this measures how much friction occurs between two objects in contact
- Damping coefficient: this measures how much velocity is lost after the collision
	Friction itself also is a little more complicated.  The coefficient of friction, for instance, is different between two surfaces in static contact and two surfaces contacting as they move relative to one another.  Another issue is that when a ball is rolling its contact point is not moving with respect to the surface- thus using the classical friction model, the ball would roll forever without slowing down.  All of these cases are handled in this game.  Contact surface relative velocity is tested to determine whether static or kinetic friction is applied, and any balls determined to be in the rolling state are given an additional friction force to slow down the roll.
	Another special case I had to deal with was dealing with gravity.  Obviously, if the ball was always in the plane of the table, I could just throw out gravity and treat it as a 2D system.  That was not an option.  On the other hand, if I applied gravity at all times, I would have to recalculate the table's reaction force at each time step, which would be too many needless calculations.  A third option would be to apply gravity only when the ball was off the table, but then there would be infinite oscillations between the ball and table due to alternately having a upward velocity and a downward force as the ball got near the surface of the table.  I handled this by keeping track of when a ball left the table, and only allowed the ball to leave the surface of the table when its upward velocity was enough so that gravity would not return the ball back past the table surface in the next time step.  This "escape velocity" calculation seemed to have quite a realistic effect, and was really the best of both worlds.  I didn't have to calculate the table reaction force at every time step, and I could still handle vertical motion when appropriate.
	So how did I detect collisions or contact and when was it applied?  There were really two parts to this - first, I had to determine the actual time when contact occurred, and simultaneously I had to determine the type and direction of contact that occurred and respond accordingly.
	The algorithm for determining the time of contact was obtained from the Baraff paper and Hecker's article on collision response (see references).  Basically, it involved stepping forward until collision was detected, then continually trying again with a smaller last time step, until the moment of exact contact was found.  At that point, using the state of the objects at the time of collision, apply an impulse (both force and torque) to the colliding objects that both prevented collision and update their velocity/angular velocity to be consistent with the result of the collision.  
	This algorithm made possible many of the interesting effects you see in the game.  Since all of the possible collisions had all of the parameters listed above, this is how I achieved spin transfer upon collision between the balls and between the ball and a wall.  Also, by increasing the cue stick angle so that you were shooting the ball into the table, you could make the ball "jump" - in some cases, you could use this to your advantage by jumping over other balls to make a cleaner shot.  In some cases, many collisions would be detected at the same time, as in the case of the break at the beginning of the game.  This was handled by resolving all collisions at each time step until a satisfactory result was obtained.  You might notice on a break that when the cue ball hits the front ball on a break, the middle balls don't move much at first - just like in the real game!
	The only thing that remains was how a state of collision was actually detected.  Well, since the balls were spheres, it was silly to do anything more than simply testing the distances between their centers.  It was very quick and clearly nothing could be more accurate.  But the table was another story.  For this, I implemented a collision detection system, borrowing some ideas from the V-Clip algorithm (see references).  Basically, the gist of my version of the algorithm is that I would determine the closest feature (face, edge, or vertex) of the closest polygon on a 3d object (the table in most cases) and calculate the distance of the ball center to that feature using the clipping planes of that closest feature.  The result would give me both a collision distance and direction, by which the collision response effects discussed above could be calculated.
	To do this, there were a couple of things I had to do.  First, I made a simpler version of the table model.  The version you see was unnecessarily complicated (to get the lighting effects that I was after) for efficient collision detection computation (though it also would have worked - just a little slower).  Second, I also had to create a way to load this model from the .obj format to something that I could use for my collision detection routines.  I ended up implementing some functions that used the data structures from the glm.h/glm.c source code, and created collision objects (containing triangles, their edges, vertices, clipping planes and normals) that I could use for collision detection.  The result was actually such that it would work for collision detection between the balls in the game and ANY objects that were loaded from the .obj format!  I didn't use this functionality, but clearly I could have brought in another table model and everything should have worked just fine.
	There is one more piece of information I used for collision detection.  Clearly, for some polygons, the collision normals should always be the same as the face normals (as in the case of a flat surface).  For other polygons, the collision normals will depend on the collision, as in a collision with a polygon with an exposed edge (as in the bumper).  To properly specify which model should be used, this information was kept in the collision object to use when resolving collisions.

6. Not-So Advanced Features, But Features Nonetheless
-----------------------------------------------------
- On screen control panel
	I had big plans for making something much more interesting here, but I did do some simple things that I definitely feel are integral to the game.  The player should know when it is his turn, which type of balls he is shooting at, and how many are left.  All this is on the screen, as are current parameters for your shot while you are preparing to shoot.

- Sound (sort of)
	Well, technically there is no sound, but since I spent $16.95 to gain access the ultimate sound archive, I had to include the .wav files I intended to use.  I ended up just plain running out of time, and couldn't add this feature.  From the sound-examples, I expected sl to be ready to go on the sweet hall computers, but this wasn't the case, and I didn't have time to figure out how to get it there at the last minute.

7. Other points of interest
---------------------------
   - In trying the make the game as true-to-life as possible, I used all of the regulation sizes, weights, etc. for my game.  I also made the game engine work according to the actual regulation rules (with a couple of exceptions that I will mention).  All of this information was found in "The Rule Book" - a must for any sports fans. (see references)
	
   - Once such exception was that instead of allowing the user to place the cue ball at the start of the game or after a scratch, I decided to have the cue ball drop in from off the table - this was an opportunity to show the 3d nature of the game, and was especially cool, if there happened to be balls in the way of the ball dropping in - you might even get some balls knocked in before your shot!

   - I had seen on another pool game (Havok.com) that you could see the balls under the table after you made them.  I thought this was a cool idea, so in my game, whenever you make a shot, the ball is dropped to the trough under the table, where you can see the made balls through an opening in the table's base.

   - No game is any good without a closing scene.  In this game, the winner of a two player game gets a trip to the "Magic Eight Ball" room, where they are greeted by a giant 8 ball on a stool, and can ask it a question.  The Magic Eight Ball knows all and is always ready with an answer.

   - Time was updated using the algorithm presented in the help session to make sure that things happened at the right speed regardless of the speed of the computer.

   - Unexpected happenings. Though it is rare, there is the potential in any game for problems to occur.  In the unlikely event that a ball enters a collision situation that it cannot get out of due to any reason, this will trigger a "magic pocket" to be formed, and the ball is seamlessly removed from the table as the game continues.  Yes, it is admittedly a hack that I added at the last second in case there were any problems in my demo, but it is better than the program crashing, and someone playing the game would definitely find it a cool feature rather than an annoying program crash.

8. External programs used
-------------------------
QME Lite - used to build new 3d models and edit existing 3d models.  I used this a ton, especially in making the table have all the properties I wanted.
UVMapper - used to generate texture coordinates on the obj files, for great texture mapping effects
3D Exploration - used to preview my models and textures, and convert between 3d formats
Corel PhotoPaint & Paint Shop Pro - used both of these to make textures, including the ball textures, which I made from scratch (no pun intended)
Visual C++ - used for most of my development

9. External code used
---------------------
glBDF - used for on-screen fonts
texture.h/texture.c - used to read in textures from rgb format
glm.h/glm.c - used to read in objects from obj format

I also looked at the source code from Jeff Lander's sample application (associated with his article listed below), where he implemented a very simple pool game that had no ball rotation or pockets or complexity in general (it only had two balls).  I used some of his ideas for the data structures to use and general ideas on the overall structure of the simulation.  I also actually used some of his utility code for some of the simple math routines (dot products, cross products, etc. - see vecmath.h/vecmath.c)  I clearly could have written these myself, but since he had a file with just these mathematical functions, it seemed silly to redo this stuff when I was creating my physics engine.  I actually ended up adding some extra utilities to this file to do some other mathematical operations I needed.

10. External sources of assets
------------------------------
Objects 
   -Pool table (before my extensive modifications) - 3D Café
   -Stool, cuestick, cue rack, triangle, lamps - 3D Café
   -Pool table base - Havok.com (included in their pool game distribution)

Textures
   -Wood on table and stools - Francesco Franceschi
   -Metal on lamps - Mann Made Images
   -Logs, Carpet, Stucco (on ceiling) - Textureartist.net
   -Felt on table and ball textures - all me

11. References
-----------------
Baraff, David.  An Introduction to Physically Based Modeling: Rigid Body Simulation II - Nonpenetration Constraints.   SIGGRAPH '97 course notes.  

Eberly, David.  Distance Between a Point and a Triangle.  Magic Software Website.

Hecker, Chris.  Physics, The Next Frontier.  Game Developer Magazine, October/November 1996.

Hecker, Chris.  Physics, Part 2: Angular Effects.  Game Developer Magazine, December 1996/January 1997.

Hecker, Chris.  Physics, Part 3: Collision Response.  Game Developer Magazine, March 1997.

Hecker, Chris.  Physics, Part 4: The Third Dimension.  Game Developer Magazine, June 1997.

Lander, Jeff.  Physics on the Back of a Cocktail Napkin.  Game Developer Magazine, September 1999.

Midgley, Ruth, ed.  The Rule Book.  St. Martin's Press, 1983.

Mirtich, Brian.  V-Clip: Fast and Robust Polyhedral Collision Detection.  Mitsubishi Electric Research Laboratory, Technical Report TR-97-05.


12.  Final thoughts
---------------------
I have never worked harder on a class project than on this one - I spent nearly every waking hour the last two plus weeks on it, and never went home from my office the last three days.  I was pretty stressed up until the very end, despite my endless work, I wasn't actually able to play a full game without any problems until about 11 pm the night before the demo.  But, in retrospect, it was also a lot of fun. I learned a ton, including that the people in this class are capable of incredible things.  I thought my project was really good as I worked mostly by myself in my own lab, but I was amazed by what people came up with for the competition.  Wow.
