TRING
A Modified Carom Billiards Game
Physics Implementation

Conservation of Kinetic Energy
KE = ½ mv2

Conservation of Momentum
p = mv

m = mass, v = velocity 

And for acceleration, we use the equations:
S = v0t + ½ a * t2

From these, we dirived the following vector based quartic:
d2 = ||(P + Vp*t + ½*ap*t2) - (Q + Vq*t + ½*aq*t2)||2
Where P and Q are the positions of the balls, Vp and Vq are the velocity vectors and ap and aq are the acceleration vectors in the direction of the velocity
We then substitute A, B and C in the following manner:
A = P - Q
B = Vp - Vq
C = ½ap - ½aq
and finally get the quartic:
1/4*t4C2 + 2*t3BC + (2AC + B2)t2 + 2ABt + A2

Then, using a function we acquired to solve quartic functions, we solve for the 4 roots and choose the best one.
When solving for a collision with the wall, we use the same method, except there is no second velocity or position.

The times are chosen at the beginning of each "time period" when the intersects function is called between all the balls.
The relevant functions can be seen below

Our Path class has a method that takes in another path and returns the earliest time that these paths collide (when they represent balls of size BALL_RADIUS), or -1 if they do not collide:

GLfloat
Path::intersects(Path &p)
{
    Vector A = position - p.position;
    Vector B = velocity - p.velocity;
	Vector C = 0.5f * (accel(velocity) - accel(p.velocity));
    
    GLfloat AdotB = A.dot(B);
    GLfloat BdotB = B.dot(B);
    GLfloat AdotA = A.dot(A);
	GLfloat AdotC = A.dot(C);
	GLfloat BdotC = B.dot(C);
	GLfloat CdotC = C.dot(C);

	GLfloat d2 = 4 * tring->getBallRadius() * tring->getBallRadius();

    double quartic[5];
	quartic[0] = AdotA - d2;
	quartic[1] = 2 * AdotB;
	quartic[2] = (2 * AdotC + BdotB);
	quartic[3] = (2 * BdotC);
	quartic[4] = CdotC;
	    
	double roots[4];
	
    int numRoots = solveQuartic(quartic, roots);

	if(numRoots == 4 && roots[0] > roots[2]){
		//put the smallest pair first
		double t1 = roots[0];
		double t2 = roots[1];
		roots[0] = roots[2];
		roots[1] = roots[3];
		roots[2] = t1;
		roots[3] = t2;
	}
	if(numRoots > 1)
		return(getMin(roots[0], roots[1]));
	else
		return(-1);
}

Similarly, the method for checking for collisions with the table is the following:

GLfloat
Path::intersects(Table &t)
{
	Vector A = position;
    Vector B = velocity;
	Vector C = 0.5f * accel(velocity);
   
    GLfloat AdotB = A.dot(B);
    GLfloat BdotB = B.dot(B);
    GLfloat AdotA = A.dot(A);
	GLfloat AdotC = A.dot(C);
	GLfloat BdotC = B.dot(C);
	GLfloat CdotC = C.dot(C);

	GLfloat d = (t.getRadius() - tring->getBallRadius());
    GLfloat d2 = d * d;	

    double quartic[5];
	quartic[0] = AdotA - d2;
	quartic[1] = 2 * AdotB;
	quartic[2] = (2 * AdotC + BdotB);
	quartic[3] = (2 * BdotC);
	quartic[4] = CdotC;    

	double roots[4];
    int numRoots = solveQuartic(quartic, roots);

	if(numRoots == 4 && roots[0] > roots[2]){
		//put the smallest pair first
		double t1 = roots[0];
		double t2 = roots[1];
		roots[0] = roots[2];
		roots[1] = roots[3];
		roots[2] = t1;
		roots[3] = t2;
	}
	if(numRoots > 1)
		return(getMax(roots[0], roots[1]));
	else
		return(-1);	
}

Now, those methods just tell us when the collisions occur. The following methods tell us the resulting paths after the collisions have taken place. This is where the collision physics come into play. We start with the collisions between balls:

void
Path::collides(GLfloat t, Path &p2, Path &newP1, Path &newP2)
{
	Vector newPos1;
	Vector newPos2;

	newPos1 = position + velocity * t + .5f * accel(velocity) * t * t;
	newPos2 = p2.position + p2.velocity * t + .5f * accel(p2.velocity) * t * t;	
	
	Vector finalV1;
	Vector finalV2;

	finalV1 = velocity + accel(velocity) * t;
	finalV2 = p2.velocity + accel(p2.velocity) * t;

	GLfloat m1 = 1.0f;
	GLfloat m2 = 1.0f;
	
	Vector n = (newPos2 - newPos1).normalize();
	GLfloat e = .8f;							// The coefficient of restitution
	GLfloat c = n.dot(finalV1 - finalV2 );

	GLfloat b1 = ((c * m2) / (m1 + m2)) * (1 + e);
	GLfloat b2 = ((c * m1) / (m1 + m2)) * (1 + e);

	Vector bah1 = n * b1;
	Vector bah2 = n * b2;

	Vector v1f = finalV1  - bah1;
	Vector v2f = finalV2  + bah2;

	newP1.setVelocity(v1f);
	newP2.setVelocity(v2f);

	newP1.setPosition(newPos1);
	newP2.setPosition(newPos2);	
}

Note the coefficient of restitution which currently is just 1, but for which we have plans to implement English. And now for the wall collisions:

void
Path::collides(GLfloat t, Table &table, Path &newP1)
{	
    GLfloat two = 2.0f;
	Vector newPos1 = position + velocity * t + .5f * accel(velocity) * t * t;	

	Vector vf = velocity + accel(velocity) * t;
    
    Vector n = (Vector(0.0f, 0.0f, 0.0f) - newPos1).normalize();
    Vector negV = Vector(0.0f, 0.0f, 0.0f) - vf;
    
    GLfloat negVdotN = negV.dot(n);
    Vector bah = n * negVdotN;
    
    Vector bahTimes2 = bah * two;
    
    Vector v1f = bahTimes2 + vf;

#define TABLE_RESPONSE 0.95f 

	newP1.setVelocity(v1f * TABLE_RESPONSE);	
	newP1.setPosition(newPos1);
}

Also, we have a method for generating all of the paths that will ever occur. This is done when the user has made his velocity selection and releases the mouse button.

