I’m using quaternions to represent tangental space basis per vertex. It works good if I transform vectors (to light & camera) in vertex shader and interpolate them (already in tangent space).
However, for some tasks I need to pass the basis itself to a fragment shader. Here is where the problem hides:
Q and -Q (component-wise) both represent the same basis (or rotation - it doesn’t really matters in this context).
So 2 very close quaternions can be interpolated through the whole turn, producing undesirable results…
First, I thought that some kind of quaternion ‘sex’ property can be kept after the initial fill, that will guarantee all the quaternions are interpolated properly. However, this idea is not working (try to set up the male and female quaternion definitions to understand why).
Have you experienced a similar problem and how did you solve it?
I have experienced the same issue, but sadly don’t have a solution to offer.
On the CPU side it is possible to define if how you wish to interpolate the quaternions (closest path, longest path, clockwise, counter-clockwise) and act on that information. I haven’t tried to apply this to the GPU side, however.
On GPU side the interpolation is always linear (w/o perspective correct) and between 3 values at a time.
So the question may be modified: is there a transformed domain for quaternions, in which they can be linearly interpolated correctly?..
I’ve been looking at the same problem recently and I’m presuming you need tangent space at the pixel level for doing things like environment mapping.
Yes, there is a transformed domain for quaternions in which they can be linearly interpolate correctly (VQS Transformation with an Incremental Approach, Xin Li,Computer Science Department, Digipen Institute of Technology)BUT you need to know explicitly the 2 quaternions you are interpolating - which in a vertex shader you don’t. Also, this only interpolates 2 not 3 quaternions, so is not really usable with vertex interpolators.
What we need (as I’m sure you’re aware) is for ALL triangles in the meshto have their 3 quaternions all aligned in the same sense. Then a normalised linear interpolation will give a good result. But, because the .w component of the quat represent the cosine of half the angle of rotation, quaternions smoothly wrap around 720 degrees, not 360 degrees. So, for a cylinder, for example, we must always get a quaternion discontinuity somewhere.
My solution to this problem is to create a seam in the mesh wherever we get an unavoidable discontinuity. Basically, as a preprocess, check each triangle’s quaternions A, B, C and the dot products (ie the cosines of the angles between them) of AB, BC and AC. If they are all positive, they are all shortest path. There should always be one pair with positive dot. The quaternion not in this pair needs negating and to hold this flipped quaternion, we create a new vertex with the same position and uv coords as the original, but with a flipped quat. This creates a seam, of course, that never existed before. The cost is just a few extra vertices, but in terms of data, we still save lots by one passing 1 quat instead of a tangent and binormal vector.
Wow, Mike, thanks for the response!
I’m really surprised to get a qualified answer to my question.
You understand my problem correctly. Moreover, your answer is detailed enough to make sense for me.
A question about your solution. How many vertices are actually duplicated in a real case? Do you have some numbers from personal experience?
Assuming the uniform quaternion distribution, the probability of the duplication is around 1/3 (correct?), so it can significantly increase the vertex number (in theory).
BTW, Welcome to OpenGL.org community!
I wish you smart questions and good answers here.
What’s the math background of this statement?
In 3D space I can have 4 vectors with angle > Pi/2 between each (making the dot product negative).
In 4D quaternion space there can be even more (5?).
“There should always be one pair with a positive dot” - well, for a start, I am making one vital assumption here, that the mesh is fairly smooth and that therefore there are relatively small angles between the 3 tangent space quats in any given triangle.
Now, let’s take the pairs AB, AC, BC. We check the cos of each, and if they are all shortest path (positive cos), no problem, we leave things as they are. But sometimes we will find longest path pairs. We know that there are only 2 possibilities for each quaternion and (because we have a relatively smooth mesh) we know that there are only small angles between any pair, as long as the sense of the 2 quats match. Let’s call the sense heads or tails. Heads and heads will give shortest path. Likewise tails and tails will give shortest path. Only heads and tails in a pair will give longest path. So, we either get heads, heads, tails in a triangle with a longest path, or tails, tails, heads. And therefore we have one shortest path pair and 2 longest path pairs.
I know this isn’t a rigorous maths proof, but it gives an outline.
How many verts will need flipping? Very few indeed. It’s not really a question of probability (if our quaternions lie on a relatively smooth surface). The problem is that quats only wrap around 720 degrees, not 360. Therefore, there’s always going to be a discontinuity somewhere, but in a very specific place.
Take a cylinder and try to map the tangent space to quats. Then there is only one straight line running down the side of the cylinder where the quats don’t wrap. You only need to duplicate the verts along that line. So, unless you have a very knotty sort of shape, the proportion of extra verts is going to be very very low and the more dense your mesh, the lower the proportion.
We can assume the mesh itself is smooth (having a fallback solution in other case), but I derive tangental space from texture coordinates, what makes my quaternions heavily depend on the quality of UV-mapping.
Just checked on one simple model and discovered a face where only 1 pair had negative dot product… (the cosines are 0.2,0.3,-0.8)
So, the next question is: how do you specify the constraints of a model for designer (to be able to apply your algorithm to tangent space quaternions)?
BTW, how do you derive the tangental space?
What is your fallback in case the quaternions are bad?
“There should always be one pair with a positive dot” - well, for a start, I am making one vital assumption here, that the mesh is fairly smooth and that therefore there are relatively small angles between the 3 tangent space quats in any given triangle.
Now, let’s take the pairs AB, AC, BC. We check the cos of each, and if they are all shortest path (positive cos), no problem, we leave things as they are. But sometimes we will find longest path pairs. We know that there are only 2 possibilities for each quaternion and (because we have a relatively smooth mesh) we know that there are only small angles between any pair, as long as the sense of the 2 quats match. Let’s call the sense heads or tails. Heads and heads will give shortest path. Likewise tails and tails will give shortest path. Only heads and tails in a pair will give longest path. So, we either get heads, heads, tails in a triangle with a longest path, or tails, tails, heads. And therefore we have one shortest path pair and 2 longest path pairs.
I know this isn’t a rigorous maths proof, but it gives an outline.
How many verts will need flipping? Very few indeed. It’s not really a question of probability (if our quaternions lie on a relatively smooth surface). The problem is that quats only wrap around 720 degrees, not 360. Therefore, there’s always going to be a discontinuity somewhere, but in a very specific place.
Take a cylinder and try to map the tangent space to quats. Then there is only one straight line running down the side of the cylinder where the quats don’t wrap. You only need to duplicate the verts along that line. So, unless you have a very knotty sort of shape, the proportion of extra verts is going to be very very low and the more dense your mesh, the lower the proportion.
Ooops, sorry about that Dmitry. I just accidentally sent the same message twice
We’re getting the tangent space from texture coordinates, but doing nothing special, just a straight import from Maya.
I would be really interested in seeing the actual simple model where you’ve found this problem, or even just the actual 3 tangent space quaternions you found where you get 2 positive dots and 1 negative.
Anyway (and briefly because I’m a bit pressed for time at the moment), the fallback is to split the triangle.
You have 2 edges which are shortest path (let’s say AB and AC) but one edge which is longest path (BC). You can’t flip any of A,B or C to solve the problem (because flipping B would make BC shortest path but AB would then become longest path, likewise for C, and flipping A would make both AB and AC longest path).
So, we find D = Slerp(B, C, 0.5f) = NormalisedLerp(B, C, 0.5f).
BD and DB should BOTH be either shortest path or longest path. If they are longest path, we flip D, if not we leave D as it is. And now we have 2 triangles ABD and ACD.
If (by any chance) the problem still persists in ABD or ACD, we need to do further splits.
Oh, and sorry about the delay inreplying properly - a long weekend !!!
Total vertices: 10366
Require duplication: 1662
Require fall-back solution: 26
The last number looks small enough but the middle one is quite huge.
You are basically increasing the model size by 15% or so.
It would be nice to see your actual statistics.
Yeah, the middle figure is rather large (but on the other hand you can be saving around 20% vertex buffer memory by sending 1 quat instead of 2 3-vectors). I haven’t looked at models anywhere near as complex yet, because we’re deliberately using very simple models at the moment for easier analysis when something goes wrong (still early days in our engine development), so any stats wouldn’t be very useful for you, I’m afraid.
There is one possible way of reducing the duplication but I won’t have time to even think in detail about it for a while. The duplication process basically produces seams on the model. However, there will already be seams due to texture mapping (eg, down the length of an arm or a leg there should be a seam to wrap the texture correctly).
If we can make the quaternion seams match the texture seams, then we effectively eliminate the duplication (these vert positions are already duplicated because of 2 different texture coords).
I think it should be possible to take the verts lying along one side of texture seam and use their quats as a reference alignment, then spread outwards from them, realigning other quats as necessary (it would have to be quite heavily recursive I think). But I am really not sure about this. Would love to try it but working on animation at the moment!
Full per-face statistics:
(all positive, one negative, two negative, all negative)
16430, 26, 1662, 0
Yeah, the middle figure is rather large (but on the other hand you can be saving around 20% vertex buffer memory by sending 1 quat instead of 2 3-vectors)
I do not require to interpolate quaternions, but it’s going to be a handy property (for deferred shading at least).
For the forward-rendering lighting I safely interpolate vectors already in tangent space, so there is no benefit here.
As for you duplicate-killing solution - I don’t see how it’s going to work. When scanning faces for the invalid vertex quaternions we already rely on the texture coordinates being correct. So, if we find a vertex to duplicate, we can not just grab the one on the other side of the texture map, just because it has different texcoord.
As far as I see, all we can do here is to minimize the amount of duplication by tracking already duplicated vertices (no need to duplicate a vertex more than once, since we have Q and -Q) and fixing the current vertex if it’s not being used by any other face at the moment of scan.
P.S. Working on it. Will keep you informed on progress.
First progress report:
From these 1662 (group 2-) faces only 377 vertices (3.5% of total vertices) require duplication, using suggested optimizations.
It’s a pretty affordable number of duplicates.
However, I still haven’t decided what to do with (1-) faces. Cutting the face looks like a working solution, but seems to be very messy.
P.S. (3-) group is easily converted to (1-) by inverting any of participating quaternions. There are no faces belonging to this group in my test, though.
I’ve finished the basic implementation and passed tests successfully. The previous number (377) was incorrect.
‘Dude’ body mesh:
added extra 767 vertices & 26 faces during the quaternion fixing stage
result total 11133 vertices & 18144 faces
As you can see the number of vertices is increased by nearly 7%, what is not bad, assuming the model can be optimized on the artist side before exporting.
For the (1-) group I’m cutting the face just once (will improve if have a real test case in future).
Thanks a lot for your help, Mike!
