Maths - discussion with minorlogic on forum

By: martinbaker ( Martin Baker )
lookat function  
2003-06-24 17:20

re: the following page:
http://www.euclideanspace.com/maths/algebra/vectors/lookat/index.htm

Here are some comments from minorlogic from earlier thread:

I tried to undersand what your "lookAt" function do ? Is it calculating quaternion
that rotate to "dir" "up" or something complicated ?

I try to find the way to calculate the such quternion , but nothing still can.
The fastest method that i know is a lookat for matrix and from matrix to
quaternion.

matrix->lookat - take a 2 sqrt and 3 cross
matrix_to_quaternion - take 1 sqrt

i tied to find solution but found for a general case still with 3 sqrt and lot
of other calculations. It produce quaternion to rotate from one dir-up into
other dir-up. It seems that your lookat work...

void LookAtQuaternion3(const vector3& dir, const vector3& up,
const vector3& from_dir, const vector3& from_up,
quaternion& q )
{
vector3 cross_dir = from_dir*dir;
float dot_dir = from_dir%dir;

quaternion dir_q( cross_dir.x, cross_dir.y, cross_dir.z, dot_dir );
dir_q.normalize();
dir_q.w += 1.0f;

quaternion qt = dir_q;
vector3 v = from_up;
// direct multyplication of quats
quaternion q0( v.x * qt.w + v.z * qt.y - v.y * qt.z,
v.y * qt.w + v.x * qt.z - v.z * qt.x,
v.z * qt.w + v.y * qt.x - v.x * qt.y,
v.x * qt.x + v.y * qt.y + v.z * qt.z);

vector3 Res2( qt.w * q0.x + qt.x * q0.w + qt.y * q0.z - qt.z * q0.y,
qt.w * q0.y + qt.y * q0.w + qt.z * q0.x - qt.x * q0.z,
qt.w * q0.z + qt.z * q0.w + qt.x * q0.y - qt.y * q0.x);

vector3 true_up = dir * ( up * dir ); // 2 cross product
vector3 rot_up(Res2);
vector3 cross_up = rot_up*true_up;
float dot_up = rot_up%true_up;

quaternion up_q(cross_up.x, cross_up.y, cross_up.z, dot_up );
up_q.normalize();
up_q.w += 1.0f;

q = up_q*dir_q;
q.normalize();
}

look terrible and it don't take any bad case.
Martin, if it intresting for you, point me please to a discussion about or let's
create new topic ?

minorlogic

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-06-24 17:21

minorlogic,

Yes, I would very much like to improve this page and your help would be much appreciated.

I can also remember seeing some discussions about lookat functions on various newsgroups and bulletin boards, for example the thread:
[www-vrml] Help with lookat function
which is here:
http://www.web3d.org/www-vrml/hypermail/2003/

What this is trying to do is to calculate how to aim a camera at a point, say it is initially pointing along the x axis, how do we rotate it to point to a given point? This is basically the same problem that we have already discussed, but this only makes sure that the point is in the middle of the image that the camera sees, but we may want to control what is 'up', in other words what appears at the top of the screen and what is at the bottom. So we need to rotate around a line from the camera to the aim point and this is where it seems to get messy.

Martin

By: nobody ( Nobody/Anonymous )
RE: lookat function  
2003-06-25 07:08

So i understand it right.
For a standsrt lookat ( the initial dir and up lay on basic axis) the fastest is lookat for matrix and convert to quaternion .

For a arbitrary oriented , i found only previous descreabed function. It create 2 quaternions ( as you do) one for "dir" , and second for "up".

To find a second up_quat , we rotate the initial "from_up" by dir quaternion and find quaternion that rotate about "dir" vector. I produce 2 cross product to be sure that "up" is perpendicular to "dir"

I think in your code you do the same , but not sure that "twist" found corect .
//
I sure that standart lookat for quaternion have a faster solution than 3 sqrt. It is very interesting to me to find a solution for this. But still have no idea how to do ...

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-06-25 09:32

Minorlogic,

> For a standsrt lookat ( the initial dir and up lay on basic axis)
> the fastest is lookat for matrix and convert to quaternion .

Is there a standard lookat for matrix? Do you know where I can get it?
Do you think it would be useful to have both matrix and quaternion versions of both the lookat and angle-between-vectors code on the web pages? As you say it is easy enough to convert between them.

> I think in your code you do the same , but not sure that "twist" found corect .
Yes, I'm not sure about it either, the axis is easy enough to find (it is just the line between the camera and the target) But how do we find the angle? I think it is the angle between two 3D vectors but in a 2D plane?

> I sure that standart lookat for quaternion have a faster solution than
> 3 sqrt.It is very interesting to me to find a solution for this. But still
> have no idea how to do ...

I don't either, are we stuck here?

Martin

By: nobody ( Nobody/Anonymous )
RE: lookat function  
2003-06-25 12:30

"Is there a standard lookat for matrix? Do you know where I can get it? "

void LookAt(const vector3& dir, const vector3& up, matrix33& m)
{
vector3 z(dir);
z.norm();
vector3 x( up * z ); // x = y cross z
x.norm();
vector3 y( z * x ); // y = z cross x
//------------
m.set_components(x,y,z );
}
x,y,z just are matrix components representing basis. Than conversion to quat take a 1 sqrt. This is a standart function in GL and DX API, but don't know its name.

"Do you think it would be useful to have both matrix and quaternion versions of both the lookat and angle-between-vectors code on the web pages? As you say it is easy enough to convert between them. "
don't know. But faster solve quat solution and convert to matrix.

" I think it is the angle between two 3D vectors but in a 2D plane? "

yes , in my code it is a plane perpendicular to "dir".
//--------------------
Martin a have idea :

void LookAtQuaternion(const vector3& dir, const vector3& up, quaternion& q )
{
vector3 z(dir);
//z.norm();
vector3 x( up * z ); // x = y cross z
//x.norm();
vector3 y( z * x ); // y = z cross x
// here vectors are perpendicular ich other.
float tr = x.x + y.y + z.z;
q.set( y.z - z.y , z.x - x.z, x.y - y.x, tr + 1.0f );
/*
if we could multiply our vectors that thay became the same length or multiplay the quaternion components that it all quat was scaled by some scale, than we have only one SQRT. The question is how to find that multipliers ? may be you can solve this ? Remember that we can easy get dot product between "up" and "z"
*/
q.norm();
}

By: nobody ( Nobody/Anonymous )
RE: lookat function  
2003-06-25 14:04

Or just create some system of equation that satisfy to conditions . It will show the complexty of the problem.

Lets think that initial direction vector is z(0,0,1), and initial up vector is y(0,1,0);

The first equation i think :
the "z_rotated" (z rotated by quaternion) give with "dir" vector the vector of zero length. Or the
dot between tham have to be length of dir vector dot*dot == dir.len_squared();

easy write by components

The second equation i think:
have a "y_rotated" (y rotated by quaternion) .
And "current_y" , it is from :
current_y = cross(z , cross(up, z ) ).

the same conditions . Their cross product is a 0 length and dot have a length of "current_y".

easy write by components

The third equation i think:
q.x*q.x + q.y*q.y + q.z*q.z +q.w*q.w = 0;

we need another equation to solve quaternion. (with 4 components). Or use some paralel dot and cross equations ?

//------------------------------
one thing disturb me ... that first two equation have a 2 solutions....
we can get a 4 solutions from first 2 equation ....( or not ?) and it look like the equation of 4 power.

if it realy 4 power equation, than we can't solve it less than 3 sqrt... :(.

Is such job hard for you ? for me it very hard (i am lazy)

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-06-25 15:48

