Distance Function
Author
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);
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)
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.
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(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...
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...
Quote:Original post by pichuWhat you posted isn't due to LaMothe, and I hope he doesn't present it as it is. The approximation
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...
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 SneftelIs 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)?
It produces values which are only 1% and 6% off the correct values, actually. Surprisingly good.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
