Simple terrain smoothing

After creating or importing terrain you may find it to be too steep or jagged. Part of this depends on how your terrain system is written, but it also depends on the resolution of the terrain and terrain you're importing.

Let's image the grid below signifies sections of our terrain, with the numbers representing elevation. We can see there are two peaks that are 20 meters tall, surrounded immediately by flat terrain that is 0 meters tall. So we basically have two very steep and pointy peaks that are 20 meters high.



To smooth the section represented here in blue, we total up all of the heights in the red squares (which gives us 20), and we divide by the number of red squares (there are 8 squares, so 20 / 8 = 2.5), and we average that result and the height of the blue square together. (20 + 2.5) / 2 = 11.25. We now have our new smoothed value, and we replace the blue square with that value.

Here we can see the results after smoothing out just the one square in the example above.

Here's what we get when we run the algorithm against every square in the grid.

Here's the algorithm:

public void SmoothTerrain(int Passes)
{
   float[,] newHeightData;

   while (Passes > 0)
   {
       Passes--;

       // Note: MapWidth and MapHeight should be equal and power-of-two values 
       newHeightData = new float[MapWidth, MapHeight];

       for (int x = 0; x < MapWidth; x++)
       {
          for (int y = 0; y < MapHeight; y++)
          {
              int adjacentSections = 0;
              float sectionsTotal = 0.0f;

              if ((x - 1) > 0) // Check to left
              {
                 sectionsTotal += HeightData[x - 1, y];
                 adjacentSections++;

                 if ((y - 1) > 0) // Check up and to the left
                 {
                    sectionsTotal += HeightData[x - 1, y - 1];
                    adjacentSections++;
                 }

                 if ((y + 1) < MapHeight) // Check down and to the left
                 {
                    sectionsTotal += HeightData[x - 1, y + 1];
                    adjacentSections++;
                 }
              }

              if ((x + 1) < MapWidth) // Check to right
              {
                 sectionsTotal += HeightData[x + 1, y];
                 adjacentSections++;

                 if ((y - 1) > 0) // Check up and to the right
                 {
                     sectionsTotal += HeightData[x + 1, y - 1];
                     adjacentSections++;
                 }

                 if ((y + 1) < MapHeight) // Check down and to the right
                 {
                     sectionsTotal += HeightData[x + 1, y + 1];
                     adjacentSections++;
                 }
              }

              if ((y - 1) > 0) // Check above
              {
                 sectionsTotal += HeightData[x, y - 1];
                 adjacentSections++;
              }

              if ((y + 1) < MapHeight) // Check below
              {
                 sectionsTotal += HeightData[x, y + 1];
                 adjacentSections++;
              }

              newHeightData[x, y] = (HeightData[x, y] + (sectionsTotal / adjacentSections)) * 0.5f;
           }
       }

      // Overwrite the HeightData info with our new smoothed info
      for (int x = 0; x < MapWidth; x++)
      {
          for (int y = 0; y < MapHeight; y++)
          {
              HeightData[x, y] = newHeightData[x, y];
          }
      }
   }
}

Here's some purposely jagged terrain, without any smoothing

Terrain after one smoothing pass

After five smoothing passes

After 50 smoothing passes. 20 passes would probably have been fine

The bounce-pad hack in LEGO Universe

The bounce-pads (also known as "bouncers") in LEGO Universe were a means of travel, when you stepped on them they sent you to a specific location in the map, usually somewhere nearby that you could not otherwise reach. Bounce-pads were one of the first gameplay elements created during the production of the game (almost 3 years before the game released), and had no real issues during the entire production run or alpha/beta testing, so we were all somewhat surprised to run into a huge bug on the very first day the game opened up to the public.

The whole company gathered in the gym around some big screen TVs so we could watch the game go live for the first time. We watched a few people get in the game and play for a short time and then we all scattered back to our desks so we could login and play the game ourselves. No sooner than had I created my first character I had a person from the live service team at my desk describing to me a serious bug. Apparently there were a large number of players that were stuck in the very first area of the game called "The Venture Explorer", a small spaceship that served as an introduction level to teach players them the basics. About two thirds of the way through the map there is a spot where you must quickbuild your first LEGO model, a bounce-pad, and afterwards you step on it and it bounces you to the next NPC to give you your next mission. It seemed that about 1 in 100 players would build the bounce-pad but could not step on it to get bounced, so they had no way to get to NPC to get the next mission. 

We had some in-game GMs talking with some of the players having this problem, and apparently they could see the bounce-pad but they couldn't step on it. The part of the code responsible for bouncing the player was the bounce-pad code that would set the player's velocity when the physics system told it that the player collided with the bounce-pad. Somewhere in that flow something was broken, and I wanted to find out what it was. We had nobody in the office that was experiencing this bug, none of our testers had seen it at any point during production either. Because we couldn't reproduce this in-house my next thought was to see what information I could get from the clients that were seeing the bug. As a gameplay programmer I didn't really know the details of what kinds of reporting and tools the live team had setup with the game to be able to get me information about this problem. As it turns out, there was almost nothing.

The client version of the game was setup to generate log messages for any errors, and there's a good chance the log file might tell me if something was amiss, like maybe the physics for the bounce-pad was failing to load, or if something was going wrong in the collision check. Sadly, the live team never got around to setting up a way for the clients to be able to send us their logs, or for a GM to be able to send a message to the client's program and have it return the logs to us. At the time they said something about possible legal reasons for us not getting information about them sent automatically to us, which seemed a bit ridiculous since the information didn't contain any account information besides the name of their in-game character, and a 32-bit account ID, which even if it got into the wrong hands is worthless. Anyway, getting any information from the client was impossible at the time.

Server log files were one thing I did have access to, unfortunately this was a client issue since not everyone was seeing it, and since the functionality to make the player bounce was entirely client-side, with only some server-side monitoring to check for cheating.

My next idea was to use some in-game tools that I had written during development, that created huge amounts of data about any object in the world. I was hoping I could use this tool to see if there might be any issues with the bounce-pad itself that the tool could find. The tool would analyze thousands of points of data on an object (at run-time) and check for any inconsistencies and report them back. This tool was not built into the version of the client that players used, so I would need to build an internal version of the client and log-in with it, additionally the server would not return the requested information unless you were using a GM account, for security reasons. It took awhile but finally I was given a temporary GM account to be able to analyze the problem, and still we were able to find nothing, mostly because the client information about the object was based on my client, which was working fine.

After about a day of sifting through logs and using tools to try and find any issues I could find nothing, and in the mean time GMs were having to sit in the game and teleport these players to the NPC so they could get their missions. The pressure was on to find a solution, but the only information I had to go on was that a small percentage of players were seeing a problem, and because this appeared to be a client-side problem and there was no system to get client logs back to me, there was nothing I could put in the game to get me any information about the problem. The reason this problem was on me was because I had written the bounce-pad system, the system that now appeared to be broken.

I enlisted the help of a couple fellow gameplay programmers to try and see what we could do to reproduce the problem in-house. We tried removing the physics asset from the computer to see how the game would react, and when starting the game the patching system would see the missing asset and simply download it again. There were code paths that could be hit if a physics file failed to load, so we put in some code to force the physics asset to fail to load, and in that case the game put in a fallback physics shape (a 1x1x1 cube), and even though that wasn't the proper shape it was still enough the player could touch it and the system would respond and bounce them, so that was a no-go. We checked to see if maybe the collision could be succeeding and somehow the bounce-pad code was failing to translate that into a bounce, but we couldn't see any point of failure, or a way to force it to fail.

So here we are with a problem we cannot produce, and a system we can't seem to make fail, and no way to get any information from the players that were seeing the problem. Leaving the bug as-is was unacceptable, as it would mean a lot of lost customers or the expense of GMs permanently stationed near the broken bounce-pad to teleport players. So the solution, was a hack.

