Tag Archives: C++

Articles

Nullptr

This last week, I spent a couple days converting all of the uses of NULL in Sauce to nullptr. As such, I wanted to take this opportunity to jot down some notes on what the differences are and why I believe that it is worth your time to convert your own code to use nullptr if you haven’t already.

NULL

Similar to many other C++ code bases, Sauce used the following code to define NULL:

#if !defined(NULL)
   #define NULL 0
#endif

While it is true that many commercial software packages and games have shipped with this definition of NULL, it is still problematic.

The reason why is that NULL is simply an integer, not an actual null pointer. The danger stems from the fact that other constructs can be implicitly converted to and from integers. This means that using NULL can hide bugs.

In fact, I’ll be the first to admit that during the transition to nullptr, I found a few of these types of conversion errors in Sauce. Sure, the code still compiled and ran — but it was a bit disheartening to find them nonetheless.

Nullptr

Unlike NULL, nullptr is a keyword (available starting in C++11). It is defined to be implicitly converted to any pointer type, but cannot be implicitly converted to an integer. This allows the compiler to recognize the sort of type mismatches we hope that it would.

Let’s walk through an example to see the difference.

An Example

The problem we will explore in this example is the fact that booleans can be compared with NULL without a compiler warning. This is because the C++ standard declares that there is an implicit conversion from bool to int.

// signature:
Result* DoSomething();
 
// client code:
if (DoSomething() == NULL)
   printf("NULL\n");
else
   printf("NOT NULL\n");

Although this example is a bit contrived, the danger it exemplifies is real.

What happens if we change the return type of DoSomething() from Result* to bool? A change like this is certainly not unheard of — instead of using a full object, maybe we feel like we can reduce the result to a simple boolean.

// signature:
bool DoSomething();
 
// client code:
if (DoSomething() == NULL)
   printf("NULL\n");
else
   printf("NOT NULL\n");

The code still compiles — no additional warnings (even on Warning level 4!). That seems wrong… checking if a boolean is equal to null pointer is nonsensical and the compiler should bark when it comes across code like this, right?

Unfortunately, the compiler can’t detect the issue because we are using a #define as a stand-in for a null pointer. Remember, it’s not really a null pointer, it’s just the same value that a null pointer evaluates to: 0. Therefore, we shouldn’t be surprised when corner cases like this result in unexpected behavior.

So what happens if we replace NULL with the nullptr keyword?

// signature:
bool DoSomething();
 
// client code:
if (DoSomething() == nullptr)
   printf("NULL\n");
else
   printf("NOT NULL\n");

Now the compiler will generate an error stating that there is no conversion from 'nullptr' to 'int'. This is much better. We know that there is a type mismatch in the comparison, and we can repair the issue.

Final Thoughts

Simply put, the nullptr keyword is a true null pointer, while NULL is not.

When I was first deciding whether I was going to undertake the conversion task, I felt a bit overwhelmed at the number of changes that I would have to make (at the time there were over 5000 instances of NULL in Sauce). However, as I mentioned earlier, had I not made the transition to nullptr, those silent implicit conversion bugs would surely still be there. As such, I feel that Sauce is far better off with nullptr.

Articles

Scoped Enums

For the most part, I really like the C++ language. That said, I also have a small list of things that I wish had been done differently. For years, enumerations have been at the top of that list. Enums have a couple of distinct problems that make them troublesome, and while there are techniques to mitigate some of their issues, they still remain fundamentally flawed.

Thankfully, C++11 added scoped enums (or “strongly-typed” enums), which address these problems head-on. In my opinion, the best part about scoped enums is that the new syntax is intuitive and feels natural to the C++ language.

In an effort to build a case for why scoped enums are superior, we will first discuss the aforementioned deficiencies of their unscoped counterparts. Throughout this discussion we will also outline how we addressed some of these concerns in Sauce. Afterward, we will explore scoped enums and the task of transitioning Sauce to use them.

Terminology

Before we begin, let’s briefly establish some terminology. An unscoped enum has the following form:

enum IDENTIFIER
{
   ENUMERATOR,
   ENUMERATOR,
   ENUMERATOR,
};

The identifier is also referred to as the “type” of the enum. The list inside the enum is composed of enumerators. Each enumerator has an integral value.

Problem 1: Enumerators are treated as integers inside the parent scope.

Aliased Values

Consider the case where you have two enums inside the same parent scope. Unfortunately, there is no reinforcement by the compiler to say that a given enumerator is associated with one enum over the other. This can cause a couple issues. Here’s an example:

namespace Example1
{
   enum Shape
   {
      eSphere,
      eBox,
      eCone,
   };
 
   enum Material
   {
      eColor,
      eTexture,
   };
}

Now let’s see what happens when we try to use these enums in some client code:

const Example1::Shape shape = Example1::eSphere;
if (shape == Example1::eSphere)
   printf("SPHERE\n");
if (shape == Example1::eBox)
   printf("BOX\n");
if (shape == Example1::eCone)
   printf("CONE\n");
 
if (shape == Example1::eColor)
   printf("COLOR\n");
if (shape == Example1::eTexture)
   printf("TEXTURE\n");

The code above prints out both “SPHERE” and “COLOR”. This is because unscoped enum enumerators are implicitly converted to integers and the value of shape is 0, which matches both eSphere and eColor.

Sadly, the only workable solution is to manually assign a value to each of the enumerators that is unique within the parent scope. This is far from ideal due to the added maintenance cost.

Enumerator Name Clashes

Additionally, there is a second issue that arises from the fact that enums are swallowed into their parent scope: enumerator name clashes. For instance, consider modifying the previous case to add an “invalid” enumerator to each enum. While this makes sense conceptually, the following code will not compile:

namespace Example2A
{
   enum Shape
   {
      eInvalid,
      eSphere,
      eBox,
      eCone,
   };
 
   enum Material
   {
      eInvalid,
      eColor,
      eTexture,
   };
}

Although enumerator name clashes are not too common, it is generally bad practice to establish coding conventions that depend on the rarity of such situations.

Consequently, this usually forces you to mangle the enumerator names to include the enum type. Modifying the previous example might look something like this:

namespace Example2B
{
   enum Shape
   {
      eShape_Invalid,
      eShape_Sphere,
      eShape_Box,
      eShape_Cone,
   };
 
   enum Material
   {
      eMaterial_Invalid,
      eMaterial_Color,
      eMaterial_Texture,
   };
}

This version of the code will compile, but now the enumerator names look a little weird. Also, it is important to point out that we are now repeating ourselves: the enum identifier and each of the enumerators.

