Skip to main content
gamedev.net
🔒 Locked 🎮 Unity

Optimize quaternion calculation

Started by MikeJM 9 replies 2.4k views
Original Post
MikeJM
MikeJM
Hello, I need to find the quaternion that rotates the forward vector (in my case (0,1,0) ) to the direction vector from entity a's position to entity b's position. What I'm doing right now seems woefully inefficient. In pseudo code: forward = 0, 1, 0 direction = normalize( b.position - a.position ) angle = acos( dot( forward, direction ) ) axis = cross( forward, direction ) return quaternion( axis, angle ); with vector cross( a, b ) { return v.x = a.y*b.z - a.z*b.y v.y = a.z*b.x - a.x*b.z v.z = a.x*b.y - a.y*b.x } quaternion::quaternion( axis, angle ) { return q.w = cos(angle/2) q.x = axis.x * sin(angle/2) q.y = axis.y * sin(angle/2) q.z = axis.z * sin(angle/2) } I think I'm missing an obvious large simplification here. Please help.
StealthNinja
StealthNinja
Both the dot product and the cross product can be simplified, since two components of forward are always 0. Just remove any math that gets multiplied by a 0.
CmpDev
CmpDev
The first obvious one I see is you are calculating sin half of the angle three times you should cache the value and use this value instead.
MikeJM
MikeJM
That was just pseudo code the actual low level optimizations are trivial.

I was thinking that there should be an algorithmic level optimization here.

For instance I already have the cosine of the angle so there should be a transformation from the cosine to the sine and cosine of the half angles without needing the arc cosine.
MikeJM
MikeJM
For instance I know that:

cos(angle) = cos(angle/2)*cos(angle/2) - sin(angle/2)*sin(angle/2)

but I'm not yet sure what I can do with that.
MikeJM
MikeJM
So far I have:


sin_half_angle = sqrt(.5 - b.y/2)
q.w = sqrt( direction.y/2 + .5 )
q.x = direction.z * sin_half_angle
q.y = 0
q.z = -direction.x * sin_half_angle

Any ideas how to remove one of those sqrts?
MikeJM
MikeJM
Still looking...
Rand
Rand
TBH, when it comes to optimising consoles etc, its best to keep it all as vectors and you end up doing a couple of quadword operations, which are very efficient.

Its nice though that there are PC programmers still bothered with optimising :)
Zipster
Zipster
You also have the formula sin(2x) = 2sin(x)cos(x). You get sin(2x) from the length of the cross-product vector (since this vector needs to be normalized anyway in order to perform the axis-angle conversion, just store the length). You can then compute either sin(x) or cos(x) from the square-root formula. Simply divide two times that quantity into the length of the aforementioned vector:

// Create vectors
direction = normalize(b.position - a.position)
axis.x = direction.z
axis.y = 0
axis.z = -direction.x

// Get axis length and normalize
sin_double_angle = length(axis)
axis /= sin_double_angle

// Compute sin and cosine of angle
sin_angle = sqrt(.5 - direction.y/2)
cos_angle = sin_double_angle / (2*sin_angle)

// Generate quaternion
q.w = cos_angle
q.x = axis.x * sin_angle
q.y = 0
q.z = axis.z * sin_angle
MikeJM
MikeJM
Quote:
Original post by Rand
TBH, when it comes to optimising consoles etc, its best to keep it all as vectors and you end up doing a couple of quadword operations, which are very efficient.

Its nice though that there are PC programmers still bothered with optimising :)


Actually I'm working on a cell phone :)
MikeJM
MikeJM
Thanks Zipster.

I had forgotten about the alternate form of the cross product formula. This should work nicely :)


Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.