Sign in to follow this  

Efficient Distance Calculation?

This topic is 4579 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

I'm currently using:
public static double GetDistance( ref float x1, ref float x2, ref float y1, ref float y2 )
{
	return Math.Sqrt( ( x1 - x2 )*( x1 - x2 ) + ( y1 - y2 )*( y1 - y2 ) );
}

I call this function many, many, many times per second server-side on my 2D space sim. The number of calls grows exponentially for each player that joins the server, so my question is, am I doing this the best way? Is there a cheat to get around doing it so much? Thanks, Cyric

Share this post


Link to post
Share on other sites
Not really, if you are having performance issues with a 2D space sim you should probably be looking at the bigger picture. There may be some other areas you can improve performance on, quadtrees perhaps? i don't know what is causing the problems but i'm sure there are other areas that you should think about optimising first.

The only trick with distances that i can think of is that if you are just comparing distance, you can compare the distances squared which avoids using the square root function. But you probably already knew that.

Share this post


Link to post
Share on other sites
One optimization that can often be done is to simply not do the square root. Use this when all you care about is comparing two distances to each other to see which one is larger. In this situation, the square root is absolutely useless, as it doesn't change the result of the comparison.

[edit]Me.Slow == true[/edit]

Share this post


Link to post
Share on other sites
Quote:
Original post by DevLiquidKnight
to increase speed u can remove the square root and work with higher values [smile]

They won't necessarily be higher: sqrt(x) > x is true for any x < 1.0

Share this post


Link to post
Share on other sites
I would suggest returning float (not double) and inlining it. A good compiler should eliminate the common sub expressions without creating the 2 extra variables.

I always...when in doubt cheat by looking at what the compiler actual does by examining the output .asm or .cod files.

Share this post


Link to post
Share on other sites
No idea why you'd have to compute distances every frame, but in any case either don't use sqrt like others said, or there are ways of approximating sqrt, which I dare not go into.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You may also be advised to look at your design and to why your execution is O(N^N)

[I'm assuming you actually did mean exponential rather than something like O(N^2)]

You can achieve a lot by saving the results of distance computations (the old space vs execution time trade-off).

Share this post


Link to post
Share on other sites
Hey, im new here and im a junior programmer pretty much, but i did some projects for mathematic calculators and collision detection....i know that newton had a very efficient method of solving square roots.....i also have a method, im not sure if its as fast as you'd like but the good thing about it is that u can give it the accuracy you want. If you need the code i'll be glad to share

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I heard somewhere that using double now is actually faster than using floats on modern computers.

Is this true?


i beleive this is true only on 64 bit processors with 64 bit o/s's

Share this post


Link to post
Share on other sites
Quote:
Original post by lunar-blue
Hey, im new here and im a junior programmer pretty much, but i did some projects for mathematic calculators and collision detection....i know that newton had a very efficient method of solving square roots.....i also have a method, im not sure if its as fast as you'd like but the good thing about it is that u can give it the accuracy you want. If you need the code i'll be glad to share

Newton refinement approximation:
answer = (value/answer + answer) / 2;
It's not as efficient as a sqrt done in hardware, I bet. Division is pretty slow.

Share this post


Link to post
Share on other sites
If you are doing collision testing, there are much better ways. (just a guess).

Also note, you are missing abs's in your distance formula


tmpa = x1 - x2;
tmpb = y1 - y2;
out = tmpa + tmpb;
outa = tmpa - tmpb;
r = roa + rob; //Set collision boundries, roa = Radius of object a, same for rob
r *= r; //Square the other side of the equasion.
ra = -r;
if (out > r) | (outa < ra) {
//Collision
}


This works out about equal to


if (sqrt(abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2))) > r {
}


Just probably a bit faster for it.

You could also try using integers instead of floats. (unless you really need them).

From,
Nice coder

Share this post


Link to post
Share on other sites
Ok, so if you're having that big O n^n problem you should use an oct-tree or break up your space into sectors and give each of them an oct-tree.

Also, you can use a combination of dirty distance methods and accurate ones. So I'd say use something really dirty for most distances, but once you get close(like for a collision or something) re-calc for something more accurate.


Dirty method one: The octagon
// perfect on the axis, 18% average error
// 8+ times faster
// assuming all numbers are positive, or changed to be... x = abs(x);
d = 0.5*(x + y + ... + max(x, y, ..)); // generally
d = 0.5*(x + y + (x>y)?x:y); // c++ish 2d case


