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?

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.

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.

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.

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 :

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   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));