Approximate distance

Approximate distance is an important concept in the Doom engine and is used in nearly all calculations in the game simulation which require the distance between two points. Because Doom was written to run on early 386 and 486 processors which often lacked a floating-point unit entirely, and its use was slow even when present, the game was written to exclusively use fixed point math. This has an important impact on how distance can be measured.

Contents

Euclidean distanceEdit

The usual ordinary measurement of distance in two- and three-dimensional spaces is determined using the Euclidean distance formula, which is derived from the Pythagorean theorem. For two points p = (p1p2,..., pn) and q = (q1q2,..., qn), the distance d between them is defined as such:

Euclidean distance.png

The square root operation in this equation is problematic for several reasons when use of floating point math is restricted:

  • Fixed point is too inaccurate and has too limited of a range to apply methods such as Taylor series approximations extensively, which require too many expensive multiplications.
  • Square root cannot be effectively implemented over arbitrary ranges using a lookup table.

Due to these factors, plus the fact that square root is a relatively expensive operation even if performed in floating point or with analytical methods where sufficient accuracy can otherwise be ensured, it is desirable in such conditions to find an approximation to Euclidean distance which avoids performing this operation while providing an adequate amount of accuracy.

DerivationEdit

The unit circle in green consists of points which have a Euclidean distance of 1 from the origin. The red points are points for which the approximate distance function gives a result of 1.

The implementation used by Doom precisely matches one expounded upon by Alan W. Paeth in the 1990 book, Graphics Gems.[1] It is derived through the following steps:

  • Dividing the function's domain into two halves, one where x > y.
  • Reducing the Taylor expansion of the function expressed for these cases specifically to the quadratic term.
  • Further approximating by considering the value of the ratio of x and y as being equal to 1 (reasonable because it lies between 0 and 1 in this formula).
  • Applying absolute value operations to yield a piecewise function in eight parts which is symmetric about both axes while minimizing the number of branches in the code.
  • Replacing division by two with bit-wise right shifting (a machine-specific operation which can have implementation defined results in the C programming language).

ErrorEdit

The minimum error of the approximation is zero, as it precisely coincides with the unit circle at the axes. However, the maximum error must be determined through trigonometric analysis. According to Paeth, the maximum error is approximately 12%. Note that the estimated distance is always greater than or equal to the actual distance, so the error is always an overestimation (as visible in the graph to the right, points closer to the origin give an answer of 1 for the approximation).

ImplementationEdit

In the Doom source code, the function P_AproxDistance is used for approximated distance calculations, and is found in the file p_maputl.c at line 43:[1]

fixed_t
P_AproxDistance
( fixed_t	dx,
  fixed_t	dy )
{
    dx = abs(dx);
    dy = abs(dy);
    if (dx < dy)
        return dx+dy-(dx>>1);
    return dx+dy-(dy>>1);
}

ReferencesEdit

  1. Glassner, Andrew S. (Ed.) Graphics Gems. Cambridge: Academic Press, Inc., 1990. pp. 427-429. ISBN 978-0122861666.