Another way to solve the name clash issue is to wrap the enum with an additional scoping object: namespace, class, or struct. Employing this method will allow us to keep our original enumerator names, which I like. However, it actually introduces a new problem: now we need two names… one for the scope and one for the enum itself.

Admittedly, there are a few different ways to handle this, but for the sake of the example let’s keep things simple:

namespace Example2C
{
   namespace Shape
   {
      enum Enum
      {
         eInvalid,
         eSphere,
         eBox,
         eCone,
      };
   };
 
   namespace Material
   {
      enum Enum
      {
         eInvalid,
         eColor,
         eTexture,
      };
   };
}

While the extra nesting does make the declaration a bit ugly, it solves the enumerator name clash problem. Furthermore, it also forces client code to prefix enumerators with their associated scoping object, which I personally consider a big win.

// in some Example2C function...
 
const Shape::Enum shape = GetShape();
if (shape == Shape::eInvalid)
   printf("Shape::Invalid\n");
if (shape == Shape::eSphere)
   printf("Shape::Sphere\n");
if (shape == Shape::eBox)
   printf("Shape::Box\n");
if (shape == Shape::eCone)
   printf("Shape::Cone\n");
 
const Material::Enum material = GetMaterial();
if (material == Material::eInvalid)
   printf("Material::Invalid\n");
if (material == Material::eColor)
   printf("Material::Color\n");
if (material == Material::eTexture)
   printf("Material::Texture\n");

In fact, before the transition to scoped enums, most of the enums in Sauce were scoped this way. Unfortunately, the availability of choices in situations like this breed inconsistency. Sauce was no exception: namespace, class, and struct were all being employed as scoping objects for enums in different parts of the code base (needless to say, I was pretty disappointed in this discovery).

Problem 2: Unscoped Enums cannot be forward declared.

This bothers me a lot. I’m very meticulous with my forward declarations and header includes, but unscoped enums have, at times, undermined my efforts. I also feel like it subverts the C++ mantra of not paying for what you don’t use.

For instance, if you want to use an enum as a function parameter, the full enum definition must be available, requiring a header include if you don’t already have it.

The following is a stripped-down example of the case in point:

Shape.h

namespace Shape
{
   enum Enum
   {
      eInvalid,
      eSphere,
      eBox,
      eCone,
   };
}

ShapeOps.h

#include "Shape.h"    // <-- BOO!
 
namespace ShapeOps
{
   const char* GetName(const Shape::Enum shape);
}

Unfortunately, there is no way around using a full include with unscoped enums. The situation is even more costly if the enum is inside a class header file that has its own set of includes.

Scoped Enums

Scoped enums were introduced in C++11. I am excited to report that not only do they solve all of the issues discussed above, but they also provide the client code with clean, intuitive syntax.

A scoped enum has the following form:

enum class IDENTIFIER
{
   ENUMERATOR,
   ENUMERATOR,
   ENUMERATOR,
};

That’s right — all you have to do is add the class keyword after enum and you have a scoped enum!

Converting the final example from the last section to use a scoped enum looks like the following:

Shape.h

enum class Shape
{
   eInvalid,
   eSphere,
   eBox,
   eCone,
};

ShapeOps.h

enum class Shape;   // forward declaration -- YAY
 
namespace ShapeOps
{
   const char* GetName(const Shape shape);
}

Here is an example of client code:

const Shape shape = GetShape();
if (shape == Shape::eInvalid)
   printf("Shape::Invalid\n");
if (shape == Shape::eSphere)
   printf("Shape::Sphere\n");
if (shape == Shape::eBox)
   printf("Shape::Box\n");
if (shape == Shape::eCone)
   printf("Shape::Cone\n");

This is exactly what we were looking for all along!

Another advantage of scoped enums is that they cannot be implicitly converted to integers. This solves the enumerator value aliasing we described earlier and is enforced by the compiler.

Transitioning to Scoped Enums

Sauce is a fairly large code base: ~200K lines of code at the time of this writing. It took me a few days to convert 100+ unscoped enums to scoped enums. Due to the fact that I was manually scoping all of the enums, this is not a simple “search and replace” task. Additionally, I spent the extra time replacing includes with forward declarations, when appropriate.

Overall, I strongly believe that the time investment is well worth the time spent. The scoped enum syntax is natural, and the fact that they can be forward declared opens an opportunity to drop your header include count in some places. If you are considering the task of transitioning your legacy code base to scoped enums, I highly recommend it!

Articles

JSON Library

Early last month, I set out to add support for JSON into the engine. To my surprise, it turned out to be a fun and rewarding adventure.

JSON logo

JSON is a very nice format that is fairly easy to parse. Its feature set is small and well defined, including:

  • explicit values for null, true, and false
  • numbers (integers and floating-point)
  • strings
  • arrays
  • hash tables

This feature set is perfect for configuration files, stylesheets, etc. In the past, I have used XML for these sort of things, but JSON is much more direct and compact.

Initially, I reached for an external library to wrap, just as I have done for many of the other file formats, namely: PNG, XML, FBX, and OGG. Of course, when it comes to external libraries, your mileage will vary. For example, we use TinyXML 2, as the basis for our XML library; it was a real pleasure to use — a very straightforward, well designed interface. The FBX SDK, on the other hand, is pretty atrocious.

Unfortunately, I wasn’t very satisfied when it came to JSON. Many of the C++ JSON libraries out there make use of STL and/or Boost, dependencies we have striven to avoid. Eventually I settled on RapidJSON due to its high praise on the web; however, about half way through my wrapper implementation, I concluded that its interface is not as clean and “wrappable” as I had originally thought it to be.

After some reflection, I decided that the best way forward was to roll my own. I found that rolling your own is an excellent decision for a few reasons:

First, the JSON format is relatively small, unambiguous, and well documented. This allows you to focus on the architecture and interface of your wrapper. I found the experience both valuable and refreshing.

Second, you are able to employ the use of your native data structures. Naturally, this is a great way to test your functionality and interface. In the case of Sauce, I was able to leverage the following Core structures: String, Vector, Array, and HashMap.

Last, but not least, I found it to be a whole lot of fun! It’s been a while since I’ve done anything like implementing a format encoder and decoder. Hopefully when you’re finished, you feel the same.

After I finished our JSON library, I converted our config files from XML to JSON with very little effort. The result is that our config files are more compact than they were with XML, and now we have the utilities required for future development. Overall, I feel it was well worth the time and effort.

Articles

Streams Library

Overview

