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 min-heap data structure to support geometric algorithms;
reverse iteration in range-based for loops; string utilities; comparisons
for shared pointers and weak pointers; and simple thread-safe 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, 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
-
Planar-Volumetric:
triangle-alignedbox, triangle-orientedbox,
rectangle-alignedbox, rectangle-orientedbox
-
Volumetric-Volumetric:
alignedbox-alignedbox, alignedbox-orientedbox, orientedbox-orientedbox
-
Image Processing.
Basic support for representing n-dimensional 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 fast-marching-based 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 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
-
Meshes.
Support for graph data structures related to meshes. These include
data structures for manifold or non-manifold meshes. The mesh types
are vertex-edge, edge-triangle, vertex-edge-triangle,
triangle-tetrahedron and vertex-triangle-tetrahedron. 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, Gauss-Newton minimization, Levenberg-Marquardt
minimization, 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, Cholesky decomposition.
There is a solver for the Linear Complementarity Problem (LCP) that
supports floating-point and arbitrary-precision arithmetic. This is useful
for convex quadratic programming (distance algorithms).
-
Physics.
A collection of algorithms to support rigid-body physics applications. These
include particle systems, mass-spring 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.