Fixed the issue that the geometry node "Edge Angle" returns the wrong sign sometimes
by changing the formula that computes the sign of the angle from using a tangent-normal
pair to insted using a matrix determinant. This should also be a tiny bit faster since
it doesn't have to iterate over the edge loop.
Details
Details
Diff Detail
Diff Detail
- Repository
- rB Blender
- Branch
- master
- Build Status
Buildable 24367 Build 24367: arc lint + arc unit
Event Timeline
| source/blender/nodes/geometry/nodes/node_geo_input_mesh_edge_angle.cc | ||
|---|---|---|
| 136–137 | I spotted an issue with this revision. When computing the center-point, the order of the vertices doesn't matter. It does matter for the edge direction though, so I should not use the edges array but the loops array. | |
Comment Actions
Updating T101979 to make edge direction independent of order and fix sign
In the previous version, the edges array was used to determine the direction
of the edge. Since the order of elements in that array is not deterministic,
it results in problems where some edges got an negated sign.
I also transposed the matrix used to compute the determinant for convexity
checking to negate the results to conform with how blender 3.3.1 works
(rather than how the documentation states that it should work).
Comment Actions
Since the order of elements in that array is not deterministic, it results in problems where some edges got an negated sign.
I'm a bit confused by this. While its valid for the edge array to have a different order, edge computation is deterministic. With the same input, the output should be the same. If that's not the case, there's most likely another bug somewhere else.
Jacques is probably a better candidate to review the math here.
| source/blender/nodes/geometry/nodes/node_geo_input_mesh_edge_angle.cc | ||
|---|---|---|
| 135–143 | Might be nice for the comment to say why it works rather than just what the code does. You can already see the determinant is used by just looking a few lines below. | |
Comment Actions
I think that it would be a little clearer, you could add an example of what exactly this patch solves.
Comment Actions
You are right, deterministic is perhaps a poor choice of word. The solution is dependent on the order of the vertices in the array to determine the direction of the edge. My first commit used the same array as the original code, but the original code was not dependent on the order since it only used the vertex positions to compute the center point. My code uses it to compute the directional vector of the edge, which is why the order is important. Both solutions are deterministic, but one is order-dependent.
I will fix the comment in the code to explain the math a bit better. A 3D matrix determinant gives you the signed volume of a parallelepiped spanned by the columns of the matrix. By creating a matrix from the normals of both faces and the edge direction, I get a parallelopiped that has a positive volume (right-hand rule) for convex edges and a negative volume for concave edges. This method of determining the convexity of the edge is independent of where the center point of the face is since it does not depend on the tangent vectors. If the two faces are processed in the opposite order, then the normal vectors will be swapped, negating the sign of the determinant. This will also affect the order that vertices are encountered though, which means that the edge direction will also be reversed, canceling out this negation.
Comment Actions
I don't fully understand how this is edge vertex order independent.
If the two faces are processed in the opposite order, then the normal vectors will be swapped [...].
Why is that? The order if vertices in a face determines the normal direction, but the order of faces is independent.
I tried to come up with an alternative fix in D16464. It address the issue in the bug more explicitly. Instead of using the polygon center (which was an arbitrary decision anyway), it uses the position of a vertex that is part of the looptri that contains the edge.
In theory we could also use the normal of that triangle, but I fear that it may jitter too much when the mesh is deformed (because the triangulation changes).
Comment Actions
Let's call the two face normals A and B. If A is processed first, then it will be the first column of the matrix and B will be the second. If B is processed first, then it will be the first column and A will be the second. In both scenarios, the third column will be the edge direction, but its direction will depend on the order of the faces. If you swap two columns in a 3x3-matrix, the effect on the determinant is that the sign is swapped. If you multiply one of the column vectors with -1, it also affects the determinant by swapping the sign. So processing B before A will cause the first two columns to swap, but it will also multiply the third column with -1. These two changes cancel out and the determinant remains the same, meaning that it is independent of order.
It can also be shown algebraically:
Comment Actions
but its direction will depend on the order of the faces
I think this is the key point that needs some explanation in a comment. Usually, the edge direction does not depend on the order of faces.