🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Is there other method than quaternion or rotation matrix to orient animate characters?

Started by
34 comments, last by taby 2 years ago

I do not know if there is one. But quaternion and rotation matrix have their drawback. I think they are counterintuitive and complicated slow in computation. So, I propose the following method:

Computing orientation with complex multiplication but without trigonometric function

Today’s methods for computing orientation are quaternion and rotation matrix. However, their efficiencies are tarnished by the complexity of the rotation matrix and the counterintuitivity of quaternion. A better method is presented here. It uses complex multiplication for rotating vectors in 3D space and can compute orientation without angle and trigonometric functions, which is simple, intuitive and fast.

See the article with figures and equations here

https://www.academia.edu/80277267/Computing_orientation_with_complex_multiplication_but_without_trigonometric_function

1. Basic orientation

A rigid body can rotate around 3 orthogonal axes in space, see Figure 1. The state of these 3 rotations is the orientation of this body. The commonly used orientation systems are Euler angles and Tait–Bryan angles[1]. Two methods are usually used to compute orientation: quaternion [2] and rotation matrix [3]. But they have their drawbacks. For quaternion, the computation for rotating a vector p needs to multiply p on the left by the rotation vector q and on the right by its conjugate q-1, which implies two 4D multiplications with p in between, see equation (1). The weird thing is that the rotation vector q is not computed with the rotation angle  but its half /2, see (2), [4]. The half angle and the “sandwich multiplication” make the quaternion method counterintuitive.

For rotation matrix, the 3 angles of orientation are mingled in the 9 elements of the matrix where one gets easily lost. For example, in «Step by step rotation in normal and high dimensional space and meaning of quaternion»[5], the transformation matrix is equation (3) which is confusing with the messed trigonometric functions.

Can we find a better method? In fact, I have constructed a 3D complex number system in «Extending complex number to spaces with 3, 4 or any number of dimensions» [6] which computes easily the rotation of a vector in 3D space. The combination of this system with the step by step rotation described in «Step by step rotation in normal and high dimensional space and meaning of quaternion»[5] gives birth to a new method. This method can use directly the coordinates of points to rotate an object without using trigonometric function. We will explain first this method that uses complex multiplication and trigonometric function.

2. Rotation using complex multiplication

a. Mixed multiplication

We notice that when a 3D vector rotates around an axis that is perpendicular to it, the vector rotates in a plane and we call it the rotation plane. For using 2D complex multiplication in 3D space, we consider the rotation plane as a complex plane and use the 2D complex multiplication to rotate a vector in this plane.

Let (e1, e2) be a plane in 3D space, e1 and e2 the base vectors of the plane, so they 3D vectors. We make this plane equivalent to the complex plane using equation (7), that is, e1 corresponds to the real axis and e2 to the imaginary axis. u is a vector in the plane and is expressed in (8), with a and b being its components. Because the plane (e1, e2) is equivalent to the complex plane, u has an equivalent complex number u, which is expressed in (9). Let v be an other complex number which is expressed in (10).

We multiply u with v and the complex product uv is given in (11). The real and imaginary parts of uv are written in (12). Because the complex plane is equivalent to the plane (e1, e2), we replace the 1 and i that are in (11) with e1 and e2 and obtain uv in (13) which is a vector in the plane (e1, e2).

So, we have created a new type of multiplication: the vector u multiplied by the complex number v. The vector u is a 3D vector because e1 and e2 are 3D vectors. The product of this multiplication is uv which is a 3D vector too. We call this multiplication “mixed multiplication” and the product “mixed product”. We state the Definition 1.

Definition 1: Mixed multiplication and mixed product

The plane (e1, e2) is equivalent to the complex plane. u is a vector in this plane and equals ae1+be2. u is a complex number and equals a+bi. v is an other complex number. u is multiplied by v and the result of this multiplication is denoted as uv and equals real(uv)e1+ imag (uv)e2, with real(uv) and imag (uv) being the real and imaginary parts of the complex product uv. uv is a vector in the plane (e1, e2). This multiplication is called the mixed multiplication and uv the mixed product.

