Sign in to follow this  

Fast Distance Approximation

This topic is 4131 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've implemented ropes in my simulation, but it gets really slow with many ropes and many particles. Does anyone know a way to quickly approximate the distance between two points, or maybe a fast square root approximation? Thanks in advance, Mr. Big

Share this post


Link to post
Share on other sites
You might want to look into SSE. It has special operations for fast square root and fast inverse square root. Since you're simulating many ropes and particles you're probably applying the same algorithms to them. If this is the case using SSE could result in up to a 4x improvement in speed (assuming a good implementation) since it performs 4 floating point operations in parallel.

Share this post


Link to post
Share on other sites
Quote:
Original post by mrbig
Does anyone know a way to quickly approximate the distance between two points, or maybe a fast square root approximation?


d = (A.a - B.a)*(A.a - B.a) + (A.b - B.b) * ...
or
d = (A - B) dot (A - B)


Re SSE

If it will not be killed in throughput and latency.

Share this post


Link to post
Share on other sites
Quote:
Original post by Raghar
d = (A.a - B.a)*(A.a - B.a) + (A.b - B.b) * ...
or
d = (A - B) dot (A - B)

This will compute |A-B|², the square of the distance.

If you can tolerate a maximum error of 6.5%, you should use an octagonal approximation: Approximate the unit circle with an octagon, giving a case-analysis on eight linear functions. The hexadecagon approximation is better yet, but (although still considerably faster than a sqrt) is a fair bit slower than the octagonal function, and is a pain to code.

More accurate approximations yet can be produced using Richardson Extrapolation (daniel_i_l's article seems like a good implementation) and if you are prepared to do the work yourself, you can tailor the speed/error tradeoff to suit your needs.

Regards
Admiral

Share this post


Link to post
Share on other sites

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