April 24, 2016. Removed the references to Wild Magic 4 code and
added pseudocode for the actual fitting algorithm. After posting the revision,
a minor change was added in the pseudocode (changed an occurrence of circles
April 7, 2016. Fixed a typographical error in the T(s) equation on
page 4 [θ(t) needed to be θ(s)].
April 2, 2016. At the request of a reader, the document was rewritten
again, this time eliminating the discussion of the min-heap speed up that was
interleaved in the algorithm. The discussion is easier to follow and it is
clearer now how the nesting of cycles is handled. More pseudocode was added.
The GTEngine source code (GteMinimalCycleBasis.h) was rewritten to match the
document. Without the min-heap support, the performance is still reasonable.
Running on an Intel i7-4790 CPU (3.6 GHz), a graph with 32K vertices and 32K
edges required 12 seconds to complete, including the validation that the
graph is planar. And this run used exact rational arithmetic.
March 14, 2016. Fixed a broken link to source code and a minor
March 7, 2016. This is a complete rewrite of the document The Minimal
Cycle Basis for a Planar Graph. The PDF name is the
same but the title is new (using correct terminology). The Wild Magic 5 sample
application was ported, but testing showed that the implementation was incorrect.
The GTEngine implementation has been tested more heavily, and code was added to
test whether the input graph is planar (requires exact arithmetic).
December 3, 2015. Fixed broken links to source code.
November 1, 2015. Provided more details for the construction of the Green's
functions. Fixed some typographical errors and incorrect equation references.
Added comments about the unboundedness of the Green's functions for dimensions 4
September 20, 2015. Fixed the pseudocode regarding intersections and overlaps.
August 16, 2015. Fixed several typographical errors and added some clarification to
August 1, 2015. Fixed several typographical errors and added some clarification to
July 25, 2015. A new document describing how to compute the minimum-volume box
that contains a set of 3D points.
June 23, 2015. Fixed some typographical errors.
May 31, 2015. Major revision of the content of the documents for
computing the distance from a 3D circle to a point, line, or circle. The
documents have been combined into a single new document. The source code
for the distance queries was updated to match the document, and unit tests
were added internally to verify the results.
The old documents have been removed, but the links to them are now redirected
to the new document.
DistancePoint3Circle3.pdf ("Distance Between Point and Circle or Disk in 3D")
DistanceLine3Circle3.pdf ("Distance Between Line and Circle or Disk in 3D")
DistanceCircle3Circle3.pdf ("Distance Between Two Circles in 3D")
DistanceCircle3Disk3.pdf ("Distance Between a Circle and a Disk in 3D")
May 17, 2015. Major revision of the document. The previous version
described only the exhaustive O(n2) algorithm for computing the
minimum-area rectangle bounding a convex polygon. The revised version describes
the O(n) rotating calipers algorithm. The GTEngine source code was modified to
match the document, and it now runs nearly twice as fast as the previous code
(that did not do an efficient job of maintaining the supporting vertex information).
May 13, 2015. Removed the document
FastInverseSqrt.pdf ("Fast and Accurate Inverse Square Root").
Enough is enough for wondering where the magic number came from (see the Wikipedia page for details
about fast inverse square root). Added the following document for approximating the inverse square
root function using a minimax approach. The algorithm is of interest because it establishes a
mathematical pattern that can be used for other function approximations. Its application to inverse
square root is of interest only for hardware that does not have support for the operation (current
generation floating-point units do have support).
April 25, 2015.
Removed documents that were not accessed frequently, are not particularly important, need significant rewriting,
or have been rewritten and the old links redirected to the new files.
Bisection.pdf ("Bisection in 1D, 2D, and 3D")
CompressedUnitVectors.pdf ("Compressed Unit Vectors")
CordicMethods.pdf ("CORDIC Methods")
CollinearityTest.pdf ("A Collinearity Test Independent of Point Order")
CommandLineParsing.pdf ("Command Line Parsing")
DistancePointToQuadratic.pdf ("Distance from Point to a General Quadratic Curve or a General Quadric Surface")
EigenSymmetric3x3.pdf ("Eigensystems for 3x3 Symmetric Matrices (Revisited)")
EigenSymmetricNxN.pdf ("Eigensystems for Symmetric Matrices")
GeometricInvariance.pdf ("Geometric Invariance (vector fields, Lie algebra, prolongations)")
LeftHandedToRightHanded.pdf ("Conversion of Left-Handed Coordinates to Right-Handed Coordinates")
OdeNumericalMethods.pdf ("Numerical Methods for Ordinary Differential Equations")
PdeNumericalMethods.pdf ("Numerical Methods for Partial Differential Equations")
PointFromDistances.pdf ("Reconstructing a Point from Distances")
Polysolids.pdf ("Polysolids and Boolean Operations")
SpecialFunctions.pdf ("Special Functions")
SphericalHarmonics.pdf ("Spherical Harmonics")
SubdivideParabola.pdf ("Subdivision of a Parabolic Segment by Arc Length")
April 25, 2015. Slight clean-up of the document and a fix to several
April 24, 2015. Expanded the document to include more NURBS representations.
In particular, there is a degree-3 representation for a full circle that uses an
internal repeated knot to splice together two half-circles. There is a tensor
product NURBS surface, degree-3 in each parameter, that uses the same idea of
an internal repeated knot to splice together two hemispheres.
April 23, 2015.
Major rewrite of the document on converting
between coordinate systems. The original version of this document was
Conversion of Left-Handed Coordinates to Right-Handed
and was written to handle
the conversion of LightWave coordinate systems (left-handed) to Wild Magic
coordinate systems (right-handed). The process was specific to LightWave's
choice of representing rotations using Euler angles, and the discussion
included how to deal with cameras, lights, and transformation hierarchies.
The new version is the general process of converting between any two
coordinate systems. An implementation is provided that automates
April 20, 2015.
Added significant improvements to the document for the test-intersection
and find-intersection queries for ellipses and to the document for computing
the area of intersection of ellipses. The source code implementation for
the test-intersection and find-intersection queries were updated to use the
details described in the document. Implemented the query for area of
intersection of ellipses.
April 4, 2015. Rewrote the document for computing the roots of low-degree
polynomials. The new document goes into great detail about the classification
of roots (real or non-real, multiplicities) and how to use exact rational
arithmetic to correctly classify the roots in a program. This leads to more
robust root finding using the closed-form expressions for polynomials of degrees
2, 3, and 4. The motivation for the revisions was based on trying to compute
intersections of ellipses, and the nonrobust root finder for quartic polynomials
created many problems numerically.
April 2, 2015. Fixed the algorithm description for conversion from a
BSRational object to a floating-point type. When the round-up
step causes a carry-out, so to speak, from the trailing significand, a block of
code was executed to set w to 1 and adjust p-q. This was incorrect and,
in fact, not necessary because w is not used as the trailing significand in the
March 29, 2015. Added some definitions for variables used in the
equations in the section Separation Tests Involving Other Directions.
Converted the verbatim pseudocode to use lstlisting format.
March 10, 2015. Fixed typographical errors and added some clarification.
January 26, 2015.
Fixed an error in the description for region 2 and added some clarification
about the sign tests for the partial derivatives of R(s,t).
January 5, 2015. Added comments about fitting lines y = a*x + b and
planes z = a*x + b*y + c, mentioning that the numerical problem for solving the
linear equations in the coefficients is ill conditioned unless you compute the averages
of the data points first and subtract those averages from the data points before
solving the linear system.
January 4, 2015. A new document describing the test-intersection query for
boxes and cones.
December 28, 2014.
Modified the document on line-cone intersection to give greater detail. The source code
was updated accordingly.
December 12, 2014. The document was rewritten to add more details about
the algorithm. The source code was modified accordingly.
December 7, 2014.
A new document describing a variation of an iterative eigensolver for
symmetric 3x3 matrices. A source code implementation and a sample application
are provided. The GTEngine code now uses only the iterative solvers for symmetric
matrices; we also have an iterative implementation for the singular value decomposition (SVD).
November 27, 2014. The pseudocode for computing the fitted cylinder
subtracted the input point average for numerically stable computations. The
returned center needed the average added to it.
November 25, 2014. Overhauled the arbitrary precision library to
improve the performance and to improve readability. The unsigned integer
arithmetic was factored out of BSNumber into two classes, one
for arbitrary precision with storage of type std::vector and one
for user-selected fixed precision with storage of type std::array.
Both classes share code for the arithmetic logic unit. Many computations
are now performed in-place to avoid expensive allocation, deallocation,
and memory copies. A new PDF is posted that greatly expands on the library
compared to the discussion in the GPGPU Programming for Games and Science
book. The document serves as a discussion about the design of the library and
a reference for how to use it. Examples are provided for using BSPrecision
to determine the template parameter of UIntegerFP<N> that represents
the maximum number of bits required to compute the exact results for a sequence
November 6, 2014. Implemented a robust algorithm for computing
the distance between line segments in any dimension. Revised the PDF
for computing distance between segments in 3D to describe the new
algorithm. A GPU implementation is available in the sample application.
October 20, 2014. The volume equation for a dodecahedron was in error.
August 15, 2014.
Fixed a typographical error in Equation (14). Replaced the LaTeX verbatim
commands with lstlisting commands for more readable pseudocode.