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.

Low Level.
Support for specialized multidimensional arrays; a logging system to
report assertions and errors (exceptions thrown when these occur)
and to report warnins and information (no exceptions thrown when these
occur); a minheap data structure to support geometric algorithms;
reverse iteration in rangebased for loops; string utilities; comparisons
for shared pointers and weak pointers; and simple threadsafe data
structures for maps and queues.

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, axisangle, and Euler angles.

Approximation.
Leastsquares 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 floatingpoint numbers in
the IEEE 7542008 Standard for FloatingPoint Arithmetic. A derived
class is IEEEBinary16 that implements 16bit floatingpoint arithmetic.
An arbitrary precision arithmetic system for exact rational arithmetic.
Both fixedsize and arbitrarysize 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 floatingpoint type (32bit or 64bit). The compute type can be
a floatingpoint type, but the algorithms are not guaranteed to produce
correct results (The Curse of FloatingPoint in Computational Geometry).
The sample applications to demonstrate this code use the exact arithmetic
system as the compute type. Lowlevel 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), minimumarea box containing
points (2D), minimumvolume box containing points (3D), minimumarea
circle containing points (2D), minimumvolume sphere containing points
(3D), separation of point sets in 2D or 3D, and nearestneighbor 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 baseclass 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 tensioncontinuitybias (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

PointLinear:
pointline, pointray, pointsegment

PointPlanar:
pointalignedbox, pointorientedbox, pointellipse

LinearLinear:
lineline, lineray, linesegment, rayray, raysegment,
segmentsegment

3D

PointLinear:
pointline, pointray, pointsegment

PointPlanar:
pointplane, pointrectangle, pointtriangle, pointcircle

PointVolumetric:
pointalignedbox, pointorientedbox, pointtetrahedron,
pointellipsoid, pointfrustum

LinearLinear:
lineline, lineray, linesegment, rayray, raysegment,
segmentsegment

LinearPlanar:
linerectangle, linetriangle, rayrectangle, raytriangle,
segmentrectangle, segmenttriangle

LinearVolumetric:
linealignedbox, lineorientedbox, rayalignedbox, rayorientedbox,
segmentalignedbox, segmentorientedbox

PlanarPlanar:
rectanglerectangle, trianglerectangle, triangletriangle,
circlecircle

PlanarVolumetric:
trianglealignedbox, triangleorientedbox,
rectanglealignedbox, rectangleorientedbox

VolumetricVolumetric:
alignedboxalignedbox, alignedboxorientedbox, orientedboxorientedbox

Image Processing.
Basic support for representing ndimensional images and for processing those
of dimension 1, 2 or 3. The processing includes level set extraction for 2D
and 3D images, binary image processing including connected component labeling,
morphological and operations, blurring filters, filters based on parabolic
partial differential equations, and fastmarchingbased segmentation.

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 CendesWong quadratic C1
interpolation (planar data, spherical data, 2D vector field data).

Intersection.
The intersection queries are of the form testintersection, where
you want to know only whether two objects intersect, or
findintersection, where you want to know the set of intersection.
The template description for testintersection is TIQuery and the template
description for findintersection 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

LinearLinear:
lineline, lineray, linesegment, rayray, raysegment,
segmentsegment

LinearPlanar:
line, ray, or segment versus alignedbox, orientedbox, triangle,
circle, or circular arc; circlecircle, circlearc, arcarc

PlanarPlanar:
alignedboxalignedbox, alignedboxorientedbox,
orientedboxorientedbox, orientedboxcircle, ellipseellipse

3D

LinearPlanar:
line, ray, or segment versus plane or triangle

LinearVolumetric:
line, ray, or segment versus alignedbox, orientedbox, sphere,
ellipsoid, cylinder, cone, or capsule; segmenthalfspace

PlanarPlanar:
planeplane, planetriangle, planecircle

PlanarVolumetric:
plane versus orientedbox, sphere, ellipsoid, cylinder, capsule;
trianglehalfspace

VolumetricVolumetric:
alignedboxalignedbox, alignedboxorientedbox,
orientedboxorientedbox, orientedboxfrustum, orientedboxsphere,
spheresphere, spherefrustum, spherecone, ellipsoidellipsoid,
capsulecapsule; halfspace versus orientedbox, sphere, ellipsoid,
cylinder, or capsule

Meshes.
Support for graph data structures related to meshes. These include
data structures for manifold or nonmanifold meshes. The mesh types
are vertexedge, edgetriangle, vertexedgetriangle,
triangletetrahedron and vertextriangletetrahedron. Code is provided
for generating standard meshes: rectangles, rectangle patches, surfaces
of revolution, and tubes.

Miscellaneous.
Code for various algorithms that do not quite fit into other
classifications in this list of topics.

Numerical Methods.
A collection of commonly occurring numerical methods is provided. These
include polynomial approximations to functions, 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, GaussNewton minimization, LevenbergMarquardt
minimization, integration (trapezoid rule, Romberg integration, Gaussian
quadrature), ordinary differential equations (Euler, implicit Euler,
midpoint, RungeKutta 4th order), eigenvalues and eigenvectors of
symmetric matrices, singular value decomposition, Cholesky decomposition.
There is a solver for the Linear Complementarity Problem (LCP) that
supports floatingpoint and arbitraryprecision arithmetic. This is useful
for convex quadratic programming (distance algorithms).

Physics.
A collection of algorithms to support rigidbody physics applications. These
include particle systems, massspring systems and a collision culling system
for bounding rectangles (2D) or bounding boxes (3). The page has links to code
for computing polyhedron properties where the polyhedron is simple, has
triangle faces and the mass density is assumed to be constant. The properties
are mass, centroid and inertia tensor, the latter either in body coordinates
or in world coordinates.

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.

Projection.
A collection of algorithms for projecting objects onto lines or planes. The
list is small at the moment but will be expanded later in the Geometry Tools
Library.