angle between vectors
Whats the most efficient way to find the angle between two vectors? basically I have a current heading and a target heading and I want to know if I should call my turnRight() or turnLeft() function based on if the angle is positive or negetive.
I'm using Ogre with the Vector3 class, but I'm only working on a 2 dimentional plane in this case. API doc is here http://www.ogre3d.org/docs/api/html/classOgre_1_1Vector3.html
It has a dotProduct() function and a getRotationTo() function.
A dot product returns a scalar of "how much", you just need to ArcSine or ArcCosine the value returned by a Dot Product operation to get the angle in degrees or radians, depending on the library. In most math libraries, the names of those funcions are asin, and acos. The return value of a dot product will range from -1.0 to 1.0, just like with a sine or cosine. asin and acosin will undo that sine or sin.
I don't know anything about Ogre, but you may have trouble with the dot product because dot products are always positive.
I don't know anything about Ogre, but you may have trouble with the dot product because dot products are always positive.
@Ridiculus - How can both arcsine and arcosine return the correct angle? Anyone want to shed some light onto which to use?
a . b = |a|*|b|*cos(theta)
where theta is the angle between the vectors a and b, |a| is the magnitude, and a . b is the dot product
You can use this to find the angle, although you have to use acos and sqrt twice... However if the vectors are normalized, you only need acos
or I guess you could rotate one vector to the x-axis, and rotate the other accordingly, then just use an atan on the other vector (with some case checking) to get the angle
where theta is the angle between the vectors a and b, |a| is the magnitude, and a . b is the dot product
You can use this to find the angle, although you have to use acos and sqrt twice... However if the vectors are normalized, you only need acos
or I guess you could rotate one vector to the x-axis, and rotate the other accordingly, then just use an atan on the other vector (with some case checking) to get the angle
Quote:Original post by Ezbez
@Ridiculus - How can both arcsine and arcosine return the correct angle? Anyone want to shed some light onto which to use?
Assuming that your two vector are normalized to unit length, then the dot product will return the cosine of the angle between the two vectors. You can then take the arccos of this value to get the angle.
a = angle
Vector1 DOT Vector2 = x
x = cosine(angle)
angle = arccos(x)
Hope this helps. You said you wanted the most "efficient" way to do this. You may want to generate a lookup table of arccos values with the resolution that you think your engine needs (assuming you have a moderate amount of memory to spare). Your game engine may already to do this, however; so check the docs. This way the arccos call is practically free.
Actually, if I understand what you want, the dot product is not what you're looking for. You can use the dot product to find the angle between the two vectors, but this will not help determine where you want to turn left or right. (specifically, the dot product commutes: A.B = B.A).
You should look into the cross product. In two dimensions, the cross product isn't defined, but you can just look at what the third component would be:
Let the current heading = <a,b> and target heading = <x,y>, and
let z = a*y-b*x
If z > 0, then you turn right; if z < 0, then turn left. (It might be the other way, I'm too lazy to think about it, but that's the basic idea)
You should look into the cross product. In two dimensions, the cross product isn't defined, but you can just look at what the third component would be:
Let the current heading = <a,b> and target heading = <x,y>, and
let z = a*y-b*x
If z > 0, then you turn right; if z < 0, then turn left. (It might be the other way, I'm too lazy to think about it, but that's the basic idea)
I was wrong about the Dot Product. It does not always return a positive value, but a value ranging from -1.0 to 1.0.
You will probably have trouble with the dot product because dot products are always positive, so you won't know which direction to turn. This question is probably going to come up sooner or later so I'll try and give some pointers about it.
The Orge::Vector3::getRotationTo() returns a Quaternion, which you can use to figure out which way to turn. I would stay away from using the quaternion approach. Its better for animations and finding intermediate rotations between two vectors. So another way would be to use a vector perpendicular to your heading and yet coplanar to whatever the 2D plane you're working with is. It's a little complicatied, but here's an example:
- Call your heading vector vHeading;
- Call your rotationTarget vector vTarget;
- Find a vector perpendicular to RotationTarget and yet coplanar to your plane and store it as vTargetPerpendicular;
(you may need to use a cross poduct here. If your working plane is on the X and Y axes, find the perpendicular vector by calling crossProduct() like this crossProduct(vTarget, vTemp */ where vTemp represents a vector of {0.0f, 0.0f, 1.0f} /*). The cross product will return a vector that is perpendicular to the other two vectors passed in)
- Get the dot product between vHeading and vTarget and store as TargetDot;
- Get the dot product between vHeading and vTargetPerpendicular and store as TargetPerpendicularDot;
- now use a serries of if statements to determine whether to turn left, right, or stay still:
The code above worked for me when I wrote it to figure which direction my car should turn to match up with the orientation of the user's camera in 3D (also working on a conceptual 2D plane though). Anyway, I may have gotten my right and left mixed up, but that's how I do it. There may be another way, but this is the only way I know of. It sould work for you since you are using 3D vectors.
EDIT:
Important note: all vectors must be normalized.
And here is a dot product function in Python, good to keep around for reference:
[Edited by - Ridiculous on May 23, 2006 4:27:07 AM]
You will probably have trouble with the dot product because dot products are always positive, so you won't know which direction to turn. This question is probably going to come up sooner or later so I'll try and give some pointers about it.
The Orge::Vector3::getRotationTo() returns a Quaternion, which you can use to figure out which way to turn. I would stay away from using the quaternion approach. Its better for animations and finding intermediate rotations between two vectors. So another way would be to use a vector perpendicular to your heading and yet coplanar to whatever the 2D plane you're working with is. It's a little complicatied, but here's an example:
- Call your heading vector vHeading;
- Call your rotationTarget vector vTarget;
- Find a vector perpendicular to RotationTarget and yet coplanar to your plane and store it as vTargetPerpendicular;
(you may need to use a cross poduct here. If your working plane is on the X and Y axes, find the perpendicular vector by calling crossProduct() like this crossProduct(vTarget, vTemp */ where vTemp represents a vector of {0.0f, 0.0f, 1.0f} /*). The cross product will return a vector that is perpendicular to the other two vectors passed in)
- Get the dot product between vHeading and vTarget and store as TargetDot;
- Get the dot product between vHeading and vTargetPerpendicular and store as TargetPerpendicularDot;
- now use a serries of if statements to determine whether to turn left, right, or stay still:
int tempTurn; // use this to store our resultif (TargetPermendicularDot > 0.0f and TargetDot < 0.0f) tempTurn = 1; // turning rightelif (TargetPerpendicularDot < 0.0f and TargetDot < 0.0f): tempTrun = -1; // turning leftelse tempTurn = 0;
The code above worked for me when I wrote it to figure which direction my car should turn to match up with the orientation of the user's camera in 3D (also working on a conceptual 2D plane though). Anyway, I may have gotten my right and left mixed up, but that's how I do it. There may be another way, but this is the only way I know of. It sould work for you since you are using 3D vectors.
EDIT:
Important note: all vectors must be normalized.
And here is a dot product function in Python, good to keep around for reference:
def dotprod(v1, v2): return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2]
[Edited by - Ridiculous on May 23, 2006 4:27:07 AM]
Dot product with a axis that is perpendicular.
turn the heading vector to one side, take the dot product between that and a vector between the objects current position, and the thing it wants to turn toward. If the value is positive, turn one way, if it's negative, turn the other [within some epsilon, so you don't just wiggle back and forth :P]
which sign that leads to which direction to turn depends on which direction you turn the heading vector toward, if you turn the heading vector to the right, a positive value would mean turn to the right, and a negative value would mean turn to the left [and the reverse is also true if you turn the heading vector to the left].
Its easy to twist the heading vector too, switch x and y, and make one of them negative [which one being made negative is decided by if its to the left or right.] No need for expensive trig functions and those god-awful arccos things, that would only tell you how much to turn, but leave you absolutely blind to direction :P
turn the heading vector to one side, take the dot product between that and a vector between the objects current position, and the thing it wants to turn toward. If the value is positive, turn one way, if it's negative, turn the other [within some epsilon, so you don't just wiggle back and forth :P]
which sign that leads to which direction to turn depends on which direction you turn the heading vector toward, if you turn the heading vector to the right, a positive value would mean turn to the right, and a negative value would mean turn to the left [and the reverse is also true if you turn the heading vector to the left].
Its easy to twist the heading vector too, switch x and y, and make one of them negative [which one being made negative is decided by if its to the left or right.] No need for expensive trig functions and those god-awful arccos things, that would only tell you how much to turn, but leave you absolutely blind to direction :P
Dot Product Rules
Angle<90 degrees result will be positive
Angle=90 degrees result will be zero
Angle>90 result will be negative
If you are working with normalized vectors use this formula
acos(A o B) = theta in radians
You can also do this:
Vector3 SubtracktVector3D(Vector3 A, Vector3 B)
{
Vector3 C;
C.x = A.x - B.x;
C.y = A.y - B.y;
C.z = A.z = B.z;
return C;
}
Let me give you an example how this works. Say in a FPS the enemy is trying to calculate the distance it would have to travel and the direction to reach the player. Lets call enemy position Vector3 A. Player would then be Vector3 B. Subtracting B from A gives us the direction the enemy (A) would have to travel to meet the player (2) and the distance it would have to travel by takng the magnitude.
A=(2,5,3)
B=(10,8,7)
B-A = (8, 3, 4)
|B-A| = sqrt(8^2 + 3^2+4^2) = ~9.43
From this we know A needs to travel at a ration of x = 10, y = 3, and z = 4 for a distance of 9.43 game units to reach the player.
Hope this Helps
Adam
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement