circle containing greatest number of points
One thing you might consider as a speed optimization is substituting the actual distance calculation with a less accurate heuristic, such as Carmack's inverse or the Manhattan distance metric. To be accurate, you'd still need to calculate the actual Euclidean distance if the result is inconclusive.
Quote:Original post by irreversible
One thing you might consider as a speed optimization is substituting the actual distance calculation with a less accurate heuristic, such as Carmack's inverse or the Manhattan distance metric. To be accurate, you'd still need to calculate the actual Euclidean distance if the result is inconclusive.
You never have to take the sqrt, you can always stay squared:
sqrt((x1-x2)^2 + (y1-y2)^2) < 0.5*r <==> (x1-x2)^2 + (y1-y2)^2 < 0.25 * r^2
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.
Quote:Original post by taz0010
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.
There's a SSE instruction that computes an approximated reciprocal of the square root (see rsqrtps). This probably means that Carmack's trick is now implemented in hardware.
Quote:Original post by taz0010
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.
I use distance calc extensively in my Boids simulator and profiled the Carmack trick, this one and the regular calculation. The 'optimizations' were actually slower than just running the distance calc.
Author
As a newbie to gamedev.net, I'm delighted that see that postings receive such interest and attention. Something tells me I'm gonna like it here. :-)
Quote:Original post by alvaroQuote:Original post by taz0010
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.
There's a SSE instruction that computes an approximated reciprocal of the square root (see rsqrtps). This probably means that Carmack's trick is now implemented in hardware.
With the only catch being that it isn't actually Carmack's ;-) It's only famous because of him, but it's not actually his.
Quote:Original post by cache_hitQuote:Original post by alvaroQuote:Original post by taz0010
There's a SSE instruction that finds the square root, so there's no need for the optimisation unless you're targeting an old machine.
There's a SSE instruction that computes an approximated reciprocal of the square root (see rsqrtps). This probably means that Carmack's trick is now implemented in hardware.
With the only catch being that it isn't actually Carmack's ;-) It's only famous because of him, but it's not actually his.
Oh, I know. I am referring to it as "Carmack's trick" because that's the name that was used elsewhere in the thread. Sorry I seem to have added to the myth that it's Carmack's code. There is a kinda inconclusive article about the origin of the code here, which leaves me without a good name for it. Any suggestions?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement