View source for Dist fast.asm

[[Category:Programming]] [[Category:Library]]

= Functions Provided =

<CENTER><TABLE BORDER><TR><TH>Entry point</TH><TH>Function provided</TH><TH>Notes</TH></TR>
<TR><TD>DIST_FAST</TD><TD ROWSPAN=2>Find the approximate Euclidean distance between two points</TD><TD>Two pairs of (x, y) coordinates passed in registers</TD></TR>
<TR><TD>DIST_FAST.1</TD><TD>Instead of raw coordinates, abs(&Delta;X) and abs(&Delta;Y) passed in registers.</TD></TR></TABLE></CENTER>
<br /><br />
See source code below for calling convention.<br /><br />

= Examples =

(todo... please contribute!)

= Notes =

This function is based on C code found in Graphics Gems IV.  The function computes an approximation of Euclidean distance, accurate to within 4%, and it does so very quickly--under 180 cycles!

The following graphs show the error characteristic for DIST_FAST.  Each pixel shows the error, in absolute distance, in the distance computed to that point from (0, 0).  The graph on the left shows the magnitude, and the graph on the right shows the sign.
<CENTER><TABLE BORDER>
<TR><TH>Error Magnitude</TH><TH COLSPAN=2>Key</TH><TH>&nbsp;</TH><TH>Error Sign</TH><TH COLSPAN=2>Key</TH></TR>
<TR><TD ROWSPAN=10>[[Image:Dfmag.gif|320px]]</TD><TD BGCOLOR=#000000>&nbsp;&nbsp;&nbsp;</TD><TD>0px</TD><TD ROWSPAN=10>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</TD><TD ROWSPAN=10>[[Image:Dfsgn.gif|320px]]</TD><TD BGCOLOR=#000000 ROWSPAN=5>&nbsp;&nbsp;&nbsp;</TD><TD ROWSPAN=5>DIST_FAST<BR />underestimates<BR />distance</TD></TR>
<TR><TD BGCOLOR=#0000C0>&nbsp;&nbsp;&nbsp;</TD><TD>1px</TD></TR>
<TR><TD BGCOLOR=#00C000>&nbsp;&nbsp;&nbsp;</TD><TD>2px</TD></TR>
<TR><TD BGCOLOR=#C0C000>&nbsp;&nbsp;&nbsp;</TD><TD>3px</TD></TR>
<TR><TD BGCOLOR=#C00000 ROWSPAN=2>&nbsp;&nbsp;&nbsp;</TD><TD ROWSPAN=2>4px</TD></TR>
<TR><TD BGCOLOR=#FFFFFF ROWSPAN=5>&nbsp;&nbsp;&nbsp;</TD><TD ROWSPAN=5>DIST_FAST<br />overestimates<br />distance</TD></TR>
<TR><TD BGCOLOR=#00FF00>&nbsp;&nbsp;&nbsp;</TD><TD>5px</TD></TR>
<TR><TD BGCOLOR=#FFFF00>&nbsp;&nbsp;&nbsp;</TD><TD>6px</TD></TR>
<TR><TD BGCOLOR=#FF0000>&nbsp;&nbsp;&nbsp;</TD><TD>7px</TD></TR>
<TR><TD BGCOLOR=#FF00FF>&nbsp;&nbsp;&nbsp;</TD><TD>8px</TD></TR>
</TABLE></CENTER>

As you can see, the error stays rather proportional to the distance, and in general, DIST_FAST tends to over-estimate rather than under-estimate distance.  For most purposes, such as having one sprite follow another by setting velocity to (&Delta;X / dist, &Delta;Y / dist), this error will hardly be noticeable.

= Source Code =

<pre>
;* ======================================================================== *;
;*  These routines are placed into the public domain by their author.  All  *;
;*  copyright rights are hereby relinquished on the routines and data in    *;
;*  this file.  -- Joseph Zbiciak, 2008                                     *;
;* ======================================================================== *;

