Jump to content
  • Advertisement
Sign in to follow this  
thecheeselover

Clockwise angle between two Vector3

Recommended Posts

I am trying to compute the clockwise angle between two 3D vectors. I searched a few hours on that question and experimented the solutions found but it just doesn't work.

A lot of threads answers redirect to this : https://stackoverflow.com/questions/14066933/direct-way-of-computing-clockwise-angle-between-2-vectors/16544330

Reading this article, I found out that the best solution to what I want is the algorithm that uses a triple product but I just don't understand what is the n vector.

Here are my variables :

v1 : The first direction and normalized vector (starting from (0, 0, 0)).

v2 : The second direction and normalized vector (starting from (0, 0, 0)).

vCross : The cross product of the v1 and v2 vectors in this order to be clockwise.

dot : The dot product of the two vectors.

n : ???

Algorithm :

// Using jMonkey Engine 3.1 in Java
vCross = v1.cross(v2);
dot = v1.dot(v2);
det = n.dot(vCross);
angle = atan2(det, dot);

Here's n definition : 

Quote

One special case is the case where your vectors are not placed arbitrarily, but lie within a plane with a known normal vector n. Then the axis of rotation will be in direction n as well, and the orientation of n will fix an orientation for that axis. In this case, you can adapt the 2D computation above, including n into the determinant to make its size 3×3.

The problem with that is that my axis of rotation is actually the cross product of v1 and v2...

 

My question question is : is there an algorithm that takes two 3D vectors and then returns the clockwise angle [0, 2𝜋] between them?

Share this post


Link to post
Share on other sites
Advertisement

Say I am looking at you face to face and I hold up a transparent sheet of plastic with the picture of two vectors on it, v1 and v2. If I measure the clockwise angle between v1 and v, I'll get a different answer than if you measure it. You need to specify from which direction you are looking at the vectors. That's where the vector n comes in.

The notion of the orientation of two vectors is not well defined in 3D, so any solution you find is bound to have issues.

What exactly are you trying to do?

 

Share this post


Link to post
Share on other sites
Posted (edited)
2 hours ago, thecheeselover said:

The problem with that is that my axis of rotation is actually the cross product of v1 and v2...

If you use the length of the cross product divided by the product of the lengths of the input vectors, that length represents the sin(angle between them).  So you can say: angle = asin(cross(a, b).Length / a.Length / b.Length);  BUT this will only ever return a value between 0 and pi because vector lengths can ever be negative.

The problem that alvaro is pointing out is that when the angle between your vectors would pass pi, the cross product becomes zero and then starts going in the opposite direction from the direction it was facing earlier.  If you do not have an additional reference vector, there is no way to distinguish this flip, and all angles you attempt to measure will be between 0 and pi.

If you do have a reference vector 'n', you can use it to figure out whether the cross product has flipped or not by using dot(cross, n) and checking whether the result is positive or negative.  If you use this information to negate the angle you get from the above equation you can get a decent enough result.  You will run into problems if your cross product is not parallel to the reference vector, and you will have a useless result if it's perpendicular since the dot product will be zero.

What would a reference vector be?  If you have a game where ground vehicles are driving around a world where Y is up, you might use the up vector (0,1,0) as your reference vector and the forward vectors of vehicles or vectors-towards-waypoints as the inputs to the cross product.  This might let you determine which way a vehicle should steer in certain situations.  For other types of games, it depends on what your intended use is.  For some games, you shouldn't use angles at all.

Edited by Nypyren

Share this post


Link to post
Share on other sites
2 hours ago, alvaro said:

Say I am looking at you face to face and I hold up a transparent sheet of plastic with the picture of two vectors on it, v1 and v2. If I measure the clockwise angle between v1 and v, I'll get a different answer than if you measure it. You need to specify from which direction you are looking at the vectors. That's where the vector n comes in.

The notion of the orientation of two vectors is not well defined in 3D, so any solution you find is bound to have issues.

What exactly are you trying to do?

 

I'm trying to do what you just described but with the direction being the cross product of the two vectors. If I do the *magic* right hand rotation gesture, I should be able to define correctly and know the direction.

Share this post


Link to post
Share on other sites
Posted (edited)
28 minutes ago, Nypyren said:

If you use the length of the cross product divided by the product of the lengths of the input vectors, that length represents the sin(angle between them).  So you can say: angle = asin(cross(a, b).Length / a.Length / b.Length);  BUT this will only ever return a value between 0 and pi because vector lengths can ever be negative.

The problem that alvaro is pointing out is that when the angle between your vectors would pass pi, the cross product becomes zero and then starts going in the opposite direction from the direction it was facing earlier.  If you do not have an additional reference vector, there is no way to distinguish this flip, and all angles you attempt to measure will be between 0 and pi.

If you do have a reference vector 'n', you can use it to figure out whether the cross product has flipped or not by using dot(cross, n) and checking whether the result is positive or negative.  If you use this information to negate the angle you get from the above equation you can get a decent enough result.  You will run into problems if your cross product is not parallel to the reference vector, and you will have a useless result if it's perpendicular since the dot product will be zero.

What would a reference vector be?  If you have a game where ground vehicles are driving around a world where Y is up, you might use the up vector (0,1,0) as your reference vector and the forward vectors of vehicles or vectors-towards-waypoints as the inputs to the cross product.  This might let you determine which way a vehicle should steer in certain situations.  For other types of games, it depends on what your intended use is.  For some games, you shouldn't use angles at all.

Very interesting and descriptive, thank you.

What I am actually trying to do is calculate the angle between two connected cells of a navigation mesh and I need it to be between [0, 2π]. Hmmm maybe if I use the edge that connects the two cells as the n vector?

 

Edit : Ohhhh I get it now! I've been using an n vector in my head without realising it. All navigation mesh cells's vertices are counterclockwise ordered. This means that I can actually use the edges as the n.

Edited by thecheeselover

Share this post


Link to post
Share on other sites
Posted (edited)

I think you'd need to make a reference vector that is perpendicular to your navmesh edges, right (a "surface normal")?  You could cross product two of your edges on the current cell.  If you know they are always in a specific order, that means the cross product of edge[0] and edge[1] should be fairly consistent between cells.

If your navmesh is always flat (or nearly flat), the normals of all of your navmesh cells should be close to the same direction ("up").  It may be simpler to just always use "up" in this case to bypass having to compute the cross product of the cell's edges each time you need it.

Alternatively if the navmesh never changes, you could at the very least precompute the normal vector of each cell when it is created.

Edited by Nypyren

Share this post


Link to post
Share on other sites
Posted (edited)
23 hours ago, thecheeselover said:

What I am actually trying to do is calculate the angle between two connected cells of a navigation mesh and I need it to be between [0, 2π]. Hmmm maybe if I use the edge that connects the two cells as the n vector?

I don't know about anyone else, but it's still clear as mud about what you are trying to do. The angle between 2 cells of a navigation mesh? Cells have several things which could be a vector. The surface normal, edges, connections between centres etc. A diagram would be very useful here, and what are you intending to do with this 'angle'?

Wildly guessing that you are talking about something to do with surface normals of the cells:

  • the dot product of their unitized normals will give you a measure of how similar they are (1 they point the same way, 0 is at 90 degrees, -1 is opposite direction).
  • Afaik acos the dot product will give you a measure of the angle between them.
  • Dot product between the cell normal and a unit vector upward will give you a measure of slope.

But I don't quite see how the clockwise bit comes in (unless you mean in calculating the polarity of the surface normal).

Edited by lawnjelly
alvaro reminds me it should be acos dot product rather than cos! doh! :)

Share this post


Link to post
Share on other sites

Here's the impression I got. Background first. The usual definition of angle in any dimension is the arccosine of the dot product of the normalized vectors. This is a number in [0,pi]. However, in 2D you can use something like atan2 to assign a sign to an angle, which is now a number in [-pi,pi], where positive means conterclockwise and negative means clockwise. Since adding 2*pi to an angle doesn't change anything, you can think of the angle as being in [0,2*pi) if you want.

This thread is about defining angles in 3D with the features of these 2D angles I just described. Unfortunately, there is no notion of clockwise in 3D in general. It is very likely that the OP has a picture in mind that is essentially 2D (e.g., a floor), and what needs to be done is project to a plane and use the 2D definition.

