If size and speed are really important, you might want to forego some of the notational niceties made possible with C++ and just concentrate on the basics.
Introduction
This article describes a simple yet powerful vector class tnVector (for Templatized Numerical Vector) that is appropriate as a low-level representation for numerical arrays whose dimensions are known at compile time. tnVector is most useful for describing points and directions in 2-D and 3-D (and occasionally 4-D or 5-D) Euclidean spaces, but can be used whenever the dimension is known beforehand by the developer. tnVector is not appropriate as a general numerical vector class, as would be needed to solve linear algebra problems over arbitrary vector spaces.
The vector library is based on a simple idea. Any C++ object representing a mathematical vector, geometric point, or direction must be at least as efficient in most cases as a C-style numerical array. The advantage of using C++ should lie in easier and less error prone coding. This requirement may appear simple and perhaps self evident, yet most vector classes do not adhere to this rule. Instead, implementations often attempt to mimic classical mathematical notation for vectors without due regard for performance and clarity.
Furthermore, the approach presented in this article supports vectors of any fixed dimension, not just two or three. Dimension safety is enforced through templates, though this feature is optional within the scheme and can be removed by wary users if desired.
Overview
The most difficult decisions made while designing the tnVector class typically involved assignment. How do you encapsulate operations between two vectors that have a vector-valued result? The simplest example is the sum of two vectors. How should we add two vectors? Many different schemes have been in use since the beginnings of C++ (such as in the RogueWave Math.h++ library.) Though elegant and suitable for linear algebra computation over large-dimensional vector spaces, most approaches are inefficient and wasteful for geometric computations.
Take as an example the implementation of wastefulVec given in Figure 1. Two vectors, a and b, are combined to form sum and difference vectors. The notation at first glance appears elegant and simple, but it really isn't. The binary arithmetic operator constructs a temporary vector to receive the result of the addition. Then the temporary vector is copied by the compiler-generated assignment operator into its final destination, after which the temporary vector is destroyed. Whew! Is this convoluted behavior really necessary to add two vectors? Moreover, it's disturbing that this complicated action is hidden behind such disarming syntax.
Although this approach is quite common and can even be found in many commercially available numerical libraries, it requires the constructor to be called every time two vectors are added. Not only are superfluous function calls introduced as a matter of course but more memory is required than is actually needed. In the second example, the code used to subtract a and b eliminates the extra copies and constructions, but does not provide adequate flexibility. What if the destination vector for the difference already exists? operator-(const wastefulVec&) isn't sufficient.
The same considerations apply to all operations that conceptually "return" a vector value. Many will argue that a good optimizing compiler should fix these problems so that what really happens, for instance, is that a and b are summed, element-wise, with the result stored in sum. That may be the case, but maybe not. In a piece of code where speed is critical, do you really trust that the compiler is doing the right thing? Why not just design the class to implement the desired behavior directly, rather than through tricks and features of the language?
The reason this above syntax is so popular is probably due to an unwitting attempt to mimic mathematical notation. Instead of adhering to a mathematical notation that was developed over one hundred years ago for pencil-and-paper computations, let us start anew and design a vector library that takes the realities of the digital processor — memory and speed — as well as notational convenience and utility into consideration.
Design
The tnVector class is designed with several goals in mind:
Minimal Memory
In most applications, vectors are the next conceptual step beyond the built-in types. Therefore, any robust vector class should minimize its memory storage. Even an extra byte (or bit!) can cause problems. As a corollary, the vector class does no memory management, but rather relies on the user to handle all space issues. Additionally, the vector elements should be contiguous in memory. There are many occasions where third-party software (OpenGL leaps to mind) can make better use of sequential values.
Fast Performance
Most applications are built on top of the vector class, so speed is paramount. The elimination of even one extra function call can often dramatically impact performance. To achieve this design goal, I have chosen to implement the vector class completely within the header file. There is no source file. All functions and operators are inline and should not require any extra overhead. Also, the tnVector class is "flat." It does not make use of C++ polymorphism because of the storage and function call overhead.
Type/Dimension Safety
The virtues of C++ for type safety have long been extolled. However, for geometric entities dimension safety is even more important. "Dimension safety" in this context means using the compiler to make sure that our dimensions check out. All the arguments for checking types at compile time are directly applicable to checking dimensions as well. For instance, adding a 2-D vector to a 3-D vector should be immediately flagged as an invalid operation. If you put 2-D and 3-D (perhaps even 4-D or 5-D) vectors in a single class, then the compiler cannot check dimensions for you.
Deferring this dimension check to run time, although popular, leads to two problems:
1. Extra code must be generated to perform the check, with commensurate memory and speed penalties.
2. You cannot guarantee when a run-time bug will be caught.
It's bad if the offending line of code is missed during testing and is first found by the customer. Instead, if the compiler does the work, you can be sure that all dimension incompatibilities have been found. Having separate classes for each dimension is the best way to keep the order. With one class per dimension, the compiler does all the work!
Note that there is no real penalty for having three (or four, or more) classes accomplishing essentially the same tasks, because there really isn't any code. All member functions are defined in the header and should expand inline with no code bloat or function overhead. As I describe below, templates provide one practical strategy for reducing the coding burden.
Simplicity
tnVector is designed to be as simple as possible. Inheritance is kept to a minimum, and there are no typedefs, enumerations, or virtual functions. Global functions and operators are avoided, along with any use of the STL. In fact, the only header file needed is <math.h>, just for a few mathematical functions like sqrt. I've included a simple interface to the iostream library as well. My compiler supports only the old-style <iostream.h> header file. You can easily upgrade the code, however, to use the new-style <iostream> header, if necessary.
Using Templates
The design specifications for the vector class require a unique class for each spatial dimension of interest. There are two drawbacks to writing code for each class that is needed. Physically writing a class for each dimension is time consuming, and the inevitable cutting and pasting may lead to errors. But more likely is the possibility that someday you'll need a vector of some other dimension. For instance, in one application I needed a 16-dimensional vector to represent the components of a 4x4 homogeneous transform. I certainly had no desire to delve back into the code for the vector class to replicate it for dimension 16. An alternative was necessary.
A better approach takes advantage of a little-used feature of templates. Most template applications templatize on class (or type), but it is also possible to define a template with a numeric parameter. You use an ordinary scalar type to define the template parameter. Each distinct value of the corresponding argument leads to a different specialization of the template. (See Bjarne Stroustrup, The C++ Programming Language, 3rd ed. section 13.2.3. for a more detailed explanation.)
In our case, the vector class is templatized on values of int. Implementing tnVector as a single templatized class drastically reduces the amount of code and also improves the clarity of what is written. As long as the dimension is known at compile time, templates are a good solution.
I advocate templates with a word of caution. The basic idea is to use templates in order to simplify the coding burden without any performance penalty at execution. However, templates are a newcomer to software development, and many bugs still remain with the concept. Many compilers do not yet fully and properly handle templates, and much confusion results when it is not clear how or when a given templatized function should be instantiated.
The tnVector class attempts to avoid most of the problems associated with templates in the following manner. The constructor, functions, and operators are all defined in the header file, and are therefore candidates for inlining by the compiler — a probable occurrence, given the brevity and simplicity of the function bodies. Furthermore, no special features of templates are invoked. Avoided are template parameters, template specializations, explicit instantiation, etc.
Implementation
Figure 2 shows a partial listing of the tnVector class with the constructors, data, and a sampling of member functions. The full code, as well as a sample program illustrating the salient features, is available from the CUJ ftp site (see p. 3 for downloading instructions). This class has over 30 member functions and operations that are suitable for most applications.
The data portion of the vector class contains doubles arranged contiguously in a C-style array, with the dimension specified at compile-time. The dimension of this vector is a parameter of the tnVector template. Fixing the dimension at compile time not only allows the compiler to check dimensions for us but also enables more aggressive optimizations. Declaring vectors on the heap not only adds extra memory and speed overhead but also thwarts optimizations.
The class has two constructors. The default constructor does not initialize the data, but the alternate constructor initializes the data with the passed values. The default copy constructor, assignment operator, and destructor are supplied by the compiler. Access to the individual elements of the vector is typically via the operator[](int) subscripting syntax to emphasize the close relation to a C-style array. Though this function is inlined to eliminate function overhead, its use should probably be avoided in favor of the higher-level vector operators whenever possible.
Throughout tnVector the programmer is responsible for allocating memory. No hidden constructors, nor assignment operators for that matter, can be found within the class functions or operators. The key point is that the user must specify not only the vector arguments for the operation, but the result vector as well. Put another way, the user must indicate where to store the result of the operation. The simplest solution, adopted here, is to have a member function (or operator, as appropriate) for each operation that modifies a vector. The function modifies the object from which it has been invoked, while leaving the arguments unchanged.
Functions that modify a vector's data take as arguments constant vectors (as appropriate) that are to be combined into the result. For instance, vector addition and subtraction are handled via setSum and setDifference, respectively, but more general functionality is available through setWeightedSum. Figure 3 provides several examples of preferred usage of the tnVector class.
Two similar functions, lengthSquared and length, are provided for convenience. To save the time it takes to extract a square root, prefer lengthSquared to length whenever possible. A similar argument applies to distanceSquared, which computes the square of the distance between two points. The mathematical operators should be self explanatory, but note that increment takes an optional second argument for scaling purposes.
A stream interface is also provided to speed up debugging and prototyping. I provide a stream insertion and a stream extraction operator that is compatible with the old-style <iostream.h> header file. Depending on the flavor of your compiler, you may have to edit the code a bit to get it working on your system.
A few more functions are not defined for specific dimensions, and so cannot be defined in the class definition. The five functions shown are still implemented inline, but only for the appropriate dimensions. In this case the linker, not the compiler, will catch the error before execution. Using the setValue functions make it more difficult to improperly set the components of a vector. Use directedAngle to compute the angle, in radians, between the vector and its argument. The angle is directed from *this to the argument vector, in a counterclockwise sense. The right-handed cross product of two 3-vectors is computed by setCross, and the standard vector triple product is computed by tripleProduct.
If you stop and think about it, the approach presented here is similar to the way vector arithmetic is handled in C or FORTRAN. Declare the memory up front and have the numerical functions take both the source and the destination vectors as arguments. We've just added the extra reliability and robustness of dimension-safety in the process. Judiciously inlining all the functions achieves a level of optimization unavailable in either C or FORTRAN.
Conclusion
The tnVector class presents a minimally object-oriented extension of the C array facility. Encapsulating the vector and vector operations within a simple class not only simplifies our coding efforts but also practically eliminates all errors arising from mixing dimensions. The price paid is minimal, at least theoretically. As long as the compiler properly inlines the functions and is able to optimize effectively, there will be no reduction in speed over equivalent C code. Tests run on an SGI IRIX workstation show approximately a twofold improvement in speed of the tnVector class over more elaborate vector classes patterned after the wastefulVec shown earlier.
Easy to use because of the simple, consistent syntax for member functions and operators, the tnVector class is also powerfully compact and results in smaller code with the same performance characteristics as more verbose (and consequently more error prone) approaches. It is my hope that other users of the tnVector class will share my enthusiasm and will find many uses for this new technique.
Fred M. Persi graduated from Princeton University in 1994 with a Ph.D. in theoretical physics. After a brief teaching stint, he joined K2T Incorporated, of Duquesne, PA in 1996 as Senior R&D Engineer. Currently he applies computer vision and image processing research to problems in commercial photogrammetry, computer-aided design, and photorealistic 3-D modeling.