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.