"Clear as mud" is a very apt description of the information we are getting from him/her. As is often the case in the Math forum, if you could express your question in correct and precise language, you probably would't need help figuring out the answer, so we should give people a little slack.

 

Share this post


Link to post
Share on other sites
Posted (edited)
18 hours ago, Nypyren said:

I think you'd need to make a reference vector that is perpendicular to your navmesh edges, right (a "surface normal")?  You could cross product two of your edges on the current cell.  If you know they are always in a specific order, that means the cross product of edge[0] and edge[1] should be fairly consistent between cells.

If your navmesh is always flat (or nearly flat), the normals of all of your navmesh cells should be close to the same direction ("up").  It may be simpler to just always use "up" in this case to bypass having to compute the cross product of the cell's edges each time you need it.

Alternatively if the navmesh never changes, you could at the very least precompute the normal vector of each cell when it is created.

 

8 hours ago, lawnjelly said:

I don't know about anyone else, but it's still clear as mud about what you are trying to do. The angle between 2 cells of a navigation mesh? Cells have several things which could be a vector. The surface normal, edges, connections between centres etc. A diagram would be very useful here, and what are you intending to do with this 'angle'?

You're right; I think I could have given more informations. Here's what I have :

Each connection :

  • Cell
  • Other cell
  • Edge left vertex (counterclockwise according to the mesh's normal)
  • Edge right vertex (counterclockwise according to the mesh's normal)

Each cell :

  • Centroid
  • Normal
  • Connections
  • Vertices

Another important thing to note is that the navmesh is 3D and cyclic, meaning that the cells can form a cube where each cell has connections on all its 4 edges. This means that I cannot simply use the UP vector unfortunately.

I have a generated navigation mesh that is made of 3D and possibly cyclic cells. Each cell is an irregular convex polygon where all its vertices share a common plane. Thus, even though a cell is in 3D, it can be represented in 2D.

The navigation mesh is generated from an also generated dungeon. Because one only navigates inside the dungeon in our game, the navigation mesh is generated from the inside of the dungeon, meaning that all surfaces inside the cube are cells.

Image result for cube wireframe

 

Having thought about it, I think the most useful way to compute the angle is using the normals. Useful in the sense that I am able to determine if the inclination is upwards or downwards according to the normal of the mesh that owns the connection. Two parallel normals and of the same direction should compute an angle of 0. An upwards inclination should be negative because of the reference n vector and a downwards inclination should be positive. In other words, the angle should be between [-π,π].

 

2 hours ago, alvaro said:

This thread is about defining angles in 3D with the features of these 2D angles I just described. Unfortunately, there is no notion of clockwise in 3D in general. It is very likely that the OP has a picture in mind that is essentially 2D (e.g., a floor), and what needs to be done is project to a plane and use the 2D definition.

I'm more an "image person" than a "word person" so that must be why it's kinda hard for me to explain my situation. The 2D picture I imagine in my head is a 2D plane projection where I see two connected cells from the side and thus they are visualized as a line. I see the normals of the two connected cells starting from their centroids. Also, both cells share a vertex (in 2D, an edge in 3D). What I need is the inclinations angle.

Here's a magnificient drawing made in Paint :

image.png.2d2aa414b7f2b874bc7ccdf1698f8887.png

Edited by thecheeselover

Share this post


Link to post
Share on other sites
2 hours ago, alvaro said:

As is often the case in the Math forum, if you could express your question in correct and precise language, you probably would't need help figuring out the answer

You're right because I think I actually got it :P  I said "I think" because there seems to be a bug in my code, which did not help me get this math algorithm right.

Vector3f directionReference = m_edgeVertexLeft.subtract(m_edgeVertexRight).normalizeLocal();
Vector3f meshNormal = m_mesh.getPolygon().getNormal();
Vector3f otherMeshNormal = m_otherMesh.getPolygon().getNormal();

float det = directionReference.dot(meshNormal.cross(otherMeshNormal));
float angle = (float) Math.atan2(det, meshNormal.dot(otherMeshNormal));

 

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  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!