Introduction
Vectors are very important in implementing games. They are used to define the direction of an object also defines the velocity which needs direction and speed. We are going to introduce the algebra of vectors, and then we will show how to use vectors in our programs by applying a simple example. An example of two bouncing balls inside a box will be introduced. The vectors will be used to define the direction of the circles (balls) while moving, also it will define the direction after bouncing. Two types of bouncing (collision) will be introduced; the first is line-circle collision and the second is circle-circle collision.
Vectors
The vector specifies a direction and magnitude and has no location. It can be represented by 3D coordinate. The addition of two vectors is represented in Fig.1 To add two vectors we use the parallelogram rule.
The dot product of two vectors or more generally the inner product of two vectors is a scalar
v1 • v2 = x1x2 + y1y2 + z1z2
the dot product is useful in defining the magnitude of the vector, also is can be used to define the angle between the two vectors. The cross product or the vector product of two vectors is a vector; the direction of the resulting vector is perpendicular on both the original vectors. The right-hand rule is used to dictate the direction of the cross product.
Combining the cross product and the dot product we can get the angle between two lines. The dot product of two vectors a,b is given by
…………………………………………………………….. (1)
The cross product is given by
……………………………………………………………(2)
The dot product and cross product is shown in Figure 6.1-4. The cross product is a vector perpendicular to both a,b. solving equations (1) and (2) together gives
……………………………………..……………………………(3)
From equation (3) we can get the angle between the two lines.
We have implemented the Vector3D class, we defined the most useful features of vectors the implementation of the Vector3D is shown in the following code segment
class Vector3D
{
public:
float x, y, z;
public:
virtual ~Vector3D();
// three-dimensional Cartesian coordinates
// constructors
Vector3D (void)
{x = y = z = 0;}
Vector3D (float X, float Y, float Z)
{
x = X; y = Y; z = Z;
}
// vector addition
Vector3D operator+ (const Vector3D& v)
const {return Vector3D (x+v.x, y+v.y, z+v.z);
}
// vector subtraction
Vector3D operator- (const Vector3D& v)
const {return Vector3D (x-v.x, y-v.y, z-v.z);}
// unary minus
Vector3D operator- (void) const
{
return Vector3D (-x, -y, -z);
}
// vector times scalar product (scale length of vector times argument)
Vector3D operator* (const float s) const
{return Vector3D (x * s, y * s, z * s);}
// vector divided by a scalar (divide length of vector by argument)
Vector3D operator/ (const float s) const {return Vector3D (x / s, y / s, z / s);}
// dot product
float dot (const Vector3D& v) const
{return (x * v.x) + (y * v.y) + (z * v.z);}
// length float length (void) const
{return (float)sqrt(lengthSquared ());}
// length squared
float lengthSquared (void) const
{return this->dot (*this);}
// normalize: returns normalized version (parallel to this, length = 1)
Vector3D normalize (void) const
{
// skip divide if length is zero
const float len = length ();
return (len>0) ? (*this)/len : (*this);
}
// cross product
void cross(const Vector3D& a, const Vector3D& b)
{
*this = Vector3D ((a.y * b.z) - (a.z * b.y), (a.z * b.x) - (a.x * b.z), (a.x * b.y) - (a.y * b.x));
}
// assignment
Vector3D operator= (const Vector3D& v)
{ x=v.x; y=v.y; z=v.z; return *this; }
// set XYZ coordinates to given three floats
Vector3D set (const float _x, const float _y, const float _z)
{ x = _x; y = _y; z = _z; return *this; }
// +=
Vector3D operator+= (const Vector3D& v)
{return *this = (*this + v);}
// -=
Vector3D operator-= (const Vector3D& v)
{return *this = (*this - v);}
// *=
Vector3D operator*= (const float& s) {return *this = (*this * s);}
// equality/inequality
bool operator== (const Vector3D& v) const
{return x==v.x && y==v.y && z==v.z;}
bool operator!= (const Vector3D& v) const
{return !(*this == v);} };
The operator overloading is used extensively to define the addition, subtraction and multiplication operations. The result of the dot product is a scalar (float), and the cross product produces a vector. Normalizing vector means truncating its length to the unity vector.
The bouncing balls with vectors
The example shows two bouncing balls, colliding in a bounding box, first we will draw the bounding box. Each edge will be a parallel line to the corresponding window edge. The circles will be drawn by the use of GL_POINTS; the polar representation of the circles will be used. The output of our program should be as shown in Fig.3.
We will consider the top edge of the window ( not the white line ) as a line and we will draw another line parallel to that edge and separated from it with defined offset. This edge is the white line in Fig.3, this procedure will be applied to the remaining edges to create the bouncing box.
Finding the parallel line
Suppose we have the following equation for a line
…………….(4)
The offset line is given by
…………….(5)
Where a, b, c are the line’s normalized coefficients, we assume that (a, b) stands for the inwards normal vector of the line. The sliding direction is given by k = ±1. k indicates whether the offset line is situated to the left (-1) or to the right of the line (+1).
The implementation of the above procedure of finding the parallel line is shown by the following code segment
inline CLine getParallelLine(int sliding_direction,float offset)
{
float dx,dy;
Vector3D parallelLineStartPoint3D,parallelLineEndPoint3D;
CLine parallelLine;
dx=endPoint3D.x-startPoint3D.x;
dy=endPoint3D.y-startPoint3D.y;
//The perpendicular direction will be
//k is the sliding direction
normalDirection3D.x=dy*sliding_direction;
normalDirection3D.y=-dx*sliding_direction;
//normalize the direction
normalDirection3D=normalDirection3D.normalize();
parallelLine.setNormal(normalDirection3D);
//multiply by the desired offset
parallelLineStartPoint3D = startPoint3D + normalDirection3D * offset;
parallelLineEndPoint3D = endPoint3D + normalDirection3D * offset;
parallelLine.setStartPoint(parallelLineStartPoint3D);
parallelLine.setEndPoint(parallelLineEndPoint3D);
return parallelLine;
}
The was defined in the class CLine which defines the line by a starting point and ending point and a normal direction.
Drawing the circles
The circles will be drawn by using the polar representation of the circle which is defined by
…………….(6)
We will start from =0 to =359 or generally the circle will be defined for a point in each angle of its 360 degrees. The code for drawing a circle is
inline void Draw()
{
glBegin(GL_POINTS);
for(int angle=0;angle<360;angle++)
{
glPointSize(border_size);
float x,y,z;
x=position3D.x+radius*cos(angle*(PI/180));
y=position3D.y+radius*sin(angle*(PI/180));
z=0; glVertex3f(x, y, z);
}
glEnd( );
}
The code is self explanatory, the loop starts with angle = 0 and ends with angle = 359. since we are working in the 2D environment we will set z=0. glPointSize defines the size of the point and glVertext3f defines the coordinates of the point.
Line-Circle collision
To find the points of intersection between a line and a circle, the code considers the line as generated by the equations:
…………….(7)
where t ranges from 0 to 1 to draw the line segment. The code plugs these equations into the equation for a circle:
…………….(8)
We then solve for t by using the quadratic formula as follow, Plugging (8) into (7) we get
…………….(9)
Then (9) will be reduced into the following quadratic form
…………….(10)
Where
,
and
Then we solve (10) for t by using the following formula
…………….(11)
The result is 0, 1, or 2 values for t. those values are plugged back into the equations (7) to get the points of intersection.
The code for finding the line circle collision is
inline bool IsIntersectedWithLine(CLine myLine)
{
//Line circle intersection
Vector3D intersectP1,intersectP2;
Vector3D startPoint3D=myLine.getStartPoint();
Vector3D endPoint3D=myLine.getEndPoint();
float x1,y1,Cx,Cy;
//the center of the circle
Cx=position3D.x;
Cy=position3D.y;
x1=startPoint3D.x;
y1=startPoint3D.y;
float dx,dy,A,B,C;
dx = endPoint3D.x-startPoint3D.x;
dy = endPoint3D.y-startPoint3D.y;
A = dx * dx + dy * dy;
B = 2 * (dx * (x1 - Cx) + dy * (y1 - Cy));
C = (x1 - Cx) * (x1 - Cx) + (y1 - Cy) * (y1 - Cy) - radius * radius;
float det = B * B - 4 * A * C;
float t;
if(A <= 0.0000001 || det <0)
return false;
else if(det==0)
{
//one solution
t=-B/(2*A);
intersectP1.x=x1+t*dx;
intersectP1.y=y1+t*dy;
return true;
}
else
{
//two solutions
t=(-B+sqrt(det))/(2*A);
intersectP1.x=x1+t*dx;
intersectP1.y=y1+t*dy;
//one solution
t=(-B-sqrt(det))/(2*A);
intersectP2.x=x1+t*dx;
intersectP2.y=y1+t*dy;
return true;
}
}
We have defined another class called CCircle which is defined by a position, direction and radius. The direction vector is very important since it will be used to define the direction of the ball after collision.
Circle-Circle collision
Consider Fig.4 showing two circles with radii r0 and r1. The points p0, p1, p2, and p3 have coordinates (x0, y0) and so forth.
Let d = the distance between the circles’ centers so
…………….(12)
Solving for a gives
…………….(13)
Now there are three cases:
- If d > r0 + r1: The circles are too far apart to intersect.
- If d < |r0 – r1|: One circle is inside the other so there is no intersection.
- If d = 0 and r0 = r1: The circles are the same.
- If d = r0 + r1: The circles touch at a single point.
- Otherwise: The circles touch at two points
The Pythagorean Theorem gives:
…………….(14)
So:
…………….(15)
Substituting a from equation (13) and multiplying this out gives:
…………………………………….….… (16)
The -b2 terms on each side cancel out. We can then solve for b to get:
…………………………………….….… (17)
Similarly:
…………………………………….….… (18)
All of these values are known so you can solve for a and b. All that remains is using those distances to find the point p3.
If a line points in direction, then two perpendicular lines point in the directions <dy, -dx> and <-dy, dx>. Scaling the result gives the following coordinates for the points p3:
…………………………………….….… (19)
Be careful to notice the ± and ± symbols. The implementation of the above procedure is shown in the following code (it is simplified for clarity).
inline bool IsIntersectedWithCircle(CCircle myCircle)
{
//circle circle intersection
float cx0,cy0,radius0;
cx0=this->position3D.x;
cy0=this->position3D.y;
radius0=this->radius;
float cx1,cy1,radius1;
cx1=myCircle.getPosition().x;
cy1=myCircle.getPosition().y;
radius1=myCircle.getRadius();
float dx,dy; float dist;
//float a, h, cx2, cy2;
dx = cx0 - cx1;
dy = cy0 - cy1;
dist = sqrt(dx * dx + dy * dy);
if(dist > (radius0 + radius1)) //no solutions the circles are too far apart
return false;
else if(dist < abs(radius0 - radius1)) //no solution one circle contatins the other
return false;
else if((dist == 0) && (radius0 == radius1)) //the circles coincide
return false;
else { return true;
}
}
The collision by using vectors
In our program, we have used two CCircle objects (firstCircle, secondCircle) and four CLine objects (upLine, downLine, rightLine, leftLine), first we need to draw the four lines, we will draw the four lines in the reshape function, this will force the lines to have the new coordinates relative to the new size of the window. Drawing lines is shown in the following code
void reshape(int w,int h)
{
win_width=w;
win_height=h;
glViewport(0,0,w,h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0,w,h,0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
//initialize the for sides of the screen
upLine.setStartPoint(Vector3D(0,0,0));
upLine.setEndPoint(Vector3D(win_width,0,0));
.setStartPoint(Vector3D(0,win_height,0));
downLine.setEndPoint(Vector3D(win_width,win_height,0));
rightLine.setStartPoint(Vector3D(win_width,0,0));
rightLine.setEndPoint(Vector3D(win_width,win_height,0));
leftLine.setStartPoint(Vector3D(0,0,0));
leftLine.setEndPoint(Vector3D(0,win_height,0));
upLine=upLine.getParallelLine(-1,30);
downLine=downLine.getParallelLine(1,30);
rightLine=rightLine.getParallelLine(-1,30);
leftLine=leftLine.getParallelLine(1,30);
}
We set the startPoint and endPoint of each line as the borders of the window. The lines will be shifted by 30 and drawn inward (by using the sliding direction +1, -1). The getParallelLine will get the parallel components of the edges of the window.
When a ball is intersected with line it will be diverted (reflected) back to the bounding box, the direction of the ball after colliding with a line of the box will be the summation of the normal vector of the line and the current direction of the ball. In Fig.5 (a) we can conclude that
-U + V = N
where U is the original direction of the ball and V is the direction after collision, we have used the vector addition to get V, solving for V we get
V= N+U
We introduced the code for detecting line-circle collision in the render function, as an example we take the upLine and detect the collision between it and the firstCircle as follow
if(firstCircle.IsIntersectedWithLine(upLine) ) { //change the direction of the circle (reflect it) firstCircle.setDirection((upLine.getNormal()+firstCircle.getDirection()).normalize()); }
We changed the firstCircle direction to the summation of the normal of the line and the current direction of the firstCircle.
For the two circles, when colliding we need to get the tangent line’s normal, this direction is obtained by subtracting the first circle position from the second circle position. We then use the vector addition to get the new direction for each ball as follow
V1= N1 + U1
V2= -N1 + U2
The implementation of the collision between the two balls will is shown in the following code
if(firstCircle.IsIntersectedWithCircle(secondCircle))
{
//get the direction of the circles toward each other
//the direction is from firstCircle center to secondCircle center
Vector3D circleCircleDirection =secondCircle.getPosition()-firstCircle.getPosition();
circleCircleDirection=circleCircleDirection.normalize();
firstCircle.setDirection((firstCircle.getDirection()-circleCircleDirection).normalize());
secondCircle.setDirection((secondCircle.getDirection()+circleCircleDirection).normalize());
}
We define the direction between the two centers of the circles then we change the direction of the two balls to the new direction which is obtained from vector addition.
Source Code
To download a sample code of the above tutorial click here