Mathematics Source Code

The source code implements an extensive collection of data types and algorithms. Much of the code was ported from Wild Magic 5 with modifications to simplify the classes and use templates. The code includes new and improved implementations; specifically, the computational geometry code has been tested extensively with sample applications illustrating each algorithm. We have added constrained Delaunay triangulation. A new exact arithmetic library has been added that performs better than the old one. We also added much improved implementations for symmetric eigensystems and for singular value decomposition.

Algebra. Code for vectors and matrices of known size at compile time; for vectors and matrices with sizes known only at run time; for transformations using translations, rotations, and scalings; and for rotational representations including matrices, quaternions, axis-angle, and Euler angles.
Approximation. Least-squares fitting of 2D point sets by Gaussian distributions, lines, circles, ellipses, and general quadratic curves. Fitting of 3D point sets by Gaussian distributions, lines, planes, spheres, ellipsoids, paraboloids, great circles and arcs (for points on a sphere), and general quadratic surfaces. Fitting of data by polynomials in 1, 2, or 3 independent variables. A base class is provided to allow fitting using RANdom SAmple Consensus (RANSAC).
Arithmetic. Functions for some simple bit manipulation of integers. A template class IEEEBinary to encapsule some information about floating-point numbers in the IEEE 754-2008 Standard for Floating-Point Arithmetic. A derived class is IEEEBinary16 that implements 16-bit floating-point arithmetic. An arbitrary precision arithmetic system for exact rational arithmetic. Both fixed-size and arbitrary-size unsigned integer classes are provided to support exact rational arithmetic, but the system is designed to allow you to provide other integer classes as long as they implement a minimum set of interfaces. The exact arithmetic system is used extensively in the computational geometry algorithms.
Computational Geometry. Several common algorithms in computational geometry are implemented using template classes. The templates have two types, the input type of the data and the compute type of the algorithm. The input type is usually a floating-point type (32-bit or 64-bit). The compute type can be a floating-point type, but the algorithms are not guaranteed to produce correct results (The Curse of Floating-Point in Computational Geometry). The sample applications to demonstrate this code use the exact arithmetic system as the compute type. Low-level geometic queries are provided that are common to the algorithms. The algorithms include convex hull in 2D and 3D, Delaunay triangulation (2D), Delaunay tetrahedralization (3D), constrained Delaunay triangulation (2D), minimum-area box containing points (2D), minimum-volume box containing points (3D), minimum-area circle containing points (2D), minimum-volume sphere containing points (3D), separation of point sets in 2D or 3D, and nearest-neighbor queries using KD trees.
Containment. Several algorithms are implemented for common container objects. The algorithms are implemented as template functions, but the naming is consistent so that later we can refactor these into template classes with a base-class abstraction similar to that of the distance and intersection queries. The template functions are GetContainer for creating a container for an input point set InContainer to test whether a point is in a container, and MergeContainers to produce a container of two input containers. Some container types might not implement all three but others implement additional queries. The containers are circles, spheres, ellipses, ellipsoids, capsules, cylinders, polygons, and oriented boxes. This section also has code for circumscribed and inscribed circles for triangles and the circumscribed and inscribed spheres for tetrahedra.
Curves, Surfaces, and Volumes. Template classes are used to implement basis functions; Bezier curves, surfaces, and volumes; NURBS curves, surfaces, and volumes; natural splines; and tension-continuity-bias (TCB) splines.
Distance. The distance queries are classified by dimension (2D or 3D) and by the intrinsic dimensionality of the objects (point, linear, planar in 2D; point, linear, planar, volumetric in 3D). The template class DCPQuery specifies that the classes are functors where operator() accepts two input objects and the returned value is a struct Result whose implementation depends on the input object types.
- 2D
  - Point-Linear: point-line, point-ray, point-segment
  - Point-Planar: point-alignedbox, point-orientedbox, point-ellipse
  - Linear-Linear: line-line, line-ray, line-segment, ray-ray, ray-segment, segment-segment
