Ali Reza Faiz gte750r@mail.gatech.edu
Charles Brian Quinn gte430p@mail.gatech.edu

TRING is a variation of the Carom Billiard game, invented by Professor Jarek Rossignac. It is played on a circular pool table with three balls: one red, one green, and one blue (as appropriate for a Graphics course). Players take turns and use a billiard cue to strike one of the balls. On each shot, a different ball is struck, cycling through the three colors. First red, then green, then blue, red again and so on. Suppose that the red ball is struck with the cue, if it touches the other two, the player scores one point and plays again, striking the green ball this time. When the cue ball (the ball struck by the cue) stops before touching the other two, the next player will play the ball with the next color in the cycle. First to reach 21 wins.

TRING is an OpenGL game programmed in C++ and with the GLUT utilities.  The goal of this version of TRING is to implement a realistic simulation using physics models to represent motion, collisions, and interactions in 2D and 3D.

Detailed schedule of project.

Milestone 1: due November 7 (by 3 pm)
Milestone 2: due November 14 (by 3 pm)
Milestone 3: due November 21 (by 3 pm)
Final Report: due December 1 (by midnight)

The high-level organization of code:

The main driver file is divided into segments that handle various aspects of the game.  It includes the sections for initialization, drawing, handling input, and physics.  Through the use of the GLUT libraries, the main file contains methods that divide the code into display, input-handling, and initialization sections.  The included files (tmatrix, tray, tvector, and math functions) handle various matrix, ray, vector and math manipulations.  These libraries are publicly available at http://nehe.gamedev.net/. 

For complete list of files and source code, see bottom of page.

In order to create a realistic simulation, we will attempt to use physics principles to imitate certain aspects of the game.

We will parameterize each ball in terms of its velocity.  We will then be able to describe each ball in terms of a velocity vector and an associated time.  Using this, we can calculate the position of a ball after a certain time, t:

A(t) = A + tV

We can then use the fact that each ball has a similar equation for its position at a certain time to find the collision by solving for t:

||AB||^2 = (2r)^2
(B - A).(B - A) = 4r^2
(B - A - tV).(B - A - tV) = 4r^2
AB.AB + t^2*v^2 - 2(AB.V)t = 4r^2

We must also be able to calculate the positions of two balls moving, to determine if they collide.  We could do this by parameterizing both and solving, like so:

A(t) = A + tV
B(t) = B + tU
||A(t)B(t)||^2 = 4r^2

But this could turn complex.  We could use the fact that the vectors combined will result in an appropriate vector for determining if they collide.  If we sum the vectors U and V, we can obtain the result.

We now must find the contact position between the two objects (ball and ball, or ball and wall).  We can use a trick and reduce the radius of one ball to a point, and add to the resulting ball the radius we subtracted.  We know they collide by using the equations above, so we can now determine the point at which they make contact.

Now, we turn to obtaining the velocities and directions of the resulting collisions.  We must use the equations of momentum conservation and kinetic energy conservation:

To conserve momentum, we use:

AVn + BVn = AV'n + BV'n

We can calculate the respective momentum (and therefore velocity) of one ball striking a static ball by setting one ball's initial velocity to 0.  We find that now, the resulting velocity is simply the sum of the initial velocity of one.  We know that the balls will have similar (if not identical) masses, and therefore it reduces to each determining one-half of the result:

AVn + B(0) = AV'n + BV'n
AVn = AV'n + BV'n

To conserve kinetic energy, we use:

(1/2)AVn^2 + (1/2)BUn^2 = (1/2)AV'n^2 + (1/2)BU'n^2

We can calculate the resulting velocity of two balls upon one striking a static ball by setting one to 0 (as demonstrated above).  We find that since kinetic energy is conserved, the resulting balls will together (summed) have no more velocity than the initial moving ball's velocity.

We now know:

-time (and location) of collision for 1 ball moving
-time (and location) of collision for 2 balls moving
-time (and location) of collision for 3 balls moving (we assume)
-contact position
-new velocities for 1 ball static
-new velocities for 2 balls moving
-friction (deceleration)

We can now attempt to use some pseudo-physics to implement the principle of English, or cue-placement.  Depending on where one strikes the ball (only vertically for now), it will determine the amount of "spin-back" of the ball.  Rather than implementing the physics equations the spin factor, we will instead change the masses of the balls to compensate. 

If the ball is hit dead center, its mass will be simply m.  If the ball is hit on the bottom, it will be (m/2), at the top, it will be 2m.  We will range the mass along the center by fractions of m.

To simplify the collision with the outer wall, we use a ray-hit-cylinder method for fast detection.  We could have simply simulated the outer edge of the pool table as a sphere with an extremely large mass, but the cylinder method provides a faster detection method for collisions.

To create a 2D simulation of the TRING game, we employed a goal-centered approach.  We implemented the 3D version, but translated the view, mouse, and screen coordinates in the 2D simulation to a top view to simulate a 2D representation.  The game actually operates in 3D, but is a simulated 2D version.