In Sauce, we have a small, tight Streams library to handle the input and output of data in a standardized manner. After all, a game engine isn’t very exciting without the ability to read in configuration and asset data.

We use a stream as our main abstraction for data that flows in and out of the engine. In the case of input, the engine doesn’t need to know the source of those bytes; they could be coming from a file, memory, or over the network. The same holds true for output data. This is an extremely important feature that we can exploit for a number of uses, including testing.

Also, it should be noted that a stream is not responsible for interpreting the data. It is only responsible for reading bytes from a source or writing bytes to a destination.

As you might expect, we have two top level interfaces: InputStream and OutputStream. We’ve seen code bases where these are merged into a single Stream class that can read and write; however, we prefer to keep the operations separate and simple. Each of these interfaces has a number of implementations as described below.

Input Streams

InputStreams

The primary function for an InputStream is to read bytes.

Also, we store the endianness of the stream. This is an important property of the stream for the code that interprets the data. If the stream and the host platform have different endians, the bytes need to be appropriately swapped after being read from the InputStream.

Our Streams library features three types of input streams:

  • File Input Stream
  • Memory Input Stream
  • Volatile Input Stream

File Input Stream

This is probably the first implementation of InputStream that comes to mind. The FileInputStream is an adaptor from our file system routines to open and read from a file to the InputStream interface.

As an optimization, we buffer the input from the file as read requests are made. However, this is an implementation detail that is not exposed in the class interface; we could just as well read directly from the file — the callsite shouldn’t know or care.

Memory Input Stream

The MemoryInputStream implements the InputStream interface for a block of memory. In our implementation, this block can be sourced from an array of bytes or a string.

This implementation in particular is extremely useful for mocking up data for tests. For example, instead of creating separate file for each JSON test, we can put the contents into a string and wrap that in a MemoryInputStream for processing.

Volatile Input Stream

Simply put, the VolatileInputStream is an InputStream implementation for an external block of memory.

For safety, the MemoryInputStream makes a copy of the source buffer. This is because in many cases, the lifetime of an InputStream may be unknown or exceed the lifetime of the source buffer.

Of course, in the cases when we do know the lifetime of the source buffer will not exceed the use of the InputStream, we can make direct use of the source buffer. This is the core principle behind the VolatileInputStream.

Output Streams

OutputStreams

The primary function for an OutputStream is to write bytes.

Also, just like in the InputStream, we store the endianness of the stream. This is an important property of the stream for the code that writes the data. If the stream and the host platform have different endians, the bytes need to be appropriately swapped before being written to the OutputStream.

Our Streams library features two types of output streams:

  • File Output Stream
  • Memory Output Stream

File Output Stream

Similar to the input version, a FileOutputStream is a wrapper around our file system routines to open and write to a file.

However, unlike the FileInputStream, we do not buffer the output.

Memory Output Stream

The MemoryOutputStream implements the OutputStream interface for a block of memory. The internal byte buffer grows as bytes are written.

For convenience, we added a method to fetch the buffer contents as a string.

Again, this is extremely useful for testing code like file writers.

Readers and Writers

Admittedly, the stream interfaces are very primitive. They are so primitive, in fact, that they can be a bit painful to use by themselves in practice. Consequently, we wrote a few helper classes to operate on a higher level than just bytes.

We’ve found this to have been an excellent choice. It is not unusual for a single stream to be passed around to more than one consumer or producer. Separating the data (stream) from the operator (reader/writer) provides us the flexibility needed and the opportunity to expose a more refined client interface.

Readers

For InputStreams, we implemented a BinaryStreamReader and a TextStreamReader.

The BinaryStreamReader can read bytes and interpret them into primitive data types, as well as a couple of our Core data types: strings and guids. We use this extensively for reading data from our proprietary file formats.

The TextStreamReader can read the stream character by character, or whole strings at a time. This makes it ideal for performing text processing tasks like decoding JSON.

Writers

For OutputStreams, we implemented a parallel pair of writers: BinaryStreamWriter and TextStreamWriter. In both, we perform the appropriate byte swapping internally when writing multi-byte data types.

The BinaryStreamWriter can take the same set of data types supported by the Reader and write their bytes to the given OutputStream.

The TextStreamWriter can write characters or strings to the given OutputStream.

Summary

The Sauce Streams library has been a vital component to our development. We use it to read in models, textures, and configuration files; and we use it to write out saved games and screenshots.

We hope that this high-level discussion will help our readers with designing their own set of stream classes.

Articles

Color Toolkit

This article was originally published on March 5, 2013 at Pulsar Engine.

It has been updated to employ the conventions we use in Sauce instead of the ones I had previously used in Pulsar — aside from that, the content remains unchanged. This article still reflects my views and code.

Background

I love color. In fact, one of my first posts I ever wrote for my developer website was based on setting up color printing for console output (which is super useful for distinguishing errors from normal informational output).

In my current code base, I have a whole library dedicated to Color. In this article, I’d like to share some code and insights for a few constructs I find really useful in everyday development.

RGB Color

Let’s start with the basics. Color32 is a simple 32-bit color structure with four 8-bit unsigned integer components: red (R), green (G), blue (B), alpha (A). Each of the components range from [0,255].

The class only has a small set of member functions for clamping, linear interpolation between two colors, etc. Also, a Color32 can be specified from four floats (range: [0,1]), though the component values are immediately converted to the byte representation.

Color-Space Conversions

RGB is so ubiquitous because it’s the color-space that rendering API calls expect for their color inputs. However, converting from RGB to other color-spaces (and back) is very important because some color operations are more natural in other color-spaces.

For the purpose of this article, we will concentrate on Hue-Saturation-Value (HSV).

HSV Color

HsvColor contains four float components: hue (H), saturation (S), value (v), alpha (A). Each of the components range from [0,1].

It is important to note that the HSV color-space is actually a cylinder, and the hue component is actually an angular value. I like to keep hue in the same [0,1] range as the other components, but that’s just a personal preference. Just be sure to convert your hue appropriately when implementing your RgbToHsv() and HsvToRgb() routines.

Furthermore, don’t be troubled that this object is a bit more heavyweight than the Color32. The main purpose for the HsvColor is to use it as a vehicle for color computation as opposed to storage.

Color Generator

Generating a good sequence of unique colors is not as trivial as it sounds. Using random number generators produces poor color sequences, and I didn’t want to limit myself to a hand-picked list of “good” colors. Instead I wanted to be able to generate a list of colors for an arbitrary size depending upon the requirements of the code. As a result, I found a couple of different articles on the subject (see References below) and implemented my own lightweight ColorGenerator class.

