Distance forumla without square roots?
Author
Is there a way to caculate the distance without having to use a square root function/operator. Mainly because i will be using quite a few square root calls and this will slow the game any tips/equations/tricks/suggestions.
Killer Eagle Software
Don''t apply square root unless you absolutely need the actual distance. For comparisons just use the squared value.
AFAIK, you can''t evaluate the distance without the square root. However, there are many tricks to avoid square root operations:
- When comparing distances, compare the squared distances to avoid sqrt altogether
- Try to keep your vector normalized. For example, the cross product of two normalized vectors is a normalized vector, so it does not need to be normalized again
- You can use "Manhattan distance" to roughly approximate the distance between two points. Make a Google search; it''s a simple concept
- You could also expand the sqrt yourself using a Taylor series, and use only the first terms to get a decent approximation
- Remember that premature optimization is the root of all evil. Nowadays, square roots are not that expensive (IIRC, some processors have a dedicated sqrt instruction). Always profile your code.
HTH,
Cédric
- When comparing distances, compare the squared distances to avoid sqrt altogether
- Try to keep your vector normalized. For example, the cross product of two normalized vectors is a normalized vector, so it does not need to be normalized again
- You can use "Manhattan distance" to roughly approximate the distance between two points. Make a Google search; it''s a simple concept
- You could also expand the sqrt yourself using a Taylor series, and use only the first terms to get a decent approximation
- Remember that premature optimization is the root of all evil. Nowadays, square roots are not that expensive (IIRC, some processors have a dedicated sqrt instruction). Always profile your code.
HTH,
Cédric
Being dumb/factious, but if you switch metric spaces you could have any distance function you wanted :-). Ok, that was a dumb joke, I''ll stop now :-)....
Jesse...
Jesse...
"- Try to keep your vector normalized. For example, the cross product of two normalized vectors is a normalized vector, so it does not need to be normalized again"
This is true for perpendicular unit vectors.
This is true for perpendicular unit vectors.
Right, sorry. Bad Cedric.
Anyway, what''s with all the sqrt threads this week? Stupid search function... Can''t blame the newbies anymore...
Cédric
Anyway, what''s with all the sqrt threads this week? Stupid search function... Can''t blame the newbies anymore...
Cédric
quote:Original post by laeuchli
Being dumb/factious, but if you switch metric spaces you could have any distance function you wanted :-). Ok, that was a dumb joke, I''ll stop now :-)....
Jesse...
I do all my distance calculations in N∞
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
Out of curiosity, Fruny, what is N-shmock?
How do you do those shmock-infinity things anyway? You always have a nice looking summation symbol, while we, lowly earthlings, have to use ASCII art. Unfair!
¦²
I can use charmap, but it's really long to find the symbol.
C¨¦dric
EDIT: No, apparently, using charmap only messes up my post
Σ
Success!
Ty, OrangyTang
[edited by - cedricl on October 19, 2002 12:00:12 PM]
[edited by - cedricl on October 19, 2002 2:04:27 PM]
[edited by - cedricl on October 19, 2002 2:04:45 PM]
[edited by - cedricl on October 19, 2002 2:05:00 PM]
[edited by - cedricl on October 19, 2002 2:05:46 PM]
[edited by - cedricl on October 19, 2002 2:06:16 PM]
How do you do those shmock-infinity things anyway? You always have a nice looking summation symbol, while we, lowly earthlings, have to use ASCII art. Unfair!
¦²
I can use charmap, but it's really long to find the symbol.
C¨¦dric
EDIT: No, apparently, using charmap only messes up my post
Σ
Success!
Ty, OrangyTang[edited by - cedricl on October 19, 2002 12:00:12 PM]
[edited by - cedricl on October 19, 2002 2:04:27 PM]
[edited by - cedricl on October 19, 2002 2:04:45 PM]
[edited by - cedricl on October 19, 2002 2:05:00 PM]
[edited by - cedricl on October 19, 2002 2:05:46 PM]
[edited by - cedricl on October 19, 2002 2:06:16 PM]
Surely you could convert the manhatten distance to the distance via trig? Although that would add the use of sine/cosine ∴ may not be any faster..
√ does seem to be a popular topic recently.. Oh, and Σ is html code & # 9 3 1 ;
√ does seem to be a popular topic recently.. Oh, and Σ is html code & # 9 3 1 ;
quote:Original post by cedricl
Out of curiosity, Fruny, what is N-shmock?
As a general rule :
||x||m; = ( Σk=0..n |xk|m )1/m
||x||∞ = maxk=0..n |xk|
quote:
How do you do those shmock-infinity things anyway?
Standard HTML character codes : http://www.w3.org/TR/REC-html40/sgml/entities.html.
& = &
∞ = ∞
Σ = Σ
And so on.
quote:You always have a nice looking summation symbol, while we, lowly earthlings, have to use ASCII art. Unfair!
Take me to your leader. Resistance is futile, you will use ISO C++.
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
[edited by - Fruny on October 19, 2002 3:39:08 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
