Sign in to follow this  
nerco666

Another way for 2D Rotation?

Recommended Posts

I completed my one method for 2D Rotation, but I was wondering if there is a better or shorter method for 2D Rotation. The shortest I've found is cos(theta)*x - sin(theta)*y; sin(theta)*x + cos(theta)*y; I just want to know if there is a shorter way to acomplish this. Thanks! N

Share this post


Link to post
Share on other sites
If rotating by a specific angle is what you want to do then not really, but you can precalculate those trig functions and put them in a matrix and then rotation becomes a single matrix multiplication. It makes code a bit more readable and runs faster if you frequently rotate by the same angles(since you don't calculate the sin/cos again). Then if you use a 3x3 matrix you can put translation into matrices as well and string those together with rotations,scaling,skewing, etc, all into a single local to world space matrix for each object. Mathematically speaking it's equivalent, but storing and manipulating all your transformations as matrices makes things appear cleaner and simpler.

For specific problems angles can be avoided altogether in favor of vector solutions, but I'd need more information about why you're rotating to give any more useful advice.

Share this post


Link to post
Share on other sites
The rotation is absolutely fine and there is no shorter way.

Why would you want to have a shorter way? Efficiency? Don't temper with early optimization. It will only slow down your programming progress. Computers (and also Smartphones) are fast enough for such computations.

Cheers

Share this post


Link to post
Share on other sites
If you are familiar with complex numbers, 2D rotation can also be expressed as a the unit-length complex number r=cos(alpha)+i*sin(alpha). In order to apply the rotation to a point, write the point as a a complex number z=x+i*y and simply compute z*r.

Another formula for r is exp(i*alpha), but don't worry about it if you don't understand it.

In the end, the operations are exactly the same, but thinking about it in terms of complex numbers helps me remember the formula better, and can make the code cleaner.

Share this post


Link to post
Share on other sites
Thanks for your replies, but could I ask for a basic example of using complex numbers in rotations?


"r=cos(alpha)+i*sin(alpha)"
Would I apply that formula for both X and Y drawing?

Example:

d[0] = a[0] - b[0];
d[1] = a[1] - b[1];

float r[2];

r[0] = d[0] * (cos(c) + I * sin(c));
r[1] = d[1] * (cos(c) + I * sin(c));

I don't think I am understanding this very well..But would you give me a brief explanation?

Thanks,

N

Share this post


Link to post
Share on other sites
#include <iostream>
#include <complex>
#include <cmath>

std::complex<double> const I(0.0,1.0);
double const PI=std::atan(1.0)*4.0;

int main() {
std::complex<double> z(10.0,0.0);
std::complex<double> r = std::exp(PI/4*I);

std::cout << "Original point: " << z << '\n';
std::cout << "Rotated point: " << (z*r) << '\n';
}




EDIT: If you still need an explanation, ask again.

Share this post


Link to post
Share on other sites
I googled this because I had no clue how complex number multiplication worked. Here's a short primer on it. You only need to read up to the red equation, really.

However, if you simplify that, you basically get the very same equations that you had in your first post. Which makes sense, I guess.

Share this post


Link to post
Share on other sites
If you think of complex numbers in their polar form, multiplication multiplies the moduli and adds up the arguments. Therefore, multiplying z by a complex number r with modulus 1 will result in a complex number with the same modulus as z and an argument that is that of z plus that of r. That's precisely the rotation you want.

You can verify this easily:
z = x + yi
r = cos(alpha) + sin(alpha)*i
z*r = (x + yi) * (cos(alpha) + sin(alpha)*i) = x*cos(alpha) - y*sin(alpha) + (x*sin(alpha) + y*cos(alpha))*i


You can see that the real and imaginary parts of the result are precisely what you posted at the top of the thread.

Euler's identity says that exp(i*alpha) = cos(alpha) + sin(alpha)*i, which my code exploits. Of course, the implementation will probably use cos() and sin() under the hood, so it's not going to be any faster. I find it a little cleaner, though.

Share this post


Link to post
Share on other sites
Thank you guys for your help.

Btw assuming "yi" is the difference between the 2 points on the y axis should i negate it since "i = negative exponent"

so a.y - - b.y = a.y + b.y..

Thanks!

[Edited by - nerco666 on March 15, 2010 8:35:17 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by nerco666
Thank you guys for your help.

Btw assuming "yi" is the difference between the 2 points on the y axis should i negate it since "i = negative exponent"

so a.y - - b.y = a.y + b.y..

Thanks!


I have no idea what you mean by that. I don't know what "2 points" you are talking about, and there is nothing negative about i... Perhaps you can try to reformulate your question more clearly.

Share this post


Link to post
Share on other sites
here is how I do simple rotation. Keep the cos and sin calcs out of the loop for speed. More speed could be gained if you put the cos and sin values into tables.

Don't try to setup a matrix to do this because it would be much slower.

cos1 = cos(ang);
sin1 = sin(ang);

for ( c = 0 ; c < vertcount ; c++ ) {
newx = vertx[c] * cos1 + verty[c] * sin1;
newy = verty[c] * cos1 - vertx[c] * sin1;
// store newx and newy here
}

Share this post


Link to post
Share on other sites
Quote:
Original post by ejthayer
Don't try to setup a matrix to do this because it would be much slower.

That is completely untrue. The matrix multiplication will perform the exact same calculations, and would be very similar in speed if this is the only transformation being done. If more than one or two transformations is being done their matrices can be concatenated and several operations can be done at one time with a single matrix multiplication, which will be much faster.

http://en.wikipedia.org/wiki/Transformation_matrix

Share this post


Link to post
Share on other sites
If we're discussing a purely mathematical exercise, the previous posters have explained things better than I can.

If there's a specific reason why you're trying to speed up rotation, it would be useful to know some more details. Depending on what you're using this code for, there is plenty of room for optimization at higher levels.

For example, if you're rotating a bitmap, you can calculate some x and y deltas at the start, then most of the actual pixels getting rotated will only require addition and table lookups. Other situations will have different optimization paths.

Share this post


Link to post
Share on other sites
For arbitrary rotations there is nothing faster than a matrix for rotating a vector.

The only possible optimization to a matrix can be made if you know that certain elements of a matrix are either 1, -1, or 0, by employing the simple, yet fundamental rule








The case of having matrix elements with 1's, -1's or 0's only happens when the angle is at 90o intervals. In such cases the matrix multiplication reduces to

Share this post


Link to post
Share on other sites
Some rotation problems involve knowing the rotation angle to begin with - for instance, the user may input the angle and the power of the gun on a tank before firing. However, most rotation problems don't initially involve angles.

The most common case is when you want to align two vectors on an object. For instance, you want to point a cannon at a duck. There is a vector that points from the center of the cannon down the muzzle of the cannon, and there is a vector that points from the center of the cannon to the duck. You want to rotate the cannon so that these vectors are aligned.

Here is a function that finds the value of the sin and cosine without all of the messy trig and inverse trig functions, using as input the initial vector i (the cannon muzzle), and the final vector f (the duck).


void findSinCos(const vec2& i, const vec2& f, float& sin, float& cos)
{
float xx = i.x*f.x;
float xy = i.x*f.y;
float yx = i.y*f.x;
float yy = i.y*f.y;

cos = xx + yy; //vector dot product
sin = xy - yx; //vector cross product in 2D

//find normalization constant
float norm = xx*xx + xy*xy + yx*yx + yy*yy;
norm = 1.0f / sqrt(norm);

//apply normalization constant
cos *= norm;
sin *= norm;
}


More than half of the cost of this funciton is performing normalization, but it is cheaper to do it here rather than normalizing the vectors externally and passing them in. If you have the normalized vectors sitting around for other purposes anyway, just make a similar function that leaves out the normalization step.

Now make a function to construct the matrix


void findRotMatrix(const vec2& i, const vec2& f, mat22& mat)
{
float s, c;

findSinCos(i, f, s, c);

mat.m00 = c;
mat.m11 = c;
mat.m01 = -s;
mat.m10 = s;
}

Share this post


Link to post
Share on other sites
Since 2D rotation matrices are all of the form

(p q)
(-q p)

you can simply store p and q. I would call that an optimization. In other words, use unit-length complex numbers the way I described earlier. :)

The equivalent of findSinCos() and findRotMatrix() in terms of complex numbers is simply this:
typedef std::complex<double> Complex;

// Find the rotation that when applied to a yields something aligned with b
Complex find_rotation(Complex a, Complex b) {
Complex d = b/a;
return d / d.abs();
}


Share this post


Link to post
Share on other sites
Cast the two vectors I and F as complex numbers




Now divide F by I



Now, if you want to take into account the fact that I and F might not be normalized, you would multiply this by the fraction |I|/|F|. The result is



If I and F are unit length, then the denominator is 1.

Notice that the real and imaginary parts correspond exactly with the cosine and sine terms in the function findSinCos. Thus - it is the exact same amount of computational work. The complex version only has less code because you've overloaded the divide operator.

Not that I am against using complex numbers to represent rotations. Complex numbers are basically the 2D version of quaternions. If you would like to see how to extend your find_rotation function to 3D - i.e. using quaternions instead of complex numbers - you can look at an article on my blog. Look toward the bottom. The function at the bottom is the quaternion equivalent of your find_rotation function, (without overloaded operators.)

[Edited by - Eric_Brown on March 17, 2010 8:34:27 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Eric_Brown
[...]

Notice that the real and imaginary parts correspond exactly with the cosine and sine terms in the function findSinCos. Thus - it is the exact same amount of computational work. The complex version only has less code because you've overloaded the divide operator.


Of course it's the same amount of computation. The only possible performance difference is that your code stores the result using four floating-point numbers, and mine uses only two.

But the real advantage of expressing it as operations on complex numbers is that it's much much shorter and easier to get right. I didn't overload the divide operator: The standard C++ library did it for me. As I said, fewer opportunities for me to mess up.

As you mention, using complex numbers to represent 2D rotations is similar in spirit to using quaternions for 3D rotations, but it's a lot easier to fit in your head. Perhaps that is really the biggest reason to learn how to use complex numbers in this fashion.

Share this post


Link to post
Share on other sites
Alvaro - I'm not sure if you know that I totally agree with you. For those with eyes to see, expressing a 2D rotation with a complex number is far simpler than using a matrix, however most game programmers I've met would probably feel less comfortable with complex numbers than matrices. I personally would avoid using the pre-canned arithmetic operations, since you can't optimize the resulting expression.

Your function finds a complex number that represents rotation. To extend the formula to 3D you would find a quaternion that represents a rotation. In the 2D case, the rotation complex number could be expressed by using 2 unit length vectors that represent the initial and final vectors.



The quaternion version of this formula is very similar, but a rotation quaternion involves cosines and sines of the half angle, not the full angle. Rather than multiplying the F vector by the conjugate of the I vector, you multiply F by the conjugate of a vector halfway between. If both of the input vectors are normalized, the halfway vector is just the average of the two. Since the average of two vectors is not normalized, you will need to normalize the halfway vector.



(NOTE: the hat symbol ^ means that you normalize the result of adding the vectors together)



This is the quaternion that will rotate I into F

[Edited by - Eric_Brown on March 17, 2010 11:20:21 PM]

Share this post


Link to post
Share on other sites
You can precalculate the sin and cos values, or have fun making use of the identity "sin^2(angle) + cos^2(angle) == 1" to derive the sin from cos, or you can do away with trig entirely if you obtain the angle via dot products of the appropriate vectors etc.

But no it doesn't get any simpler than four multiplications and two additions/subtractions, because a rotation is fundamentaly a linear combination of your existing variables. That's as simple as it gets:
newx = cos_theta*x - sin_theta*y;
newy = sin_theta*x + cos_theta*y;

Share this post


Link to post
Share on other sites
Quote:
Original post by Eric_Brown
Alvaro - I'm not sure if you know that I totally agree with you. For those with eyes to see, expressing a 2D rotation with a complex number is far simpler than using a matrix, however most game programmers I've met would probably feel less comfortable with complex numbers than matrices.

Yes, I know you agree, and I am aware of this being a less natural way to think about the Math for game programmers. I am just preaching to see if I can change the situation. :)

Quote:
I personally would avoid using the pre-canned arithmetic operations, since you can't optimize the resulting expression.

Here we disagree. The compiler has been better than me at optimizing code for a while now. If I have a profiler telling me that some of my functions involving complex numbers are taking up a long time, and only in that case, I will consider not using pre-canned arithmetic operations.

I know how to find the most natural rotation that maps one vector to another using quaternions. If you do it carefully, you can actually avoid evaluating any trigonometric functions, since sin(theta/2) and cos(theta/2) can be computed from the value of cos(theta). Did you think about that?

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
I am just preaching to see if I can change the situation. :)


