Sign in to follow this  
neonoblivion

Distance Function

Recommended Posts

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by pichu
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. [...] 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:
http://groups.google.com/group/comp.graphics/msg/f610d24d5fcd2ee6

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

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
It 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[i]+R[i])/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 this post


Link to post
Share on other sites
Quote:
Original post by Christer Ericson
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)?

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this