void Tring::doPrediction(){
	
	GLfloat currentTime = 0;
	scoreTime = -1;

	/*  In order for a point to happen, the current ball, designated
        by the hitting variable, must hit the other two balls at some
        point */
	bool hits[3];
	hits[0] = hits[1] = hits[2] = false;

	while(currentTime <= endTime + 1){
		
		//See if all balls stopped, if so, end this

		if(	ballPaths[0]->getCurrentPath()->getVelocity().length() == 0 &&
			ballPaths[1]->getCurrentPath()->getVelocity().length() == 0 &&
			ballPaths[2]->getCurrentPath()->getVelocity().length() == 0){
			endTime = currentTime;
			break;
		}

		GLfloat minTime = HUGE_FLOAT;
		GLfloat st = 0;

		int p1 = -3, p2 = -3;
		for(int a = 0 ; a < 3 ; a++){			

			for(int b = 0; b < 3 ; b++){
				//Don't want tot check with itself, but I want a reduntant check, just cuz :P

				if(a == b)
					continue;
				//Check for hitting of any of the other balls

				GLfloat t = ballPaths[b]->getCurrentPath()->intersects(*ballPaths[a]->getCurrentPath());
								

				//See if it's closer than anything else

				if(t < minTime && t >= 0){
					//HAX

					if(t == 0){
						cout<<"HAX"<<endl;
						t = -TINY_FLOAT;
					}
					//END HAX

					minTime = t;
					p1 = a;
					p2 = b;
				}				
			}
            
			//Check to see when the ball hits the edge of the table			

			GLfloat t = ballPaths[a]->getCurrentPath()->intersects(*tringTable);			

			if(t < minTime && t >= 0){
				//HAX

				if(t == 0){
					cout<<"HAX"<<endl;
					t = -TINY_FLOAT;
				}
				//END HAX

				minTime = t;
				p1 = a;
				p2 = -1;
			}			

			
			//Check to see when the ball will stop, if not already stopped

			if(ballPaths[a]->getCurrentPath()->getVelocity().length() > 0){
				st = -ballPaths[a]->getCurrentPath()->getVelocity().length() / decelerateValue;
				if(st < minTime){
					minTime = st;
					p2 = -2;
					p1 = a;
				}
			}
		}
		
		//Increment absolute time to account for the new found collision

		currentTime += minTime;

		//If 2 balls collided

		if(p2 >= 0){

			//Did we hit another ball with the one we hit?

			if((p1 == hitting || p2 == hitting) && scoreTime == -1 && (currentTime) <= endTime){
				hits[p1] = true;
				hits[p2] = true;
				//This is the time that the score happened

				if(hits[0] && hits[1] && hits[2]){
					scoreTime = currentTime;							
				}
			}

			Path *newP1, *newP2;
			newP1 = new Path();
			newP2 = new Path();

			//Get the resultant paths from the collides() function

			ballPaths[p1]->getCurrentPath()->collides(minTime, *ballPaths[p2]->getCurrentPath(), *newP1, *newP2);

			
			//Set the start times of the new paths

			newP1->setStartTime(currentTime);
			newP2->setStartTime(currentTime);

			//Add the paths to the complete ballpath

			ballPaths[p1]->addPath(newP1);
			ballPaths[p2]->addPath(newP2);
			
			//Now we need to create a new path for the ball that's NOT

            //involved, so all times are synchronized

			for(int a = 0 ; a < 3 ; a++)
				if(a != p1 && a != p2){
					Path *newp =
                        new Path(*ballPaths[a]->getCurrentPath());
					newp->setStartTime(currentTime);

					newp->setPosition(newp->getPosition() + newp->getVelocity() * minTime + .5f * accel(newp->getVelocity()) * minTime * minTime);
					newp->setVelocity(newp->getVelocity() + accel(newp->getVelocity()) * minTime);
									
					ballPaths[a]->addPath(newp);
				}
		}
		//If the a ball hit the wall

		else if (p2 == -1){

			Path *newP1;
			newP1 = new Path();

			//Get the resultant path

			ballPaths[p1]->getCurrentPath()->collides(minTime, *tringTable, *newP1);

			//Set the new path start time

			newP1->setStartTime(currentTime);
					
			//Add the path to the total path

			ballPaths[p1]->addPath(newP1);

			//Syncrhonize the paths of the other 2 balls

			for(int a = 0 ; a < 3 ; a++)
				if(a != p1){
					Path *newp =
                        new Path(*ballPaths[a]->getCurrentPath());
					newp->setStartTime(currentTime);
					
					//Set the accel value of the last path before this one


					//Set new position based on velocity, time & accel

					newp->setPosition(newp->getPosition() + newp->getVelocity() * minTime + .5f * accel(newp->getVelocity()) * minTime * minTime);
					newp->setVelocity(newp->getVelocity() + accel(newp->getVelocity()) * minTime);
										
					ballPaths[a]->addPath(newp);
				}

		}
		else if(p2 == -2){
			//a ball stopped

			Path *newP1;
			newP1 = new Path();
			Path *temp = ballPaths[p1]->getCurrentPath();			
		
			//Set the new path start time

			newP1->setStartTime(currentTime);		

			//Set the stopping position

			newP1->setPosition(temp->getPosition() + temp->getVelocity() * minTime + .5f * accel(temp->getVelocity()) * minTime * minTime);

			//Set 0 velocity

			newP1->setVelocity(Vector(0, 0, 0));
					
			//Add the path to the total path

			ballPaths[p1]->addPath(newP1);

			//Syncrhonize the paths of the other 2 balls

			for(int a = 0 ; a < 3 ; a++)
				if(a != p1){
					Path *newp =
                        new Path(*ballPaths[a]->getCurrentPath());
					newp->setStartTime(currentTime);
					
										
					//Set new position based on velocity, time & accel

					newp->setPosition(newp->getPosition() + newp->getVelocity() * minTime + .5f * accel(newp->getVelocity()) * minTime * minTime);
					newp->setVelocity(newp->getVelocity() + accel(newp->getVelocity()) * minTime);
										
					ballPaths[a]->addPath(newp);

				}	
		}
		//If it gets here, it means nothing was hit

		else{		
			continue;
		}        
	}
	if(scoreTime > endTime)
		scoreTime = -1.f;
}


navigate
about us
links