• Create Account

# quasar3d

Member Since 01 Dec 2001
Offline Last Active Aug 20 2014 04:01 AM

### #5173371Quaternion angle with itself > 0.001

Posted by on 13 August 2014 - 10:58 AM

Hey guys,

I'm in the process of working out my math library, and so I was testing out a function that returns the angle between two quaternions..

{ return 2.0f * acos( Abs( Dot4( qa, qb ) ) ); }

.. but for some reason, I'm either getting a lot of floating point error in the result, or I'm not checking for a situation that I should be. While testing a quaternion (which was generated by a random axis+angle rotation and appears to be very close to normalized)..

{ x=0.0172970667 y=-0.0245058369 z=0.0205858145, w=-0.999337912    }

.. with itself, I'm getting a result angle of 0.00138106791 (or almost 0.1 degrees)..

I'm just wondering if this is acceptable error when working with float variables? And is there anything I can do to improve this issue other than switching to double type or something else as drastic?

edit note: After testing some more, the highest "error angle" I've been able to generate (through random axis-angles) is 0.001953125. And that was getting the angle (from itself) of a quaternion generated by the axis @ angle: { -0.833756,0.551120,-0.033417 @ 2.960138559341 } (quaternion result: { -0.830327,0.548853,-0.033279,0.090603 } )

Thank you

The reason why the error gets so big, is that the inverse cosine function is very steep around 1. This has the effect that the (even exact) inverse cosine of a dot product which is only a tiny bit off, will give a pretty big angle difference.

For example, the cosine of 0.1 degree is 0.99999847691, and so if your dot product would give 0.99999847691 (which is a pretty good approximation of 1), the angle you get will be around 0.1

I bet that the reason why, after renormalizing your quaternions, you did get the correct result, was that this gave a dot product of exactly 1, but I don't think this will work for all quaternions. There will certainly be normalized quaternions, which give a dot product with themselves not exactly equal to 1.

The good news is that it's only this bad when you're computing the angle between quaternions which are almost parallel. For quaternions which are not nearly parallel, the result will be more accurate.

### #5114256Quaternions and matrices

Posted by on 04 December 2013 - 02:44 AM

Another important reason is of course that you usually combine the translation, rotation, and any other transformations into a single matrix which you use to transform your points. So indeed, it's usual to use quaternions while animating, but once you have determined the transformation for a mesh, you create a matrix, and use that matrix to transform its vertices.

### #5113366Homogenous coordinates

Posted by on 30 November 2013 - 05:11 PM

An easy way to get a hang of 3D homogeneous coordinates (which consist of 4 coordinates) is to see them as a higher dimension analogue to fractions.

- A fraction $a/b$ represents a number on the 1D real axis, but really consists of 2 "coordinates", ie. (a,b). In a similar way, the 3D vector (x/w,y/w,z/w) corresponds to the 4D homogeneous vector (x,y,z,w).
- Just as with fractions, multiplying all components by the same value doesn't change its value, ie. a/b = (sa)/(sb), or in coordinate form (a,b) = (sa,sb), for some scalar s. Similarly, since (x/w,y/w,z/w) = ((sx)/(sw),(sy)/(sw),(sz)/(sw)), the homogeneous vectors (x,y,z,w) and (sx,sy,sz,sw) are considered the same vector.

And then it just so happens that many operations on 3D vectors can be done much more elegantly on their homogeneous representation, most importantly, transformations like translation and projection become representable by just a matrix. Since for a 4x4 matrix a 4D vector and a scalar s, A(sx) = s(Ax), multiplying a homogeneous vector by a matrix is well defined, ie. if two vectors are equivalent (they represent the same 3D point, even while their 4D representation may be different), they will still be equivalent after they're multiplied with a matrix.

### #5041813Cross Product of Many Vectors

Posted by on 11 March 2013 - 06:21 AM

This is exactly what least squares solves.

### #5017425Calculating the required rotation.

Posted by on 04 January 2013 - 07:34 AM

There's indeed a most natural rotation. It's the one that leaves vectors perpendicular to the plane of A and B invariant.

To derive such a matrix, note that any composition of 2 (or any even number of) reflections is a rotation. With this, you can easily construct a matrix that satisfies your requirements.

Let S_1 be the matrix that reflects A to -A, and let S_2 be the matrix that reflects A + B to -(A + B). The composition S_2 S_1 is then your rotation matrix.

In vectors, reflecting a vector x in a normal vector n is

{eqn} x' = x - 2 n (n \cdot x) {/eqn}

or in matrix notation, where vectors are column vectors

{eqn}
x' = x - n (n^T x)
= (I - n n^T) x
{/eqn}

so your reflection matrix is then {eqn} I - n n^T {/eqn} so your rotation matrix, which rotates a to b