Let us use the newly defined mixed multiplication to rotate the vector u given in (14). The complex number u given in (4) is the complex equivalent of u and the complex number v is the ei given in (5). The complex product uv is computed in (6). Then the mixed product uv is given in (15) whose components equal the real and imaginary parts in (6). So, uv is well the vector u rotated by the angle . We see that mixed multiplication is a very easy way to compute the rotation of a 3D vector in the rotation plane.

See the article with figures and equations here

1. https://www.academia.edu/80277267/Computing_orientation_with_complex_multiplication_but_without_trigonometric_function

2. https://pengkuanonmaths.blogspot.com/2022/05/computing-orientation-with-complex.html

If you wish to download but cannot do from Academia, please click the second link in which please click the black button on the top-right corner of the view window to download

1. Basic orientation 1

2. Rotation using complex multiplication 1

a. Complex multiplication 1

b. Mixed multiplication 2

3. Reference frames 2

a. Ground frame and proper frame 2

b. Direction frame 3

4. Base vectors of the direction frame 3

a. Rotation around the z axis 3

b. Rotation around the y axis 3

c. The 3 axes of the direction frame 4

d. Direction frame and 3d complex number 4

5. Roll, Pitch and Yaw 4

a. Roll 4

b. Pitch and Yaw 4

6. Determination of the angles 5

a. Direction angles 5

b. Roll angle 5

c. Direction frame angles without trigonometric functions 5

d. Roll angle without trigonometric functions 6

7. Computation for oriented points 6

a. Position of one point 6

b. Computation without trigonometric functions 6

c. Procedure of computation without trigonometric function 7

8. Discussion 7

Advertisement

“Extending complex numbers to the 3D space” is literally what quaternions are. (You end up with 4 values, normalized, because Math.) And, if you count number of multiplies and additions, multiplying a vector by a matrix is the minimum possible numeric operations you can do while still having a linearly independent rotation.

Anyway – what you should post is an analysis of the number of multiplications and additions needed for your method, compared to vector-matrix multiplication, and quaternion multiplication. This will work very well to convince people whether it's worth their time to download/access your PDF file and try to read through it, or not.

Now, your claim that matrices make you “easy to get lost” seems like an interpretation problem, not a mathematical problem. Personally, I quite like it that I can just read the three basis vectors right out, and know exactly how my object will be rotated when I rotate it by that matrix. It's really hard to think of anything simper. Other rotational representations, such as the ones you suggest (Tait-Bryant, Heading-pitch-roll, XYX, etc,) and presumably the ones you propose in your paper, may also be helpful, depending on what particular frame of reference you're using, or which particular use case you have (navigating an airplane is different from animating a character is different from physically simulating a rigid body,) but given the strength of conventions already established, the burden of “this is actually easier” is pretty high.

enum Bool { True, False, FileNotFound };

After reading the paper a bit, not going into details, i think your idea could be described this way:

A rotation in 3D can be reduced to a 2D rotation around the axis of rotation.
To do so, we project the 3D vector to the plane of rotation axis, then use complex numbers to rotate the projected 2D vector, after that add the axis times signed distance from the plane to get back to 3D.

Do get this correctly? I'm more assuming. The paper is a bit confusing to me, as it's hard to describe this with words and 2D images. Would be interesting if you could post some minimal code representing your idea.
If my assumptions are right, then there would be nothing new or different about your method, but i may just miss it.

Would your method allow to solve some open problems, e.g. calculating a weighted average of N rotations?

hplus0603 said:
Now, your claim that matrices make you “easy to get lost” seems like an interpretation problem, not a mathematical problem.

The same issue with the claim of quaternions using half angles to be counter intuitive.
If we want to rotate a point 60 degrees, we can reflect it by the line at 30 degrees to get there. (Saw such example in some paper trying the demystify quaternions.)

It's probably no good idea to use such subjective impressions as arguments in your paper.
Proper arguments would be ‘storage of 6 (if so) vs. 9 matrix numbers’, or less operations to rotate a point (if so).

Also, i think you want to elaborate on a data structure from the start. Currently you talk about a method initially, but not so much about the required data structure.

@JoeJ

JoeJ said:

After reading the paper a bit, not going into details, i think your idea could be described this way:

A rotation in 3D can be reduced to a 2D rotation around the axis of rotation.
To do so, we project the 3D vector to the plane of rotation axis, then use complex numbers to rotate the projected 2D vector, after that add the axis times signed distance from the plane to get back to 3D.

