Distance Function

Huh, I haven't seen that one before. Where did you come across it?

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)

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.

Umm I mean root3 and root2.

It produces values which are only 1% and 6% off the correct values, actually. Surprisingly good.

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(yif(zif(yint 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...

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]

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.

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.