Home Game Development Game Physics Cookbook

Game Physics Cookbook

By Gabor Szauer
books-svg-icon Book
eBook $35.99 $24.99
Print $43.99
Subscription $15.99 $10 p/m for three months
$10 p/m for first 3 months. $15.99 p/m after that. Cancel Anytime!
What do you get with a Packt Subscription?
This book & 7000+ ebooks & video courses on 1000+ technologies
60+ curated reading lists for various learning paths
50+ new titles added every month on new and emerging tech
Early Access to eBooks as they are being written
Personalised content suggestions
Customised display settings for better reading experience
50+ new titles added every month on new and emerging tech
Playlists, Notes and Bookmarks to easily manage your learning
Mobile App with offline access
What do you get with a Packt Subscription?
This book & 6500+ ebooks & video courses on 1000+ technologies
60+ curated reading lists for various learning paths
50+ new titles added every month on new and emerging tech
Early Access to eBooks as they are being written
Personalised content suggestions
Customised display settings for better reading experience
50+ new titles added every month on new and emerging tech
Playlists, Notes and Bookmarks to easily manage your learning
Mobile App with offline access
What do you get with eBook + Subscription?
Download this book in EPUB and PDF formats, plus a monthly download credit
This book & 6500+ ebooks & video courses on 1000+ technologies
60+ curated reading lists for various learning paths
50+ new titles added every month on new and emerging tech
Early Access to eBooks as they are being written
Personalised content suggestions
Customised display settings for better reading experience
50+ new titles added every month on new and emerging tech
Playlists, Notes and Bookmarks to easily manage your learning
Mobile App with offline access
What do you get with a Packt Subscription?
This book & 6500+ ebooks & video courses on 1000+ technologies
60+ curated reading lists for various learning paths
50+ new titles added every month on new and emerging tech
Early Access to eBooks as they are being written
Personalised content suggestions
Customised display settings for better reading experience
50+ new titles added every month on new and emerging tech
Playlists, Notes and Bookmarks to easily manage your learning
Mobile App with offline access
What do you get with eBook?
Download this book in EPUB and PDF formats
Access this title in our online reader
DRM FREE - Read whenever, wherever and however you want
Online reader with customised display settings for better reading experience
What do you get with video?
Download this video in MP4 format
Access this title in our online reader
DRM FREE - Watch whenever, wherever and however you want
Online reader with customised display settings for better learning experience
What do you get with video?
Stream this video
Access this title in our online reader
DRM FREE - Watch whenever, wherever and however you want
Online reader with customised display settings for better learning experience
What do you get with Audiobook?
Download a zip folder consisting of audio files (in MP3 Format) along with supplementary PDF
What do you get with Exam Trainer?
Flashcards, Mock exams, Exam Tips, Practice Questions
Access these resources with our interactive certification platform
Mobile compatible-Practice whenever, wherever, however you want
BUY NOW $10 p/m for first 3 months. $15.99 p/m after that. Cancel Anytime!
eBook $35.99 $24.99
Print $43.99
Subscription $15.99 $10 p/m for three months
What do you get with a Packt Subscription?
This book & 7000+ ebooks & video courses on 1000+ technologies
60+ curated reading lists for various learning paths
50+ new titles added every month on new and emerging tech
Early Access to eBooks as they are being written
Personalised content suggestions
Customised display settings for better reading experience
50+ new titles added every month on new and emerging tech
Playlists, Notes and Bookmarks to easily manage your learning
Mobile App with offline access
What do you get with a Packt Subscription?
This book & 6500+ ebooks & video courses on 1000+ technologies
60+ curated reading lists for various learning paths
50+ new titles added every month on new and emerging tech
Early Access to eBooks as they are being written
Personalised content suggestions
Customised display settings for better reading experience
50+ new titles added every month on new and emerging tech
Playlists, Notes and Bookmarks to easily manage your learning
Mobile App with offline access
What do you get with eBook + Subscription?
Download this book in EPUB and PDF formats, plus a monthly download credit
This book & 6500+ ebooks & video courses on 1000+ technologies
60+ curated reading lists for various learning paths
50+ new titles added every month on new and emerging tech
Early Access to eBooks as they are being written
Personalised content suggestions
Customised display settings for better reading experience
50+ new titles added every month on new and emerging tech
Playlists, Notes and Bookmarks to easily manage your learning
Mobile App with offline access
What do you get with a Packt Subscription?
This book & 6500+ ebooks & video courses on 1000+ technologies
60+ curated reading lists for various learning paths
50+ new titles added every month on new and emerging tech
Early Access to eBooks as they are being written
Personalised content suggestions
Customised display settings for better reading experience
50+ new titles added every month on new and emerging tech
Playlists, Notes and Bookmarks to easily manage your learning
Mobile App with offline access
What do you get with eBook?
Download this book in EPUB and PDF formats
Access this title in our online reader
DRM FREE - Read whenever, wherever and however you want
Online reader with customised display settings for better reading experience
What do you get with video?
Download this video in MP4 format
Access this title in our online reader
DRM FREE - Watch whenever, wherever and however you want
Online reader with customised display settings for better learning experience
What do you get with video?
Stream this video
Access this title in our online reader
DRM FREE - Watch whenever, wherever and however you want
Online reader with customised display settings for better learning experience
What do you get with Audiobook?
Download a zip folder consisting of audio files (in MP3 Format) along with supplementary PDF
What do you get with Exam Trainer?
Flashcards, Mock exams, Exam Tips, Practice Questions
Access these resources with our interactive certification platform
Mobile compatible-Practice whenever, wherever, however you want
  1. Free Chapter
    Vectors
