Difference between revisions of "Dist fast.asm"
m (→Notes) 
m (Protected "Dist fast.asm" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))) 
(No difference)

Latest revision as of 08:16, 4 December 2010
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 quicklyunder 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 overestimate rather than underestimate 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 ;; ;; 22Apr2002 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 deltaX (eg. abs(x0  x1)) ;; ;; R3 Absolute value of deltaY (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 16bit values for the incoming ;; ;; coordinates, and should correctly calculate abs(x0  x1) ;; ;; and abs(y0  y1) for the full 16bit range. ;; ;; ;; ;; The output should have the same dynamic range as the inputs. ;; ;; Thus, if the inputs are in an 8bit range, so will be the ;; ;; output. If the inputs are in a 16bit 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 ;; ;; ;; ;; /* 2D 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 ;; ;; ======================================================================== ;;