The matrix to quat that I have here:
http://www.euclideanspace.com/maths/geometry/rotations/conversions/matrixToQuaternion/index.htm
Is:
public final void set(Matrix4f m1) {
w = Math.sqrt(1.0 + m1.m00 + m1.m11 + m1.m22) / 2.0;
double w4 = (4.0 * w);
x = (m1.m21 - m1.m12) / w4 ;
y = (m1.m02 - m1.m20) / w4 ;
z = (m1.m10 - m1.m01) / w4 ;
}
This assumes that the matrix is orthogonal (does making one row equal the cross product of the others do that?)
So if we expand out the lookat function we get:
vector3 z(dir);
z.norm();
vector3 x( up * z ); // x = y cross z
x.norm();
vector3 y( z * x ); // y = z cross x
qw = Math.sqrt(1.0 + x.x + y.y + z.z) / 2.0;
double w4 = (4.0 * w);
qx = (z.y - y.z) / w4 ;
qy = (x.z - z.x) / w4 ;
qz = (y.x - x.y) / w4 ;

I am sure this could be optimised by expanding out the cross products because not all the matrix elements are needed.

However I would be much happier if I knew how this matrix lookat method is derived. It is so simple that there must be something fundamental that I am missing.

Martin

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-06-26 06:09

I am trying to work out what the physical meaning of taking 3 vectors and putting them together in a matrix is? The vector cross product has a physical meaning (a vector which is perpendicular to the two input vectors) So can we give a physical interpretation to the matrix operation. Is it multiply the first vector by x, the second by y and the third by z then add them together? I'm not sure I may have changed over the rows and columns?

I'm still trying to think through this problem but I'm still confused.

Martin

By: nobody ( Nobody/Anonymous )
RE: lookat function  
2003-06-26 07:04

Yes , thats a method that use 3 sqrt , you wrote. It is a common method, to setup quaternion from "dir"- "up" , just look in some tutorials about camera orientation.

"I am sure this could be optimised by expanding out the cross products because not all the matrix elements are needed."
Yes we can , but a only little bit. Cross product is a fast enough operation. If we could avoid the sqrt's ...
//---
"However I would be much happier if I knew how this matrix lookat method is derived. It is so simple that there must be something fundamental that I am missing.
"
Yes it is fundamental.
Sorry , im not sure that use correct eanglish terminology...
The coordinate basis is a 3 ( noncomplanar )vectors and by default they are (dekart) (here and later i mean 3x3 matrix)
(1,0,0)
(0,1,0)
(0,0,1)
(it is a default matrix that do not transform)

In a computer graphics the matrix is Transform from one geometric system to other. It mean that matrix represent a 3d basis of the system, related to one of orthogonal unit basis.

And components of matrix is a transformed vectors of the 3d basis. It is a just coordinates of a transformed basis.

So physicaly matrix components is a vectors that represent
(1,0,0)
(0,1,0)
(0,0,1)
after rotation.
In a given lookat method we do cross product to be sure that "dir" and "up" will be perpendicular , than normalize components and we get normalized orthogonal matrix.

To see graphicaly just rotate the three vectors
(1,0,0)
(0,1,0)
(0,0,1)

and look on their projections to coordinates and see that it is a given transformation matrix.
(the same is correct not only for rotations , for scale and shear too).

If you want to get more , just take a look at "linear algebra".

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-06-26 15:28

Minorlogic,

> and look on their projections to coordinates and see
> that it is a given transformation matrix

Yes, I see what you mean, I need to understand projections onto a 2D plane. I have started to work this out on this page:
http://www.euclideanspace.com/maths/geometry/coordinatesystems/plane/index.htm
I need to do some more work on this before I can understand the lookup method better.

I think 'dekart' must be 'identity' matrix

Thanks, Martin

By: nobody ( Nobody/Anonymous )
RE: lookat function  
2003-06-27 09:53

Martin ! I'm hapy ! ! !
I found some thing very intresting. Look at it carefuly please !

The transform (rotation) from one rotation matrix to the other have a general very nice solution for a quaternion.

lets see the rotation matrix like a three vector.

if we have the matrix "from_matrix" and "to_matrix" (where from_x, to_x ... their components (unit) )

then:
vector3 cross_sum = cross(from_x, to_x) +
cross(from_y, to_y) +
cross(from_z, to_z) ;

float dot_sum = dot(from_x, to_x) +
dot(from_y, to_y) +
dot(from_z, to_z) ;