About this book
Physics is really important for game programmers who want to add realism and functionality to their games. Collision detection in particular is a problem that affects all game developers, regardless of the platform, engine, or toolkit they use. This book will teach you the concepts and formulas behind collision detection. You will also be taught how to build a simple physics engine, where Rigid Body physics is the main focus, and learn about intersection algorithms for primitive shapes. You’ll begin by building a strong foundation in mathematics that will be used throughout the book. We’ll guide you through implementing 2D and 3D primitives and show you how to perform effective collision tests for them. We then pivot to one of the harder areas of game development—collision detection and resolution. Further on, you will learn what a Physics engine is, how to set up a game window, and how to implement rendering. We’ll explore advanced physics topics such as constraint solving. You’ll also find out how to implement a rudimentary physics engine, which you can use to build an Angry Birds type of game or a more advanced game. By the end of the book, you will have implemented all primitive and some advanced collision tests, and you will be able to read on geometry and linear Algebra formulas to take forward to your own games!
Publication date:
March 2017
Publisher
Packt
Pages
480
ISBN
9781787123663

 

Chapter 1. Vectors

In this chapter, we will cover the following vector operations:

  • Addition

  • Subtraction

  • Multiplication

  • Scalar Multiplication

  • Cross Product

  • Dot Product

  • Magnitude

  • Distance

  • Normalization

  • Angle

  • Projection

  • Reflection

 

Introduction


Throughout this book we are going to explore the mathematical concepts required to detect and react to intersections in a 3D environment. In order to achieve robust collision detection and build realistic reactions, we will need a strong understanding of the math required. The most important mathematical concepts in physics are Vectors and Matrices.

Physics and collisions rely heavily on Linear Algebra. The math involved may sound complicated at first, but it can be broken down into simple steps. The recipes in this chapter will explain the properties of vectors using math formulas. Each recipe will also contain a visual guide. Every formula will also have an accompanying code sample.

Note

This chapter does not assume you have any advanced math knowledge. I try to cover everything needed to understand the formulas presented. If you find yourself falling behind, Khan Academy covers the basic concepts of linear algebra at: www.khanacademy.org/math/linear-algebra.

 

Vector definition


A vector is an n-tuple of real numbers. A tuple is a finite ordered list of elements. An n-tuple is an ordered list of elements which has n dimensions. In the context of games n is usually 2, 3, or 4. An n-dimensional vector is represented as follows:

The subscript numbers are called the components of the vector. Components are expressed as a number or as a letter corresponding to the axis that component represents. Subscripts are indexed starting with 0. For example, is the same as . Axis x, y, z, and w correspond to the numbers 0, 1, 2, and 3, respectively.

Vectors are written as a capital bold letter with or without an arrow above it. and V are both valid symbols for vector V. Throughout this book we are going to be using the arrow notation.

A vector does not have a position; it has a magnitude and a direction. The components of a vector measure signed displacement. In a two-dimensional vector for example, the first component represents displacement on the X axis, while the second number represents displacement on the Y axis.

Visually, a vector is drawn as a displacement arrow. The two dimensional vector would be drawn as an arrow pointing to 3 units on the X axis and 2 units on the Y axis.

A vector consists of a direction and a magnitude. The direction is where the vector points and the magnitude is how far along that direction the vector is pointing. You can think of a vector as a series of instructions. For example, take three steps right and two steps up. Because a vector does not have a set position, where it is drawn does not matter as shown in the following diagram:

The preceding figure shows several vectors, with vector (3,2) appearing multiple times. The origin of a vector could be anywhere; the coordinate system of the preceding figure was omitted to emphasize this.

Getting ready

Video games commonly use two, three, and four-dimensional vectors. In this recipe, we are going to define C++ structures for two and three-dimensional vectors. These structures will expose each component of the vector by the name of an axis, as well as a numeric index.

