Game Math and Geometry Library
My C++ library for 3D mathematics and geometry manipulation.
This code library contains implementations of 3D vector, matrix and quaternion classes and several primitive geometric objects. Its focus is for use in games and (potentially untrusted) script execution environments.
This is perhaps the fifth math library I have been implementing over the years, and I decided to make an effort to build it clean enough this time, so that I will not need to start writing a sixth one too soon. There are several existing game math libraries available on the net, but I was not able to find one to fit my goals. For a brief comparison, see the Alternatives page.
This library was written with the aim at following goals:
- Clean and simple.
- I am not much a fan of namespaces. Or templates. Two of the previous math libraries I wrote templated on the scalar type and matrix/vector size, as is commonly done. I grew to dislike it, called out YAGNI, and this time just diligently wrote the different classes I actually need. I don't mangle or decorate, but keep the names short and sweet.
- Rich API.
- This library is intended for generic use, and not only for a single purpose, like collision detection. It contains a wide range of utility functions for each geometric primitive, stressing conveniency and expressiveness over API minimalism or irreducibility. The aim is to provide rich functionality of common operations in the math layer so that the client code would not need to build a middle-layer codebase of utilities on top of this library.
- Documented with care.
- For almost all C++ projects I have ever written, I have used doxygen. It is an excellent piece of software, but I think it generates messy documentation pages that are difficult to explore. As a side project to this project, I have implemented a custom documentation generator frontend for doxygen, with which I am trying to capture the look of clean and easily explorable HTML documentation. The reference documentation for this library is created using this documentation generator.
- One of the uses of this library is in an environment which meets new users who do not have knowledge of mathematics for 3D graphics. Therefore the intent of the documentation is not only to explain the code itself, but to also explore the underlying concepts, and to provide references to other sources for more information.
- A significant portion of game mathematics relies on conventions. Left- or right-handed? Clock-wise or counter-clockwise? What is your up axis? How do you transform a vector by a matrix? In which order do you concatenate Euler rotations? A lot of code out there choose conventions or make assumptions without explicitly making note, and leaving them for the reader to decipher. This library desires to be unambiguous and explicit in its choices of convention, and where practical, try to be agnostic of any conventions and allow the user to make that choice by providing the alternatives.
- Safe and script-friendly.
- This library is being used in a project where the library is exposed to a script environment with potentially malevolent scripts running. Automated tests are run on each function of the library with randomized inputs to ensure that it is not possible to crash or halt the system via this library. Additionally, any preconditions on inputs, like unitarity and orthonormality, are tracked at runtime and errors reported to the user.
It would be very time-consuming to try to build a library for everything and everyone. To ease the development, the following aspects/features have been pushed aside as non-goals:
- Fast code is important for games, but at least initially, I am not worrying about optimizations. Some of the functions are unbelievably naive and written as placeholders waiting to be replaced by a faster test. I am, however, very aware about performance, and have marked down with TODOs the places I know can be improved. Additionally, the documentation generator runs both a time and memory consumption profiling step on each function and embeds the results into the documentation pages, so that the performance is explicitly visible. For more information, see the section on Performance.
- Genericity or extensibility.
- Several libraries provide very generic implementations of different data structures and algorithms, which enable N-dimensional calculations with custom tuple types like ints in cartesian or polar coordinates. I do not. Look at the Alternatives section if that is important to you.
- No 2D.
- This library is 3D only. There is the class float2, but apart from that, all primitives are 3D, and not 2D. If in distress, it is possible to perform 2D geometry manipulations with the 3D libraries by setting z=0, but naturally this is slightly suboptimal.
- Not a Physics Engine or a Scene Manager.
- While this library contains a lot of algorithms commonly found in physics packages or scene management libraries, this library implements neither. This means that scene groups/hierarchies, collision detectors and resolvers, or acceleration data structures for scene queries are not provided. If you are interested in physics engines, see here.
- Not a Renderer.
- The geometric objects that this library provides are used only for mathematical representation and manipulation. The library does not implement a renderer for drawing these objects (using OpenGL, Direct3D or similar) or scene trees to store groups of geometric objects, but it does provide functions for triangulation and line list conversion, so you can render the objects in your own 3D engine.
- No double-precision.
- All computation is performed using the float type. If you need double-precision, have a look at one of the alternatives. There does not even exist a typedef for configuring single- or double-precision, but this might come in the future.
- No C++11.
- This library does not use any language features from ISO/IEC 14882:2011 (C++11), and there are no plans to do so. The reason for this is that most of the library code is quite "basic" and there has not been a pressing need to use the new standard. If C++11 features come in, they will be conditionally enabled to retain full C++03 support as well.
This library consists of the following components:
- Low-level data structures for 3D and homogeneous 4D algebra:
- Data structures for expressing geometric objects:
- Line types: Line, Ray, LineSegment.
- Planar types: Plane, Triangle, Polygon.
- Quadratic types: Circle/Disc, Sphere, Capsule.
- Polyhedral types: Axis-Aligned Bounding Box (AABB), an arbitrarily Oriented Bounding Box (OBB), a perspective or orthographic viewing Frustum and an arbitrary shaped Polyhedron.
- Other utility data structures:
These components implement the following features:
- Functions for operating with standard 3D graphics operations: translation, rotation, scaling, perspective and orthographic projection.
- An API of standard mathematical functions for trigonometry, exponentiation, etc. (resorting to C math libraries currently for most implementations)
- A library of vector logic and arithmetic operations similar to the ones present in the HLSL language (Min, Max, Sign, Step, Clamp, ...).
- Basic matrix operations for row and column manipulation, inverses, transposes and matrix-vector transforms.
- Functions for more uncommon transformations like mirror, reflect, refract and shear.
- Extensive support for representing and converting between rotations expressed as matrices, quaternions, axis&angle and different forms of Euler angles.
- Functions for traditional Translate*Rotate*Scale matrix decompositions, LookAt and From-To rotations.
- A collection of geometric intersection and containment tests for provided object types.
- A collection of closest point pair and distance computation for provided object types.
- Various clipping operations of line segments, triangles, polygons and polyhedrons.
- Algorithms for bounding volume computations.
- Basic geometric shape queries: vertex/edge/face examination, parametric point representation and generation.
- Random point generation across corner/edge/face/surface/inside of geometric shapes.
- Geometric object triangulation for rendering as triangle lists or edge lists.
Additionally, the following high-level features are provided:
- Enforces preconditions on all input.
- This library intends to be user-friendly by detecting and providing an error message whenever the user passes in bad data. If the library expects a normalized vector, and you pass in an unnormalized one, the library will yell at you.
- No exceptions.
- However, the library design follows the garbage in - garbage out principle. If you pass in bad data, you will get bad data out (with an error message). Few functions report error codes at runtime. C++ exceptions are not used in any part of the library.
- Unless you enable MATH_ENABLE_INSECURE_OPTIMIZATIONS, you should not be able to crash or halt the system by providing bad data (except if passing bad pointers or references). All code is tested using an automated random call profiler.
- No RTTI.
- Currently all classes provided in this library are concrete value types, and there is no need to use the virtual keyword anywhere. So far, it intends to stay that way.
- Optional STL.
- A current work-in-progress is to remove the dependency to any STL classes. At current stage the library does build without STL, but some classes (Polygon, Polyhedron) are severely crippled in features if you do so.
- Re-entrancy safe.
- The classes are not thread-safe, meaning that you cannot access the same object simultaneusly from multiple threads. However, all code is re-entrant, meaning that you can operate on separate instances of any class of the math library in separate threads without problems.
- Synthetic benchmarks.
- As part of the documentation generation process, an automated profiler is run on each function of the library. This profiler measures the runtime performance and dynamic allocations performed by each function. These results are available on the documentation page for each function, but remember that the results need to be taken with great reservations.
Supporting the following platforms/compilers is in the scope of this project:
- Windows with Visual Studio 2008/2010/2012.
- Windows with MinGW or MinGW-64.
- Linux with GCC 4.3.6 or newer.
- Mac OS X with Clang 3.1 or newer, or GCC.
- Android NDK, iOS, Google NaCl.
- Emscripten C++ -> JS compiler.
There is a continuous build architecture that immediately recompiles the library and runs tests on the different platforms at MathGeoLib build report page. If you encounter any issues building, use the Github bug tracker to report them.
To configure the behavior of the library, the following options exists:
- A #define MATH_ENABLE_STL_SUPPORT controls whether the C++ STL libraries are used (std::string, std::vector, etc.). (This support is currently partial, work-in-progress).
- Mathematicians frown if multiplication is defined pointwise for vector*vector or matrix*matrix. Also, for 3D graphics it is relatively rare that matrices or quaternions are added together. A #define MATH_ENABLE_UNCOMMON_OPERATIONS flag is used to control whether these error-prone or otherwise non-standard operations are added for use in the library.
- For double-checking parts of the internal working in the math library, a #define MATH_ASSERT_CORRECTNESS flag exists. This enables checks that test that the implementations are correct.
- The library uses a custom-defined macro assume(), which is similar to assert(), but instead of halting on failure, an error message is generated (both in debug and release mode). Use the #define MATH_ASSERT_ON_ASSUME to make assume() behave identically to assert() instead.
- On the other hand, if #define MATH_SILENT_ASSUME is enabled, the assume() macros are stripped completely from the build, which makes the math library work silently and not test the input that is given to it. Setting this flag improves runtime performance, but does not change the behavior of this library otherwise.
- By default, the math libraries should be safe, which means that bad input, like out-of-bounds indices, can not crash or deadlock the system. These safety checks are present both in debug and release, and are different from MATH_ASSERT_CORRECTNESS and MATH_SILENT_ASSUME. If this is not important, set #define MATH_ENABLE_INSECURE_OPTIMIZATIONS to remove all safety-related runtime checks and improve runtime performance. Bad input pointers or references cannot be checked automatically, so be sure to sandbox these if you are looking to provide a fully secure scripting environment.
- If you are co-using or migrating from other math libraries, the #defines MATH_QT_INTEROP, MATH_IRRLICHT_INTEROP, MATH_OGRE_INTEROP and MATH_BULLET_INTEROP exist, which enable implicit conversions between low level types of the various libraries.
At the current stage, spending time to optimize for the fastest possible runtime performance is not the first goal. It is assumed that the compiler can do efficient LTCG and (N)RVO optimizations. Manual inlining has not been done, except where it is convenient for documentational purposes. Little care has been taken to write code in a manner that omits redundant temporaries from being created, and code clarity is preferred, while assuming that the compiler is smart enough to do the job.
Experience shows that compilers tend to not be that smart in practice, and therefore several obvious optimization opportunities have been marked down as todos in the code. Additionally, some of the functionality has been literally written in less than five minutes of effort, in a ridiculously naive manner. All these todos are visible in the reference documentation pages.
To give an estimate of the practical performance of the different functions, synthetic benchmarks are run to capture a profile of the time and memory consumption for each function. These should naturally be taken with great reservations, since the timings will vary between systems, and the inputs given to the functions. The aim is to provide a rough backup estimate for detecting code that runs obviously slow, or allocates memory when it shouldn't. For what it is worth to know, the profiles were run on my Fujitsu Lifebook T901 laptop with Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz and Windows 7 Professional 64-bit.
As an experimental feature, I have added the ability to post comments into the documentation. This was inspired by PHP.net's reference documentation pages (e.g. here). Use the comments section to
- point out documentation-related bugs.
- supplement the reference documentation for missing or lacking information.
- provide code examples, by using the [code] + [/code] tags to create a syntax-highlighted code block.
Do not use the comments section to
- start up a help thread. The comments system is very primitive, and it is better to use a thread on a forum for asking questions.
- report bugs in the library itself. Prefer using the github issue tracker, since it is more flexible for the purpose.
- try to do any retarded SQL or HTML injection, or flood the system with viagra links. I have done my homework, and all input does get sanitized. There also exists an IP address -based spam filtering, so please go elsewhere if you need to prove something. If this feature gets abused, I will take it offline. Do not use HTML tags, they are not supported.