During early development of LEGO Universe, almost all gameplay was entirely server-based. Things like attacking, picking up power-ups on the ground, and using bounce-pads were done entirely on the server and then the server would inform the client of the event. This was very secure but it resulted in laggy gameplay, which didn't work well for an action game like LEGO Universe. Along with other systems the bounce-pads were made so that the client-side object did the bouncing of the player, and simply told the server what it had done so that the server could check for any possible cheating or hacking. So, remembering that it used to work on the server years ago, and that the bounce-pads were still properly loading on the server, the solution presented itself. I put in code on the server so that if the player stood on a bounce-pad for more than half of a second and did not get a message from the client's bounce-pad that they've bounced, that it would assume the bounce-pad on the client was broken and bounce the player from the server. The result was that for those 1 in 100 players seeing the problem, that one bounce-pad on the first level would feel a little bit laggy but it would work. We also setup some server-side logging for any time the server-side bounce-pad needed to take over, and we found that we were only ever seeing the logging for that one bounce-pad in the first level of the game. For some reason that we never tracked down, it was only ever that one asset that exhibited this problem in the game, there was never another problem related to the physics for an asset not properly loading. 

We did make the assumption that the physics were likely failing somehow on those clients, because the only way we weren't able to bounce on the client was if a physics collision message was never sent to the bouncer, so I do feel some comfort in that the system I wrote may not have been the problem, it just affected my system. Even though as a team we take responsibility for the entire product, rather than saying "this is my code, that is your code", it's still feels good when you've written a system that works well, so you never want to see it break down and fail. It remains the biggest hack that I've ever made to a released product, but I don't feel bad about it, I feel like I made the best of the situation with what I was given, and in the end the players never knew the difference. 

Let's Make a Game Engine for XNA 4.0r, Prologue

I was in the middle of making a simple game engine framework so I could start writing blog posts about things like creating camera, input systems, terrain systems, spatial partitioning, etc., when I realized that I should document the actual creation of the framework.

I chose XNA for a few reasons:
1.) I'm already familiar with it after having developed a game engine for it: http://quickstartengine.codeplex.com/
2.) It's fast for prototyping
3.) It handles the back-end for a lot of mundane things like creating a Window, handling Windows messaging, handling DirectX. All of that means less I have to explain here on my blog, and that lets us get to the interesting parts more quickly.

You'll need some familiarity with Visual Studio 2010:
XNA 4.0r runs only in Visual Studio 2010. Luckily it works in the free version of VS2010 C# Express, which you can get here: http://www.microsoft.com/visualstudio/en-us/products/2010-editions/visual-csharp-express

The upcoming blog posts assume you know C#:
XNA runs within C#. If you do not know C# then you may want to stop now and spend a couple of days getting a basic rundown of C#. When I first started with XNA I knew only C++, I picked up enough about C# in about 8 hours to start making simple games in XNA. If you know C++ or Java fairly well then you can probably pick up the basics of C# pretty quickly.

If you're not familiar with XNA:
I would recommend at least spending a few hours looking a few simple tutorials to learn about some of the main functionality, how to create a project, and how the content pipeline works.
These links should cover just enough for you to grasp what you'll need to make this game engine.:
http://www.xnadevelopment.com/tutorials/gettingstartedwithxnadevelopment/GettingStartedWithXNADevelopment.shtml
http://www.xnadevelopment.com/tutorials/creatinganewxnagameproject/CreatingANewXNAWindowsGameProject.shtml
http://www.xnadevelopment.com/tutorials/addinganimagetothegameproject/AddingAnImageToTheGameProject.shtml

Ok, if you made it this far you are reasonably familiar with Visual Studio 2010 Express, C# and XNA 4.0r. Now we can continue on to Part 1 of this series.

MMO Architecture: Creating a ghosting system

In this post I will talk about a common part of an MMO's internal architecture, often referred to as ghosting. Ghosting is how the server tells the client about the world loading around the player as that player moves through the world. Because MMOs are often open-world games you cannot simply have the player load up all of the objects in the entire zone they're in, the game just couldn't run like that on a single player's computer. On top of that the server would have to constantly update every player about every thing happening within a zone, which would create bandwidth issues for both clients and server.

I'll discuss a few different, but similar, ways that ghosting can be achieved (I'm sure there are other ways as well). First of all, the server will only need to send down information of objects in the world that are not environmental, for example there is no need to send information to a client about a tree they're in range of, because that tree is likely static and can never change. The client will know about that tree based on assets/files on their own computer. The server will have an easy way to know which objects have information that can change (like their position, or stats, or state, etc...), so the main work the server will need to do is determine which of these networked objects are close enough to the player to tell the client about.

Method #1: Ghosting objects within a proximity around the player
With most physics engine the most efficient way to ghost objects within a proximity of the player is to give the player an axis-aligned bounding box (AABB). Axis-aligned shapes will have smaller broadphase sizes, which will result in them being checked against less objects for collision. Attach an AABB to a player on the server, and whichever networked objects collide with this box are entered into a list to send updates to the player about. Whenever the object un-collides with the bounding box then the server can tell the client to unload that object. Generally this bounding box is large enough the player doesn't see all of the objects loading and unloading right around them.

Method #2: Ghosting objects that have players in their proximity
This method is similar to the last method in that we're ghosting objects to clients based on proximity to those objects, the difference here is that rather than attaching an AABB to the player, you instead put AABBs on the networked objects instead. This method has its pros and cons. On the plus side this allows designers and engineers to tweak the distances that an object with ghost down to the player, on a per object basis. This means that if an object is deemed to be a higher priority than other objects then designers can increase the distance as which they'll ghost to players. The down side to this method is that it will use more memory and hit performance a bit more on the server, this is because you have potentially many more AABBs in the world checking for collisions.

Method #3:  Distance checking
This method is similar to method #1 in that it is proximity-based. This method entails mathematically brute force checking the player's position against the position of ghosted objects nearby. To realistically use this in a large-world MMO you would need some kind of spatial partitioning in your world so you knew which sub-set of objects were close enough to the player to do distance checking again, otherwise you'd likely be doing hundreds of distances checks per frame per player, possibly many more. If you already have spatial partitioning in your world you may not even need this method, which leads me to Method #4.

Method #4: Spatial partitioning
If your MMO's world is using a decent spatial partitioning algorithm to sort the scene then the server may already know which networked objects are close enough to the player, and could send those objects down. This method is the least expensive in terms of how expensive the ghosting is, however the spatial partitioning itself has a decent expense to it most of the time, so if ghosting was your only reason for using spatial partitioning on the server, then you're probably just as well off using Method #1 so long as you have a decent physics engine (as most physics engines have their own spatial partitioning anyway).

The above methods will allow you gather the objects that a client will care about. From here it's fairly simple, when the objects first enter range of the player (or the player first enters the object's range), you send the player an initial packet with the full current info about the object, and any changes that need to be networked while that object is in range will also go the player. This allows the player to get the full info as objects enter range so that they can see that object in the same state that the server does, and then it should receive any changes from the server object while it's in range as well. Combining all of this gives you a basic but fairly complete ghosting system for an MMO.

Havok: Setting mesh color in the Visual Debugger, Part 2

In part 1 of this series I showed you how to colorize your physics meshes in the Havok Visual Debugger (HVD). However as you may have noticed, this only works for colorizing meshes that are already loaded in the HVD, so if you connect the HVD to the game after those colors have been set you will not see that information. Here's a simple way to get around that problem.

You program is likely directly using an hkVisualDebugger, what you will need to do is derived a new class from hkVisualDebugger. The hkVisualDebugger class has an m_clients variable, but it's access is protected, and there is no accessor to its information in hkVisualDebugger so unless you have the actual source code for Havok, you're going to need to derive your own class from hkVisualDebugger so you can create an accessor to the data that you need.

Create a new header file in your project, name it 'PhysicsVisualDebugger' or whatever class name you would like to use. The code below is the entire class, no .cpp file is needed.

#pragma once

#ifndef __PhysicsVisualDebugger_h_
#define __PhysicsVisualDebugger_h_

#include <common\visualize\hkvisualdebugger.h>

class PhysicsVisualDebugger : public hkVisualDebugger
{
public:
    PhysicsVisualDebugger(const hkArray<hkProcessContext*>,
                          const class hkVtableClassRegistry* classReg = HK_NULL)
         : hkVisualDebugger(contexts, classReg)
    {}

    virtual ~PhysicsVisualDebugger() {};

    unsigned int GetNumClients() const { return m_clients.getSize(); }
};

#endif //__PhysicsVisualDebugger_h_

Make sure any place you were using an 'hkVisualDebugger' that you're not using your new class you've just made.

The goal we're aiming for is to know when somebody connects the HVD to your program. The GetNumClients() above will return to you the number of current clients connected, if you call it at the appropriate time you can compare it to check if that number has just increased.

In my example below, 'm_pDebugger' is a pointer to a 'PhysicsVisualDebugger'. Put this code wherever you're currently stepping the HVD.

unsigned int numConnections = m_pDebugger->GetNumClients();

// Update the debuggers (which also checks for new clients)
m_pDebugger->step(m_fStepLength);

// If there are now more connections than before the update
if ( m_pDebugger->GetNumClients() > numConnections )
{
    // This is where you will want to go through all physics
    // objects and have to re-send their color info to the
    // debugger.
    UpdateDebuggerInfoForAllEntities();
}

Notice we query the number of connections before stepping the debugger, store that number, and then after stepping the debugger we query for number of connections again. If the number of clients has increased, then you should find a way of having all of your objects resend their color information to the HVD. In my case whenever I add an object to the Havok world, I keep track of its pointer in a list so I can call a function on everything in that list at any time to have them refresh their information for the HVD.

Calculus: Network prediction, calculating distance over time

I've actually found that I rarely need to use any calculus in most game programming I run into. Games are generally frame-based, and as such you can generally just update variables each frame by the elapsed time. One of the main benefits of calculus is when you need to know what a value is at any given point in time, so it's very valuable when you're trying to predict where something will be after a given amount of time, and prediction is very common in any networked game.

I used a similar method to this while developing LEGO Universe's moving platform system, a system which lets the player ride upon a moving object to travel short or long distances. If a client's program had hitched for a small amount of time while on the platform, the platform would naturally see a larger gap of time had elapsed, and Havok's physics would usually accurately calculate where the platform should end up. However, we had to limit how much time we were able to skip all at once because if the client make their game hitch for a long period of time, say 5 seconds, and we let Havok just move everything ahead 5 seconds based on their current velocity, we could potentially have the player going places where they shouldn't be able to go. I can go into more detail some other time on this subject, but suffice to say we couldn't always just allow the game to move objects large distances because a large time had elapsed between frames.

The moving platform system had unique prediction algorithms because it had invisible predefined rails it had to stay on, and at each waypoint it had a speed it must be traveling at the moment it got to that point. Based on defined points on these paths, and speeds at those points, we should be able to determine exactly where a moving platform should be after any amount of elapsed time.

The image below represents a simple path for a moving platform to follow, and at each point I've labeled the speed that moving platform must be going at the time it reaches at point. So basically what this image says is when the platform leaves P1, it will be moving at 5 meters per second, and it will have a constant acceleration all the way to P2, and by the time it reaches P2 it will be moving at 10 meters per second. As it leaves P2 it will decelerate constantly such that it will be moving at 5 meters per second as it reaches P3. Long story short, it speeds up until it gets to P2, and then slows down again as it reaches P3.

In order to calculate where a platform could be at any time we need to know its acceleration. If the platform wasn't accelerating, calculating it's position at any time would be extremely simple, and would just be:
Position += Velocity * Time;

But because velocity is constantly changing as the platform speeds up and slows down along its journey, we'll need calculus to tell us what the acceleration is between the two points a platform currently lies, and then we can use that acceleration to calculate the distance traveled.

So to keep the scenario as simple as possible, lets just calculate where the platform will be after 1 second if it begins at P1.

Difference vector from P1 to P2 = (10 - 0, -3 - 0) = (10, -3)
Length of difference vector = √(10² + -3²) = √(100 + 9) = √109 = 10.440306 meters

The formula for calculating constant acceleration is:

v(f) is final velocity, v(i) is the initial velocity, and 'd' is distance it will be travelling.

The code for this is:

float CalculateConstantAccel(const float initVelocity, 
                             const float finalVelocity,
                             const float distance)
{
    if ( distance <= 0.0f )
    {
        return 0.0f;
    }
    
    float finalVelocitySqr = finalVelocity * finalVelocity;
    float initVelocitySqr = initVelocity * initVelocity;
    
    return (finalVelocitySqr - initVelocitySqr)
           / (2 * distance);
}

Plugging our values in we get:

Acceleration = (10² - 5²) / (2 * 10.440306) = (100 - 25) / 20.880612 = 3.591849

Knowing our constant acceleration, we can now calculate where the platform will be in 1 second. Here's the formula for calculating distance over time given a constant acceleration:

'd' is distance, v(i) is the initial velocity, 't' is time, and 'a' is the acceleration we already calculated above.

The code for this is:

float CalcDistanceOverTime(const float initVelocity, 
                           const float constantAccel,
                           const float timeDelta)
{
    return  (initVelocity * timeDelta)
          + (0.5f * constantAccel * (timeDelta * timeDelta);
}

Plugging our values in we get:

Distance = 5 * 1 + ( 0.5 * 3.591849 * 1² ) = 5 * 1.7959245 = 8.9796225

So the moving platform will have traveled 8.9796225 meters after 1 second, which puts it pretty close to P2, which was 10.440306 meters away. In fact, we know the direction between P1 and P2, so if we want to put the platform where is should be we can move it there based on the distance we calculated. Our difference vector from P1 -> P2 was (10, -3). We need to unitize it to make it a direction vector, and we already have the length of the vector so that saves us another step. Inverse length is = 1 / 10.440306 = 0.0957826 Unitized difference vector is ( 10 * 0.0957826, -3 * 0.0957826 ) = (0.957826, -0.2873478) And now we just multiply our direction vector by the distance we need to travel and then add it to P1: P1 + ( distance * ( direction )); New position = (0, 0) + ( 8.9796225 * (0.957826, -0.2873478)) = ( 8.600916, -2.5802747 ) So as you can see, our position after 1 second is approx ( 8.6, -2.58 ), which puts it close to P2, which is at (10, -3).

That concludes this blog post, but here's some food for thought: What if the client's game had hitched for 2 seconds? That would've put them far past P2, so you end up needing an algorithm to figure out how much time it took to reach P2, then based on the remain time left from the original 2 seconds you have to figure out how far they went between P2 and P3. Stay tuned for the solution to this in the next blog post.

Ballistic trajectory to travel between two points, and rotating a point around an axis

The formula for calculating ballistic trajectory is tricky, luckily one doesn't have to reinvent the wheel to do it  because someone has already done it for us. If you would like to see the math behind how it is calculated, click here. Be aware this does not account for wind or air resistance, so if your game is realistic enough to have either, you'll probably want to look here. Today we're just looking at the version without air resistance.

Ballistic trajectory is the angle required to launch an object from one point to another. For example if you wanted to fire a cannonball out of a cannon to a reticule that the player gets to aim, you would need something like this:

// Returns true if 'end' can be reached at the given 'speed', otherwise
// it returns false.
bool CalculateTrajectory(const Vector3& start, const Vector3& end,
                     const float speed, const float gravity,
                     const bool bUseHighArc, Vector3& outTrajectory, 
                     float& outAngle)
{
    bool canHit = false;

    // We use doubles instead of floats because we need a lot of
    // precision for some uses of the pow() function coming up.
    double term1 = 0.0f;
    double term2 = 0.0f;
    double root = 0.0f;

    Vector3 diffVector = destination - origin;

    // A horizontally-flattened difference vector.
    Vector3 horzDiff = Vector3(diffVector.x, 0.0f, diffVector.y);
  
    // We shrink our values by this factor to prevent too much
    // precision loss.
    const float factor = 100.0;

    // Remember that Unitize returns length
    float x = horz.Unitize() / factor; 
    float y = diffVector.y / factor;
    float v = speed / factor;
    float g = gravity / factor;

    term1 = pow(v, 4) - (g * ((g * pow(x,2)) + (2 * y * pow(v,2))));

    // If term1 is positive, then the 'end' point can be reached
    // at the given 'speed'.
    if ( term1 >= 0 )
    {
        canHit = true;

        term2 = sqrt(term1);

        double divisor = (g * x);

        if ( divisor != 0.0f )
        {
            if ( bUseHighArc )
            {
                root = ( pow(v,2) + term2 ) / divisor;
            }
            else
            {
                root = ( pow(v,2) - term2 ) / divisor;
            }

            root = atan(root);

            angleOut = static_cast<float>(root);

            Vector3 rightVector = horz.Cross(Vector3::UnitY);

            // Rotate the 'horz' vector around 'rightVector' 
            // by '-angleOut' degrees.
            RotatePointAroundAxis(rightVector, -angleOut, horz); 
        }

        // Now apply the speed to the direction, giving a velocity
        outTrajectory = horz * speed;
    }

    return canHit;
}

Bear in mind that the above function assumes an 'up' direction of +Y, and also assumes gravity to be -Y, which is why only a float is needed to represent gravity, rather than a vector.

The formula used by this function gives two trajectories to reach the 'end' point, the highest possible trajectory, and the lowest possible trajectory. The 'bUseHighArc' variable passed in is what determines which result is used.

You'll notice a reference to a new function called 'RotatePointAroundAxis' in there, I have not yet gone over matrix mathematics in my blog, and rather than get into that now I will supply you with the math required create a rotation matrix and use that to rotate our point. If you think of the example I gave earlier about firing a cannon ball, imagine that the cannon was spun around to face the direction it needs to fire, but hasn't yet been elevated to the correct firing angle, this function is what we're using to rotate our currently flat 'horz' vector into the air.

Vector3 RotatePointAroundAxis( const Vector3& axis, const float
                               radians, const Vector3& point )
{
    float matrix[3][3];

    float sn = sinf(radians);
    float cs = cosf(radians);

    float xSin = axis.x * sn;
    float ySin = axis.y * sn;
    float zSin = axis.z * sn;  
    float oneMinusCS = 1.0f - cs;
    float xym = axis.x * axis.y * oneMinusCS;
    float xzm = axis.x * axis.z * oneMinusCS;
    float yzm = axis.y * axis.z * oneMinusCS;

    matrix[0][0] = (axis.x * axis.x) * oneMinusCS + cs;
    matrix[0][1] = xym + zSin;
    matrix[0][2] = xzm - ySin;
    matrix[1][0] = xym - zSin;
    matrix[1][1] = (axis.y * axis.y) * oneMinusCS + cs;
    matrix[1][2] = yzm + xSin;
    matrix[2][0] = xzm + ySin;
    matrix[2][1] = yzm - xSin;
    matrix[2][2] = (axis.z * axis.z) * oneMinusCS + cs;

    return Vector3
    (
        matrix[0][0] * point.x + matrix[0][1] * point.y + matrix[0][2] * point.z,

        matrix[1][0] * point.x + matrix[1][1] * point.y + matrix[1][2] * point.z,

        matrix[2][0] * point.x + matrix[2][1] * point.y + matrix[2][2] * point.z
    );   
}

Normally you wouldn't have to create your own function to rotate a point around an axis, this would generally be part of the Matrix class you would find in a math library. What you'll often find when programming is that you need to understand the concept behind which functions you're using so that you can make an educated decision about which functions you will need to perform a task. There is little need for you to memorize the exact function above, because you'll have it as part of an engine or you can look it up online, but knowing how the function works is something you might want to do some day. For now I'll skip the lesson on matrix math.

Using Vector Mathematics, Point against sphere intersection test

In this post we learn how to do a simple check to see if a point in 3D space intersects a sphere. It is common practice in games to approximate complicated shapes with a sphere for collision or proximity checks, for example if you want to fire a bullet and see what objects that bullet may hit, you could approximate the bullet path with a straight line (which isn't entirely accurate), and approximate certain objects with spheres (also not entirely accurate).

This is a very simple intersection test. We just need to know how far the point is from the center of the sphere, and if that distance is greater than the radius of the circle. As per usual for distance comparisons we can used squared lengths for this to save us a square-root calculation.

For a simple example we'll place a sphere at (0, 0, 0), with a radius of 5, and we'll check against a point in space at (4, 4, 4).

Squared radius of sphere = 5² = 25
Difference vector between point and center of sphere = (4 - 0, 4 - 0, 4 - 0) = (4, 4, 4)
Squared length of difference vector = ( 4² + 4² + 4² ) = ( 16 + 16 + 16 ) = 48
Because the length of the difference vector is greater than the sphere's radius, we know the point does intersect the sphere.

Here is the code for this intersection test:

bool Vector3::IsWithinSphere(const Vector3& SphereCenter,
                             const Vector3& SphereRadius)
{
    Vector3 diffVector = Vector3(x - SphereCenter.x,
                                 y - SphereCenter.y,
                                 z - SphereCenter.z);

    return (diffVector.LengthSqr() < (SphereRadius * SphereRadius));
}

Using Vector Mathematic, Finding closest point on a line

In this post we will be looking at determining the closest point on a line from another point. This technique by itself isn't worth much, but it's required as part of other techniques, such as an intersection test between a line and a sphere, which I may post about later.

Describing how this works using only words is going to be tough. Lets start with a picture to help:

Of the points in this picture, only point B lies along the line segment. Technically you could say that the closest point on the segment to point A is P1, and to C is P2, but in most cases where you want the closest point on a line segment you want to exclude points that aren't going to lie in that segment, so we will exclude them for our purposes.

First we need to get some information setup that we'll be able to test with.

1. We need a vector from P1 to P2, which is achieved by doing P2 - P1.
   Line difference vector is (5 - 0, 0 - 0, 0 - 0) = (5, 0, 0)
2. We need the squared length of the vector we just got in step 1.
   I'm not even doing the math for this part, only one component is non-zero, which is the 5, so the   length in this case is 5, leaving squared length at 25.
3. We need a vector from P1 to our test point (point B), which is B - P1.
   Point difference from P1 is (3 - 0, 0 - 0, -2 - 0) = (3, 0, -2)

Now we do the dot product between our line difference vector and our line to point vector
line diff ( dot ) line to point = ( 3*5 + 0*0 + -2*0 ) = 15

Notice that unlike previous posts, we don't unitize our difference vectors before doing a dot product. In this case we take that dot product and now divide it by the squared length.

Percentage from start to end point = 15 / 25 = 0.6 (0.6 is the same as saying 60%)

Note: We didn't test points A or C because we could see from the picture they weren't on the line segment, but normally you won't be able to just pick which point you want to test, you test every point, and if your value above (which for point B is 0.4) is less than 0.0 or greater than 1.0, then you know it's outside of the line segment.

Now, the closest point is calculated as such:
P1 + ( U * ( P2 - P1 ) )

Which for our example becomes this:
(0, 0, 0) + ( 0.6 * ( 0, 0, 5 ) ), which simplifies to ( 3, 0, 0 )

Here's the code for this:

Vector3 GetClosestPointOnLineSegment(const Vector3& LinePointStart, const Vector3& LinePointEnd,
                                     const Vector3& testPoint)
{
    const Vector3 LineDiffVect = LinePointEnd - LinePointStart;
    const float lineSegSqrLength = LineDiffVect.LengthSqr();

    const Vector3 LineToPointVect = testPoint - LinePointStart;
    const float dotProduct = LineDiffVect.dot(LineToPointVect);

    const float percAlongLine = dotProduct / lineSegSqrLength;

    if (  percAlongLine  < 0.0f ||  percAlongLine  > 1.0f )
    {
        // Point isn't within the line segment
        return Vector3::ZERO;
    }

    return ( LinePointStart + ( percAlongLine * ( LinePointEnd - LinePointStart ));
}

Using Vector Mathematics (and a bit of trig), Point against cone intersection test

In this post we're going to see how to check if a point lines within a 3D cone. To be clear, it's not exactly a cone, it's like a cone that goes on forever, or if we give a max distance it's like a cone with a round bottom instead of flat.

You might wonder what this kind of intersection test is good for; It's mostly used for things like checking if a point is within an object's field-of-view.

So for checking if a point is within an object's field of view, we need 4 parameters.
We need the position of the object, the direction it is facing, the position of the point we're checking, and the field of view of the object.

We'll pick some convenient values to make things easier to understand.
Object position = (0, 0, 0)
Object facing direction (0, 0, 1)
Point position = (0.5, 0, 1.5)
Field of view = π/3 radians (60 degrees)

We need to get the direction from the object to the point:
Difference vector = (0.5 - 0, 0 - 0, 1.5 - 0) = (0.5, 0, 1.5)

Now that we have the difference, we need to unitize it to get a direction.
length = √( 0.5² + 0² + 1.5² ) = √( 0.25 + 0 + 2.25 ) = √2.5 = 1.5811388
inverse length = 1 / 1.5811388 = 0.63245554
direction = (0.5 * 0.63245554, 0 * 0.63245554, 1.5 * 0.63245554) = (0.31622777, 0, 0.94868331)

Now that we have the direction from the object to the point we get the dot product between that vector and the object's facing direction.

Facing direction (dot) direction to point = (0 * 0.31622777 + 0 * 0 + 1 * 0.9486331) = 0.9486331

Now we need to calculate the cosine of half of the player's field of view. We use half because we want the angle from the center of the cone of FOV, just like dot product is the angle from the center.

half of FOV = π/6
cosine(π/6) = 0.866025

And finally, what determines if the point is in the object's FOV is if the dot product (0.9486331) is greater than or equal to the cosine of half of the FOV (0.866025). In this case it is greater than or equal to the cosine of the FOV, so that point is in the object's FOV.

And here's the function for doing this type of calculation:

bool IsPointWithinCone(const Vector3& coneTipPosition,
                       const Vector3& coneCenterLine,
                       const Vector3& point,
                       const float FOVRadians)
{
    Vector3 differenceVector = point - coneTipPosition;
    differentVector.Unitize();

    return ( coneCenterLine.Dot(differenceVector) >=
             cos( FOVRadians ) );
}

The above function assumes a cone the continues on forever. If the we assume that our object cannot see for an infinite distance then we can add a distance check.

bool IsPointWithinFiniteCone(const Vector3& coneTipPosition,
                             const Vector3& coneCenterLine,
                             const Vector3& point,
                             const float FOVRadians,
                             const float maxDistance)
{
    Vector3 differenceVector = point - coneTipPosition;

    // Notice that Unitize() is returning a float. The
    // original one we wrote didn't return a float, we'll
    // cover this change in an upcoming blog post
    float length = differentVector.Unitize();

    if ( length > maxDistance )
    {
        return false;
    }

    return ( coneCenterLine.Dot(differenceVector) >=
             cos( FOVRadians );
}

In our original example at the top of the post our point was 1.58 units away, so if we used a finite distance check like the function just above and passed a max distance of 1.5 in, the object would be considered outside of the view.

Using Vector Mathematics, Complete Vector3 Class

After a large series of vector mathematics blog posts, here is a full Vector3 class that I wrote, it's fairly efficient and should be enough to suit your needs if you would like to use it. There are other 3rd-party math libraries out there if you'd like to browse your options.

Header file: Vector3.h

#pragma once // Most compilers are compatible, remove if yours isn't
#ifndef VECTOR_3
#define VECTOR_3

#include <math.h>
#include <ostream>

class Vector3
{
public:
Vector3(void);
explicit Vector3(const float x, const float y, const float z);

// Copy constructor
Vector3(const Vector3& rhs);

~Vector3(void);

bool operator==(const Vector3& rhs) const { return ( (x == rhs.x) 
                                                  && (y == rhs.y)
                                                  && (z == rhs.z));}
bool operator!=(const Vector3& rhs) const { return ( (x != rhs.x)
                                                  || (y != rhs.y)
                                                  || (z != rhs.z));}
Vector3 operator+(const Vector3& rhs) const;
void operator+=(const Vector3& rhs);
Vector3 operator-(const Vector3& rhs) const;
Vector3 operator-(void) const;
void operator-=(const Vector3& rhs);
void operator*=(const int scalar);
void operator*=(const float scalar);

// Non-member operators get a friend declaration
friend Vector3 operator*(const Vector3& vector, const int scalar);
friend Vector3 operator*(const Vector3& vector, float scalar);
friend Vector3 operator*(const int scalar, const Vector3& vector);
friend Vector3 operator*(const float scalar, const Vector3& vector);
friend std::ostream& operator<<(std::ostream& ofs,const Vector3& rhs);

inline void Flip(void) { x = -x; y = -y; z = -z; }

inline float Dot(const Vector3& rhs) const { return (x * rhs.x
                                                   + y * rhs.y
                                                   + z * rhs.z); }

Vector3 Cross(const Vector3& rhs) const;

float Length(void) const { return sqrtf( LengthSqr() ); }

inline float LengthSqr(void) const { return (x * x + y * y + z * z); }

float Unitize(void);

void Reflect( const Vector3& rhs );

static Vector3 Reflect( const Vector3& first, const Vector3& second );
static Vector3 GetLongest(const Vector3& first, const Vector3& second);

static const Vector3 Left;
static const Vector3 Right;
static const Vector3 Up;
static const Vector3 Down;
static const Vector3 Forward;
static const Vector3 Backward;

static const Vector3 UnitX;
static const Vector3 UnitY;
static const Vector3 UnitZ;

static const Vector3 Zero;


float x;
float y;
float z;
};

#endif //VECTOR_3

Implementation File, Vector3.cpp:

#include "Vector3.h"

#include <sstream>

const Vector3 Vector3::Right(1.f, 0.f, 0.f);
const Vector3 Vector3::Up(0.f, 1.f, 0.f);
const Vector3 Vector3::Forward(0.f, 0.f, 1.f);
const Vector3 Vector3::Left(-1.f, 0.f, 0.f);
const Vector3 Vector3::Down(0.f, -1.f, 0.f);
const Vector3 Vector3::Backward(0.f, 0.f, -1.f);

const Vector3 Vector3::UnitX(1.f, 0.f, 0.f);
const Vector3 Vector3::UnitY(0.f, 1.f, 0.f);
const Vector3 Vector3::UnitZ(0.f, 0.f, 1.f);
const Vector3 Vector3::Zero(0.0f, 0.0f, 0.0f);

Vector3::Vector3(void) : x(0.0f), y(0.0f), z(0.0f)
{
}

Vector3::Vector3(const float x, const float y, const float z)
{
    this->x = x;
    this->y = y;
    this->z = z;
}

// Copy constructor
Vector3::Vector3(const Vector3& rhs)
{
    x = rhs.x;
    y = rhs.y;
    z = rhs.z;
}

Vector3::~Vector3(void)
{
}
Vector3 Vector3::operator+(const Vector3& rhs) const
{
    Vector3 newVector;
    newVector.x = x + rhs.x;
    newVector.y = y + rhs.y;
    newVector.z = z + rhs.z;
    return newVector;
}

void Vector3::operator+=(const Vector3& rhs)
{
    x += rhs.x;
    y += rhs.y;
    z += rhs.z;
}

Vector3  Vector3::operator-(const Vector3& rhs) const
{
    Vector3  newVector;
    newVector.x = x - rhs.x;
    newVector.y = y - rhs.y;
    newVector.z = z - rhs.z;
    return newVector;
}

Vector3 Vector3::operator-(void) const
{
    Vector3  newVector(-x, -y, -z);
    return newVector;
}

void Vector3::operator-=(const Vector3& rhs)
{
    x -= rhs.x;
    y -= rhs.y;
    z -= rhs.z;
}

void Vector3::operator*=(const int scalar)
{
    x *= scalar;
    y *= scalar;
    z *= scalar;
}

void Vector3::operator*=(const float scalar)
{
    x *= scalar;
    y *= scalar;
    z *= scalar;
}

Vector3 operator*(const Vector3& vector, const int scalar)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const Vector3& vector, const float scalar)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const int scalar, const Vector3& vector)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const float scalar, const Vector3& vector)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}
std::ostream& operator<< (std::ostream& os, const Vector3& vector)
{
    std::stringstream stream;
    stream << "X: " << vector.x << ", Y: " << vector.y << ", Z: " << vector.z; 
    os.write(const_cast<char*>(stream.str().c_str()),
             static_cast<std::streamsize>(stream.str().size() *
             sizeof(char)) );
    return os;
}