;; ======================================================================== ;;
;;  DIST_FAST Approximate the distance between two points to 4% error.      ;;
;;  DIST_FAST.1 Alternate entry point                                       ;;
;;                                                                          ;;
;;  AUTHOR                                                                  ;;
;;      Joseph Zbiciak <intvnut AT gmail.com>                               ;;
;;                                                                          ;;
;;  REVISION HISTORY                                                        ;;
;;      22-Apr-2002 Initial Revision                                        ;;
;;                                                                          ;;
;;  INPUTS for DIST_FAST                                                    ;;
;;      R0    Coordinate x0                                                 ;;
;;      R1    Coordinate y0                                                 ;;
;;      R2    Coordinate x1                                                 ;;
;;      R3    Coordinate y1                                                 ;;
;;      R5    Return address                                                ;;
;;                                                                          ;;
;;  INPUTS for DIST_FAST.1                                                  ;;
;;      R2    Absolute value of delta-X (eg. abs(x0 - x1))                  ;;
;;      R3    Absolute value of delta-Y (eg. abs(y0 - y1))                  ;;
;;      R5    Return address                                                ;;
;;                                                                          ;;
;;  OUTPUTS                                                                 ;;
;;      R0    Unchanged                                                     ;;
;;      R1    Trashed                                                       ;;
;;      R2    Trashed                                                       ;;
;;      R3    Approximate Euclidean distance from (x0, y0) to (x1, y1).     ;;
;;                                                                          ;;
;;  NOTES                                                                   ;;
;;      This returns a value which is approximately sqrt(dx**2 + dy**2),    ;;
;;      within 4%.  This should be sufficient for most applications.        ;;
;;                                                                          ;;
;;      The code accepts unsigned 16-bit values for the incoming            ;;
;;      coordinates, and should correctly calculate abs(x0 - x1)            ;;
;;      and abs(y0 - y1) for the full 16-bit range.                         ;;
;;                                                                          ;;
;;      The output should have the same dynamic range as the inputs.        ;;
;;      Thus, if the inputs are in an 8-bit range, so will be the           ;;
;;      output.  If the inputs are in a 16-bit range, so is the output.     ;;
;;                                                                          ;;
;;      Although the arguments list R0 and R2 as the X coordinates          ;;
;;      and R1 and R3 as the Y coordinates, these assignments may be        ;;
;;      swapped.  (eg. R1 and R3 are X coordinates, R0 and R2 are Y         ;;
;;      coordinates.)  Euclidean distance doesn't change when you rotate    ;;
;;      the page 90 degrees or flip it over.  :-)                           ;;
;;                                                                          ;;
;;  SOURCE                                                                  ;;
;;      Graphics Gems IV (see C code below)                                 ;;
;;                                                                          ;;
;;      C code from the article                                             ;;
;;      "Fast Linear Approximations of Euclidean Distance in                ;;
;;      Higher Dimensions" by Yoshikazu Ohashi, yoshi@cognex.com            ;;
;;      in "Graphics Gems IV", Academic Press, 1994                         ;;
;;                                                                          ;;
;;      /* 2-D Euclidean distance approximation          */                 ;;
;;      /* c1 = 123/128, c2 = 51/128 and max(e) = 4.0%   */                 ;;
;;      int veclen2 (int ix, int iy)                                        ;;
;;      {                                                                   ;;
;;          int  t;                                                         ;;
;;                                                                          ;;
;;          ix= (ix<0 ? -ix : ix);   /* absolute values */                  ;;
;;          iy= (iy<0 ? -iy : iy);                                          ;;
;;                                                                          ;;
;;          if(ix<iy)        /* swap ix and iy if (ix < iy) */              ;;
;;          {                /* See Wyvill (G1, 436)        */              ;;
;;              ix=ix^iy;                                                   ;;
;;              iy=ix^iy;                                                   ;;
;;              ix=ix^iy;                                                   ;;
;;          }                                                               ;;
;;                                                                          ;;
;;          t = iy + (iy>>1);                                               ;;
;;                                                                          ;;
;;          /* return (123 * ix + 51 * iy) / 128; */                        ;;
;;          return (ix - (ix>>5) - (ix>>7)  + (t>>2) + (t>>6));             ;;
;;      }                                                                   ;;
;;                                                                          ;;
;;  CODESIZE                                                                ;;
;;      28 words                                                            ;;
;;                                                                          ;;
;;  CYCLES                                                                  ;;
;;      150 to 178 cycles for DIST_FAST.                                    ;;
;;      124 to 140 cycles for DIST_FAST.1.                                  ;;
;;                                                                          ;;
;; ======================================================================== ;;

DIST_FAST   PROC
            SUBR    R0,     R2  ;   6
            ADCR    PC          ;   7 Skip negr if R2 was greater than R0
            NEGR    R2          ;   6
                                ;----
                                ;  13 best case
                                ;  19 worst case

            SUBR    R1,     R3  ;   6
            ADCR    PC          ;   7 Skip negr if R3 was greater than R1
            NEGR    R3          ;   6
                                ;----
                                ;  26 best case
                                ;  38 worst case

@@1:        CMPR    R2,     R3  ;   6  Put larger value in R3
            BC      @@no_swap   ; 9/7 
            XORR    R2,     R3  ;   6 \
            XORR    R3,     R2  ;   6  |-- Swap R2 and R3 if necessary.
            XORR    R2,     R3  ;   6 /
                                ;----
                                ;  41 best case
                                ;  69 worst case
@@no_swap:
            MOVR    R2,     R1  ;   6
            SLR     R1,     1   ;   6
            ADDR    R1,     R2  ;   6 t = iy + (iy >> 1)

            MOVR    R3,     R1  ;   6
            SLR     R1,     2   ;   8
            SLR     R1,     2   ;   8
            SLR     R1,     1   ;   6 R1 = ix >> 5
            SUBR    R1,     R3  ;   6 R3 = ix - (ix>>5)
            SLR     R1,     2   ;   8 R1 = ix >> 7
            SUBR    R1,     R3  ;   6 R3 = ix - (ix>>5) - (ix>>7)
            SLR     R2,     2   ;   8 R2 = t >> 2
            ADDR    R2,     R3  ;   6 R3 = ix - (ix>>5) - (ix>>7) + (t>>2)
            SLR     R2,     2   ;   8
            SLR     R2,     2   ;   8 R2 = t >> 6
            ADDR    R2,     R3  ;   6 R3 = ix - (ix>>5) - (ix>>7) + (t>>2) + (t>>6)
                                ;----
                                ; 143 best case
                                ; 171 worst case

            JR      R5          ;   7
                                ;----
                                ; 150 best case
                                ; 178 worst case
            ENDP

;; ======================================================================== ;;
;;  End of File:  dist_fast.asm                                             ;;
;; ======================================================================== ;;
</pre>