The view is:

/* eye point coordinates for view */
GLfloat eye_x = 0.0001;
GLfloat eye_y = 0;
GLfloat eye_z = 20;
....
gluLookAt(set_eye_x,set_eye_y,set_eye_z, 0,0,0, 0,0,1);

In order to translate screen coordinates to the 3D coordinates of the board, we make a fairly accurate conversion, based on the view point.  We are assured this will work as long as the view is not rotated (which can only be done in the 3D view window).  The screen conversion is as follows:

 /* Scaling the screen map to the board */
startX = (GLfloat) (WINY - y - 400) * -0.033333;
startY = (GLfloat) (x - 400) * 0.033333;

Mouse movements are converted by these scaling factors that incorporate one half the height and width of the screen.  This allows the "cue stick" to be drawn on the board in the appropriate place scaled and translated to appear "above" the balls.

/* display cue stick arrow */
void display_arrow()
{
  float scale_factor = 0;
  
  glPushMatrix();
    glMaterialfv(GL_FRONT_AND_BACK, GL_AMBIENT_AND_DIFFUSE, mat_cue);
    glTranslatef(startX,startY,ball_r+1);
    glRotatef(angle+90, 0, 0, 1);
    glRotatef(90, 1, 0, 0);
    scale_factor = sqrt( (startX - endX) * (startX - endX) + 
			 (startY - endY) * (startY - endY) );
    glScalef(1,1,scale_factor/3); 
    gluCylinder(quadObj, 0.1, 0.2, 3, 50, 50);
  glPopMatrix();
}

To simulate the physics properties, we employ methods based on physical principles.  The method find_collision() takes in the cue ball as the first parameter, and simulates the collisions with other balls and the wall.

/* find if any of the current balls intersect with each other in the 
 * current timestep.  returns the index of the 2 intersecting balls, 
 * the point and time of intersection */
int find_collision(TVector& point, double& timePoint, double time2, 
	     int& ball1, int& ball2) {

  TVector relativeV;
  TRay rays;
  double Mytime = 0.0, Add = time2/150.0, timedummy = 10000, timedummy2 = -1;
  TVector posi;
  
  for (int i = 0; i < ball_count - 1; i++){
    for (int j = i+1; j < ball_count; j++){

      // Find Distance
      relativeV = ball_vel[i]-ball_vel[j];
      rays = TRay(old_pos[i],TVector::unit(relativeV));
      Mytime = 0.0;
      
      // If distance detween centers greater than 2*radius an 
      // intersection occurred loop to find the exact intersection point
      if ( (rays.dist(old_pos[j])) > ball_r * 2 ) 
	continue;  
      
      while (Mytime < time2) {
	Mytime += Add;
	posi = old_pos[i] + relativeV*Mytime;
	if (posi.dist(old_pos[j]) <= ball_r * 2 ) {
	  point = posi;
	  if (timedummy > (Mytime - Add)) timedummy = Mytime-Add;
	  ball1 = i;
	  ball2 = j;
	  break;
	}
      }
    }
  }
  
  if (timedummy!=10000) { 
    timePoint=timedummy;
    return 1;
  }
  
  return 0;
}

To compute the resulting velocities, we use the following code (taken from compute_velocities()):

	.....
	/* V1,V2 are the new velocities after the impact */
	V1x=( (U1x*mass[ball1]+U2x*mass[ball2] - 
	     (U1x-U2x))*mass[ball2] ) * 
	  (1 / (mass[ball1] + mass[ball2]));
	V2x=( (U1x*mass[ball1]+U2x*mass[ball2] - 
	     (U2x-U1x))*mass[ball1] ) * 
	  (1 / (mass[ball1] + mass[ball2]));
	V1y=U1y;
	V2y=U2y;
	.....

Note the existence of the conservation of momentum equations to calculate the resulting velocities.

The user interface is comprised of 3 windows.  The main 2D view window is located prominently in the center.  The 3D view is located in the top right, and the score window is located just below that.  These windows appear upon program execution. 

The main view relies on mouse input to determine cue stick placement.  The user may click on a ball (where the start point is snapped automatically to the center of the ball) and then drag back to determine the power of the shot.  The user may then right click to cancel, or click once again to proceed with the shot.  The 2D view animates, and the 3D view animates at the same time.

The 3D view operates using mouse commands.  You can click and drag to rotate the view.  You can even do this while the game is moving the balls.  You can even flip the table over and play Tring upside down.  Try it out!

The score and current turn window is updated after each turn.

Click on any of the following screen shots to get a larger view.  It was hard to capture the movement of the balls, as the OpenGL window was subject to updates outside of the screenshot program.  It produced some weird effects, but they are not included below.

Complete source code is available below.

Makefile
defs.h
prj4.cpp
tmatrix.cpp
tmatrix.h
tray.cpp
tray.h
tvector.cpp
tvector.h
mathex.h

Entire source: proj4.tar.gz