Sign in to follow this  
rumblesushi

Most efficient method of implementing 6dof objects?

Recommended Posts

Hello,

I've had a gander at a couple of pages of 6dof posts, and found some interesting stuff, but not what I'm looking for.

Basically, what is the most efficient method of implementing 6dof and also, how can you avoid gimbal lock with pure matrix transformations, and no quaternions?

I thought I had correctly implemented 6dof in my engine, as in previous demos and tests, moving objects seemed to rotate correctly on all 3 axis (balls for example). I'm obviously wrong though, because activating roll in my driving game produces entirely wrong, and completely random results.

What I'm doing now is simply using the difference between the current angle in radians and the previous frame's angle in radians to increment my objects rotation, around the local axis.

I use a temporary rotation matrix for the axis rotation, for each rotation I transform (well, multiply) the axis of my model, Z and Y for pitch, Z and X for yaw, and X and Y for yaw.

I then fill the 3 columns of my model transform matrix with the values of the 3 axis.

For a few seconds, the 3 rotations appear to be correct, but then it immediately becomes completely out of sync, with the car just sort of randomly rotating around like a ball. Normalising the 3 axis makes no difference.

If I use yaw around the local axis, this also becomes out of sync and all over the place. If I use a Y rotation around the global axis, the yaw is actually correct, but pitch and roll are wrong, and only work if used individually with yaw.

And in regards to efficiency, my platform is AS3/Flash. Basically, consider it like a mobile platform but without a GPU. Every bit of juice counts.

Yesterday I tried implementing a Quaternion. I simply constructed a quaternion each frame from Euler angles, then converted it to a matrix. Predictably, this didn't work either, but ironically worked better than my matrix setup. It didn't go out of whack, and didn't exhibit classic gimbal lock, it's more like the roll seemed somewhat random, sometimes working, sometimes not.

If pure Matrix 6dof is achievable, what am I doing wrong? What should I be doing? Also, if it IS achievable, then what are the purpose of Quaternions? Why are they so popular for orientation, 6dof in particular?

I seem to recall seeing some code for Quaternion rotation somewhere that actually used 3 quaternions, one each for yaw, pitch and roll.

This seems like a somewhat excessive solution, one for each axis, and having to convert back to a matrix presumably for each axis? Is this what's necessary to get quaternions working properly?

Excuse the novel, I like to be thorough ;)

Cheers,
RumbleSushi

Share this post


Link to post
Share on other sites
Quote:
Original post by rumblesushi
how can you avoid gimbal lock with pure matrix transformations, and no quaternions?
You actually avoid gimbal lock with matrices in exactly the same way you do with quaternions. So, if you can avoid gimbal lock with quaternions, applying the same process but with matrices rather than quaternions should give you the same result.
Quote:
If pure Matrix 6dof is achievable, what am I doing wrong?
There are lots of things that can go wrong with respect to rotations, and to me at least, it's not really clear from your description what the exact problem is in this case. (If you could post the relevant source code, it might be easier to identify the problem.)
Quote:
Also, if it IS achievable, then what are the purpose of Quaternions? Why are they so popular for orientation, 6dof in particular?
Generally speaking, quaternions behave the same way matrices do with respect to rotations. The advantages that they have are related mostly to efficiency and storage requirements. Note that that doesn't mean it's always more efficient to use a quaternion; it just means that working with quaternions *can* be more efficient than working with matrices in some cases.

Quaternions are cheaper to concatenate and normalize (orthogonalization being the equivalent matrix operation) than matrices, which can be advantageous if performance is a concern. You just have to weigh that against the fact that usually you're going to need the orientation in matrix form anyway (e.g. for interoperation with a graphics API), so you have to factor the cost of that conversion in. Still, quaternions are certainly a reasonable choice as far as implementing 6DOF motion goes.
Quote:
I seem to recall seeing some code for Quaternion rotation somewhere that actually used 3 quaternions, one each for yaw, pitch and roll.
There's little point in that, IMO.
Quote:
Is this what's necessary to get quaternions working properly?
No, not at all.

Share this post


Link to post
Share on other sites
Hey jyk,

Thanks for the reply, I assumed you would answer, as it was one of your posts I read suggesting that gimbal lock is just as avoidable with matrices ;)

My 3D engine is a software renderer, with everything done from scratch, so not reliant on any external libraries at all, or a GPU etc.

I must admit I didn't know quaternions were used for performance reasons at all. I thought they simply provided the most accurate results for full 3D rotation. Unless they were used alone, because surely used in conjunction with matrices is going to use more juice? Though obviously, I have no experience with using Quaternions, so there may be a more efficient method of using them than I am privy to.

What is the most efficient pipeline for using Quaternions then? Essentially feeding a quaternion angles in radians, then converting to a Matrix, and using just one Quaternion.

And how about 6dof with just Matrices? 5dof works perfectly. Moving in all directions obviously is easy, then getting pitch and yaw working together is very easy too. It's as soon as you introduce roll that things become tricky.

What is your transformation pipeline with matrices to achieve flawless 6dof rotation?

Here's some code as requested.

Here is the local axis rotation function.

Quote:

public function axisRotation (x:Number, y:Number, z:Number, angle:Number):void {
//
n11 = 1; n12 = 0; n13 = 0; n14 = 0;
n21 = 0; n22 = 1; n23 = 0; n24 = 0;
n31 = 0; n32 = 0; n33 = 1; n34 = 0;
n41 = 0; n42 = 0; n43 = 0; n44 = 1;
//
var cos:Number = Math.cos(angle);
var sin:Number = Math.sin(angle);
var scos:Number = 1 - cos;
//
var sxy:Number = x * y * scos;
var syz:Number = y * z * scos;
var sxz:Number = x * z * scos;
var sz:Number = sin * z;
var sy:Number = sin * y;
var sx:Number = sin * x;
//
n11 = cos + x * x * scos;
n12 = - sz + sxy;
n13 = sy + sxz;
//
n21 = sz + sxy;
n22 = cos + y * y * scos;
n23 = - sx + syz;
//
n31 = - sy + sxz;
n32 = sx + syz;
n33 = cos + z * z * scos;
//
}


Here is the roll function for example.

Quote:

public function mRoll(angle:Number):void {
//
var newAngle:Number = (angle - roll);
if (newAngle == 0) return;
//
tempMtx.axisRotation ( zAxis.x, zAxis.y, zAxis.z, newAngle );
var x:Number, y:Number, z:Number;
//
x = xAxis.x; y = xAxis.y; z = xAxis.z;
xAxis.x = (x * tempMtx.n11 + y * tempMtx.n12 + z * tempMtx.n13);
xAxis.y = (x * tempMtx.n21 + y * tempMtx.n22 + z * tempMtx.n23);
xAxis.z = (x * tempMtx.n31 + y * tempMtx.n32 + z * tempMtx.n33);
//
x = yAxis.x; y = yAxis.y; z = yAxis.z;
yAxis.x = (x * tempMtx.n11 + y * tempMtx.n12 + z * tempMtx.n13);
yAxis.y = (x * tempMtx.n21 + y * tempMtx.n22 + z * tempMtx.n23);
yAxis.z = (x * tempMtx.n31 + y * tempMtx.n32 + z * tempMtx.n33);
//
roll = angle;
//
}



Then after calculating rotations/transforming the axis vectors, I simply do this

Quote:

modelMtx.n11 = xAxis.x;
modelMtx.n21 = xAxis.y;
modelMtx.n31 = xAxis.z;
//
modelMtx.n12 = yAxis.x;
modelMtx.n22 = yAxis.y;
modelMtx.n32 = yAxis.z;
//
modelMtx.n13 = zAxis.x;
modelMtx.n23 = zAxis.y;
modelMtx.n33 = zAxis.z;
//
modelMtx.n14 = position.x;
modelMtx.n24 = position.y;
modelMtx.n34 = position.z;


Fill the model transform with the 3 axis and model position.

So if you could advise me on a solid transformation pipeline for either pure matrices or quaternions for 6dof movement, it would be much appreciated.

Cheers.

Share this post


Link to post
Share on other sites
Providing a really detailed answer would probably make for a fairly long post, but I'll at least try to answer some of your questions:
Quote:
I must admit I didn't know quaternions were used for performance reasons at all. I thought they simply provided the most accurate results for full 3D rotation.
No, aside from minor numerical variations, there's no functional difference between quaternions and matrices as far as rotations go, and neither is more 'accurate' than the other. However, as previously mentioned, certain operations (concatenation, normalization, and interpolation in particular) are considerably more efficient with quaternions than with matrices.
Quote:
Unless they were used alone, because surely used in conjunction with matrices is going to use more juice?
It all depends on the context.

I didn't review your code carefully, but implementing 6DOF motion is basically the same whether you're using quaternions or matrices (only the details are different). Typically you would apply incremental, relative rotations each update, and then normalize the orientation to prevent numerical drift (which equates to normalization with quaternions and orthogonalization with matrices).

To apply a local rotation about a local axis (side, up, or forward), you can build a world-axis rotation and multiply on one side, or build a local-axis rotation and multiply on the other side (which side is which depends on the conventions of the math library you're using). Here's how it might look for a typical quaternion-based implementation (untested pseudocode):
quaternion x = quaternion_from_axis_angle(1, 0, 0, x_rot);
quaternion y = quaternion_from_axis_angle(0, 1, 0, y_rot);
quaternion z = quaternion_from_axis_angle(0, 0, 1, z_rot);
orientation *= x * y * z;
orientation.normalize();
Note that although I used separate x, y, and z rotation quaternions in this example, it's not the same thing as using what you might call 'from-scratch' Euler angles.

Share this post


Link to post
Share on other sites
Hey jyk, well regarding accuracy, obviously rotating by an angle is rotating by an angle, whether it's euler rotations using raw trigonometry, or matrices or quaternions.

However, I'm sure I've read that quaternions are less prone to rotation errors or "numerical drift" than matrices, or at least it's easier to achieve accurate rotations with no errors.

Applying incremental, relative rotations ultimately stored in one matrix is what I'm doing by the way, so I really don't understand why the Z rotation makes things go so out of whack.

I'm normalizing the 3 axis, not orthogonalizing them, but that can't be the problem, it goes dramatically out of sync too fast.

Thanks for the example, but actually the example is what you described as unnecessary, ie having a quaternion for rotation X, Y and Z.

In your example, you simply feed the 3 axis quaternions euler angles, multiply them with the main orientation quaternion that retains the rotation information, then just the one orientation needs to be converted to a matrix right?

Also, do you happen to know of any source code featuring pure matrix 6dof rotation? I want to know what I'm doing wrong, it's annoying.

Cheers.

Share this post


Link to post
Share on other sites
Quote:
Original post by rumblesushi
However, I'm sure I've read that quaternions are less prone to rotation errors or "numerical drift" than matrices, or at least it's easier to achieve accurate rotations with no errors.
Yes, the 'numerical drift' part is right. The problem (as I see it at least) is that to say a rotation is 'accurate' is not a precise statement. If I implemented 6DOF control of an object using quaternions and matrices and asked you to try each application and tell me which used quaternions and which used matrices, you wouldn't be able to (aside from guessing, that is). In that sense, quaternions and matrices are both 'equally accurate'.

In some circumstances, when multiple operations are performed in sequence there may be less accumulated error with quaternions than with matrices. However, in most cases you'll be correcting any accumulated error every update anyway (at least that's what I generally do), so I'm not sure how much that matters. (What might matter more though is that normalizing a quaternion is much cheaper than orthogonalizing a matrix.)
Quote:
Applying incremental, relative rotations ultimately stored in one matrix is what I'm doing by the way, so I really don't understand why the Z rotation makes things go so out of whack.
I couldn't tell you that without greater knowledge of your specific application. Is there any possibility that 6DOF isn't really what you're looking for? (That does seem to happen occasionally - there have been quite a few posts where people thought their 6DOF implementation wasn't behaving correctly, but it actually was behaving correctly and the real problem was simply that 6DOF wasn't what they actually wanted.)
Quote:
Thanks for the example, but actually the example is what you described as unnecessary, ie having a quaternion for rotation X, Y and Z.
No (and I mentioned this in the post as well). All that's happening in that example is that you're rotating about the local x, y, and z axes, which is exactly what you have to do if you...wait for it...want to rotate about the local x, y, and z axes. You could combine those into a 'quaternion from Euler' function, but it'll be the same thing, just perhaps a little more efficient.

The distinction to be made here is between what I usually call 'from-scratch' Euler angles (where the orientation is built 'from scratch' each update) and what you might call 'incremental' Euler angles. Technically, when you combine the three axis rotations, that's an Euler angle construction. However, the artifacts we generally worry about with Euler angles (such as gimbal lock) are generally not a concern in this context.

A phrase you might hear with respect to this topic is 'infinitesimal rotations commute'. Obviously rotations will not be infinitesimal in a computer simulation, but for practical purposes we can treat them as if they are. With this assumption made, the order in which the rotations are combined does not matter, and artifacts such as gimbal lock are not a concern.
Quote:
In your example, you simply feed the 3 axis quaternions euler angles, multiply them with the main orientation quaternion that retains the rotation information, then just the one orientation needs to be converted to a matrix right?
Yes, that sounds right.
Quote:
Also, do you happen to know of any source code featuring pure matrix 6dof rotation? I want to know what I'm doing wrong, it's annoying.
A typical matrix-based implementation would look just like the quaternion version that I posted, just with matrices instead of quaternions (and of course with multiplication order adjusted if needed). There are various ways the code could be expressed, but the operations that are performed will be essentially the same regardless.

Share this post


Link to post
Share on other sites
Fair enough jyk, regarding accuracy.

I'm pretty sure 6dof is what I want. It's not unwanted roll etc that I'm experiencing, it's simply huge rotation errors where the car ends up a rotational mess.

Obviously I want the car to be able to rotate around it's own Z axis on banked curves or sideways on a hill etc, to be able to rotate and move in all directions, which is obviously 6dof.

And I understand the difference between the 2 examples, creating a quaternion from euler angles from scratch each frame, and rotating around axes incrementally. My only point is that it still takes 3 (well 4) quaternions to achieve this, or rather 3 quaternion axis rotations, and then multiplications with the main orientation quaternion which of course is updated each frame, not created from scratch.

Obviously you have to do the same thing with matrices, rotate around an arbitrary axis for each rotation, then multiply with the main transformation matrix.

I guess I just didn't know exactly how quaternions work, and it seems like a lot of work considering you have to convert back to matrix. But I guess it probably evens out to be honest, because there is less work to be done with rotating a quaternion around an axis compared to a matrix, and multiplication/normalising is faster too.

Thanks for the info, I'll get the quaternions working now.

Cheers.

Share this post


Link to post
Share on other sites
Quote:
Obviously I want the car to be able to rotate around it's own Z axis on banked curves or sideways on a hill etc, to be able to rotate and move in all directions, which is obviously 6dof.
Sure, it does sound like 6DOF is what you want. The only thing I'll mention is that in that sort of context, rotation of the object is usually at least partially determined by the orientation of the surface beneath the object (either using ad hoc methods, or by way of a physics engine). So it's less an issue of 'applying local roll' as it is adjusting the orientation so that it's aligned with the surface normal (which often involves rotating about an axis that is not one of the local cardinal axes).
Quote:
My only point is that it still takes 3 (well 4) quaternions to achieve this, or rather 3 quaternion axis rotations, and then multiplications with the main orientation quaternion which of course is updated each frame, not created from scratch.
Right, at this point we're just talking about implementation details that aren't necessarily that important. Technically though, I wouldn't say that the process 'requires' 3 (or 4) quaternions.

What it really reduces to is that, basically, if you want to apply N rotations, you'll have to apply N rotations. If N is 3, then one way to do that is to combine 3 rotations in quaternion form, as in my example. But, you could also do this using a 'quaternion from Euler' function. In that case, are you still using 3 quaternions (implicitly)? Or just one? Also, some math libraries have functions that will 'rotate a quaternion' about one of its local axes without actually performing a full quaternion multiplication. Does that involve one extra quaternion? Or zero? It's a little hard to say, and probably isn't really important in most cases.