How to do it…

Follow these steps to start implementing a math library with vector support:

  1. Create a new C++ header file; call this file vectors.h; add standard C-style header guards to the file:

    #ifndef _H_MATH_VECTORS_
    #define _H_MATH_VECTORS_
    
    // Structure definitions
    // Method declarations
    
    #endif
  2. Replace the // Structure definitions comment with the definition of a two-dimensional vector:

    typedef struct vec2 {
       union {
          struct {
             float x;
             float y;
          };
          float asArray[2];
       };
     
       float& operator[](int i) {
          return asArray[i];
       }
    } vec2;
  3. After the definition of vec2, add the definition for a three-dimensional vector:

    typedef struct vec3 {
       union {
          struct {
             float x;
             float y;
             float z;
          };
          float asArray[3];
       };
    
       float& operator[](int i) {
          return asArray[i];
       }
    } vec3;

How it works…

We have created two new structures, vec2 and vec3. These structures represent two and three-dimensional vectors, respectively. The structures are similar because with every new dimension the vector just adds a new component.

Inside the vector structures we declare an anonymous union. This anonymous union allows us to access the components of the vector by name or as an index into an array of floats. Additionally, we overloaded the indexing operator for each structure. This will allow us to index the vectors directly.

With the access patterns we implemented, the components of a vector can be accessed in the following manner:

vec3 right = {1.0f, 0.0f, 0.0f};
std::cout<< "Component 0: " <<right.x<< "\n";
std::cout<< "Component 0: " <<right.asArray[0] << "\n";
std::cout<< "Component 0: " <<right[0] << "\n";

There's more…

Games often use a four-dimensional vector, which adds a W component. However, this W component is not always treated as an axis. The W component is often used simply to store the result of a perspective divide, or to differentiate a vector from a point.

The W component

A vector can represent a point in space or a direction and a magnitude. A three-dimensional vector has no context; there is no way to tell from the x, y, and z components if the vector is supposed to be a point in space or a direction and a magnitude. In the context of games, this is what the W component of a four-dimensional vector is used for.

If the W component is 0, the vector is a direction and a magnitude. If the W component is anything else, usually 1, the vector is a point in space. This distinction seems arbitrary right now; it has to do with matrix transformations, which will be covered in Chapter 3, Matrix Transformations.

We did not implement a four-dimensional vector because we will not need it. Our matrix class will implement explicit functions for multiplying points and vectors. We will revisit this topic in Chapter 3, Matrix Transformations.

 

Component-wise operations


Given two vectors, there are several component-wise operations we can perform. These operations will operate on each component of the vector and yield a new vector.

You can add two vectors component wise. Given two n-dimensional vectors and , addition is defined as follows:

You can also subtract two vectors component wise. Given two n-dimensional vectors and , subtraction is defined as follows:

Multiplying two vectors can also be done component wise. There are other ways to multiply two vectors; the dot product or cross product. Both of these alternate methods will be covered later in this chapter. Given two n-dimensional vectors and , multiplication is defined as follows:

In addition to multiplying two vectors, you can also multiply a vector by a scalar. In this context, a scalar is any real number. Given vector and scalar S, scalar multiplication is defined as follows:

Finally, we can check for vector equality by comparing each component of the vectors being tested. Two vectors are the same only if all of their components are equal.

Getting ready

We're going to implement all of the preceding component-wise operations by overloading the appropriate C++ operators. All of the operators presented in this section can be overloaded in C# as well. In languages that do not support operator overloading, you will have to make these into regular functions.

How to do it…

