TheMoebius 112 Report post Posted May 20, 2006 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. 0 Share this post Link to post Share on other sites
RidiculousX 140 Report post Posted May 20, 2006 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. 0 Share this post Link to post Share on other sites
Ezbez 1164 Report post Posted May 20, 2006 @Ridiculus - How can both arcsine and arcosine return the correct angle? Anyone want to shed some light onto which to use? 0 Share this post Link to post Share on other sites
deej21 152 Report post Posted May 20, 2006 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 productYou 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 acosor 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 0 Share this post Link to post Share on other sites
TheMoebius 112 Report post Posted May 20, 2006 Is there a way just to get the direction that is less expensive? 0 Share this post Link to post Share on other sites
jdaniel 211 Report post Posted May 20, 2006 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 = angleVector1 DOT Vector2 = xx = 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. 0 Share this post Link to post Share on other sites
mooserman352 168 Report post Posted May 20, 2006 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>, andlet z = a*y-b*xIf 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) 0 Share this post Link to post Share on other sites
RidiculousX 140 Report post Posted May 20, 2006 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: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] 0 Share this post Link to post Share on other sites
Peachy keen 234 Report post Posted May 20, 2006 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 0 Share this post Link to post Share on other sites
adam23 164 Report post Posted May 21, 2006 Dot Product RulesAngle<90 degrees result will be positiveAngle=90 degrees result will be zeroAngle>90 result will be negativeIf you are working with normalized vectors use this formulaacos(A o B) = theta in radiansYou 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.43From 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 HelpsAdam 0 Share this post Link to post Share on other sites
Grain 500 Report post Posted May 22, 2006 TheMoebius this is a very easy problem. You don’t need cos or acos and you don’t need to normalize any thing.To know which way to turn you first need a vector perpendicular to the vector that tells which way you are currently pointing. In 2d this is simple.Assume V1 is the direction you are facing.V2.x = V1.y;V2.y = -V1.x;Then to determine which way you have to rotate just get the dot product of V2 and the vector pointing from you to the target(Target position -Your position). Check if the dot product is greater or less than 0. If it’s greater you turn one way if less your turn the other. 0 Share this post Link to post Share on other sites
Emmanuel Deloget 1381 Report post Posted May 22, 2006 Quote:Original post by RidiculousI was wrong about the Dot Product. It does not always return a positive value, but a value ranging from -1.0 to 1.0.Are you sure? [smile]Let's do it: v1 = (1, 2, 3), v2 = (3, 2, 1) then v1 dot v2 = 1*3 + 2*2 + 3*1 = 10It seems that you are somewhat disturbed by the notion of dot product :)The dot product of unit-length vectors is in the [-1, 1] range.Regards, 0 Share this post Link to post Share on other sites
yaustar 1022 Report post Posted May 22, 2006 Would it be possible to 'abuse' Cross product in some way? Depending which side the direction vector is of the target vector, the cross product will produce a vector out of a possible two. From that you can find out whether to turn left or right.For example, assume that the y an x axis is on the horiztonal plane and the direction and target vectors are parallel to that plane. The cross product of those vectors is either straight up or down. 0 Share this post Link to post Share on other sites
jyk 2094 Report post Posted May 22, 2006 Quote:Original post by GrainTheMoebius this is a very easy problem. You don’t need cos or acos and you don’t need to normalize any thing.To know which way to turn you first need a vector perpendicular to the vector that tells which way you are currently pointing. In 2d this is simple.Assume V1 is the direction you are facing.V2.x = V1.y;V2.y = -V1.x;Then to determine which way you have to rotate just get the dot product of V2 and the vector pointing from you to the target(Target position -Your position). Check if the dot product is greater or less than 0. If it’s greater you turn one way if less your turn the other.In case anyone missed it, above is the correct answer to the question of how to determine which direction to turn. To get the actual (signed) angle:angle = atan2(perp_dot(forward, vector_to_target), dot(forward, vector_to_target));Note that neither algorithm requires that vector_to_target be normalized. 0 Share this post Link to post Share on other sites
RidiculousX 140 Report post Posted May 23, 2006 Quote:Original post by Emmanuel DelogetThe dot product of unit-length vectors is in the [-1, 1] range.Thank you for the correction. I forgot to mention in all my posts that all vectors must be normalized. I was under the assumption that that was a given. :)And here is a really great resource on vectors. It gets into it deep. I mentioned it in another topic, but it won't hurt to mention it again:http://chortle.ccsu.ctstateu.edu/VectorLessons/vectorIndex.htmlThat's eveything you ever wanted to know about vectors (or not). 0 Share this post Link to post Share on other sites
TheMoebius 112 Report post Posted May 23, 2006 Isn't cross product the easiest and cheapest? At least if I'm not concerned with the actual angle and only which way to turn. This is my code.double y = mvHeading.x * target->z - target->x * mvHeading.z; if (y<0) { turnLeft();}else if (y>=0) { turnRight();} 0 Share this post Link to post Share on other sites
mooserman352 168 Report post Posted May 23, 2006 Moebius,As I had posted above, that is indeed the fastest and easiest way to do this. Note that Grain's method is equivalent mathematically, and adds somewhat of a geometric interpretation to what is being done. 0 Share this post Link to post Share on other sites
TheMoebius 112 Report post Posted May 23, 2006 Quote:Original post by mooserman352Moebius,As I had posted above, that is indeed the fastest and easiest way to do this. Note that Grain's method is equivalent mathematically, and adds somewhat of a geometric interpretation to what is being done.Yeah, thats the one I used. Thx for that. 0 Share this post Link to post Share on other sites