Vector3 Vector3::Cross(const Vector3& rhs) const
{
    return Vector3( (y * rhs.z) - (z * rhs.y), 
                    (z * rhs.x) - (x * rhs.z),
                    (x * rhs.y) - (y * rhs.x) );
}

float Vector3::Unitize(void)
{
    const float length = Length();
    const float inverseLength = 1.0f / length;
    x *= inverseLength;
    y *= inverseLength;
    z *= inverseLength;
    return length;
}

void Vector3::Reflect( const Vector3& normal )
{
    const float dotProductTimesTwo = Dot(normal) * 2.0f; 
    x -= dotProductTimesTwo * normal.x;
    y -= dotProductTimesTwo * normal.y;
    z -= dotProductTimesTwo * normal.z;
}

Vector3 Vector3::Reflect(const Vector3& vector, const Vector3& normal)
{
    Vector3  newVector;
    const float dotProductTimesTwo = vector.Dot(normal) * 2.0f;
    newVector.x = vector.x - (dotProductTimesTwo * normal.x);
    newVector.y = vector.y - (dotProductTimesTwo * normal.y);
    newVector.z = vector.z - (dotProductTimesTwo * normal.z);
    return newVector;
}

Vector3 Vector3::GetLongest(const Vector3& first, const Vector3& second)
{
    if ( first.LengthSqr() > second.LengthSqr() )
        return first;

    return second;
}