Follow these steps to override common operators for the vector class. This will make working with vectors feel more intuitive:

  1. In vectors.h, add the following function declarations:

    vec2 operator+(const vec2& l, const vec2& r);
    vec3 operator+(const vec3& l, const vec3& r);
    vec2 operator-(const vec2& l, const vec2& r);
    vec3 operator-(const vec3& l, const vec3& r);
    vec2 operator*(const vec2& l, const vec2& r);
    vec3 operator*(const vec3& l, const vec3& r);
    vec2 operator*(const vec2& l, float r);
    vec3 operator*(const vec3& l, float r);
    bool operator==(const vec2& l, const vec2& r);
    bool operator==(const vec3& l, const vec3& r);
    bool operator!=(const vec2& l, const vec2& r);
    bool operator!=(const vec3& l, const vec3& r);
  2. Create a new C++ source file, vectors.cpp. Include the following headers in the new file:

    #include "vectors.h"
    #include <cmath>
    #include <cfloat>
  3. Add a macro for comparing floating point numbers to vectors.cpp:

    #define CMP(x, y)                    \
        (fabsf((x)–(y)) <= FLT_EPSILON * \
          fmaxf(1.0f,                    \
          fmaxf(fabsf(x), fabsf(y)))     \
       )
  4. Add the implementation of vector addition to the vectors.cpp file:

    vec2 operator+(const vec2& l, const vec2& r) {
       return { l.x + r.x, l.y + r.y };
    }
    
    vec3 operator+(const vec3& l, const vec3& r) {
       return { l.x + r.x, l.y + r.y, l.z + r.z };
    }
  5. Add the implementation of vector subtraction to the vectors.cpp file:

    vec2 operator-(const vec2& l, const vec2& r) {
       return { l.x - r.x, l.y - r.y };
    }
    
    vec3 operator-(const vec3& l, const vec3& r) {
       return { l.x - r.x, l.y - r.y, l.z - r.z };
    }
  6. Add the implementation for vector multiplication to the vectors.cpp file:

    vec2 operator*(const vec2& l, const vec2& r) {
       return { l.x * r.x, l.y * r.y };
    }
    
    vec3 operator*(const vec3& l, const vec3& r) {
       return { l.x * r.x, l.y * r.y, l.z * r.z };
    }
  7. Add the implementation for scalar multiplication to the vectors.cpp file:

    vec2 operator*(const vec2& l, float r) {
       return { l.x * r, l.y * r };
    }
    
    vec3 operator*(const vec3& l, float r) {
       return { l.x * r, l.y * r, l.z * r };
    }
  8. Finally, add the implementation for vector equality to the vectors.cpp file. This is where the compare macro we created in step 3 comes in:

    bool operator==(const vec2& l, const vec2& r) { 
       return CMP(l.x, r.x) && CMP(l.y, r.y);
    }
    
    bool operator==(const vec3& l, const vec3& r) {
       return CMP(l.x, r.x) && CMP(l.y, r.y) && CMP(l.z, r.z);
    }
    
    bool operator!=(const vec2& l, const vec2& r) {
       return !(l == r);
    }
    
    bool operator!=(const vec3& l, const vec3& r) {
       return !(l == r);
    }

How it works…

What these components-wise operations are doing might not be obvious from the definitions and code provided alone. Let's explore the component-wise operations of vectors visually.

Addition

Every vector describes a series of displacements. For example, the vector (2, 3) means move two units in the positive X direction and three units in the positive Y direction. We add vectors by following the series of displacements that each vector represents. To visualize this, given vectors and , draw them so the head of touches the tail of The result of the addition is a new vector spanning from the tail of to the head of :

Subtraction

Subtraction works the same way as addition. We have to follow the negative displacement of vector starting from vector . To visually subtract vectors and , draw and with their tails touching. The result of the subtraction is a vector spanning from the head of to the head of :

A more intuitive way to visualize subtraction might be to think of it as adding negative to, like so; . If we represent the subtraction like this, visually we can follow the rules of addition:

In the above image, the vector appears multiple times. This is to emphasize that the position of a vector does not matter. Both of the vectors above represent the same displacement!

Multiplication (Vector and Scalar)

Multiplying a vector by a scalar will scale the vector. This is easy to see when we visualize the result of a multiplication. The scalar multiplication of a vector will result in a uniform scale, where all components of the vector are scaled by the same amount. Multiplying two vectors on the other hand results in a non-uniform scale. This just means that each component of the vector is scaled by the corresponding component of the other vector:

Comparison

Comparing vectors is a component-wise operation. If every component of each vector is the same, the vectors are equal. However, due to floating point error we can't compare floats directly. Instead, we must do an epsilon comparison. Epsilon tests commonly fall in one of two categories: absolute tolerance and relative tolerance:

#define ABSOLUTE(x, y) (fabsf((x)–(y)) <= FLT_EPSILON)
#define RELATIVE(x, y) \
(fabsf((x) – (y)) <= FLT_EPSILON * Max(fabsf(x), fabsf(y)))

The absolute tolerance test fails when the numbers being compared are large. The relative tolerance test fails when the numbers being compared are small. Because of this, we implemented a tolerance test with the CMP macro that combines the two. The logic behind the CMP macro is described by Christer Ericson at www.realtimecollisiondetection.net/pubs/Tolerances.

There's more…

It's desirable to make vectors easy to construct in code. We can achieve this by adding default constructors. Each vector should have two constructors: one that takes no arguments and one that takes a float for each component of the vector. We do not need a copy constructor or assignment operator as the vec2 and vec3 structures do not contain any dynamic memory or complex data. The pair of constructors for the vec2 structure will look like this:

vec2() : x(0.0f), y(0.0f) { }
vec2(float _x, float _y) : x(_x), y(_y) { }

