# Distance Function

This topic is 4541 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

This seems to work with really good precision. Is there a name for this operation? x=abs(x); y=abs(y); z=abs(z); d=(((x+y)-(x*y/2))+z)-(((x+y)-(x*y/2))*z/2);

##### Share on other sites
Huh, I haven't seen that one before. Where did you come across it?

##### Share on other sites
That doesnt make sense. You mean distance from (0,0,0)? Try using x=1, y=1 and z=1, or x=1, y=1 and z=0. Shouldnt that return 1? I'd be suprised if you could derive a formula for distance that doesnt involve a square root somewhere, although I'm not a maths buff.

Usually you'd use euclidean geometry:

d = Sqrt(X*X + Y*Y + Z*Z) for distance from (0,0,0)

##### Share on other sites
Quote:
 Original post by ScuppyTry using x=1, y=1 and z=1, or x=1, y=1 and z=0. Shouldnt that return 1?

No.

##### Share on other sites
Umm I mean root3 and root2.

##### Share on other sites
It produces values which are only 1% and 6% off the correct values, actually. Surprisingly good.

##### Share on other sites
I think I recall seeing something like that in one of Andre LaMothe's books... it looks similar, can't recall off the top of my head.

Edit: or maybe not...
His function doesn't really fit on one line
int x=fabs(fx) * 1024;
int y=fabs(fy) * 1024;
int z=fabs(fz) * 1024;
if(y<x) SWAP(x,y)
if(z<y) SWAP(y,z)
if(y<x) SWAP(x,y)
int dist = (z+11*(y>>5)+x>>2));
return( (float)( dist>>10) );

Accuracy of ~8% ?

he said it had to do something with Taylor/Maclaurin series expansion.. whatever that is. LaMothe does some incredible math stuff...

Thanks for yours by the way, that'll help with my cloth sim stuff...

##### Share on other sites
Quote:
 Original post by pichuI think I recall seeing something like that in one of Andre LaMothe's books... it looks similar, can't recall off the top of my head. [...] LaMothe does some incredible math stuff...
What you posted isn't due to LaMothe, and I hope he doesn't present it as it is. The approximation

max + (11/32)*med + (1/4)*min, where
max=Max(x,y,z),
med=Median(x,y,z), and
min=Min(x,y,z)

to sqrt(x^2+y^2+z^2) is from Jack Ritter's article "A fast approximation to 3D euclidian distance" (Graphics Gems, pp 432-433).

Edit: btw, here's Ritter's original post to comp.graphics back in 1989:

[Edited by - Christer Ericson on June 7, 2006 11:57:33 PM]

##### Share on other sites
Quote:
 Original post by SneftelIt produces values which are only 1% and 6% off the correct values, actually. Surprisingly good.
Is that for the formula the OP posted? Not sure how you'd get those errors for that formula (and why you have two errors). Are you assuming inputs in some limited range (i.e. prescaled values)?

The OP's formula when written out is:

x*y*z/4 - (x*y + x*z + y*z)/2 + x + y + z

For ease of error calculation, assume x=y=z. Then the formula simplifies to x^3/4 - 3*x^2/2 + 3*x. If you compute the limit of this expression divided by sqrt(3*x^2), which is the accurate sqrt for the vector x=y=z, you get infinity, which is usually deemed much larger than 6%! ;)

As a generic approximation it's pretty awful. It might do OK for certain fixed ranges of x, y, and z.

You can get reasonable approximations to the distance function by plugging a decent guess into the Newton-Raphson formula for sqrt: R[i+1] = (N/R+R)/2. For example, if you start with the guess |x|+|y|+|z| for the root, then one round of NR gives:

sqrt(x^2+y^2+z^2) ~= (x^2 + y^2 + z^2 + |x*y| + |x*z| + |y*z|)/(|x| + |y| + |z|)

If you compute the limit of this expression over sqrt(3*x^2) for x=y=z you'll get roughly a 15% error.

Obviously there are many other approximations one can do as well.

##### Share on other sites
Quote:
 Original post by Christer EricsonIs that for the formula the OP posted? Not sure how you'd get those errors for that formula (and why you have two errors). Are you assuming inputs in some limited range (i.e. prescaled values)?

My reply was to Scuppy's examples.
Quote:
 For ease of error calculation, assume x=y=z.

Yes, x=y=z appears to be the worst case scenario.

1. 1
2. 2
Rutin
13
3. 3
4. 4
5. 5

• 9
• 9
• 14
• 12
• 10
• ### Forum Statistics

• Total Topics
633262
• Total Posts
3011128
• ### Who's Online (See full list)

There are no registered users currently online

×