Using Vector Mathematics, Cross Products

Cross products are the most complicated use of vectors we've covered so far. One thing you'll need to know is if your game engine's coordinate system is left-handed or right-handed. If you're unfamiliar with coordinate system handedness, you might read over this article on Wikipedia.

The cross product method is very handy for finding the vector that is perpendicular/orthogonal to two other vectors. Any two non-parallel vectors will form a plane, and the line perpendicular to that plane that passes through the two vectors will always exist, that line can be found with a cross product. You might be asking how this is useful in 3D games? It's often used for finding an object's forward, up, or right vector. An object's forward vector is the vector that goes from the position of the object outward through the front of the object, an up vector is a vector that goes from the position of the object upward out of the top of the object, and the right vector goes from the position of the object out the right side of the object. Any vectors parallel to those vectors qualify as well. A picture might help clarify (or it might confuse you more):

Don't worry, this stuff confused me when I first started as well, a large part of being comfortable doing vector mathematics in games is just being able to picture multiple points and vectors in 3D, so you can picture exactly what it is you're trying to get. If you still want some info on Cross Product after this blog post, this video on YouTube might clarify.

Anyway, let's move on to explaining the math behind a cross product. Here's the exact formula:

If A and B are vectors, and x, y, z, denote the parameter within the vector

A (cross) B = ( Ay*Bz - Az*By, Az*Bx - Ax*Bz, Ax*By - Ay*Bx )

Don't feel bad if you don't memorize this, I haven't got it memorized either.

So let's take some vectors we know to be orthogonal, and see if the cross product gets us the same result:

Vector A = (1, 0, 0)

Vector B = (0, 1, 0)

Vector C = (0, 0, 1)

A (cross) B, should result in C given the three vectors we defined just above.

A (cross) B = ( 0*0 - 0*1, 0*0 - 1*0, 1*1 - 0*0 ) = (0, 0, 1)

As you can see A (cross) B, does indeed give us Vector C as we had defined it above.

