6 ms·

Taking the dot product of the [x,y] with the 8 directions and picking the one with the largest magnitude might be faster in some cases.

by thexa4 4y ago

rocqua 4y ago
You only need 4 directions, and can look at the sign of the dot-product.
tgv 4y ago
Good idea. Only four inproducts and comparisons are needed: the other four have the same value, but negated. Might be SIMD-able.
- Someone 4y ago
  I was thinking about a more complicated approach (edit2: that ends up simpler). A 4-way version of this can be done with two comparisons (if x > y to check on what side of one diagonal the point lies and if x > -y to check the same for the other diagonal, plus some bit twiddling to get the required two bits out). One can do that, rotate by 45 degrees, do that again, and do some further bit manipulation to combine the two bits of the first 4-way version with those of the second into the three bits this should produce. That would be four comparisons, a 2×2 matrix multiplication (edit: that’s a matrix-vector multiplication) with a known-ahead rotation matrix (naively, that would be 8 (edit: 4) multiplications and 4 (edit: 2) additions, but I think we can lose those multiplications because all elements of a 45 degree rotation matrix have absolute value 1/√2 and the problem is scale-invariant) and some bit twiddling. Now, make that branchless… Edit2: and of course, you can do both splits into quadrants by just looking at the signs of x and y. That rotates the four quadrants by 45 degrees, but that doesn’t matter. That makes the 4-way version simply (x>0) + 2 × (y>0): two comparisons and a bit shift. twoBits = (x > 0) + 2 × (y > 0) x’ = x + y y’ = x - y twoMoreBits = (x’ > 0) + 2 × (y’ > 0) (Some bit twiddling with ‘twoBits’ and ‘twoMoreBits’ Feel free to compute those bit pairs differently if it makes the bit twiddling easier)

Taking the dot product of the [x,y] with the 8 directions and picking the one with the largest magnitude might be faster in some cases.

by thexa4 4y ago

Taking the dot product of the [x,y] with the 8 directions and picking the one with the largest magnitude might be faster in some cases.

rocqua 4y ago

You only need 4 directions, and can look at the sign of the dot-product.

tgv 4y ago

Good idea. Only four inproducts and comparisons are needed: the other four have the same value, but negated. Might be SIMD-able.

Someone 4y ago
I was thinking about a more complicated approach (edit2: that ends up simpler). A 4-way version of this can be done with two comparisons (if x > y to check on what side of one diagonal the point lies and if x > -y to check the same for the other diagonal, plus some bit twiddling to get the required two bits out). One can do that, rotate by 45 degrees, do that again, and do some further bit manipulation to combine the two bits of the first 4-way version with those of the second into the three bits this should produce. That would be four comparisons, a 2×2 matrix multiplication (edit: that’s a matrix-vector multiplication) with a known-ahead rotation matrix (naively, that would be 8 (edit: 4) multiplications and 4 (edit: 2) additions, but I think we can lose those multiplications because all elements of a 45 degree rotation matrix have absolute value 1/√2 and the problem is scale-invariant) and some bit twiddling. Now, make that branchless… Edit2: and of course, you can do both splits into quadrants by just looking at the signs of x and y. That rotates the four quadrants by 45 degrees, but that doesn’t matter. That makes the 4-way version simply (x>0) + 2 × (y>0): two comparisons and a bit shift. twoBits = (x > 0) + 2 × (y > 0) x’ = x + y y’ = x - y twoMoreBits = (x’ > 0) + 2 × (y’ > 0) (Some bit twiddling with ‘twoBits’ and ‘twoMoreBits’ Feel free to compute those bit pairs differently if it makes the bit twiddling easier)