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.