So in summary, it's not a given (IMO) that applying rotations in this way 'requires 3 quaternions'. That said, the question isn't really that important. (Unless, I suppose, you're trying to minimize operations as much as possible, which it sounds like you are. In that case, you might want to try the 'quaternion from Euler' or 'rotate about local axis' approach, as they both effectively eliminate some unnecessary operations.)
Quote:
I guess I just didn't know exactly how quaternions work, and it seems like a lot of work considering you have to convert back to matrix. But I guess it probably evens out to be honest, because there is less work to be done with rotating a quaternion around an axis compared to a matrix, and multiplication/normalising is faster too.
Yes, it's a tradeoff, and whether it's likely to be a win really depends on the circumstances. But, you can of course try it both ways and see if there's any noticeable difference.

Share this post


Link to post
Share on other sites
I've now realised it has absolutely nothing to do with how I'm handling rotations, they are fine.

It's actually how I'm calculating the angles that I'm using to rotate in the first place.

I'm correct that in previous demos, I had working 6dof working perfectly using pure matrix rotations, ie aeroplane style controls, able to incrementally pitch, yaw and roll to move in any direction.

Share this post


Link to post
Share on other sites
Oh, what I want to ask is, could you advise me on a better way to handle the vehicle's orientation?

What I'm doing now is simply calculating the angle in radians between the front and back of the car for pitch and yaw, and the angle between the 2 front wheels for the roll, as it's colliding with the ground obviously.

Then I'm using the difference between the current angle and the previous frame's angle to increment the rotation.

It actually works for a few seconds, but then starts to go completely out of whack. Not glitchy, spinning around etc, it just builds huge rotational errors, far more than is possible by simply not normalising the rotations, ie the yaw or roll gradually just goes out of sync by say 20 degrees.

Share this post


Link to post
Share on other sites
Quote:
Original post by rumblesushi
Oh, what I want to ask is, could you advise me on a better way to handle the vehicle's orientation?
The most direct solution to this problem, IMO, is to use an existing physics engine that provides robust vehicle dynamics.

Aside from that, I can't really offer any sort of conclusive answer. You can simply align the object to the surface beneath it of course, but even with interpolation it's only an approximation and will likely result in your vehicle clipping into other objects in the scene.

Another option might be to raycast downwards from each of the four wheels (assuming there are four wheels), and choose from the four planes that can be generated from the intersection points one for which the other intersection point lies below the plane, and then align and position the vehicle accordingly. But, I'm just guessing - I haven't tried anything of that sort myself, so I can't say for sure how effective it would be.

Again though, for any sort of realistic simulation, an existing physics engine might be your best bet.

Share this post


Link to post
Share on other sites
I probably should have said, an existing physics engine isn't possible, because I'm working in AS3.

Obviously in C++ you have the luxury of engines like Bullet, that apparently perform very well.

The only existing physics engine is HIDEOUSLY slow, so I really have no choice but to do all my own physics, which so far, work pretty well.

I have a highly efficient broadphase and sphere to triangle routine, for general object to environment collisions, but obviously vehicle physics are a fair bit more complex than that.

Also as it happens, the handling and collision detection on my soft body car is absolutely fine, the only bit that isn't working is the orientation (when introducing roll), which should be significantly easier than the handling and collisions. I have a collision routine for all 4 wheels and it works perfectly. My car is essentially a 3D rectangle tied together with constraints.

So really, orienting it to the terrain shouldn't be difficult at all, I have 4 points that define a plane (the wheels), maybe my best bet would be to simply orient the vehicle to the normal generated by these plane points.

Thanks for your help anyway jyk.

Share this post


Link to post
Share on other sites
Yeah, if you have a rectangle in 3-d, you should be able to build the orientation from that. You can compute the forward and side basis vectors by subtracting appropriate vertices of the rectangle from other vertices of the rectangle and normalizing, and then compute the up basis vector as the cross product of those two. Then, you can build a matrix from these basis vectors and a position vector (e.g. the center of the rectangle).

Share this post


Link to post
Share on other sites
Because I'm working on so many things at once I tend to overlook the obvious.

For some reason I was incrementing the rotation of each axis on the car from the angles defined by the front/back of the car, and the left/right wheels.

When of course, the best, simplest and most accurate thing to do is simply define the matrix from scratch for the car's orientation.

So obviously the car's z axis is the vector from the front and back of the car, the car's y axis is the plane normal defined by the 4 wheels, pointing up, and the x axis is the cross product between the z axis and normal.

It works perfectly now.

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