Let’s Build a 3D Graphics Engine: Points, Vectors, and Basic Concepts

This entry is part 1 of 1 in the series Let's Build a 3D Graphics Engine

The 3D game engines that are behind today’s biggest games are staggering works of mathematics and programming, and many game developers find that understanding them in their entirety is a difficult task. If you are lacking in experience (or a college degree like myself), this task becomes even more arduous. In this series, I aim to walk you through the basics of graphics systems in 3D engines. More specifically, in this tutorial we will be discussing points and vectors, and all of the fun that comes with them. If you have a basic grasp of algebra (variables and variable math) and Computer Science (the basics of any object-oriented programming language), you should be able to make it through most of these tutorials, but if you’re having trouble with any of the concepts, please ask questions! Some of these topics can be terribly difficult.

---

Basics of Coordinate Systems

Let’s start from the basics. Three-dimensional graphics require the concept of a three-dimensional space. The most widely used of these spaces is called the Cartesian Space, which gives us the benefit of Cartesian coordinates (the basic \((x,y)\) notations and 2D grid-spaced graphs that are taught in most high schools). Pictured: the bane of many high schoolers’ existence. 3-dimensional Cartesian space gives us an x, y, and z axis (describing position based on horizontal placement, vertical placement, and depth respectively). The coordinates for any point within this space are shown as a tuple (in this case a 3-tuple, since there are three axes). On a 2-dimensional plane, a tuple could be depicted as \((x,y)\), and in 3-dimensional plane, it is depicted as \((x,y,z)\). The use of this 3-tuple is that it shows a point’s location relative to the space’s origin (which itself is typically shown as \((0,0,0)\)). Tip: Tuple: an ordered list (or sequence) of elements in computer science or mathematics. So, \((K,y,l,e)\) would be a 4-tuple, showing a sequence of characters that make up my name. Within this space, we are going to define a point as a representation of a 3-tuple. This can also be shown as: \[P = (x,y,z)\] In addition to this definition of a point, we must define its parts. Each of the elements within this 3-tuple is a scalar (number) that defines a position along a basis vector. Each basis vector must have a unit length (that is, a length of exactly 1), so 3-tuples such as \((1,1,1)\) and \((2,2,2)\) could not be basis vectors as they are too long. We define three basis vectors for our space: \[\begin{aligned} X & = (1,0,0)\\ Y & = (0,1,0)\\ Z & = (0,0,1) \end{aligned}\] Source: http://www.thefullwiki.org/Arithmetics/Cartesian_Coordinate.

---

The Coordinate System

Now let’s talk about the mathematical definition of our coordinate system, how it affects our graphics system, and the calculations we can make.

Representing Points

The origin point of our coordinate system can be depicted as the point \(O\), which represents the 3-tuple (0,0,0). This means that the mathematical representation of our coordinate system can be depicted as: \[\{O;X,Y,Z\}\] By this statement, you can say that \((x,y,z)\) represents a point’s position in relation to the origin. This definition also means that any point \(P\), \((a, b, c)\), can be represented as: \[P = O + aX + bY + cZ\] From here on, I will reference scalars in lower-case and vectors in upper-case – so \(a\), \(b\), and \(c\) are scalars, and \(X\), \(Y\), and \(Z\) are vectors. (They are actually the basis vectors we defined earlier.) This means that a point whose tuple is (2,3,4) could be represented as: \[\begin{aligned} (2,3,4) & = (2,0,0) + (0,3,0) + (0,0,4)\\ & = (0,0,0) + (2,0,0) + (0,3,0) + (0,0,4)\\ & = (0,0,0) + 2(1,0,0) + 3(0,1,0) + 4(0,0,1)\\ & = O + 2X + 3Y + 4Z\\ \end{aligned}\] So, we’ve taken this abstract concept of “a point in 3D space” and defined it as four separate objects added together. This kind of definition is very important whenever we want to put any concept into code.

Mutually Perpendicular