The vec3 constructors will look similar, it adds an additional component. The constructors for the vec3 structure will look like this:

vec3() : x(0.0f), y(0.0f), z(0.0f) { }
vec3(float _x, float _y, float _z) : x(_x), y(_y), z(_z) { }
 

Dot product


The dot product, sometimes referred to as scalar product or inner product between two vectors, returns a scalar value. It's written as a dot between two vectors, . The formula for the dot product is defined as follows:

The sigma symbol means sum (add) everything up that follows. The number on top of the sigma is the upper limit; the variable on the bottom is the lower limit. If n and i is 0, the subscripts 0, 1, and 2 are processed. Without using the sigma symbol, the preceding equation would look like this:

The resulting scalar represents the directional relation of the vectors. That is, represents how much is pointing in the direction of . Using the dot product we can tell if two vectors are pointing in the same direction or not following these rules:

  • If the dot product is positive, the vectors are pointing in the same direction

  • If the dot product is negative, the vectors point in opposing directions

  • If the dot product is 0, the vectors are perpendicular

How to do it…

Follow these steps to implement the dot product for two and three dimensional vectors:

  1. Add the declaration for the dot product to vectors.h:

    float Dot(const vec2& l, const vec2& r);
    float Dot(const vec3& l, const vec3& r);
  2. Add the implementation for the dot product to vector.cpp:

    float Dot(const vec2& l, const vec2& r) {
       return l.x * r.x + l.y * r.y;
    }
    
    float Dot(const vec3& l, const vec3& r) {
       return l.x * r.x + l.y * r.y + l.z * r.z;
    }

How it works…

Given the formula and the code for the dot product, let's see an example of what we could use it for. Assume we have a spaceship S. We know its forward vector, and a vector that points to its right, :

We also have an enemy ship E, and a vector that points from our ship S to the enemy ship E, vector :

How can we tell if the the ship S needs to turn left or right to face the enemy ship E?

We need to take the dot product of and . If the result of the dot product is positive, the ship needs to turn right. If the result of the dot product is negative, the ship needs to turn to the left. If the result of the dot product is 0, the ship does not need to turn.

There's more…

Our definition of the dot product is fairly abstract. We know that the dot product gives us some information as to the angle between the two vectors, and . We can use the dot product to find the exact angle between these two vectors. The key to this is an alternate definition of the dot product.

Geometric definition

Given the vectors and , the geometric definition of the dot product is the length of multiplied by the length of multiplied by the cosine of the angle between them:

The || operator in the above equation means length and will be covered in the next section. We will cover the geometric definition and other properties of the dot product later in this chapter.

 

Magnitude


The magnitude or length of a vector is written as the letter of the vector surrounded by two bars, . The magnitude of a vector is the square root of the dot product of the vector with itself:

In addition to implementing the magnitude function, we're also going to implement a magnitude squared function. The formula is the same, but it avoids the expensive square root operation:

In games we often compare the magnitude of a vector to known numbers; however, doing a comparison between a number and the magnitude is expensive because of the square root operation. A simple solution to this problem is to square the number, and then compare against square magnitude. This means, instead of the following:

if (Magnitude(someVector) < 5.0f) {

We could instead write the following:

if (MagnitudeSq(someVector) < 5.0f * 5.0f) {

We'd then get the same result, avoiding the expensive square root operation.

Getting ready

To find the magnitude of a vector, take the square root of the vector's dot product with its-self. The square root operation is a relatively expensive one that should be avoided whenever possible. For this reason, we are also going to implement a function to find the square magnitude of a vector.

How to do it…

Follow these steps to implement a function for finding the length and squared length of two and three dimensional vectors.

  1. Add the declaration for magnitude and magnitude squared to vectors.h:

    float Magnitude(const vec2& v);
    float Magnitude(const vec3& v);
    
    float MagnitudeSq(const vec2& v);
    float MagnitudeSq(const vec3& v);
  2. Add the implementation for these functions to vectors.cpp:

    float Magnitude(const vec2& v) {
       return sqrtf(Dot(v, v));
    }
    
    float Magnitude(const vec3& v) {
       return sqrtf(Dot(v, v));
    }
    
    float MagnitudeSq(const vec2& v) {
       return Dot(v, v);
    }
    
    float MagnitudeSq(const vec3& v) {
       return Dot(v, v);
    }

How it works…

We can derive the equation for the magnitude of a vector from the geometric definition of the dot product that we briefly looked at in the last section:

Because we are taking the dot product of the vector with itself, we know the test vectors point in the same direction; they are co-directional. Because the vectors being tested are co-directional, the angle between them is 0. The cosine of 0 is 1, meaning the part of the equation can be eliminated, leaving us with the following:

If both the test vectors are the same (which in our case they are) the equation can be written using only :

We can rewrite the preceding equation, taking the square root of both sides to find the length of vector :

There's more…

The magnitude of a vector can be used to find the distance between two points. Assuming we have points and , we can find a vector () that connects them by subtracting from , as shown in the following diagram:

The distance between the two points is the length of . This could be expressed in code as follows:

float Distance(const vec3& p1, const vec3& p2) {
   vec3 t = p1 - p2;
   return Magnitude(t);
}
 

Normalizing


A vector with a magnitude of 1 is a normal vector, sometimes called a unit vector. Whenever a vector has a length of 1, we can say that it has unit length. A normal vector is written as the letter of the vector with a caret symbol on top instead of an arrow, . We can normalize any vector by dividing each of its components by the length of the vector:

We never implemented division operators for the vector class. We can rewrite the preceding equation as reciprocal multiplication. This means we can obtain the normal of a vector if we multiply that vector by the inverse of its length:

Getting ready

We are going to implement two functions, Normalize and Normalized. The first function will change the input vector to have a length of 1. The second function will not change the input vector; rather it will return a new vector with a length of 1.

How to do it…

Follow these steps to implement functions which will make a vector unit length or return a unit length vector. These steps utilize reciprocal multiplication.

  1. Declare the Normalize and Normalized functions in vectors.h:

    void Normalize(vec2& v);
    void Normalize(vec3& v);
    
    vec2 Normalized(const vec2& v);
    vec3 Normalized(const vec3& v);
  2. Add the implementation of these functions to vectors.cpp:

    void Normalize(vec2& v) {
       v = v * (1.0f / Magnitude(v));
    }
    
    void Normalize(vec3& v) {
       v = v * (1.0f / Magnitude(v));
    }
    
    vec2 Normalized(const vec2& v) {
       return v * (1.0f / Magnitude(v));
    }
    
    vec3 Normalized(const vec3& v) {
       return v * (1.0f / Magnitude(v));
    }

How it works…

Normalizing works by scaling the vector by the inverse of its length. This scale makes the vector have unit length, which is a length of 1. Unit vectors are special as any number multiplied by 1 stays the same number. This makes unit vectors ideal for representing a direction. If a direction has unit length, scaling it by some velocity becomes trivial.

 

Cross product


The cross product is written as a X between two vectors, . It returns a new vector that is perpendicular to both vectors and . That is, the result of the cross product points 90 degrees from both vectors.

The cross product is defined only for three-dimensional vectors. This is because any two non-parallel vectors form a plane, and there will always exist a line perpendicular to that plane. As such, we will only be implementing the cross product for the vec3 structure.

The equation of the cross product is as follows:

Getting ready

The formula behind the cross product seems large and complicated. We're going to implement a pattern in code that hopefully will make remembering this formula easy.

How to do it…

The cross product is only well defined for three dimensional vectors. Follow these steps to implement the cross product in an intuitive way:

  1. Add the declaration for the cross product to vectors.h:

    vec3 Cross(const vec3& l, const vec3& r);
  2. Start the implementation in vectors.cpp:

    vec3 Cross(const vec3& l, const vec3& r) {
       vec3 result;
       // We will add more code here
       return resut;
    }
  3. Start by listing out the x, y, and z components of the result in a column:

    vec3 Cross(const vec3& l, const vec3& r) {
       vec3 result;
       result.x = /* Will finish in step 6 */
       result.y = /* Will finish in step 6 */
       result.z = /* Will finish in step 6 */
       return resut;
    }
  4. Flesh out the first row by multiplying l.y and r.z. Notice how the first column contains x, y, and z components in order and so does the first row:

    vec3 Cross(const vec3& l, const vec3& r) {
       vec3 result;
       result.x = l.y * r.z /* Will finish in step 6 */
       result.y = /* Will finish in step 6 */
       result.z = /* Will finish in step 6 */
       return resut;
    }
  5. Follow the x, y, z pattern for the rest of the rows. Start each row with the appropriate letter following the letter of the first column:

    vec3 Cross(const vec3& l, const vec3& r) {
       vec3 result;
       result.x = l.y * r.z /* Will finish in step 6 */
       result.y = l.z * r.x /* Will finish in step 6 */
       result.z = l.x * r.y /* Will finish in step 6 */
       return resut;
    }
  6. Finally, complete the function by subtracting the mirror components of the multiplication from each row:

    vec3 Cross(const vec3& l, const vec3& r) {
       vec3 result;
       result.x = l.y * r.z - l.z * r.y;
       result.y = l.z * r.x - l.x * r.z;
       result.z = l.x * r.y - l.y * r.x;
       return resut; // Done
    }

How it works…

We're going to explore the cross product using three normal vectors that we know to be perpendicular. Let vector , , and represents the basis of , three-dimensional space. This means we define the vectors as follows:

  • points right; it is of unit length on the x axis:
  • points up; it is of unit length on the y axis:
  • points forward; it is of unit length on the z axis:

Each of these vectors are orthogonal to each other, meaning they are 90 degrees apart. This makes all of the following statements about the cross product true:

  • Right X Up = Forward,
  • Up X Forward = Right,
  • Forward X Right = Up,

The cross product is not cumulative, is not the same as . Let's see what happens if we flip the operands of the preceding formulas:

  • Up X Right = Backward,
  • Forward X Up = Left,
  • Right X Forward = Down,

Matrices will be covered in the next chapter, if this section is confusing, I suggest re-reading it after the next chapter. One way to evaluate the cross product is to construct a 3x3 matrix. The top row of the matrix consists of vector , , and . The next row comprises the components of the vector on the left side of the cross product, and the final row comprises the components of the vector on the right side of the cross product. We can then find the cross product by evaluating the pseudo-determinant of the matrix:

We will discuss matrices and determinants in detail in Chapter 2, Matrices. For now, the preceding determinant evaluates to the following:

The result of is a scalar, which is then multiplied by the vector. Because the vector was a unit vector on the x axis, whatever the scalar is will be in the x axis of the resulting vector. Similarly, whatever is multiplied by will only have a value on the y axis and whatever is multiplied by will only have a value on the z axis. The preceding determinant simplifies to the following:

 

Angles


We have had a brief introduction to the angle between vectors when we discussed the dot product and the magnitude of a vector. In this recipe, we will discuss how to find the actual angle between two vectors. The formula to find angle theta between two vectors is:

Getting ready

We have already implemented both the dot product and magnitude functions for vectors; this means we have everything needed to find the angle between two vectors already written. In general, this is a very expensive function, as it performs two square roots and an inverse cosine. Because it's such an expensive function, we try to avoid it whenever possible.

We can save a little bit of performance if, instead of multiplying the length of both vectors, we multiply the squared length of the vectors and then do just one square root operation on the result.

How to do it…

  1. Add the declaration of the angle function to vectors.h:

    float Angle(const vec2& l, const vec2& r);
    float Angle(const vec3& l, const vec3& r);
  2. Provide the implementation of the angle function in vectors.cpp:

    float Angle(const vec2& l, const vec2& r) {
       float m = sqrtf(MagnitudeSq(l) * MagnitudeSq(r));
       return acos(Dot(l, r) / m);
    }
    
    float Angle(const vec3& l, const vec3& r) {
       float m = sqrtf(MagnitudeSq(l) * MagnitudeSq(r));
       return acos(Dot(l, r) / m);
    }

How it works…

This formula relies on the geometric definition of the dot product:

This formula states that the dot product of two vectors is the cosine of the angle between them multiplied by both of their lengths. We can rewrite this formula with the cosine being isolated if we divide both sides by the product of the lengths of and :

We can now use the inverse of cosine, the arc cosine (acos), to find the angle theta:

There's more…

The acos function we used to find the angle between vectors comes from the standard C math library. This implementation of acos returns radians, not degrees. It's much more intuitive to think of angles in terms of degrees than radians.

Radians and degrees

Add the following macros to the top of the vectors.h header file:

#define RAD2DEG(x) ((x) * 57.295754f)
#define DEG2RAD(x) ((x) * 0.0174533f)

Using these macros you can convert between radians and degrees. For example, if you wanted to get the angle in degrees between vectors and , you could use the following code:

float degrees = RAD2DEG(Angle(A, B));

If you are interested in the math used to derive these numbers, I suggest watching the following Khan Academy video:

https://www.khanacademy.org/math/algebra2/trig-functions/intro-to-radians-alg2/v/introduction-to-radians

 

Projection


Sometimes it's useful to decompose a vector into parallel and perpendicular components with respect to another vector. Projecting onto will give us the length of in the direction of . This projection decomposes into its parallel component with respect to . Once we know the parallel component of , we can use it to get the perpendicular component. The formula for projecting onto is as follows:

The perpendicular component of with respect to is defined as follows:

Getting ready

Implementing the projection is fairly straightforward as we already have both the dot product and magnitude squared defined. In the following function, the vector being projected is represented by the variable length, and the vector it is being projected onto is represented by the variable direction. If we compare it to the preceding formula, length is , and direction is .

How to do it…

Follow these steps to implement projection functions for two and three dimensional vectors. A function to get the perpendicular component of the projection is also described:

  1. Declare the projection and perpendicular functions in vectors.h:

    vec2 Project(const vec2& length, const vec2& direction);
    vec3 Project(const vec3& length, const vec3& direction);
    
    vec2 Perpendicular(const vec2& len, const vec2& dir);
    vec3 Perpendicular(const vec3& len, const vec3& dir);
  2. Add the implementation of projection to vectors.cpp:

    vec2 Project(const vec2& length, const vec2& direction) {
       float dot = Dot(length, direction);
       float magSq = MagnitudeSq(direction);
       return direction * (dot / magSq);
    }
    
    vec3 Project(const vec3& length, const vec3& direction) {
       float dot = Dot(length, direction);
       float magSq = MagnitudeSq(direction);
       return direction * (dot / magSq);
    }
  3. Add the implementation of perpendicular to vectors.cpp:

    vec2 Perpendicular(const vec2& len, const vec2& dir) {
       return len - Project(len, dir);
    }
    
    vec3 Perpendicular(const vec3& len, const vec3& dir) {
       return len - Project(len, dir);
    }

How it works…

Let's explore how projection works. Say we want to project onto , to find . Having a ' character next to a vector means prime; it's a transformed version of the vector; is pronounced A-Prime:

From the preceding figure we see that can be found by subtracting some unknown vector from . This unknown vector is the perpendicular component of with respect to , let's call it :

We can get the perpendicular component by subtracting the projection of onto from. The projection at this point is still unknown, that's what we are trying to find:

Because points in the same direction as , we can express as scaling by some unknown scalar s, . Knowing this, the problem becomes, how do we find s?:

The dot product of two perpendicular vectors is 0. Because of this, the dot product of and is going to be 0:

Substitute the value of with the equation we use to find its value, :

Finally, let's substitute with the equation we use to find its value, :

Now the only unknown in the formula is s, let's try to find it. The dot product exhibits the distributive property, let's distribute :

Let's start to isolate s, first we add to both sides of the equation:

Now we can isolate s if we divide both sides of the equation by . Remember, the dot product of a vector with itself yields the square magnitude of that vector:

Now we can solve by substituting s with the preceding formula. The final equation becomes:

 

Reflection


One of the most important concepts in physics for games is collision response and how to react to a collision occurring. More often than not this involves one of the colliding objects bouncing off the other one. We can achieve the bounding through vector reflection. Reflection is also heavily used in many areas of game development, such as graphics programming, to find the color intensity of a fragment.

Given vector and normal , we want to find a vector that is reflected around :

The reflected vector can be found with the following formula:

Keep in mind, in the preceding equation, is a unit length vector. This means that the part of the equation actually projects onto . If was a non-normalized vector, the preceding equation would be written as follows:

Getting ready

Implementing the preceding formula is going to look a little different, this is because we only overloaded the vector scalar multiplication with the scalar being on the right side of the equation. We're going to implement the function assuming is already normalized.

How to do it…

Follow these steps to implement a function which will reflect both two and three dimensional vectors.

  1. Add the declaration of the reflection function to vectors.h:

    vec2 Reflection(const vec2& vec, const vec2& normal);
    vec3 Reflection(const vec3& vec, const vec3& normal);
  2. Add the implementation of the reflection function to vectors.cpp:

    vec2 Reflection(const vec2& vec,const vec2& normal) {
       float d = Dot(vec, normal);
       return sourceVector - normal * (d * 2.0f );
    }
    
    vec3 Reflection(const vec3& vec, const vec3& normal) {
       float d = Dot(vec, normal);
       return sourceVector - normal * (d * 2.0f);
    }

How it works…

Given and , we're going to find , which is the reflection of around :

First, we project onto , this operation will yield a vector along that has the length of :

We want to find the reflected vector . The following figure shows in two places, remember it doesn't matter where you draw a vector as long as its components are the same:

Looking at the preceding figure, we can tell that subtracting from will result in :

This is how we get to the final formula, .

About the Author
  • Gabor Szauer

    Gabor Szauer has been making games since 2010. He graduated from Full Sail University in 2010 with a bachelor's degree in game development. Gabor maintains an active Twitter presence, and maintains a programming-oriented game development blog. Gabor's previously published books are Game Physics Programming Cookbook and Lua Quick Start Guide, both published by Packt.

    Browse publications by this author
Latest Reviews (5 reviews total)
I thought I bought hard cover version but I received it as a digital file.
At this moment i only read one of the books, the Game Physics Cookbook, i think it is a very good book with a very good examples. The only thing that are missing is more details one collsions reactions. One second book with more physics simulations can be a good ideia.
Didáctico y muy completo. El nivel es el adecuado para mis necesidades.
Game Physics Cookbook
Unlock this book and the full library FREE for 7 days
Start now