Internally, it uses the HSV color-space to generate a new unique color each time Generate() is called. The saturation and value components are kept constant during generation, while the hue is rotated around the HSV color cylinder using the golden ratio.

const float cInvGoldenRatio = 0.618033988749895f;

The Generate() routine below uses the cInvGoldenRatio constant as the hue increment.

Color32 Generate() const
{
   const float nextHue = mHsvColor.H + cInvGoldenRatio;
   mHsvColor.H = MathCore::Wrap(nextHue, 0.0f, 1.0f);
   return ColorOps::HsvToRgb(mHsvColor);
}

It’s important to note that the colors are not pre-generated and stored. Instead, I simply have a single HsvColor that stores the state of the generator between calls to Generate().

Color Palette

The ColorPalette class is a named container of colors. The array of colors is set on construction, and each individual color can be accessed via the bracket operator.

I call it a “palette” because it stores a fixed array of colors that are not assumed to be associated with each other in any particular way (order doesn’t matter, etc.). Although this class seems trivial, it serves as a basis for a couple really cool constructs.

Prefab Color Palettes

As a convenience, I have a set of ColorPalette creation routines (listed and respectively displayed in the image below).

  • Black and White.
  • Rainbow: Red, Orange, Yellow, Green, Cyan, Blue, Violet.
  • Monochrome: single color spectrum (more precisely: a spectrum from black to a single color).
  • Spectrum: a set of bands between two colors.
  • Pastels: a generated set of pastel colors. (h:0.0f, s:0.5f, v:0.95f)
  • Bolds: a generated set of saturated colors. (h:0.0f, s:0.9f, v:0.95f)

Color Ring

A ColorRing is a simple wrapper class that operates on a given ColorPalette, treating it like a circular list. Each time client code calls GetColor(), the current color is returned and the current color index is increased (wrapping back to 0 if it passes the last color).

This class useful when you have a group of items but want to limit their color choices to a certain set of colors (which may or may not be equal to the number of items): build a palette with your desired set of colors and then use a ColorRing when performing the color assignment.

Color Ramp

The ColorRamp class also operates on a given ColorPalette. It treats the ColorPalette as its own color subspace that can be accessed via a parametric value in the range of [0,1]. In other words, when client code wants a color from the ColorRamp, they must provide a parametric value which is then mapped into the ColorPalette.

Additionally, my implementation includes a RampType flag that indicates whether it will behave as a gradient or whether it will round (up or down) to the nearest neighboring color in the palette.

The Evaluate() routine uses the given parametric value to find the two nearest colors, and then computes a resulting color based on the aforementioned RampType flag. In the case of the gradient, the colors are linearly interpolated with the parametric value remainder; while the other two behaviors simply round to one color or the other based on the parametric value remainder.

Color32 Evaluate(const float parametricValue) const
{
   if (parametricValue <= 0.0f)
   {
      return mColorPalette[0];
   }

   if (parametricValue >= 1.0f)
   {
      return mColorPalette[mColorPalette.Count-1];
   }

   const float cValue = parametricValue * (mColorPalette.Count - 1);

   const int idxA = (int)MathCore::Floorf(cValue);
   const int idxB = idxA + 1;

   switch (mRampType)
   {
      case RampTypeId::eGradient:
         {
            const float fracBetween = cValue - (float)idxA;
            const Color32& colorA = mColorPalette[idxA];
            const Color32& colorB = mColorPalette[idxB];
            return Color32::Lerp(colorA, colorB, fracBetween);
         }

      case RampTypeId::eRoundDown:
         return mColorPalette[idxA];

      case RampTypeId::eRoundUp:
         return mColorPalette[idxB];

      default:
         SE_ASSERT(false);
         break;
   }

   // should never get here
   return Color32::eBlack;
}

Here’s what it looks like when we create a corresponding gradient ColorRamp for each of the palettes shown above:

Initially, I wrote the ColorRamp class to help with assigning color values to vertices in a height field, but since then I have found several other interesting applications for it.

Final Thoughts

While I concentrated on exhibiting a few of the core classes in my Color library at a high level, it should be pretty clear that there are a lot of possibilities when it comes to Color. You can find more in-depth information, gritty details, and sample code in the references provided below. I highly encourage you to read them even if you’re only the slightest bit interested — they are well worth your time.

References

Articles

Unit Testing Ambiguity

This article was originally published on September 25, 2010 at Pulsar Engine.

It has been updated to employ the conventions we use in Sauce instead of the ones I had previously used in Pulsar — aside from that, the content remains unchanged. This article still reflects my views and code.

Background

This post is related to the previous post on testing a return value that consists of a set of items with no predefined order (see Unit Testing Unordered Lists)[1]. However, it differs in that this time the problem is a little more mathematical in nature: how do we properly test a routine that performs an operation that may have multiple correct solutions?

For those of you who have written core math routines and solvers before, you know exactly what I’m referring to, but even if you haven’t I still encourage you to continue reading. I’ve chosen a relatively simple, common, yet important example to work through — there’s a good chance you’ll make use of this knowledge somewhere.

Unit Testing Ambiguity

There have been times when I’ve found myself trying to impose unrealistic expectations on my routines. Of course, when I test for them, I end up with failed tests and my first thought is more often than not: the code being tested must be wrong. However, the reality is that I have actually written a bad test.

A good example of this happened to me when I was working on my ComputeOrthoVectors() routine[2]. The purpose of the function is: given a single Vector3, compute two additional Vector3s which form an orthonormal basis with the input Vector3. So, I wrote the following test:

TEST(CanComputeOrthoBasisVectors)
{
   Vector3 vecA;
   Vector3 vecB;
   ComputeOrthoBasisVectors(vecA, vecB, Vector3::UNIT_X);

   CHECK_ARRAY_CLOSE(Vector3::UNIT_Y, vecA, 3, EPSILON);
   CHECK_ARRAY_CLOSE(Vector3::UNIT_Z, vecB, 3, EPSILON);
}

The primary issue here is that the operation itself is soaked in ambiguity. More specifically, the two Vector3s that make up the return value can be produced by one of many valid solutions. To see this, let’s look at the math required for the implementation.

Computing an Orthonormal Basis

First, let’s be clear on the terminology: a set of three Vector3s that are each perpendicular to the other two is called an orthogonal basis. If we normalize the vectors in the set, we can call it an orthonormal basis. In other words: A 3D orthonormal basis is a set of three vectors that are each perpendicular to the other two and each of unit length.

The need for creating an orthonormal basis from a single vector is a fairly common operation (probably the most common usage is in constructing a camera matrix given a “look-at” vector).

