Vectors and Matrices

Vector and matrices APIs have been around for a long time in the Java world. Because the core operations are so basic (add, multiple, sqrt), this is one of the easiest APIs to port across programming languages, and many early vector and matrix APIs were quick ports of existing C/C++ libraries.

They are so generally useful there even exists specific machine architectures built just for computing matrices as fast as possible. The use of vectors and matrices in games is typically 2D and 3D vector manipulation for computing motion and physics, collision detection, and rendering. Vector and matrix math is a foundation of 3D graphics.

Java3D javax.vecmath

When Sun released Java3D, it included javax.vecmath, a vector and matrix API that is core to Java3D with useful 3D vector operations, as well as classes for general (m x n) matrix computations and other rotation classes, AxisAngle and Quaternion. Interestingly, it also included the seemingly out of place Java3D Color classes. (In vecmath there is an inheritance model in which all vectors inherit from Tuple, a generic component vector. Because color is a three-component set, it inherits from Tuple.)

Part of the cost of computing vector and matrix operations is the actual math operations themselves—the adds, the multiplications, and so on. On most JIT-capable VMs, these operations execute as native operations and are as fast as native code. In fact, this is one of the places JIT-compiled Java code can get really close to C++ (and sometimes even better) in terms of performance. Often, however, the performance problem can be the object data access for these operations. Depending on the object structure and the method organization, vector/matrix APIs can be either as fast as C++ or many times slower.

Java3D vecmath API is about as good as it gets. It is fairly simple (compared to many other available vector/matrix APIs) and cleanly implemented. It uses instance variables instead of arrays and doesn’t generate any object garbage, and the instances are as compact as possible with no extraneous instance data. In our tests on the latest Java VM that support SIMD-enabled JIT compilation, we are seeing appropriate performance gains, meaning the functions are written so cleanly that the SIMD JIT compiler is having great success in matching the instructions. For most purposes, it is a fine vector/matrix API.

vecmath Weaknesses

However, for gaming, vecmath has a few weaknesses.

One, it is only distributed as bundled with Java3D, even though you can pull it out of the install and use it separately. No one can download it from Sun as a single API, and it is not bundled with the standard JDK.

Two, where trig and square root functions are needed, it uses the standard Math functions. Therefore, if you want to use the techniques from earlier in this chapter, you’ll have to write your own utility class for vecmath and use those functions instead.

For example, rotX creates a rotation matrix using the standard formula from linear algebra, which uses Math.sin() and Math.cos(). If you want to use a lookup table or other sin/cos technique, you must write your own rotX method from scratch. Not a terribly big deal, but once you start, you’ll see you will want a new rotY, rotZ, and so on, using the new fast trig functions, too.

Third, there is a float-to-double-to-float conversion in several of the matrix functions where it need not be. Of course, if you never use those methods, you’ll never incur the casting cost and heavier data processing, but there is no documentation denoted where this happens, so you are on your own.

Fourth, vecmath was designed and written before ByteBuffers were in the Java platform, and much of the Java Game Technology Group’s new APIs use ByteBuffers for all the reasons covered in Chapter 5, “Java IO and NIO.” Because much of game vector/matrix output ends up in ByteBuffers, utility classes for this will need to be written.

Last, it is not open source, so if you did wish to simply modify the routines to make use of faster trig functions, for example, you simply do not have the option.

Even if you choose not to use Java3D vecmath, other available vector/matrix APIs often still suffer from the previously mentioned problems.

It’s not a terribly big job to write such a library, because just about all of the algorithms are published in numerous game and mathematical resources. If a project is already using a particular vector/matrix API, it’s usually not terribly difficult to port the project to an improved one, either.

One last thing to consider is that these classes are often the core data structures for most games. Having total control over these is a wise design decision, especially for a commercial game.

Faster Vectors and Matrices

There are many ways in Java to create the core vector and matrix classes for a vector math library. The vector classes can use publicly exposed arrays of float, class fields, or even ByteBuffers for the vector components or hide them and provide only accessor methods in an extreme object-oriented design. They could be parent fields in an inheritance hierarchy in a general n-dimensional subclassing design. Each scheme has its pros and cons, but from the gaming perspective, the reigning issue is performance. In key places in games (and other real-time applications), developers must forgo academic object-oriented design for performance-oriented design. There’s never a shortage of discussion and disagreement about where and when performance-oriented design should affect object-oriented design, if at all. In any case, we will develop a performance-oriented vector/matrix API based on the best information we have gathered about doing so in Java. The key thing to remember is to verify that the design and implementation actually improves performance, and not just appears to be improved. That is, all assumptions must be proven correct for the best possible design. The Java VM and JIT compiler must be accounted for as well and embraced as part of the design choices for any Java performance-oriented system. We will see that with the latest VMs, the object-oriented design and performance-oriented design are not as far apart as they once were.

