Approximate distance

From DoomWiki.org

Revision as of 14:11, 3 May 2019 by Quasar (talk | contribs) (Derivation: clarify)


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.

Euclidean distance

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.

Derivation

The resulting approximation (red lines) plotted against a unit circle (in blue; full graph scaled by 1024 for visibility).

The implementation used by Doom precisely matches one expounded upon by Andrew S. Glassner in his 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).

Error

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 Glassner, the maximum error is approximately 12%. Note that the estimated distance is always less than the actual distance, so the error is always an underestimation.

Implementation

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);
}

References

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