correction to shortestArcQuat

Post Reply
melax
Posts: 42
Joined: Mon Apr 24, 2006 4:55 pm

correction to shortestArcQuat

Post by melax »

Need to make a small correction to the function shortestArcQuat() in bullet. Any math library that has a similar function might want to also ensure the implementation is correct.

The problem is in the special case where the two vectors are collinear, but facing opposite directions. Refer to line 00301 in the code snippit below, where d approaches -1:

Code: Select all

00296 shortestArcQuat(const btVector3& v0, const btVector3& v1) // Game Programming Gems 2.10. make sure v0,v1 are normalized
00297 {
00298         btVector3 c = v0.cross(v1);
00299         btScalar  d = v0.dot(v1);
00300 
00301         if (d < -1.0 + SIMD_EPSILON)
00302                 return btQuaternion(0.0f,1.0f,0.0f,0.0f); // just pick any vector
00303 
00304         btScalar  s = btSqrt((1.0f + d) * 2.0f);
00305         btScalar rs = 1.0f / s;
00306 
00307         return btQuaternion(c.getX()*rs,c.getY()*rs,c.getZ()*rs,s * 0.5f);
00308 }
When d approaches -1, the solution is indeed not unique. There are many 180 degree rotations that will rotate "from" vector v0 to "to" vector v1. However the axis of the rotation must be orthogonal to v0 (and consequently v1). There are many solutions, but many more wrong solutions. To do this correctly, you just need to find any vector 'a' that is orthogonal to v0 and then the quaternion to return is simply (a.x a.y a.z 0)


When I wrote the game gem i focused more on explaining how the half angle formulas could be used to make a robust implemetation as v1 and v0 converged to the same vector - a much more common case. I mention the opposite case (v0=-v1) but didn't include all the details or provide a proper implementation in the code. I probably should have discussed this more. I suspect there are a lot of implementations out there that dont quite handle this properly. Perhaps this post should also go into bullet's general discussion forum too.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: correction to shortestArcQuat

Post by Erwin Coumans »

Hi Stan,

Thanks for the report. Do you have a reproduction testcase that shows the problem? And/or a patch, so we can fix it?

There is an issue report here, to track progress:
http://code.google.com/p/bullet/issues/detail?id=44

Thanks again,
Erwin
melax
Posts: 42
Joined: Mon Apr 24, 2006 4:55 pm

Re: correction to shortestArcQuat

Post by melax »

Code I sent to Erwin in case anybody is interested.

Code: Select all


SIMD_FORCE_INLINE btQuaternion 
shortestArcQuat(const btVector3& v0, const btVector3& v1) 
    // Game Programming Gems 2.10. make sure v0,v1 are normalized
{
	btVector3 c = v0.cross(v1);
	btScalar  d = v0.dot(v1);

	if (d < -1.0 + SIMD_EPSILON)
	{
		extern SIMD_FORCE_INLINE void btPlaneSpace1 (const btVector3& n, btVector3& p, btVector3& q);  // Please Include bttransformutil.h instead of this hack!!!
		btVector3 n,unused;
		btPlaneSpace1(v0,n,unused);
		return btQuaternion(n.x(),n.y(),n.z(),0.0f); // just pick any vector that is orthogonal to v0
	}
	btScalar  s = btSqrt((1.0f + d) * 2.0f);
	btScalar rs = 1.0f / s;

	return btQuaternion(c.getX()*rs,c.getY()*rs,c.getZ()*rs,s * 0.5f);
}



Rather than writing and adding a new 3d "perp" or "orth" function, I found a routine within Bullet that provided what was needed.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: correction to shortestArcQuat

Post by Erwin Coumans »

This fix has already been rolled into Subversion, and available in the latest Bullet 2.68 beta 2.

The btPlaneSpace1 has been moved to btVector3, so it is more widely available.
Thanks a lot Stan,
Erwin
shogun
Posts: 34
Joined: Tue Mar 04, 2008 3:16 pm

Re: correction to shortestArcQuat

Post by shogun »

I don't see that this is fix is in SVN ... am I doing something wrong?
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: correction to shortestArcQuat

Post by Erwin Coumans »

No, I was doing something wrong :oops:

It has been finally committed, ready for Bullet 2.75 release:
http://code.google.com/p/bullet/source/detail?r=1707

Thanks a lot for the reminder!
Erwin
Post Reply