Dist fast.asm

From Intellivision Wiki

You do not have permission to edit this page, for the following reasons:

• The action you have requested is limited to users in the group: Administrators.
• This page has been locked to prevent editing.

You can view and copy the source of this page:

[[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>

Return to Dist fast.asm.