Given two non-coincident[3] vectors, we can use the cross product to find a third vector that is perpendicular to both the input vectors. This is often why we say that two non-coincident vectors span a plane, because it is from these two vectors that we can compute the normal to that plane.

The thing to note here is that there are an infinite number of valid non-coincident vectors that span a plane. You can imagine grabbing the normal vector as if it were a rod connected to two other rods (the input vectors) and spinning it; any orientation you spin it to is a valid configuration that would produce the same normal vector. I have created an animation demonstrating this below:

Animation of two vectors orthogonal to input vector. The two vectors remain in the plane defined by the input vector (the plane normal).

In essence, this is why the results of the operation are valid, yet, for the lack of a better word, ambiguous. In the case of our routine, we are supplying the normal and computing two other vectors that span the plane. The fact that the two returned vectors are orthogonal to the input vector does not change the fact that there are an infinite number of configurations.

Testing the Geometry, Not the Values

Returning to the original testing dilemma, since there are an infinite number of possible solutions for our returned pair of Vector3s, if we write tests that check the values of those vectors, then our tests will be bound to the implementation. The result is a ticking time-bomb that may explode in our face later on (maybe during an optimization pass) because, although we may change the pair of vectors returned for a given input, the three vectors still form an orthonormal basis — the correct and desired result — in spite of the fact that we now have failing tests.

My solution was to check the following geometric properties:

  1. All three vectors are perpendicular to each other (in other words, they form an orthogonal basis).
  2. The two returned vectors are of unit length (input vector is assumed to be normalized).

The following are a few tests (straight from my codebase) that employ this approach:

TEST(CanComputeOrthoBasisVectors_UnitX)
{
   Vector3 vecA;
   Vector3 vecB;
   ComputeOrthoBasisVectors(vecA, vecB, Vector3::UNIT_X);

   CHECK_CLOSE(0.0f, vecA.Dot(vecB), EPSILON);
   CHECK_CLOSE(0.0f, vecA.Dot(Vector3::UNIT_X), EPSILON);
   CHECK_CLOSE(0.0f, vecB.Dot(Vector3::UNIT_X), EPSILON);
   CHECK_CLOSE(1.0f, vecA.Mag(), EPSILON);
   CHECK_CLOSE(1.0f, vecB.Mag(), EPSILON);
}


TEST(CanComputeOrthoBasisVectors_UnitY)
{
   Vector3 vecA;
   Vector3 vecB;
   ComputeOrthoBasisVectors(vecA, vecB, Vector3::UNIT_Y);

   CHECK_CLOSE(0.0f, vecA.Dot(vecB), EPSILON);
   CHECK_CLOSE(0.0f, vecA.Dot(Vector3::UNIT_Y), EPSILON);
   CHECK_CLOSE(0.0f, vecB.Dot(Vector3::UNIT_Y), EPSILON);
   CHECK_CLOSE(1.0f, vecA.Mag(), EPSILON);
   CHECK_CLOSE(1.0f, vecB.Mag(), EPSILON);
}


TEST(CanComputeOrthoBasisVectors_UnitZ)
{
   Vector3 vecA;
   Vector3 vecB;
   ComputeOrthoBasisVectors(vecA, vecB, Vector3::UNIT_Z);

   CHECK_CLOSE(0.0f, vecA.Dot(vecB), EPSILON);
   CHECK_CLOSE(0.0f, vecA.Dot(Vector3::UNIT_Z), EPSILON);
   CHECK_CLOSE(0.0f, vecB.Dot(Vector3::UNIT_Z), EPSILON);
   CHECK_CLOSE(1.0f, vecA.Mag(), EPSILON);
   CHECK_CLOSE(1.0f, vecB.Mag(), EPSILON);
}


TEST(CanComputeOrthoBasisVectors_RefPaperExample)
{
   Vector3 vecA;
   Vector3 vecB;
   const Vector3 unitAxis(-0.285714f, 0.857143f, 0.428571f);
   ComputeOrthoBasisVectors(vecA, vecB, unitAxis);

   CHECK_CLOSE(0.0f, vecA.Dot(vecB), EPSILON);
   CHECK_CLOSE(0.0f, vecA.Dot(unitAxis), EPSILON);
   CHECK_CLOSE(0.0f, vecB.Dot(unitAxis), EPSILON);
   CHECK_CLOSE(1.0f, vecA.Mag(), EPSILON);
   CHECK_CLOSE(1.0f, vecB.Mag(), EPSILON);
}

By testing these properties, as opposed to testing for the resulting vector values directly (as in the original test shown above), it doesn’t matter how the internals of the ComputeOrthoBasisVectors() produces the two returned Vector3s. As long as the input vector and the returned vectors all form an orthonormal basis, our tests will pass.

Final Thoughts

My hope is that the example presented in this article demonstrates one of the pitfalls of having tests that depend on the internal implementation of the routine being tested. As I have stated before, although it is important to write tests for the functionality, it can be difficult to recognize when a test is bound to the implementation.

A good place to start looking for this sort of scenario is in tests that explicitly check return values. Certainly, explicit checks is actually what you want in most cases, but for some operations it is not.

Footnotes

  1. Originally, these two topics were going to be addressed in a single article, but I decided against it in hopes that keeping them separate would allow for more clarity in each.
  2. In fact, the trouble I had in testing the ComputeOrthoVectors() routine is what inspired me to post both this article and the last.
  3. Two vectors are said to be coincident if they have the same direction when you discard their magnitudes. In other words, two vectors are coincident if you normalize both of them and the results are the same.

References

  • Möller, Tomas and John F. Hughes. Building an Orthonormal Basis from a Unit Vector. [ pdf ]
Articles

Unit Testing Unordered Lists

This article was originally published on August 31, 2010 at Pulsar Engine.

It has been updated to employ the conventions we use in Sauce instead of the ones I had previously used in Pulsar — aside from that, the content remains unchanged. This article still reflects my views and code.

Background

If you’ve read just about any of my earlier posts, you know that I write tests for Sauce. This includes unit tests, functional tests, and performance tests, all in addition to the demo / visual tester applications that I usually post my screenshots from. The details on the structure to my codebase are probably worth outlining in a future post, but in this post now I’m going to focus in on the unit tests.

Implementation Note: I use UnitTest++ as my test harness. It is simple, lightweight, and quick to integrate into a codebase. If you don’t have a testing framework setup for your codebase yet, I highly recommend UnitTest++.

Unit Testing Unordered Lists