Would your method allow to solve some open problems, e.g. calculating a weighted average of N rotations?

In fact, it is not the position vector of a point of the object that I rotate, but the proper frame of the object. For example, the proper frame of a man. Let us see the man as a cross with the vertical beam as his z axis from feet to head, the body axis, and his horizontal y axis is the straight line from his left to right hand while he open his arms to the horizontal. The x axis is in front of his chest.

My solution is to rotate the cross. First, we rotate the cross around the z axis, that is, the body axis. The arms rotate in the horizontal plane. Then, the unit vectors along the x axis and that of the y axis (the arms), are computed with complex multiplication.

Then, the z axis and y axis, that is, the body axis and the chest axis, are rotated in the vertical plane, which also, can be computed with complex multiplication. At this state, the body cross is in the desired orientation. Then, all the points of the man can be positioned in the ground frame by using the unit vectors in the x, y and z direction. This is a transformation of coordinates from the proper frame to the ground frame like with rotation matrix, but without building the matrix.

So, it is not a rotation of one position vector of the man at a time, but the rotation of his frame, then all his points are positioned in the ground frame. It is not the projection of a vector that is rotated, but the base vectors of the frame that are rotated. The base vectors are always perpendicular to the axis of rotation, so we can always use complex multiplication to rotate them and the orientation computation is simplified.

JoeJ said:

hplus0603 said:
Now, your claim that matrices make you “easy to get lost” seems like an interpretation problem, not a mathematical problem.

The same issue with the claim of quaternions using half angles to be counter intuitive.
If we want to rotate a point 60 degrees, we can reflect it by the line at 30 degrees to get there. (Saw such example in some paper trying the demystify quaternions.)

It's probably no good idea to use such subjective impressions as arguments in your paper.
Proper arguments would be ‘storage of 6 (if so) vs. 9 matrix numbers’, or less operations to rotate a point (if so).

Also, i think you want to elaborate on a data structure from the start. Currently you talk about a method initially, but not so much about the required data structure.

The argument with quaternion was just for noting what is the advantage of my method, which justifies that it deserves to be introduced.

I think one of the good arguments in my paper is that one can use complex function which x and y at once using builtin function, which reduces the number of line of code.

As for storage, I have indeed 6 instead of 9, because I define the orientation with the number a, b, d, f, g and h while matrix needs 9. And thus,

I've got to agree with hplus on this one. The standard matrix form is trivial to read, and has all kinds of good info to easily see the basis vectors, the position, and even a little flag to tell you if it is being used as a vector or a point. Although far less convenient to read the quaternion offers benefits for rotation, constant angular velocity, no gimbal lock, and most critically to our uses, less computation work for many operations.

The general expression is “put up or shut up”, and you made a bold claim in your paper:

An other advantage of this method is that the computation of orientation will be faster when the time consuming trigonometric functions are not used and because the process of computation has fewer steps. This is very beneficial for video games, computer-aided design (CAD) or mathematical graphics plotting.

Put up the code library and the disassembled CPU instructions. Prove to the world that it has even less computation work, or is demonstrably faster than what is used now on graphics cards.

I can't tell from your paper if it's faster or has fewer steps than what is currently used. If you provide detailed code both in C++ form and assembly form, especially one that takes advantage of SIMD operations, it would go a long way to prove your point.

Get your raw assembly, get the actual real-world timings versus industry standard best-of-class libraries. Put them side by side. Then it can be a good discussion.

You get those metrics in place and they prove your claim, then you can be sure your new, faster implementations will be adopted across the world.

@frob

I will shut up with you.

pengkuan said:
Then, all the points of the man can be positioned in the ground frame by using the unit vectors in the x, y and z direction. This is a transformation of coordinates from the proper frame to the ground frame like with rotation matrix, but without building the matrix.

You may not build a matrix, but if you calculate rotated points from 3 basis vector defining a frame, you replicate the exact same math a matrix times vector operation is doing:

vec3 rotated = matrix.row0 * local.x + matrix.row1 * local.y + matrix.row2 * local.z

local is a vec3 defining the point in local space, and the 3 rows of the 3x3 rotation matrix represent the same basis vectors you describe as axis.