and quaternion representing rotation is a

quaternion q(cross_sum.x, cross_sum.y, cross_sum.z, dot_sum + 1.0f );
and than normalize it:
q.normalize();

And i think that a Matrix to quaternion conversions ( on your page) is special case of this equation with from_matrix as identity.
//--------------------------------
and we have :

void LookAtQuaternion4(const vector3& dir, const vector3& up,
const vector3& from_dir, const vector3& from_up,
quaternion& q )
{
// standart lookat
vector3 to_z = dir;
to_z.norm();
vector3 to_x = ( up * to_z );
to_x.norm();
vector3 to_y = to_z*to_x;
//----------------------------------------------
// let's think that from is a unit vectors
vector3 from_z = from_dir;
//from_z.norm(); if not unit
vector3 from_x = ( from_up * from_z );
//from_x.norm(); if not unit
vector3 from_y = from_z*from_x;

vector3 cross_sum = cross(from_x, to_x) + cross(from_y, to_y) + cross(from_z, to_z);
float dot_sum = dot( from_x, to_x) + dot(from_y, to_y) + dot(from_z, to_z);
q.set(cross_sum.x, cross_sum.y, cross_sum.z, dot_sum + 1.0f );
q.normalize();
}

Let's simplify this ! It look promising !
Sorry but i don't have any proove of this function ^( but it work , i tested it with a lot of random vectors. it give a right result. I found it with intuitive with graphics experiments.

It is still 3 sqrt but i have some general case to experiment...

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-06-27 15:49

Minorlogic,

Thanks for this, I agree its very interesting. Its going to take me some time to think through the issues, it looks so simple that it suggests that there must be some fundamental principle behind it that we haven't worked out yet?

It looks a bit like a way to translate from one coordinate system to another?

Again its spitting the matrix up into 3 vectors and I still need some more time to work through the equations for projecting 3D points onto a 2D surface.

> And i think that a Matrix to quaternion conversions ( on
> your page) is special case of this equation with
> from_matrix as identity.
The matrix to quaternion conversions can be derived from the way that the matrix and quaternion transform an arbitrary point, so can we work back from this to prove your method?

Anyway I need a few days (or possibly more) to work through the issues.

Martin

By: nobody ( Nobody/Anonymous )
RE: lookat function  
2003-06-27 16:16

martin ....
it look like matrix multiplication...
I know the place where is a sample,

http://www.gamasutra.com/features/19990702/data_structures_01.htm

here work with matrices like with 3 vectors , look here. It is a nice article.

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-06-28 09:06

I found the following interesting:
v_body.x = v.dot( X_body );
v_body.y = v.dot( Y_body );
v_body.z = v.dot( Z_body );
If I understood correctly this is equivalent to transforming the vector by the inverse of the matrix (or since its Orthogonal, by the transpose of the matrix).
Where does he get this from? Is it related to the issues that we have been discussing?
It is also interesting that he, thinks of a matrix as 3 vectors instead of a 3x3 array of scalars, but I could not see any fundamental reasoning behind this.

Martin

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-06-29 17:46

minorlogic,

I have been doing some work on the issues that we are discussing as follows:

I have been thinking about basis vectors and have put a simple explanation here:
http://www.euclideanspace.com/maths/algebra/matrix/orthogonal/index.htm

I have been attempting to prove matrix version of the lookat method form the quaternion version, I am now stuck but I have put my workings so far here:
http://www.euclideanspace.com/maths/algebra/vectors/lookat/index.htm

In order to do the calculations above I need a matrix version of the angle between two vectors, again I have got bogged down in complexity. Given the simplicity of the other results I was hoping that I would get a simple result. My working so far is here:
http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm

I have worked out the projection matrix to project any points in 3D space onto 2D plane, I have put this here:
http://www.euclideanspace.com/maths/geometry/coordinatesystems/plane/index.htm

Martin

By: nobody ( Nobody/Anonymous )
RE: lookat function  
2003-07-01 07:41