- 3D
  - Point-Linear: point-line, point-ray, point-segment
  - Point-Planar: point-plane, point-rectangle, point-triangle, point-circle
  - Point-Volumetric: point-alignedbox, point-orientedbox, point-tetrahedron, point-ellipsoid, point-frustum
  - Linear-Linear: line-line, line-ray, line-segment, ray-ray, ray-segment, segment-segment
  - Linear-Planar: line-rectangle, line-triangle, ray-rectangle, ray-triangle, segment-rectangle, segment-triangle
  - Linear-Volumetric: line-alignedbox, line-orientedbox, ray-alignedbox, ray-orientedbox, segment-alignedbox, segment-orientedbox
  - Planar-Planar: rectangle-rectangle, triangle-rectangle, triangle-triangle, circle-circle
Functions. A fast and accurate approximation to SLERP is available. Macro constants are defined for commonly occurring numbers. Minimax polynomial approximations are implemented for common functions (acos, asin, atan, cos, exp2, exp, invsqrt, log2, log, sin, sqrt, tan). Macro constants are defined for sharing by these functions and their SIMD counterparts.
Geometric Primitives. Classes that represent geometric primitives for 2D and 3D. In 2D we have lines, rays, segments, aligned and oriented boxes, triangles, polygons, circles and arcs, and ellipses. In 3D we have lines, rays, segments, planes, triangles, rectangles, circles, ellipses, aligned and oriented boxes, tetrahedra, polyhedra, orthogonal frusta, spheres, ellipsoids, cylinders, cones, capsules, halfspaces, and torii.
Interpolation. A collection of interpolation methods is provided. These include bilinear, bicubic, trilinear, tricubic, Akima interpolation, thin plate splines, linear interpolation for nonuniform data, and Cendes-Wong quadratic C1 interpolation (planar data, spherical data, 2D vector field data).
Intersection. The intersection queries are of the form test-intersection, where you want to know only whether two objects intersect, or find-intersection, where you want to know the set of intersection. The template description for test-intersection is TIQuery and the template description for find-intersection is FIQuery. These specify that the classes are functors where operator() accepts two input objects and the returned value is a struct Result whose implementation depends on the input object types. The queries are also classified by dimension (2D or 3D) and by the intrinsic dimensionality of the objects (linear, planar in 2D; linear, planar, volumetric in 3D).
- 2D
  - Linear-Linear: line-line, line-ray, line-segment, ray-ray, ray-segment, segment-segment
  - Linear-Planar: line, ray, or segment versus alignedbox, orientedbox, triangle, circle, or circular arc; circle-circle, circle-arc, arc-arc
  - Planar-Planar: alignedbox-alignedbox, alignedbox-orientedbox, orientedbox-orientedbox, orientedbox-circle, ellipse-ellipse
- 3D
  - Linear-Planar: line, ray, or segment versus plane or triangle
  - Linear-Volumetric: line, ray, or segment versus alignedbox, orientedbox, sphere, ellipsoid, cylinder, cone, or capsule; segment-halfspace
  - Planar-Planar: plane-plane, plane-triangle, plane-circle
  - Planar-Volumetric: plane versus orientedbox, sphere, ellipsoid, cylinder, capsule; triangle-halfspace
  - Volumetric-Volumetric: alignedbox-alignedbox, alignedbox-orientedbox, orientedbox-orientedbox, orientedbox-frustum, orientedbox-sphere, sphere-sphere, sphere-frustum, sphere-cone, ellipsoid-ellipsoid, capsule-capsule; halfspace versus orientedbox, sphere, ellipsoid, cylinder, or capsule
Numerical Methods. A collection of commonly occurring numerical methods is provided. These include linear system solvers and Gaussian elimination, root finding (bisection, Brent's method, polynomial root bounding), minimization in any dimension using Powell's direction set method for searching, integration (trapezoid rule, Romberg integration, Gaussian quadrature), ordinary differential equations (Euler, implicit Euler, midpoint, Runge-Kutta 4th order), eigenvalues and eigenvectors of symmetric matrices, singular value decomposition. There is now a solver for the Linear Complementarity Programming (LCP) problems.
Projection. A collection of algorithms for projecting objects onto lines or planes. The list is small at the moment but will be expanded later as we port the remaining code from Wild Magic 5.
SIMD. Intel's Streaming SIMD Extensions (SSE) for 4x1 vectors, 4x4 matrices, and quaternions including the basic algebraic operations applied to such objects. The matrix storage convention and matrix-vector multiplication convention that are used for the CPU implementations are adhered to in the SIMD implementations. We will soon provide the SSE implementations for the minimax function approximations mentioned previously in this list.