a worthy endeavor

So, if you wanted to employ the double angle identity, you would dot the normalized input vectors to get cos(θ) (3 mults, 2 adds). Then you could employ the double angle identity to get cos2(θ/2) (1 add, 1 mult). You then employ the pythagorean identity to get sin2(θ/2) (1 subtraction). You take the square root of these (2 square roots).

To find the axis, you cross the input vectors (6 mults, 3 subtractions), and normalize (3 mults, 2 adds, 1 square root, 1 divide). You then multiply the sin(θ/2) with the axis (3 mults).

The total budget of this is:
3 square roots
1 divide
16 mults
9 add/subtract

The formula I provided (i.e. multiply the final vector by the conjugate of the halfway vector) has the following budget:
1 square root
1 divide
15 mults
9 add/subtract

Share this post


Link to post
Share on other sites
Quote:
Original post by Eric_Brown
[...]

The total budget of this is:
3 square roots
1 divide
16 mults
9 add/subtract

The formula I provided (i.e. multiply the final vector by the conjugate of the halfway vector) has the following budget:
1 square root
1 divide
15 mults
9 add/subtract


Doesn't your formula also involve one acos(), one cos() and one sin()? Or perhaps I didn't understand your formula?
[EDIT: Indeed, I just went to your blog and I see that I must have missed something. I'm a bit busy now, but I'll carefully read that text later. [FURTHER EDIT: Got it. Using a half-way vector to quickly obtain the cos(theta/2) and the rotation vector already scaled to sin(theta/2) is very nice. Now back to work. :) ]]

Share this post


Link to post
Share on other sites

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