"I found the following interesting:
v_body.x = v.dot( X_body );
v_body.y = v.dot( Y_body );
v_body.z = v.dot( Z_body );
If I understood correctly this is equivalent to transforming the vector by the inverse of the matrix (or since its Orthogonal, by the transpose of the matrix).
Where does he get this from? "

The dot product give a module of projection to given vector (scaled by length).
Than if we think that matrix is 3 vectors , the coordinates of point in that frame is a projection to 3 given vectors. Like a standart point coordinates in (indentity frame) is a projections to basic Axes, that graphicaly it can be represented as combination of a given 3 basis vectors scaled by coordinates. It work not only for a rotation matrices.
//------------------
the prove of quaternion version can be derived from (i think)
taken from :
http://www.flipcode.com/cgi-bin/msg.cgi?showThread=00007782&forum=3dtheory&id=-1

"@minorlogic
I would say to make a quaternion that translates from M1 to M2 you should build it from the transient matrix:

M = inverse( M1 ) * M2
Q = M.asQuaternion()

The other way would be to make two quaternions and divide them

Q1 = M1.asQuaternion()
Q2 = M2.asQuaternion()
Q = inverse( Q1 ) * Q2

I don't know, depends on what is more expensive: matrix inverse or conversion to quaternion
"
So i think we deal with the matrix multiplication ( one is a transposed) and than comversion to quaternion.

And i think the second method "conversion to quats and multiplication on the inverse" take a 3 sqrt too...
here is a two versions in pseudo code:
quaternion lookat1( matrix33 m_from, matrix33 m_to )
{
matrix m = m_from.tranpose() * m_to;
return m.get_quaternion();
}

quaternion lookat2( matrix33 m_from, matrix33 m_to )
{
quaternion from = m_from.get_scaled_quternion();
quaternion to = m_to.get_scaled_quternion();
// we can work with scaled quats , it still keep rotation and than normalize it
from.inverse();
quaternion q = from*to;
q.normalize();
return q;
}

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-07-02 15:48

Minorlogic,

I think I see what you mean. If a point is defined in terms of a set of basis, it can be defined in terms of another set of basis by projecting the old basis onto the new basis.

> the prove of quaternion version can be derived from (i think)
> taken from :http://www.flipcode.com/ . <snip>

I did not find this but I am interested that Clifford Algebra was mentioned. Have you studied this? I am interested in this, I have been trying to work out:
1) The inverse for a 3D multivector (which contains scalar, vector, bivector and trivector).
2) How can 3D multivector represent affine transformations (ie without adding a 4th dimention)

Martin

By: nobody ( Nobody/Anonymous )
RE: lookat function  
2003-07-03 06:58

"I think I see what you mean. If a point is defined in terms of a set of basis, it can be defined in terms of another set of basis by projecting the old basis onto the new basis."
Yes , exactly.

"I did not find this but I am interested that Clifford Algebra was mentioned."
There is no proof , but some point that can help to derive.

" Have you studied this? I am interested in this, I have been trying to work out:
1) The inverse for a 3D multivector (which contains scalar, vector, bivector and trivector).
2) How can 3D multivector represent affine transformations (ie without adding a 4th dimention)
"
I tried to read some thing about Clifford Algebra , but still didn't find some thing that can be used in 3d. And lot of theory is not clear for me ( i am not a mathematician ). But i hear many and many good responds of clifford algenra, and i think it is very intrest.

I hope to find good tutorials for this, may be on your page it will come ?

minorlogic

By: martinbaker ( Martin Baker )
RE: lookat function  
2003-07-03 17:17

Minorlogic,

> I tried to read some thing about Clifford Algebra , but still didn't
> find some thing that can be used in 3d. And lot of theory is not clear
> for me ( i am not a mathematician ). But i hear many and many good
> responds of clifford algenra, and i think it is very intrest.

I am in a similar situation, I will do some more reading on the subject and if I don't find the answers to my questions I'll try to find a suitable newsgroup to ask my questions.

I'll put what I find on my website, I will also follow up the issues that we discussed and update the website with these issues also. So I'm going to be very busy in the coming weeks and months!

Thanks very much for giving me so much to think about!

Martin