Dirty method two: Know your floating point, EDIT: this is for 32bit float
// perfect for powers of 2, 1.8% average error
// 6+ times faster
union{float f[2]; // store your x, y & z
unsigned int i[2];};// temp
i[0] <<= 1;
i[1] <<= 1;
i[0] -= 0x3F800000;
i[1] -= 0x3F800000;
f[0] += f[1];
i[0] += 0x3F800000;
i[0] >>= 1;
// f[0] is your final distance

EDIT: unless you're squaring complex numbers(normal float doesn't support) then you don't need to abs() your displacements (x1-x2)... we forgive him, the hour is late...


I see through the lies of the Jedi... to learn the true power of the code one must look at both sides and find their true power!

[Edited by - ismakefire on June 4, 2005 4:07:57 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by lunar-blue
Hey, im new here and im a junior programmer pretty much, but i did some projects for mathematic calculators and collision detection....i know that newton had a very efficient method of solving square roots.....i also have a method, im not sure if its as fast as you'd like but the good thing about it is that u can give it the accuracy you want. If you need the code i'll be glad to share


I use my own method, wich is the binary method.

Basically, you express number n in the form a * 2^0 + b * 2^1.... then you halve each exponent.

Dead simple in hw. (with some mods, it can be done without transisters at all).

In sw, you need tables tho...

Theres other things, like binary trees, ect. Which can be faster...

From,
Nice coder

Share this post


Link to post
Share on other sites
"Nice coder"

Can you please show an example of this process of sqrt-ing? (I don't mean code example - I mean just pick a number and show the process of sqrt-ing it)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by cyric74
I'm currently using:
*** Source Snippet Removed ***

I call this function many, many, many times per second server-side on my 2D space sim. The number of calls grows exponentially for each player that joins the server, so my question is, am I doing this the best way? Is there a cheat to get around doing it so much?

Thanks,
Cyric





WHy do you need the distance, and do you need the actual value or just use it for comparison against a threshold???

If only comparison, you need only compare the squares (no need for sqrt).

If it can be a rough distance to compare, you can do the clasic box test:
rough_dist = MAX(x2-x1, y2-y1, z2-z1);

You can also do whats called lazy evaluation where if you know the 2 objects
will not need to be processes if they are outside of a threshold distance, you first do a rough dist calc and then if its inside of your threshold then you do the costlier sqrt calculations.


Another estimation calc (that is only a few percent off) for 2D is adding the length of the longest delta (X or Y) to the shortest delta (Y or X) divided by 2.

dx = abs(x2-x1)
dy = abs(y2-y1)
if dx>dy dist=dx+(dy/2) else dist=dy+(dx/2)



Another idea (depending on how it is used) is to store the distances in a table
and then only update them on an interval proportinal to the distance (probably by distance intervals of squares).







Share this post


Link to post
Share on other sites
that works just fine for an int value into float, but that's basiclly what the 2nd method I showed does, but it transfers from powers of 2 linearly(which is why it's so fast). I've tried it and any use of tables will either be inaccurate(using an incomplete table) or slows it down to the point where you should just use a sqrt(if you use a complete table or linearly interpolate). Having a 18%, 2% and a 1%< function isn't a bad combination.Just remember to use them right. So if you're testing something bounded by 10 then use 12 for the first function(18%) and like 10.2 for the 2nd one(1.8%). Don't be afrad of using a function with a moderatly sized error, because all the floating point calculations you make have errors... we just like to ignore them :)

So I'd say use the three functions in conjuction with quad-trees(oct-trees are 3d) if you want a real speed up. Maybe even make the real memory for preformace trade off and slice up your space.

In the end, you are the programmer. Run some time tests and see what ranges work the best, and maybe just drop the calculation quality when there's a slow down rather then always having some distances a certen % off.

EDIT: will ppl PLEASE stop posting how you can compare two vector distances without the square root, it's been said 3 times! It would be nice if ppl would read the thread rather then just posting everything they know!

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
Also note, you are missing abs's in your distance formula


if (sqrt(abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2))) > r {
}


From,
Nice coder


Please define a number n where (n * n) != (abs(n) * abs(n) + e)
Where e is a small value.


As for the problem, you really have to tell us a bit more of what you are doing?

Share this post


Link to post
Share on other sites

This topic is 4579 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.

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