Jump to content
  • Advertisement
Sign in to follow this  
neonoblivion

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.

If you intended to correct an error in the post then please contact us.

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


Link to post
Share on other sites
Advertisement
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
Quote:
Original post by Scuppy
Try using x=1, y=1 and z=1, or x=1, y=1 and z=0. Shouldnt that return 1?

No.

Share this post


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

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+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 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!