https://lemire.me/blog/2022/07/24/round-a-direction-vector-to-the-nearest-8-way-compass/ Skip to content Daniel Lemire's blog Daniel Lemire is a computer science professor at the University of Quebec (TELUQ) in Montreal. His research is focused on software performance and data engineering. He is a techno-optimist and a free-speech advocate. Menu and widgets * My home page * My papers * My software Subscribe Join 12,500 subscribers: Email Address [ ] [ ] [Subscribe by email] You can also follow this blog on telegram. Search for: [ ] [Search] Support my work! I do not accept any advertisement. However, you can support the blog with donations through paypal. Please consider getting in touch if you are a supporter so that I can thank you. You can also support my work on GitHub. Recent Posts * Round a direction vector to an 8-way compass * Science and Technology links (July 23 2022) * Negative incentives in academic research * How quickly can you convert floats to doubles (and back)? * Filtering numbers faster with SVE on Graviton 3 processors Recent Comments * Daniel Lemire on Round a direction vector to an 8-way compass * Lorin K. on Round a direction vector to an 8-way compass * Pierre B. on Round a direction vector to an 8-way compass * Daniel Lemire on Round a direction vector to an 8-way compass * The 8th mage on Round a direction vector to an 8-way compass Pages * A short history of technology * About me * Book recommendations * Cognitive biases * Interviews and talks * My bets * My favorite articles * My favorite quotes * My readers * My sayings * Predictions * Recommended video games * Terms of use * Write good papers Archives Archives [Select Month ] Boring stuff * Log in * Entries feed * Comments feed * WordPress.org Round a direction vector to an 8-way compass Modern game controllers can point in a wide range of directions. Game designers sometimes want to convert the joystick direction to get 8-directional movement. A typical solution offered is to compute the angle, round it up and then compute back the direction vector. double angle = atan2(y, x); angle = (int(round(4 * angle / PI + 8)) % 8) * PI / 4; xout = cos(angle); yout = sin(angle); If you assume that the unit direction vector is in the first quadrant (both x and y are positive), then there is a direct way to compute the solution. Using 1/sqrt(2) or 0.7071 as the default solution, compare both x and y with cos(3*pi/8) and cos(pi/8), and only switch them to 1 or 0 if they are larger than cos(3*pi/8) or smaller than cos(pi/8). The full code looks as follows: xout = 0.7071067811865475; yout = 0.7071067811865475; if (x >= 0.923879532511286) {// sin(3*pi/8) xout = 1; } if (y >= 0.923879532511286) {// sin(3*pi/8) yout = 1; } if (x < 0.3826834323650898) {// sin(pi/8) xout = 0; } if (y < 0.3826834323650898) {// sin(pi/8) yout = 0; } You can generalize the solution for the case where either x or y (or both) are negative by first taking the absolute value, and then restoring the sign at the end: bool xneg = x < 0; bool yneg = y < 0; if (xneg) { x = -x; } if (yneg) { y = -y; } double outx = 0.7071067811865475; double outy = 0.7071067811865475; if (x >= 0.923879532511286) {// sin(3*pi/8) outx = 1; } if (y >= 0.923879532511286) {// sin(3*pi/8) outy = 1; } if (x < 0.3826834323650898) {// sin(pi/8) outx = 0; } if (y < 0.3826834323650898) {// sin(pi/8) outy = 0; } if (xneg) { outx = -outx; } if (yneg) { outy = -outy; } You can rewrite everything with the ternary operator to entice the compiler to produce branchless code (i.e., code without jumps). The result is more compact. bool xneg = x < 0; x = xneg ? -x : x; bool yneg = y < 0; y = yneg ? -y : y; outx = (x >= 0.923879532511286) ? 1 : 0.7071067811865475; outy = (y >= 0.923879532511286) ? 1 : 0.7071067811865475; outx = (x < 0.3826834323650898) ? 0 : outx; outy = (y < 0.3826834323650898) ? 0 : outy; outx = xneg ? -outx : outx; outy = yneg ? -outy : outy; I wrote a small benchmark that operates on random inputs. Your results will vary but on my mac laptop with LLVM 12, I get that the direct approach is 25 times faster. with tangent 40 ns/vector fast approach 1.5 ns/vector Published by [2ca999] Daniel Lemire A computer science professor at the University of Quebec (TELUQ). View all posts by Daniel Lemire Posted on July 24, 2022July 25, 2022Author Daniel LemireCategories 5 thoughts on "Round a direction vector to an 8-way compass" 1. [d08192] The 8th mage says: July 25, 2022 at 12:06 am 1. Cos(atan(x)) has a nice identity as 1/sqrt(x^2+1), while sin is x/sqrt(x^2+1). What about implementing it that way? In this way you have a branch less solution which can be vectorized (although your scenario suggests there's only one vector). 2. it seems to me that you don't normalize the input vector. is the input circle in the unit disk? What happens if both x and y are lower than cos(3pi/8) then the vector will be zero, and you have the dead zone dependent on your rouding. If you assume the unit disk, can some of the branches be filded together in that scenario? Reply 1. [2ca999] Daniel Lemire says: July 25, 2022 at 12:21 am In this way you have a branch less solution which can be vectorized My version can be compiled to branchless code and is vectorizable. it seems to me that you don't normalize the input vector. We are assuming here that the direction vector has been normalized (it is a 'unit' direction vector). If you assume the unit disk, can some of the branches be filded together in that scenario? You can rewrite the the logic to have fewer apparent branches, but all my branches are subject to becoming mere selection (condition moves). I certainly do not claim that my code is the most efficient possible. In fact, I am sure you can do better !!! Reply 2. [c98e79] Pierre B. says: July 25, 2022 at 3:16 pm The original code could avoid both sin and cos by computing as value between 0 and 7 and a switch with hard-coded values. Your code would still be faster vy avoiding atan2, but by a lesser factor. Reply 1. [edc3dc] Lorin K. says: July 25, 2022 at 9:40 pm Remove the if, instead use a ternary operator and then we get branchless code when using clang. Funny that Clang only successfully goes branchless when using ternary operator instead of if. https://godbolt.org/z/so5hhqvMo Reply 1. [2ca999] Daniel Lemire says: July 25, 2022 at 10:13 pm Correct. Reply Leave a Reply Cancel reply Your email address will not be published. The comment form expects plain text. If you need to format your text, you can use HTML elements such strong, blockquote, cite, code and em. For formatting code as HTML automatically, I recommend tohtml.com. [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comment * [ ] Name * [ ] Email * [ ] Website [ ] [ ] Save my name, email, and website in this browser for the next time I comment. Receive Email Notifications? [no, do not subscribe ] [instantly ] Or, you can subscribe without commenting. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] You may subscribe to this blog by email. Post navigation Previous Previous post: Science and Technology links (July 23 2022) Terms of use Proudly powered by WordPress