The coordinate system that we will be using also has the valuable property of being mutually perpendicular. This means that there is a 90 degree angle between each of the axes where they meet on their respective planes. Our coordinate system will also be defined as “right-handed”: Source: http://viz.aset.psu.edu/gho/sem_notes/3d_fundamentals/html/3d_coordinates.html. In mathematical terms, this means that: \[X = Y \times Z\] …where \(\times\) represents the cross product operator. In case you aren’t sure what a cross product is, it can be defined by the following equation (assuming you are given two 3-tuples): \[(a,b,c) \times (d,e,f) = (bf - ce, cd - af, ae - bd)\] These statements might seem tedious, but later on, they will allow us to do a variety of different calculations and transformations much more easily. Luckily, you don’t have to memorize all of these equations when building a game engine – you can simply build from these statements, and then build even less complicated systems on top of that. Well, until you have to edit something fundamental within your engine and have to refresh yourself on all of this again!

---

Points and Vectors

With all of the basics of our coordinate system locked down, its time to talk about points and vectors and, more importantly, how they interact with one another. The first thing to note is that points and vectors are distinctly different things: a point is a physical location within your space; a vector is the space between two points. To make sure that the two don’t get confused, I’ll write points in capital italics, as \(P\), and vectors in capital boldface, as \(\mathbf{V}\). There are two main axioms that we are going to deal with when using points and vectors, and they are:

• Axiom 1: The difference of two points is a vector, so \(\mathbf{V} = P – Q\)
• Axiom 2: The sum of a point and a vector is a point, so \(Q = P + \mathbf{V}\)

Tip: An axiom is a point of reasoning, often seen as evident enough to be accepted without argument.

---

Building the Engine

With these axioms stated, we now have enough information to create the building block classes that are at the heart of any 3D game engine: the Point class and the Vector class. If we were going to build our own engine using this information, there would be some other important steps to take when creating these classes (mostly having to do with optimization or dealing with already existing APIs), but we are going to leave these out for the sake of simplicity. The class examples below are all going to be in pseudocode so that you can follow along with your programming language of choice. Here are outlines of our two classes:

Point Class
{
 Variables:
  num tuple[3]; //(x,y,z)

 Operators:
  Point AddVectorToPoint(Vector);
  Point SubtractVectorFromPoint(Vector);
  Vector SubtractPointFromPoint(Point);

 Function:
  //later this will call a function from a graphics API, but for now
  //this should just be printing the points coordinates to the screen
  drawPoint; 
}

Vector Class
{
 Variables:
  num tuple[3]; //(x,y,z)

 Operators:
  Vector AddVectorToVector(Vector);
  Vector SubtractVectorFromVector(Vector);
}

[...]
Read more: Let’s Build a 3D Graphics Engine: Points, Vectors, and Basic Concepts

How to Create a Custom 2D Physics Engine: The Core Engine

This entry is part 2 of 2 in the series How to Create a Custom Physics Engine

In this part of my series on creating a custom 2D physics engine for your games, we’ll add more features to the impulse resolution we got working in the first part. In particular, we’ll look at integration, timestepping, using a modular design for our code, and broad phase collision detection.

---

Introduction

In the last post in this series I covered the topic of impulse resolution. Read that first, if you haven’t already!
Let’s dive straight into the topics covered in this article. These topics are all of the necessities of any half-decent physics engine, so now is an appropriate time to build more features on top of the core resolution from the last article.

• Integration
• Timestepping
• Modular Design
  • Bodies
  • Shapes
  • Forces
  • Materials
• Broad Phase
  • Contact pair duplicate culling
  • Layering
• Halfspace Intersection Test

---

Integration

Integration is entirely simple to implement, and there are very many areas on the internet that provide good information for iterative integration. This section will mostly show how to implement a proper integration function, and point to some different locations for further reading, if desired.
First it should be known what acceleration actually is. Newton’s Second Law states:
\[Equation 1:\\
F = ma\]
This states that the sum of all forces acting upon some object is equal to that object’s mass m multiplied by its acceleration a. m is in kilograms, a is in meters/second, and F is in Newtons.
Rearranging this equation a bit to solve for a yields:
\[Equation 2:\\
a = \frac{F}{m}\\
\therefore\\
a = F * \frac{1}{m}\]
The next step involves using acceleration to step an object from one location to another. Since a game is displayed in discrete separate frames in an illusion-like animation, the locations of each position at these discrete steps has to be calculated. For a more in-depth cover of these equations please see: Erin Catto’s Integration Demo from GDC 2009 and Hannu’s addition to symplectic Euler for more stability in low FPS environments.
Explicit Euler (pronounced “oiler”) integration is shown in the following snippet, where x is position and v is velocity. Please note that 1/m * F is acceleration, as explained above:

// Explicit Euler
x += v * dt
v += (1/m * F) * dt

dt here refers to delta time. Δ is the symbol for delta, and can be read literally as “change in”, or written as Δt. So whenever you see dt it can be read as “change in time”. dv would be “change in velocity”.This will work, and is commonly used as a starting point. However, it has numerical inaccuracies that we can get rid of without any extra effort. Here is what is known as Symplectic Euler:

// Symplectic Euler
v += (1/m * F) * dt
x += v * dt

Note that all I did was rearrange the order of the two lines of code – see “>the aforementioned article from Hannu.
This post explains the numerical inaccuracies of Explicit Euler, but be warned that he starts covering RK4, which I don’t personally recommend: gafferongames.com: Euler Inaccuracy.
These simple equations are all that we need to move all objects around with linear velocity and acceleration.

---

Timestepping

Since games are displayed at discrete time intervals, there needs to be a way of manipulating the time between these steps in a controlled manner. Have you ever seen a game that will run at different speeds depending on what computer it is being played on? That’s an example of a game running at a speed dependent on the computer’s ability to run the game.
We need a way to ensure that our physics engine only runs when a specific amount of time has passed. This way, the dt that is used within calculations is always the exact same number. Using the exact same dt value in your code everywhere will actually make your physics engine deterministic, and is known as a fixed timestep. This is a good thing.
A deterministic physics engine is one that will always do the exact same thing every time it is run assuming the same inputs are given. This is essential for many types of games where gameplay needs to be very fine-tuned to the physics engine’s behavior. This is also essential for debugging your physics engine, as in order to pinpoint bugs the behavior of your engine needs to be consistent.
Let’s first cover a simple version of a fixed timestep. Here is an example:

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// In units of seconds
float frameStart = GetCurrentTime( )

// main loop
while(true)
  const float currentTime = GetCurrentTime( )

  // Store the time elapsed since the last frame began
  accumulator += currentTime - frameStart( )

  // Record the starting of this frame
  frameStart = currentTime

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  RenderGame( )

This waits around, rendering the game, until enough time has elapsed to update the physics. The elapsed time is recorded, and discrete dt-sized chunks of time are taken from the accumulator and processed by the physics. This ensures that the exact same value is passed to the physics no matter what, and that the value passed to the physics is an accurate representation of actual time that passes by in real life. Chunks of dt are removed from the accumulator until the accumulator is smaller than a dt chunk.
There are a couple of problems that can be fixed here. The first involves how long it takes to actually perform the physics update: What if the physics update takes too long and the accumulator goes higher and higher each game loop? This is called the spiral of death. If this is not fixed, your engine will quickly grind to a complete halt if your physics cannot be performed fast enough.
To solve this, the engine really needs to just run fewer physics updates if the accumulator gets too high. A simple way to do this would be to clamp the accumulator below some arbitrary value.

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// In units seconds
float frameStart = GetCurrentTime( )

// main loop
while(true)
  const float currentTime = GetCurrentTime( )

  // Store the time elapsed since the last frame began
  accumulator += currentTime - frameStart( )

  // Record the starting of this frame
  frameStart = currentTime

  // Avoid spiral of death and clamp dt, thus clamping
  // how many times the UpdatePhysics can be called in
  // a single game loop.
  if(accumulator > 0.2f)
    accumulator = 0.2f

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  RenderGame( )

Now, if a game running this loop ever encounters some sort of stalling for whatever reason, the physics will not drown itself in a spiral of death. The game will simply run a little more slowly, as appropriate.
The next thing to fix is quite minor in comparison to the spiral of death. This loop is taking dt chunks from the accumulator until the accumulator is smaller than dt. This is fun, but there’s still a little bit of remaining time left in the accumulator. This poses a problem.
Assume the accumulator is left with 1/5th of a dt chunk every frame. On the sixth frame the accumulator will have enough remaining time to perform one more physics update than all the other frames. This will result in one frame every second or so performing a slightly larger discrete jump in time, and might be very noticeable in your game.
To solve this, the use of linear interpolation is required. If this sounds scary, don’t worry – the implementation will be shown. If you want to understand the implementation there are many resources online for linear interpolation.

// linear interpolation for a from 0 to 1
// from t1 to t2
t1 * a + t2(1.0f - a)