Every once in a while (primarily in my Geometry / Collision Detection library), I have run into the need for unordered lists in my test suite. In fact, it has come up often enough that I decided to share some thoughts and my solution here.

Although I’m going to explain this issue through a somewhat contrived example, I chose it because the premise is easy to understand and visualize; certainly this could be extended to other, more complex cases.

Let’s say you have the following Rectangle class that represents an 2D axis-aligned box:

class Rectangle
{
public:
   Vector2 mMin;
   Vector2 mMax;
};

Next, say we are writing a ComputeCorners() member function. As you probably guessed, this routine needs to return four Vector2s that are the coordinates of each of the corners on the Rectangle. This can be done in one of the following two flavors:

  • add a struct with four Vector2s, each with sensible member names
  • use an array: Vector2[4]

If your calling code requires explicit knowledge that maps each returned point to its corresponding corner on the Rectangle, you would probably choose to use the first option.

However, let’s assume that all we actually need are the points themselves and we don’t really care which point is which (maybe we’re just going to insert them into some larger list of points that will be processed, or whatever). Using the array approach, our test code might look something like this:

TEST(CanComputeCorners)
{
   Rectangle rect;
   rect.mMin.Set(1.2f, 1.4f);
   rect.mMax.Set(2.5f, 1.7f);
  
   Vector2 corners[4];
   rect.ComputeCorners(corners);
  
   CHECK_EQUAL(Vector2(1.2f, 1.4f), corners[0]);
   CHECK_EQUAL(Vector2(2.5f, 1.4f), corners[1]);
   CHECK_EQUAL(Vector2(1.2f, 1.7f), corners[2]);
   CHECK_EQUAL(Vector2(2.5f, 1.7f), corners[3]);
}

Without sweating the details of testing against an epsilon, this test looks pretty good at first glance, and it probably succeeds without trouble.

However, there is a subtle problem here: our test is assuming that there is a specific order to the points being returned. Nothing in our function dictates that we absolutely have to return the points in that order, but because of the way we have written our test any change to the order of the returned points in the implementation will result in a failing test.

So how exactly can we test this routine (and others like it) properly? In other words, how can we write our test to be order-independent?

My solution (as straightforward as it may be) was to implement a testing helper routine:

bool ArrayContainsItem(
   const Vector2* itemArray, const uint itemCount,
   const Vector2& itemToFind)
{
   for(uint idx = 0; idx < itemCount; ++idx)
   {
      const Vector2& curItem = itemArray[idx];
      if(curItem == itemToFind)
      {
         return true;
      }
   }
  
   return false;
}