The problem is: Your explanation is hard to follow precisely and may be interpreted in other ways you intend, so the general audience (like me), tends to assume: ‘The guy did just reinvent wheels, without noticing those wheels already exist.’
Combined with the other general assumption of ‘If there was a better method to do 3D rotations, we would already know about it for decades / centuries’, and we end up ignoring your method, although - eventually - we should take it more serious.

That's why i propose you show code instead equations and pictures, because this way you can replicate your idea exactly.
Then we can understand without risk of wrong interpretation, and we can compare storage and instructions with other methods to confirm technical advantage.

pengkuan said:
so we can always use complex multiplication to rotate them and the orientation computation is simplified.

Your description sounds you actually perform two rotations in sequence to get the final, desired frame.
Not sure if that's simpler than doing just one. It reminds me of Euler angles, which do a sequence of 3, making them very inefficient.

But the bigger question is: How do we define our desired orientation? What's your input and starting point? Multiple angles, one axis and one angle, something like a target point which we want to point at with one basis vector?

pengkuan said:
As for storage, I have indeed 6 instead of 9, because I define the orientation with the number a, b, d, f, g and h while matrix needs 9. And thus,

Post seems corrupted. I guess you tried to post a link. Forum editor tends to crash and cuts your text. Sadly they never fix this bug. Try to avoid links, or put them at the very end, or eventually in a second post.

The 6 numbers are an argument over storage hungry matrices.
Though, we could store just two rows and get the third from a cross product of them. I would assume your method includes the math of this cross product, so more instructions, but less storage.
Storage wise quaternions are very good with 4 numbers, so we often use them because reading memory is more expensive than doing more math instructions.

If your method gives some new sweet spot, yes we should learn and use it. Just post some code.

@JoeJ

JoeJ said:
That's why i propose you show code instead equations and pictures, because this way you can replicate your idea exactly. Then we can understand without risk of wrong interpretation, and we can compare storage and instructions with other methods to confirm technical advantage.

I’m not in game programming and I do not know code. So, I cannot provide code to show the thing. But I think that if in mathematics, we have fewer operations, in computing we will consume less time. So, I provide you with the formulae that show that there are fewer mathematical operations for computing rotation with my method.

Let me explain the joined image of formulae. When computing using trigonometric function, we have to compute cosine and sine for the N+1 thetas.

When computing the complex number way, we start with the complex number z0 and the multiplicative increment zd. The complex product z0*zd=z1 is the complex number of the angle theta1. Then we multiply z1*zd and obtain z2… This chain multiplication is done until N.

As complex multiplication is less time consuming than trigonometric function, the computation of complex multiplication for cosine and sine for the N+1 thetas will use less time than with trigonometric function. Since we have 3 angles to compute, we save 3 times the same amount of time.

Edgar Malinovsky has shown that multiplication wins against trigonometric function. He computed using multiplication instead of trigonometric function to generate 3D fractals objects. He noticed a real acceleration of computation speed. The images of these objects are here as proof.

https://pengkuanonmaths.blogspot.com/2022/04/rendering-of-3d-mandelbrot-lambda-and.html

JoeJ said:
Your description sounds you actually perform two rotations in sequence to get the final, desired frame. Not sure if that's simpler than doing just one. It reminds me of Euler angles, which do a sequence of 3, making them very inefficient.

I have forgotten to mention the rotation around the chest axis. This will make 3 rotations. But, the rotations around the head axis, arms axis and chest axis are more intuitive then Euler's rotations.

JoeJ said:
Post seems corrupted. I guess you tried to post a link. Forum editor tends to crash and cuts your text. Sadly they never fix this bug. Try to avoid links, or put them at the very end, or eventually in a second post.

Thanks for signaling this to me. Have corrected the top post. But I put the links here anyway

1. https://www.academia.edu/80277267/Computing_orientation_with_complex_multiplication_but_without_trigonometric_function

2. https://pengkuanonmaths.blogspot.com/2022/05/computing-orientation-with-complex.html

JoeJ said:
Storage wise quaternions are very good with 4 numbers, so we often use them because reading memory is more expensive than doing more math instructions.

This is also an argument for complex multiplication because real and imaginary parts of a complex numbers are stored together. Fetching one complex number is less expensive than Fetching 2 real numbers. Complex number multiplication is surely more optimised than multiplication of 2 2D vectors.

This topic is closed to new replies.

Advertisement