Dist fast.asm
Revision as of 08:16, 4 December 2010 by Mr z (talk | contribs) (Protected "Dist fast.asm" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite)))
Functions Provided
| Entry point | Function provided | Notes |
|---|---|---|
| DIST_FAST | Find the approximate Euclidean distance between two points | Two pairs of (x, y) coordinates passed in registers |
| DIST_FAST.1 | Instead of raw coordinates, abs(ΔX) and abs(ΔY) passed in registers. |
See source code below for calling convention.
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.
| Error Magnitude | Key | Error Sign | Key | |||
|---|---|---|---|---|---|---|
 | 0px |  | DIST_FAST underestimates distance | |||
| 1px | ||||||
| 2px | ||||||
| 3px | ||||||
| 4px | ||||||
| DIST_FAST overestimates distance | ||||||
| 5px | ||||||
| 6px | ||||||
| 7px | ||||||
| 8px | ||||||
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 (ΔX / dist, ΔY / dist), this error will hardly be noticeable.
Source Code
;* ======================================================================== *;
;* 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 ;;
;; ======================================================================== ;;