A few easy choices based on current general performance can be made up front. Many of these were also the same considerations for other vector/matrix APIs, such as javax.vecmath, but some are not.

Allow public access to vector and matrix components: Accessors are nice and could also be there, but public access eliminates function overhead (where VMs don’t automatically eliminate it) and is often the expected usage for someone who works with vectors. Using getX(), getY(), and getZ() is quite cumbersome and unnatural.

Use only floats: This action will save on memory footprint as well as on processing costs. If, for whatever reason, double accuracy is needed, it can easily be duplicated for doubles, provided source is available. The original Java3D vecmath offered floats and double version of all of its classes.

No inheritance and only final methods: Runtime inheritance has some costs in memory and performance, and in a well-designed set of vector classes, it is not needed. This statement is arguable because vector classes do lend themselves to polymorphism, but because most methods must be reimplemented for each type anyway, we would get no real net gain in terms of method reuse, only method name uniformity, which we can just as well create by design. Therefore, in an effort to be as lightweight as possible, our classes will not have any inheritance (outside of the base Java Object), and thus, each separate 2D, 3D, and n-D class will be completely implemented.

Making the methods final does two things. First, it prevents reimplementation of the methods in a user-derived child class. Sometimes this prevention can be an annoyance, but for vectors it makes sense. There is little need to customize vector operations, and these classes are meant for in-game runtime execution. In any case, the source is open, so the developer can easily refactor the classes if he feels that action is justified.

Second, many JVMs can make special runtime optimizations to methods that are final, although newer JVMs are getting good at doing the same to non-final methods.

Use class fields instead of arrays as components: This rule is particular to Java over a C/C++ version, because in C/C++ most vector/matrix APIs use arrays. However, in Java, as was covered earlier, arrays have a hidden security cost in bounds checking. The way that a vector/matrix API accesses the components is often in semi-unordered fashion, forcing bounds checking on each access on JVMs. So, in most performance tests, even on the latest JVMs, vector component class fields are faster to access than vector component arrays. This situation may change in the future (JVM 1.5 has some new features relating to access arrays in a loop), but today and for the near future, class fields have faster access.

Use a faster math library for the core math operations: Again, the idea here is that the new math functions must really be faster on the target environment. With the latest JVM in the mix, sometimes what looks faster isn’t, because the JIT will do interesting optimizations behind the scenes, and the new math method may not actually prove to be faster than the standard, as we saw earlier.

Use any specialized math instructions supported by the CPU: An example of this would be Intel Streaming SIMD Extensions (SSE) and SSE2 instructions for accelerating multimedia applications. SSE is found on Intel Pentium III processors; SSE2 is Intel’s newer instruction set supported on Intel Pentium 4 processors. SSE and SSE2 are perfect for vector/matrix operations, and specialized C vector/matrix libraries exist that use the SSE instructions to get maximum performance on Intel hardware. It may seem desirable to have a Java vector/matrix API use the SSE instructions, but this would require the vector/matrix API to use the JNI, which introduces complications and costs that make it not worthwhile in terms of performance. (See Chapter 6, “Performance and the Java Virtual Machine.”) Fortunately, there is no need to even bother developing an API that accesses these instructions because the latest JVM implementations are beginning to automatically use Pentium SSE/SSE2 features in their JITing and execution, and this will only improve in future versions.

For example, Java version 1.4.2 now uses SSE and SSE2 instruction sets for floating-point computations on platforms that support this. Figure 8.4 shows the performance gain of SSE and SSE2 instruction support as measured by SciMark 2.0, a scientific and numerical computing application that performs floating-point computations.

Figure 8.4: Floating-point performance improvement.

With this set of guidelines and the previous fast math functions, we create optimal 3D vector and matrix classes, which are nearly compatible with Java3D vecmath Vector3f, Point3f, and Matrix3f/4f.