TEST(CanComputeCorners)
{
   Rectangle rect;
   rect.mMin.Set(1.2f, 1.4f);
   rect.mMax.Set(2.5f, 1.7f);
  
   Vector2 corners[4];
   rect.ComputeCorners(corners);
  
   CHECK(ArrayContainsItem(corners, 4, Vector2(1.2f, 1.4f));
   CHECK(ArrayContainsItem(corners, 4, Vector2(2.5f, 1.4f));
   CHECK(ArrayContainsItem(corners, 4, Vector2(1.2f, 1.7f));
   CHECK(ArrayContainsItem(corners, 4, Vector2(2.5f, 1.7f));
}

Notice that this routine is intended for the purposes of simplifying the test and resides with the testing code, not packaged up with the library itself. It is perfectly acceptable to have to perform additional setup (mock objects, etc.) or implement a helper or two for testing.

Also, you could certainly generalize this unit test helper routine a little so it can be used in other unordered list instances — I’ve found many uses for my own implementation while testing Sauce libraries.

Final Thoughts

The real take away from this actually isn’t about how to test an unordered set of objects; in fact, I think the lesson is much bigger and important: be careful to write tests for the functionality, not for the implementation.

This key point to this lesson is subtle and sometimes easy to miss / hard to catch.

To be clear, functionality is what the routine does that can be inspected from the outside view of the object, or, in the case of a non-member (“free”) function, from the return value. On the other hand, implementation is much more tightly bound to the code itself (the internal process of a routine) and how it operates on an object or data.

In the example case above, we saw that the interface did not specify an ordering for the list of returned corner coordinates, yet our initial test definitively expected an ordering which happened to be based on our knowledge of the implementation.

I’ll be the first to admit that it isn’t always clear when implementation details have crept into the tests — this has happened to me a lot more often than I care to reveal (especially while practicing Test-Driven Development).

In closing, I believe that the first line of defense against this problem is to simply be aware that it can show up when testing container return values. As a result, I encourage you to take some additional time to make sure that the tests really are testing the functionality and not the implementation.

Articles

Reading PNG Images from Memory

This article was originally published on January 14, 2009 at Pulsar Engine.

It has been updated to employ the conventions we use in Sauce instead of the ones I had previously used in Pulsar — aside from that, the content remains unchanged. This article still reflects my views and code.

As far as I can tell most everyone is interested in reading PNG image data from file (internally done in libpng via fread()). I thought: “Wow, that’s quite unfortunate.” and figured I’d write about it after I figured it out. The article below is the result.

NOTE: the intent of this article is to help you get something up and running quickly. By design, it does not provide detailed explanations about the functions or interface of libpng — that’s what the documentation is for.

Motivation

There are several reasons why one might want to have data read from memory rather than directly from a file.

Testing – This was the first reason that came to my mind. In the Sauce engine codebase, I want to test my format data loaders, which includes anything from textures and models to config files and scripts. More on this later.

Archives – If you pack a “file” into a custom archive, do you expect you want to hand a third-party library your file pointer? …

IO Performance – File IO has never been instant, and it can be worse depending upon the platform. As a result, you’re usually better off if you read in a file in its entirety as opposed to only reading a small chunk at a time, since the device may have seeked to somewhere else in between your reads.

Scenario in Sauce

I have abstracted the operation of reading into an InputStream interface so that the source of the data (file, buffer in memory, network, or whatever) can be swapped out without affecting the behavior of the loader classes.

The function signature looks like this:

size_t InputStream::Read(byte* dest, const size_t byteCount);

You will see this used as the main data pipe in the next section.

Implementation

I will assume you have already set the include and library dependencies for libpng. The libpng documentation is pretty clear about this topic, so I won’t delve into it here.

I should also note that the code provided below is practical and is taken from a module in my codebase. It includes a basic amount of error checking, but I stripped the rest of it out for clarity sake. As such, I recommend that you use this as a starting point.

You will undoubtedly have to switch out the calls to sauce::InputStream::Read() and replace with them your own data source’s read interface.

Lastly, I have typedefed a few basic data types in my engine. For example: byte is typedefed as an unsigned char.

Setup

First, we check if the data has the PNG signature, which is held in the first 8 bytes of the image data. If libpng determines that the signature is invalid, we bail.

constexpr size_t kPngSignatureLength = 8;
byte pngSignature[kPngSignatureLength];

// call to sauce::InputStream::Read()
// -> replace with your own data source's read interface
inputStream.Read(pngSignature, kPngSignatureLength);

if(!png_check_sig(pngSignature, kPngSignatureLength))
{
   return false;
}

Next, we need to create a pair of file info structures. For future compatibility reasons, libpng must allocate and free the memory for these structures. If either one of these calls fail, we perform the necessary cleanup and bail.

// get PNG file info struct (memory is allocated by libpng)
png_structp png_ptr = NULL;
png_ptr = png_create_read_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);

if(png_ptr == NULL)
{
   return false;
}

// get PNG image data info struct (memory is allocated by libpng)
png_infop info_ptr = NULL;
info_ptr = png_create_info_struct(png_ptr);

if(info_ptr == NULL)
{
   // libpng must free file info struct memory before we bail
   png_destroy_read_struct(&png_ptr, NULL, NULL);
   return false;
}

This is where the magic happens. Now we must tell libpng to use a our own custom routine for retrieving the image data. To do this, we use the png_set_read_fn() routine:

png_set_read_fn(png_ptr, &inputStream, ReadDataFromInputStream);

The first parameter is the pointer to the first struct we asked libpng to create for us: png_ptr.

The second parameter is a void pointer to the data source object. In this case, the data source my InputStream object.

The final parameter is a pointer to a function that will handle copying the data from the data source object into a given byte buffer. Here, my reader function is called ReadDataFromInputStream(). This routine must have the following function signature:

void ReadDataFromInputStream(png_structp png_ptr, png_bytep outBytes,
   png_size_t byteCountToRead);

Now that we have told libpng where to go when it needs to read bytes, we need to implement that routine. Mine looks like this:

void ReadDataFromInputStream(png_structp png_ptr, png_bytep outBytes,
   png_size_t byteCountToRead)
{
   png_voidp io_ptr = png_get_io_ptr(png_ptr);
   if(io_ptr == NULL)
   {
      return;   // add custom error handling here
   }

   // using pulsar::InputStream
   // -> replace with your own data source interface
   InputStream& inputStream = *(InputStream*)io_ptr;
   const size_t bytesRead = inputStream.Read(
      (byte*)outBytes,
      (size_t)byteCountToRead);

   if((png_size_t)bytesRead != byteCount)
   {
      return;   // add custom error handling here
   }
}

The last piece of setup we need to do is tell libpng that we have already read the first 8 bytes when we checked the signature at the beginning.

// tell libpng we already read the signature
png_set_sig_bytes(png_ptr, kPngSignatureLength);

PNG Header

Now we are ready to read the PNG header info from the data stream. There is a lot of data one could extract from this, but here I’m only going to grab a few important values. Refer to the libpng documentation for more details on this function.

png_read_info(png_ptr, info_ptr);

png_uint_32 width = 0;
png_uint_32 height = 0;
int bitDepth = 0;
int colorType = -1;
png_uint_32 retval = png_get_IHDR(png_ptr, info_ptr,
   &width,
   &height,
   &bitDepth,
   &colorType,
   NULL, NULL, NULL);

if(retval != 1)
{
   return false;	// add error handling and cleanup
}

The width and height parameters are the image dimensions in pixels.

The bitDepth is the number of bits per channel. It is important to note that this is not per pixel (which is what is normally the value stored in a TGA or BMP).

The final parameter we care about is colorType which is an integer that maps to one of the predefined values in libpng that describe the image data (RGB, RGBA, etc). You will need this to determine how many channels you need to read from the bytes into your pixel color.

PNG Image Data

We have reached the point where we can now read in the image data into our internal image pixels.

outImage.Init(width, height);

switch(colorType)
{
   case PNG_COLOR_TYPE_RGB:
      ParseRGB(outImage, png_ptr, info_ptr);
      break;

   case PNG_COLOR_TYPE_RGB_ALPHA:
      ParseRGBA(outImage, png_ptr, info_ptr);
      break;

   default:
      SE_ASSERT_MSG(false, "Invalid PNG ColorType enum value given.\n");
      png_destroy_read_struct(&png_ptr, &info_ptr, NULL);
      return false;
}

First, I initialize my internal image format, which allocates the appropriate memory for the pixels — each of which is a Color32 (red, green, blue, alpha).

The switch is to differentiate my parsing routines (one of which is listed below) based on the colorType value we retrieved from the header.

To parse the data into pixel colors all we have to do is grab each row from the image and proceed to read each tuple of bytes that represents a pixel. The number of bytes we read is dependent upon the data stored, which is why we differentiate between parsing a 24-bit (RGB) color value and a 32-bit (RGBA) color value via colorType.

I have provided the ParseRGBA() routine below. The ParseRGB() is very similar except no bytes are read for the alpha channel.

void ParseRGBA(Image& outImage, const png_structp& png_ptr,
   const png_infop& info_ptr)
{
   const u32 width = outImage.GetWidth();
   const u32 height = outImage.GetHeight();

   const png_uint_32 bytesPerRow = png_get_rowbytes(png_ptr, info_ptr);
   byte* rowData = new byte[bytesPerRow];

   // read single row at a time
   for(u32 rowIdx = 0; rowIdx < height; ++rowIdx)
   {
      png_read_row(png_ptr, (png_bytep)rowData, NULL);

      const u32 rowOffset = rowIdx * width;

      u32 byteIndex = 0;
      for(u32 colIdx = 0; colIdx < width; ++colIdx)
      {
         const u8 red   = rowData[byteIndex++];
         const u8 green = rowData[byteIndex++];
         const u8 blue  = rowData[byteIndex++];
         const u8 alpha = rowData[byteIndex++];

         const u32 targetPixelIndex = rowOffset + colIdx;
         outImage.SetPixel(targetPixelIndex, Color32(red, green, blue, alpha));
      }
      SE_ASSERT(byteIndex == bytesPerRow);
   }

   delete [] rowData;
}

Cleanup

Finally, now that the image data has been read we should clean up the libpng structures, then we can be on our merry way!

png_destroy_read_struct(&png_ptr, &info_ptr, NULL);

That’s it! Now we can go do whatever we need to with the image data we just read in!

Conclusion

Here I’ve only touched on the basics. This seemingly simple task was practically nowhere to be found when I searched for it, resulting in me having to piece it together. Hopefully this will same someone else some time.

Resources

Articles

Image Library Resources

This article was originally published on January 5, 2009 at Pulsar Engine.

It has been updated to employ the conventions we use in Sauce instead of the ones I had previously used in Pulsar — aside from that, the content remains unchanged. This article still reflects my views and code.

I have compiled a listing of resources I used while implementing my Image library. This will be updated as things progress.

TARGA File Format

Extension tga
Endian Little Endian

Resources:

Bitmap File Format

Extension bmp
Endian Little Endian

Resources:

PNG File Format

Extension png

Resources:

DXT File Formats

Extension dds
Endian Little Endian
Data Compression Lossy

Resources:

Tools:

Book Reviews

Book Review: Data Structures and Algorithms for Game Developers

This article was originally published on December 5, 2008 at Pulsar Engine.

Data Structures and Algorithms for Game Programmers

Data Structures and Algorithms for Game Developers

Allen Sherrod

Thoughts Overall

Overall, I thought DSAGD was a worthwhile book. I can honestly say that I had fun reading through the basics again and coding up the data structure(s) with each chapter. It has been a good 7+ years since I have written any of the data structures covered in this book, and (as some people know) sorting has never been one of my strengths.

That said, there were also some technicalities about this book (mostly mechanical) that stick out like a sore thumb, which makes me disappointed because I think that they could have all been avoided had someone (not the author in particular) actually taken the time to sit down, read, and give the content a proper editing pass.

Do I Recommend this Book?

I’m usually pretty decisive on this issue, but in this case I’m actually a little bit ambivalent on whether I would recommend this book or not. I will say that DSAGD is not a book I would recommend everyone to read — it certainly depends on the programming level of the person in question.

If they are weak in the areas of (or have just started learning) data structures and sorting, then I think this book is perfect for them. In other words, I would have loved to have this book when I was in CSE 12 back in Spring of 2001 because it makes a point to explain things clearly. It also doesn’t hold your hand in terms of C++ like some other books I have on my book shelf; it just jumps straight into the details about what you need to know about the data structures themselves. I appreciated these aspects of the book a lot throughout the read.

However, I would not recommend this book to a seasoned programmer who is simply looking for a refresher in these topics. I recommend that they should turn to a more solid source (maybe Algorithms in C++ by Robert Sedgewick), as this book will leave them wanting.

Pros

As I mentioned earlier, DSAGD does a good job of staying on track when it comes to what you need to know about fundamental data structures and sorting algorithms.

Here is a list of the data structures covered:

  • Array
    • Unordered Array
    • Ordered Array
    • Bit Array
  • Linked List
    • Singly-Linked List
    • Double-Ended Link List
    • Doubly-Linked List
  • Stack
  • Queue
  • Deque
  • Hash Table
    • Open-Addressing
      • Linear Probing
      • Quadric Probing
      • Double Hashing
    • Separate Chaining
  • Binary Tree
  • kd Tree
  • Heap
  • Priority Queue
  • Graph

Here is a list of the algorithms covered:

  • Sorting
    • Bubble Sort
    • Insertion Sort
    • Selection Sort
    • Merge Sort
    • Shell Sort
    • QuickSort
    • Radix Sort
  • Compression
    • Run-Length Encoding (RLE)
    • Huffman Coding
  • Misc
    • Partitioning

Everything listed above is explained well and has a corresponding implementation. Most of these implementations are fully fleshed out… my main complaint is that the kd-tree is lacking in a couple of important features (such as a Remove() routine).

DSAGD also has a decent amount of examples of when to use certain data structures and sorting algorithms over others. Seeing how this is just as (if not more) important than knowing how to implement them on your own, I could put this point in either the Pros or Cons section, but I’m feeling generous here because I did in fact feel more confident about my stance on data structure usage after finishing DSAGD.

Also, I was pleasantly surprised to see that DXT compressions were covered in the final chapter. I’ve never spent much time in graphics-land, so while I had a basic idea of the differences across the formats nothing was particularly solid — this part of the book was certainly helpful.

Another unexpected surprise that I was happy to see was the provision of a fully functional, platform-independent implementation of a DDS (DirectDraw Surface) file loader (pg 502-509).

Cons

No book is perfect. It is excusable to see a typo or two. But in this book there were enough spelling and grammar errors that it became noticeable… and that’s when it started to distract from the reading.

I also think that this book could have either been 100 pages shorter, or have 100 more pages worth of examples, data structures, and algorithm implementations (like a SkipList or a Remove() routine for the kd-tree!). I make this claim based on the fact that there were places where the code was simply reprinted — for no good reason. I can understand when an author wants to explain things in-line with the code; so they print the implementation and then write a few paragraphs of explanation. I can also understand the benefit of having the entire class printed in completion after the routines and member variables and any miscellaneous assumptions have been explained. But it does not make sense to do both — please pick one or the other! Again, like the textual errors mentioned above, if it had happened only once or twice, I could see it being because there was reasoning behind it; but after the third time I seriously started to get the feeling the author was simply trying to fill space.

I’m tired of books printing listings of the signatures of STL routines… and on top of that, getting them wrong. Yes, DSAGD talks about the STL in addition to the custom implementations listed earlier. At this point in the article, it should be apparent which I am more interested in… it’s why I bought the book in the first place! If you’re looking for a games-oriented view on the STL, check out chapters 8 and 9 in C++ for Game Programmers for a solid, well-written discussion. I own a couple books that focus exclusively on the STL, including: The C++ Standard Library: A Tutorial and Reference and Meyer’s Effective STL, and there are many more books dedicated to explaining the STL in detail out there, so I highly recommend going to one of those before thinking of using DSAGD as an STL reference.

My final complaint was the glossing over of scene-management topics at the end of the book. Granted, this was not what this book was about, and I still have yet to read a really good book on the subject of scene-management, but I felt like I had been taunted after I had finished reading that chapter. Sherrod prints a full implementation of a Vector3d class when he could have at least spent some more time talking about the QuadTree and Octree… or better yet: explaining a concrete implementation! Surely these spatial data structures aren’t difficult to implement on my own but I’m still wondering why he took a step backwards to print the Vector3d code… this is a data structures book, not a math primer.

Final Word

Despite the aforementioned shortcomings, I think DSAGD handles the subject of the fundamental data structures and sorting algorithms very well. The book has a lot of potential and deserves a second edition to clean up the mechanical errors. In the meantime, just be prepared to skip multiple pages at a time when he reprints code, and don’t get your expectations up too high about the content of the final four chapters.