Using this we can interpolate (approximate) where we might be between two different time intervals. This can be used to render the state of a game in between two different physics updates.
With linear interpolation, the rendering of an engine can run at a different pace than the physics engine. This allows a graceful handling of the leftover accumulator from the physics updates.
Here is a full example:

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// In units seconds
float frameStart = GetCurrentTime( )

// main loop
while(true)
  const float currentTime = GetCurrentTime( )

  // Store the time elapsed since the last frame began
  accumulator += currentTime - frameStart( )

  // Record the starting of this frame
  frameStart = currentTime

  // Avoid spiral of death and clamp dt, thus clamping
  // how many times the UpdatePhysics can be called in
  // a single game loop.
  if(accumulator > 0.2f)
    accumulator = 0.2f

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  const float alpha = accumulator / dt;

  RenderGame( alpha )

void RenderGame( float alpha )
  for shape in game do
    // calculate an interpolated transform for rendering
    Transform i = shape.previous * alpha + shape.current * (1.0f - alpha)
    shape.previous = shape.current
    shape.Render( i )

Here, all objects within the game can be drawn at variable moments between discrete physics timesteps. This will gracefully handle all error and remainder time accumulation. This is actually rendering ever so slightly behind what the physics has currently solved for, but when watching the game run all motion is smoothed out perfectly by the interpolation.
The player will never know that the rendering is ever so slightly behind the physics, because the player will only know what they see, and what they’ll see is perfectly smooth transitions from one frame to another.
You may be wondering, “why don’t we interpolate from the current position to the next?”. I tried this and it requires the rendering to “guess” where objects are going to be in the future. Often, objects in a physics engine make sudden changes in movement, such as during collision, and when such a sudden movement change is made, objects will teleport around due to inaccurate interpolations into the future.

---

Modular Design

There are a few things every physics object is going to need. However, the specific things each physics object needs may change slightly from object to object. A clever way to organize all this data is required, and it would be assumed that the lesser amount of code to write to achieve such organization is desired. In this case some modular design would be of good use.
Modular design probably sounds a little pretentious or over-complicated, but it does make sense and is quite simple. In this context, “modular design” just means we want to break a physics object into separate pieces, so that we can connect or disconnect them however we see fit.

Bodies

A physics body is an object that contains all information about some given physics object. It will store the shape(s) that the object is represented by, mass data, transformation (position, rotation), velocity, torque, and so on. Here is what our body ought to look like:

struct body
{
  Shape *shape;
  Transform tx;
  Material material;
  MassData mass_data;
  Vec2 velocity;
  Vec2 force;
  real gravityScale;
};

This is a great starting point for the design of a physics body structure. There are some intelligent decisions made here that tend towards strong code organization.
The first thing to notice is that a shape is contained within the body by means of a pointer. This represents a loose relationship between the body and its shape. A body can contain any shape, and the shape of a body can be swapped around at will. In fact, a body can be represented by multiple shapes, and such a body would be known as a “composite”, as it would be composed of multiple shapes. (I’m not going to cover composites in this tutorial.)

Body and Shape interface. The shape itself is responsible for computing bounding shapes, calculating mass based on density, and rendering.
The mass_data is a small data structure to contain mass-related information:

struct MassData
{
  float mass;
  float inv_mass;

  // For rotations (not covered in this article)
  float inertia;
  float inverse_inertia;
};

It is nice to store all mass- and intertia-related values in a single structure. The mass should never be set by hand – mass should always be calculated by the shape itself. Mass is a rather unintuitive type of value, and setting it by hand will take a lot of tweaking time. It’s defined as:
\[ Equation 3:\\Mass = density * volume\]
Whenever a designer wants a shape to be more “massive” or “heavy”, they should modify the density of a shape. This density can be used to calculate the mass of a shape given its volume. This is the proper way to go about the situation, as density is not affected by volume and will never change during the runtime of the game (unless specifically supported with special code).
Some examples of shapes such as AABBs and Circles can be found in the previous tutorial in this series.

Materials

All this talk of mass and density leads to the question: Where does the density value lay? It resides within the Material structure:

struct Material
{
  float density;
  float restitution;
};

Once the values of the material are set, this material can be passed to the shape of a body so that the body can calculate the mass [...]

Read more: How to Create a Custom 2D Physics Engine: The Core Engine