And to give a real world scenario I often run into in actual game development. If we take an NPC that is always upright (by upright I mean that it's not laying on its side or something), if we want to get its right or left vectors, we just need the forward vector, and since its always upright we already have the up vector. Based on having the forward and up vector, forward (cross) up will give you the right vector.

Here's a guide of what vectors crossed (in a left-handed coordinate system) will give you:

Forward (cross) up --> Right

Up (cross) Forward --> Left

Forward (cross) right --> Down

Right (cross) Forward --> Up

Up (cross) right --> Backward

Right (cross) up --> Forward

If you read that first link I gave to Wikipedia about coordinate handedness, you'll find you can use your pointer finger, thumb, and middle finger to represent the three axes to determine the cross product order and what it will give you. 

I'll try and explain. Hold out your left hand in closed fist and give a thumbs up, now point your pointer finger straight ahead of you now point your middle finger out perpendicular to your thumb and pointer finger. In this position you can think of the cross product as:

Pointer (cross) Thumb --> Middle

Using this you can use whatever vectors you have to figure out which order to use the cross product. For example let's say you want an UP vector. Hold out your hand like I explained earlier, but turn your arm or wrist so that your middle finger is pointed upward now, and you will now see that your pointer finger is pointing Forward, and your thumb is pointed Left. Therefore: Forward (cross) Left --> Up, and you can always reverse the order to get Down, so Left (cross) Forward --> Down.

Hope this all makes sense. And here's the function for a cross product:

Vector3 Vector3::Cross(const Vector3& rhs) const
{
    return ( (y * rhs.z) - (z * rhs.y),
             (z * rhs.x) - (x * rhs.z),
             (x * rhs.y) - (y * rhs.x) );
}

Using Vector Mathematics, finding a signed angle between two vectors

In the last blog post we talked about finding the angle between two vectors, but sometimes you will find it necessary to know which side of a vector another vector is. This is especially useful for A.I. steering, having an enemy know that it needs to turn 50 degrees isn't useful unless you also can tell it which way to turn.

Here's a handy little function you can use to get the angle between vectors in a signed format (+/-). You'll pass in your source vector (which is generally the way something is facing), the destination vector (the way something is wanting to turn to), and an angle that is 90 degrees to the right of the destination angle (we'll call it 'DestsRight'). To get an angle 90 degrees to the right of the destination angle you may need to use a Cross Product, which we'll be going over in the this blog post.

float GetSignedAngleBetweenVectors( const Vector3& Source, 
                                    const Vector3& Dest,
                                    const Vector3& DestsRight ) 
{    // We make sure all of our vectors are unit length
    Vector3 SourceCopy = Source;
    SourceCopy.Unitize();
    Vector3 DestCopy = Dest;
    DestCopy.Unitize();
    Vector3 DestsRightCopy = DestsRight;
    DestsRightCopy.Unitize();
    
    float forwardDot = Vector3.Dot( SourceCopy, DestCopy );
    float rightDot = Vector3.Dot( SourceCopy, DestsRightCopy );

    // Make sure we stay in range no matter what, so Acos
    // doesn't fail later
    if ( forwardDot < -1.0f )
    { 
        forwardDot = -1.0f;
    }
    else if ( forwardDot > 1.0f )
    {
        forwardDot = 1.0f;
    }

    float angleBetween = acos( forwardDot ); 

    if ( rightDot < 0.0f )
    {        
        angleBetween *= - 1.0f;
    }        

    return angleBetween;
}

If we were to use this above function with these vectors:

The dot between S and D would be greater than 0, dot between S and R would be less than 0, so the final result angle would be negative, so we would know if D is the way we're facing we'd need to turn left to get to S.

The dot between S and D would be greater than 0, dot between S and R would be greater than 0, so the final result angle would be positive, so we would know if D is the way we're facing we'd need to turn right to get to S.

I'm too lazy right now to do a math proof of the above function, so you'll just need to trust me that it works (I've used something like this in production code).

Using Vector Mathematics, finding angle between two vectors

In the last blog post we learned about Dot Products, and how it could be used to find relative differences between two vectors, but now we will learn how to find the exact angle between those two vectors.

For this example we will use two very simple vectors. To get the angle between two vectors you will need to unitize your vectors or make sure they're already unit-length, for simplicity I will just use two unit-length vectors to start with in this example:

Vector a = (1, 0, 0)
Vector b = (0, 0, 1)

You'll notice the above vectors are both along an axis, which means they're perfectly perpendicular, which also means we know already that they're 90 degrees apart ( π/2 radians apart ), but we'll use that knowledge as proof that what I'm about to show you does in fact work. Also, for future reference, please note that any vectors that are perpendicular to each other are also known as orthogonal, this term is often used when referring to vectors, so it's important to know.

Ok, so first we'll get the dot product of the vectors, which should end up being 0 since the vectors are orthogonal.

a (dot) b = (1*0 + 0*0 + 0*1) = 0

And now to get the angle between the vectors, we will use the trigonometric function for arc-cosine, called acos(). Please note that acos() requires a value between -1 and 1, anything outside of that range will cause acos() to return a non-number return value, which you don't want. It's safest to range check what you're about to pass it just in case.

acos(0) = π/2 radians, which is 90 degrees.

If you have two vectors that are parallel, you'll always get a dot product of ±1, and acos(-1) or acos(1) is always 0 radians/degrees as you would expect. But lets test it with a dot product just for fun:

Vector c = (1, 0, 0)
Vector d = (1, 0, 0)

c (dot) d = (1*1 + 0*0 + 0*0) = 1
acos(1) = 0 radians/degrees

Vector e = (-1, 0, 0)

c (dot) e = (1*-1 + 0*0 + 0*0) = -1
acos(-1) = 0 radians/degrees

And.....now some code:

inline float FindAngleBetweenVectors( const Vector3& first,
                                      const Vector3& second )
{
    // You might leave these Unitize calls out if you know
    // you're always passing in Unitized vectors. However
    // I recommend having two versions of this function,
    // one that takes unit vectors, and one that will unitize
    // them for you.
    // Copies are required because we're passing in 'first'
    // and 'second' by const reference, which allows the
    // user to pass in vectors and not worry about them
    // unintentionally getting unitized.
    Vector3 firstCopy = first;
    firstCopy.Unitize();

    Vector3 secondCopy = second;
    secondCopy.Unitize();

    const float dotProduct = firstCopy.Dot(secondCopy);

    // A range check here is a good idea for safe code, I'll
    // leave it out for this sample though.

    return acos(dotProduct);
}

Using Vector Mathematics, Dot Products

Dot product is one of the properties of vectors that you can get when multiplying them. The dot product has many useful properties with vectors, in fact, the Dot Product and Cross Product are probably some of the most important properties of vectors in 3D math used in video games. The Dot Product is most often used to tell us information about the angle between two vectors, this can be used, for example, to tell if a point is in front of a player, or behind them.

To get a dot product, you multiply each component of two vectors, and then add each component together, like such:

Vector a = (3, -5, 7)
Vector b = (5, -2, -9)

a (dot) b = ((3 * 5) + (-5 * -2) + (7 * -9)) = 15 + 10 - 63 = -38

While the above method is using the dot product, most often you'll find you need the dot product of two unit-length vectors, which will always yield a result between -1 and +1, and as we'll discuss later on, that is extremely useful. So, we will unitize the two vectors from our above example, which will basically give us two direction vectors.

Length of a = √(3*3 + -5*-5 + 7*7) = √(9 + 25 + 49) = √83 = 9.110433
Inverse length of a = 1 / 9.110433  = 0.1097642
Unitized vector a = (3 * 0.1097642, -5 * 0.1097642, 7 * 0.1097642) = (0.3292926, -0.548821, 0.7683494)

Length of b = √(5*5 + -2*-2 + -9*-9) = √(25 + 4 + 81) = √110 = 10.488088
Inverse length of b = 1 / 10.488088 = 0.0953463
Unitized vector b = (5*0.0953463, -2*0.0953463, -9*0.0953463) = (0.4767315, -0.1906926, -0.8581167)

Alright, now that we have unit vectors let's try the dot product again:
a (dot) b = (0.3292926 * 0.4767315) + (-0.548821 * -0.1906926) + (0.7683494 * -0.8581167)
              = 0.1569842 + 0.1046561 + -0.65933345
              = -0.39769315, or let's just round it to -0.4

So, what does -0.4 really mean to you in this case? Well here's the cool part. With a dot product, if we treat the two vectors as directions, then a value less than 0 means that vector 'b' is behind vector 'a'. A value greater and 0 means it would be in front, and a value of 0 means it's directly to the left or right of 'a'.

So in this particular example, if we think of 'a' as the direction an object is facing, and think of vector 'b' as a point in space than that means that the point 'b' is behind the object. This is extremely useful for things like artificial intelligence, if an enemy knows the player is behind them, then it can be told to start turning around to face the player, or if the enemy knew the player was in front of them then they might know they are able to attack the player. Knowing where one object is in relation to another, especially based on that object's rotation, is essential for all kinds of things that require steering, not just A.I. So if you plan on making a 3D game, then the Dot Product is your friend. Learn it, live it, love it.


Here's a rough sketch of what this looks like, in this example I've done a top-down perspective, so I left the Y component out of the sketch, but based on the Y-components if this were in-game the enemy would be slightly higher than the player. Anyway, in the picture the arrow is the direction the player is facing, the line perpendicular to the arrow would be the left and right of the player, and as you can see the position of the enemy (which is 5, -9) is behind the player (and a bit to the right as well).

And finally, here's the code for our above example:

The Dot function would be a member of a Vector class most likely:

inline float Vector3::Dot( const Vector3& rhs ) const
{
    return (x * rhs.x
          + y * rhs.y
          + z * rhs.z);
}

And now to put our new Dot function to use:

Vector3 first = Vector3(3, -5, 7);
Vector3 second = Vector3(5, -2, -9);

first.Unitize();
second.Unitize();

float dotProduct = first.Dot(second);

// dotProduct is approx. -0.4

Using Vector Mathematics, utilizing squared lengths

As we've learned in the Optimizing Methods blog post, the most expensive part about doing distance checks is the square-root calculation. There are some cases where we need to do things like compare distances, but we can forego the square-root calculation.

If we want to compare two vectors to see which is longer we can do that without a square-root calculation. We don't need to know the exact length of each vector, we just need to know which is longer, so if we just skip the square-root calculation during the Length() function, when instead end up getting a squared length, which is all we want in this case.

Here's a static/helper method:

float GetSquaredLength( const Vector3& inVect )
{
    return ( inVect.x * inVect.x
           + inVect.y * inVect.y
           + inVect.z * inVect.z );
}

Here's the method you might find in a Vector class:

inline float Vector3::SquaredLength() const
{
    return ( x*x + y*y + z*z );
}

So if we put this two the test, with two vectors, (2, 2, 2) and (2, 2, 3).

The squared length of (2, 2, 2) is ( 2² + 2² + 2² ), or 12.

The squared length of (2, 2, 3) is ( 2² + 2² + 3² ), or 17.

Based on the calculations we know that (2, 2, 2) is the shorter of the two vectors, which may have been obvious, but now we've seen the proof. The actual length of these vectors isn't needed to know which is shorter, but just for some more proof, to find the actual lengths now is very easy because we already have the squared length, so we can now just do the square-root calculation:

The length of (2, 2, 2) is √12, or 3.4641.
The length of (2, 2, 3) is √17, or 4.1231.

In the Optimizing Methods blog post I mentioned that sometimes is isn't the method itself that needs to be optimized, but rather that sometimes you can avoid needing the expensive methods together. Using squared lengths for distance comparisons is just one example of this.

Here's a helper function for returning the longest of two vectors:

Vector3 Vector3::GetLongest(const Vector3& first,
                            const Vector3& second) const
{
    if ( first.SquaredLength() > second.SquaredLength() )
        return first;

    return second;
}

Using Vector Mathematics, finding direction from one point to another

Finding the direction from one point to another is fairly easy, in order to do this you'll need to understand how to unitize vectors and how to do vector subtraction, please make sure you've read up about unitizing vectors from this blog post, and read up about vector subtraction from this blog post.

If you understand unitizing vectors and vector subtraction, then this will be incredibly simple.

Let's imagine our player is standing at position (10, 4, 7), and an enemy is standing at position (5, 9, -9), and we want to find the direction from the player to the enemy. To do this we first subtract the player's position from the enemy's position, and this gives us the vector from the player to the enemy.

(5 - 10, 9 - 4, -9 - 7) = (-5, 5, -16).

Now we simply unitize this vector and we have our direction.
Get the length of the vector √(-5 * -5 + 5 * 5 + -16 * -16) = √(25 + 25 + 256) = √306 = 17.4928556
Now using the inverse of length we can get unitize the vector:

Inverse length = 1 / 17.4928556, or 0.05711619.

Multiple inverse length by each element of our vector:
( -5 * 0.05711619, 5 * 0.05711619, -16 * 0.05711619 ) = ( -0.28583097, 0.28583097, 0.91385904 )


The code for this is very simple, we'll use the Unitize() method from our previous blog post, which is this:

inline void Vector3::Unitize()
{
    const float inverseLength = 1.0f / GetLength(); 
    x *= inverseLength;
    y *= inverseLength;
    z *= inverseLength;
}

Here's our simple function from getting the direction from the first point to the second:

Vector3 GetDirectionFromFirstToSecond( const Vector3& first,
                                       const Vector3& second )
{
    const Vector3 differenceVector = second - first;
    differenceVector.Unitize();
    return differenceVector;
}

Here's what the original sample vectors about would look like in code:

Vector3 playerPos = (10, 4, 7);
Vector3 enemyPos = (5, 9, -9);

Vector3 dirPlayerToEnemy = GetDirectionFromFirstToSecond( 
                                       playerPos, enemyPos );

// dirPlayerToEnemy is ( -0.28583097, 0.28583097, 0.91385904 )

Havok: Connecting your in-game camera to the Havok Visual Debugger

In projects using Havok, one thing that I've found invaluable is having the Havok Visual Debugger (HVD) visually match what you see in the game. Luckily, Havok provides a way for you to pass your camera's information to the HVD.

To send a camera's information to the HVD, you'll need the following:

• The position of the camera
• The forward/facing direction
• The up vector/axis
• The near and far plane distances
• The camera's FOV (field of view), in degrees (NOT radians)
• The name of the camera that you want to be seen and shown in the HVD.

Once you have all that information, you simply make the call to Havok's macro. I recommend creating an update function that you can call each frame when the camera updates, or when the renderer finally grabs the camera's information.

void UpdateVisualDebugger()
{
    Vector3 destination = m_position + m_forwardDir;

    HK_UPDATE_CAMERA( m_position, destination, m_upDir, m_nearPlaneDist, 
                      m_farPlaneDist, m_FOV, m_Name.c_str() );
}

Havok doesn't deal with STL types like strings, so you'll need to use .c_str() to send it the char pointer instead.

When you first connect the debugger to the game you will notice it isn't connected to the camera (this can be made to happen automatically, I may go over that in a future post). To connect to the camera, go to View->User Cameras->WhateverCameraNameYouChose.

If you're not properly or currently sending any camera information to Havok you may not see the 'User Cameras' option at all. Use a breakpoint to make sure you're hitting the macro during program execution.

If all worked well you should see your HVD window match your game's window. Please note that you can resize your HVD window and game window seperately, if you chose different aspect ratios for each window you will not get a perfect visual match between them, so try and keep them similar.

You'll also notice at the bottom of the HVD the name of the camera you're attached to. In my example above I've named my camera "Main Camera".

You may find that you're changing or creating cameras during the course of a game's execution, unfortunately Havok does not support automatically changing to new or different user cameras in the debugger when you change camera's from within game. I have put a support ticket in with them to consider including this in a future version. In the mean-time if you want this functionality you will need to have a user camera name that represents whatever camera happens to be active at the time. I recommend sending the active camera each frame under a generic name like "Active Camera" or "Main Camera", as well as the active camera by its unique name like "Character Camera". This will allow the developer to choose to always see the active camera from within Havok, or choose a unique camera and not have it switch automatically.

Havok: Setting mesh color in the Visual Debugger, Part 1

Anyone developing a game using Havok no doubt knows about the Havok visual debugger (which I'll refer to as the HVD), however if you're using the free SDK there is little provided information on how to send data to the visual debugger. Having worked with the full Havok source on a previous project I can provide what I hope to be some valuable insight on how to better utilize the HVD, which should help you debug your game easier.

Setting colors is the HVD is actually really simple, Havok provides a macro that does the work for you, you only have to pass a byte-packed unsigned 32-bit integer representing the color you want, and the pointer to the hkpCollidable. The format of your integer is 1 byte per channel, first byte is the alpha-channel, then red, blue, and green.

Here's a simple function that does the dirty work for you:

// Needed for calling color change macro
#include <common\visualize\hkdebugdisplay.h>

// You'll of course need any other headers for any other physics stuff 
// you're doing in your file

void SetColorForPhysicsDebugger( unsigned int Red, unsigned int Green,
                                 unsigned int Blue, unsigned int Alpha, 
                                 const hkpCollidable* pCollidable )
{
    // Havok takes an unsigned int (32-bit), allowing 8-bits for 
    // each channel (alpha, red, green, and blue, in that
    // order).

    // Because we only need 8-bits from each of the 32-bit ints 
    // passed into this function, we'll mask the first 24-bits.
    Red &= 0x000000FF;
    Green &= 0x000000FF;
    Blue &= 0x000000FF;
    Alpha &= 0x000000FF;

    // Now we pack the four channels into a single int
    const uint32_t color = (Alpha << 24) | (Red << 16) | (Green << 8) | Blue;

    // We use the macro provided by Havok
    HK_SET_OBJECT_COLOR( reinterpret_cast<hkulong>( pCollidable ), color );
}

In the image below you can see this in action. I have a running sample in which rigid bodies are red and opaque by default, whereas phantoms/triggers are blue and translucent.

Using colors for different categories of objects in your game can be extremely powerful. On one project I was on I created an entire custom interface and tool around filtering physics to show developers only what they were looking for, for example NPCs could collide with certain triggers that human players could not, so there was a filter for looking at the physics world from an NPCs point of view, while in the filter you could only see physics that the NPC could collide with.

This is part 1 of 2 of this series, part 2 shows you how to know when somebody connects to the HVD, because you'll need to resend all color information anytime someone connects.