{eqn} R = (I - \frac{(a + b) (a + b)^T}{|a + b|^2)(I + \frac{a a^T}{|a|^2}) {/eqn}

EDIT: Can't get latex to work

### #4896536Math challenge (no particular purpose, prize = a -50% coupon on steam)

Posted by on 22 December 2011 - 09:03 AM

Will be nice for my christmas holiday, but I have a suspicion it's an NP problem, so probably won't be very easy.

### #4887303find rectangle around points on plane

Posted by on 24 November 2011 - 10:46 AM

The matrix you create is the matrix that maps the xz plane with z = 0 to your original plane (the inverse of the matrix you eventually transform your vertices with). The rotation part of this matrix yields a plane through the origin, parallel to portalPlane. Then to let it map to portalPlane, you have to shift this plane by -portalPlane.w into the direction of its normal. This means that you can simply set the last column of planeMatrix to normal * -portalPlane.w. There's no need to transform this by the rotation part of your matrix, as you are doing now.

Also, right now you do the transpose after you add the translation part, even though you do use the last column instead of the last row for it. To fix this, either add the rotation to the last row, or do the transpose before you add the translation.

### #4886910Fourier transform on image - problem with sharpening filter

Posted by on 23 November 2011 - 10:04 AM

And still she's beautiful:)

### #4886590find rectangle around points on plane

Posted by on 22 November 2011 - 09:38 AM

Yes, Kryzon gave an explanation how to switch betwen these two spaces.

Kryzon gave an explanation how to switch a space which has the plane with the points aligned on the x,y plane. This doesn't turn the bounding rect into an axis aligned one though.

### #4879457Create a sphere that intersects another at right angles

Posted by on 01 November 2011 - 05:27 PM

If the tangent lines make an angle of 90 degrees, than so do the vectors from the centers of the circles to the points where they intersect. Using this it should be pretty easy to solve.

### #4870894Fixed Point vs. Fractional Integers

Posted by on 09 October 2011 - 04:44 PM

Aren't these two just the same?

### #4851730LookAt matrix

Posted by on 20 August 2011 - 03:28 PM

your matrix takes the camera axes to world space axes, but you actually want to convert from world to camera space, so you have to invert your matrix, which, since your matrix is orthonormal, is just its transpose (the rotation part that is).

### #4838001Converting a polygon into the least number of triangles possible?

Posted by on 20 July 2011 - 09:49 AM

http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf ;)

### #4817652Gödelization - help needed.

Posted by on 30 May 2011 - 02:38 PM

You probably know (and as luca-deltadesco explained) that any integer can be factored into a unique prime factorization, and Gödelization is a trick that uses this fact to encode a whole sequence of numbers into a single integer by taking the product of the first prime raised to the power of the first element of your sequence, the second prime raised to the power of the second element, and so on. This gives you a single integer that encodes your whole sequence.

for example, the sequence of the first 4 squares (1,4,9,16) can be encoded as

2^1 * 3^4 * 5^9 * 7^16 = 10515106938037816406250

### #4802277Total area of overlapping circles

Posted by on 24 April 2011 - 06:10 AM

irreversible, do you actually need the area of their overlap, or just a boolean value which tells whether they overlap or not?

If you actually need the area, then I think a simple way to do it is:
- compute the intersection points of all pairs of circles
- discard points that lie outside any other circle
- compute the convex hull of these points
- compute the area as the area of the convex hull polygon, plus the area of the parts between each edge of the convex hull, and the corresponding circular arc.

There are probably many ways to do the first two steps quicker than N^2

Let me know if this is clear. I can probably draw some pictures to clarify things a bit.

But if you only need to know whether they intersect at all, then there are probably easier solutions.

I want to calculate the overall unique coverage of my units' FOV (which are all circular). Luckly I don't need to do this every frame, but I can expect to have up to several dozens of circles that can overlap each other partially, fully ot not at all, although as a game-specific dynamic, there should not be any disjoint circles (that is, there can be, but I'm interested in the total coverage of all circles that are chain-connected to one control circle).

I'm having some trouble coming up with a a solution that is both fast and reasonably exact. Truth be told, since this is for a game, I'm not bound by any ground rules and could simply opt for a tile coverage count (which should be doable in linear time); however, the problem itself intrigues me and I'm wondering if I could do away with the N^2 intersection tests that I'm guessing I'm stuck with if I want an exact method.

PS - even though this might seem like a school assignment, it is not.

You don't have to do N^2 intersection tests if you have a scenegraph of some sort, for a 2D game you could simply split the level into section, then you simply only run tests against units in the same or neighbouring sections. (It will reduce the worst case scenario slightly, and depending on section size (Which would have to be atleast as big as the biggest FoV for the method to work).

also, checking if 2 circles intersect eachother is extremely fast (just compare the sqared distance with the squared sum of the circles radius) (The reason for comparing squared values is that it eliminates the need to calculate the square root in the distance calculation)

You can have a set of circles that all mutually intersect, but which still have an empty total intersection.

PARTNERS