public class Vector3f {     public float x;     public float y;     public float z;     public Vector3f(float xx, float yy, float zz)     {         x = xx;         y = yy;         z = zz;     }     public Vector3f(float vec[])     {         x = vec[0];         y = vec[1];         z = vec[2];     }     public Vector3f(Vector3f vec)     {         x = vec.x;         y = vec.y;         z = vec.z;     }     public Vector3f()     {         x = 0.0f;         y = 0.0f;         z = 0.0f;     }     public String toString()     {         return "(" + x + ", " + y + ", " + z + ")";     }     public final void set(float xx, float yy, float zz)     {         x = xx;         y = yy;         z = zz;     }     public final void set(float vec[])     {         x = vec[0];         y = vec[1];         z = vec[2];     }     public final void set(Vector3f vec)     {         x = vec.x;         y = vec.y;         z = vec.z;     }     public final void get(float vec[])     {         vec[0] = x;         vec[1] = y;         vec[2] = z;     }     public final void get(Vector3f vec)     {         vec.x = x;         vec.y = y;         vec.z = z;     }     public final void add(Vector3f vec1, Vector3f vec2)     {         x = vec1.x + vec2.x;         y = vec1.y + vec2.y;         z = vec1.z + vec2.z;     }     public final void add(Vector3f vec)     {         x += vec.x;         y += vec.y;         z += vec.z;     }     public final void sub(Vector3f vec1, Vector3f vec2)     {         x = vec1.x - vec2.x;         y = vec1.y - vec2.y;         z = vec1.z - vec2.z;     }     public final void sub(Vector3f vec)     {         x -= vec.x;         y -= vec.y;         z -= vec.z;     }     public final void negate(Vector3f vec)     {         x = -vec.x;         y = -vec.y;         z = -vec.z;     }     public final void negate()     {         x = -x;         y = -y;         z = -z;     }     public final void scale(float scalar, Vector3f vec)     {         x = scalar * vec.x;         y = scalar * vec.y;         z = scalar * vec.z;     }     public final void scale(float scalar)     {         x *= scalar;         y *= scalar;         z *= scalar;     }     public final void absolute(Vector3f vec)     {     x = Math.abs(vec.x);     y = Math.abs(vec.y);     z = Math.abs(vec.z);     }     public final void absolute()     {         x = Math.abs(x);         y = Math.abs(y);         z = Math.abs(z);     }     public final void interpolate(Vector3f vec1, Vector3f vec2,      float alpha)     {         x = (1.0f - alpha) * vec1.x + alpha * vec2.x;         y = (1.0f - alpha) * vec1.y + alpha * vec2.y;         z = (1.0f - alpha) * vec1.z + alpha * vec2.z;     }     public final void interpolate(Vector3f vec, float alpha)     {         x = (1.0f - alpha) * x + alpha * vec.x;         y = (1.0f - alpha) * y + alpha * vec.y;         z = (1.0f - alpha) * z + alpha * vec.z;     }     public final float lengthSquared()     {         return x * x + y * y + z * z;     }     public final float length()     {         return (float)Math.sqrt(x * x + y * y + z * z);     }     public final void cross(Vector3f vec1, Vector3f vec2)     {         float xx = vec1.y * vec2.z - vec1.z * vec2.y;         float yy = vec2.x * vec1.z - vec2.z * vec1.x;                z = vec1.x * vec2.y - vec1.y * vec2.x;         x = xx;         y = yy;     }     public final float dot(Vector3f vec)     {         return x * vec.x + y * vec.y + z * vec.z;     }     public final void normalize(Vector3f vec)     {         float inverseMag = 1.0f / (float)Math.sqrt(vec.x *           vec.x + vec.y * vec.y + vec.z * vec.z);         x = vec.x * inverseMag;         y = vec.y * inverseMag;         z = vec.z * inverseMag;     }     public final void normalize()     {         float inverseMag = 1.0f / (float)Math.sqrt(x * x + y          * y + z * z);         x *= inverseMag;         y *= inverseMag;         z *= inverseMag;     }     public final float angle(Vector3f vec)     {         double d = dot(vec) / (length() * vec.length());         if(d < -1D)             d = -1D;         if(d > 1.0D)             d = 1.0D;         return (float)Math.acos(d);     }          public final float distanceSquared(Vector3f point)     {         float dx = x - point.x;         float dy = y - point.y;         float dz = z - point.z;         return dx * dx + dy * dy + dz * dz;     }     public final float distance(Vector3f point)     {         float dx = x - point.x;         float dy = y - point.y;         float dz = z - point.z;         return (float)Math.sqrt(dx * dx + dy * dy + dz * dz);     } }

The complete Matrix classes included on disk are implemented similarly.