Category Archives: Unit Testing

Unit Testing Ambiguity

Posted on by

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, 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, 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, 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, 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, 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 ]

Unit Testing Unordered Lists

Posted on by

Background

If you’ve read just about any of my earlier posts, you know that I write tests for Pulsar. 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 Pulsar 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.