在实时应用程序中高效使用四元数
4.95/5 (11投票s)
各种使用四元数的方法，
引言
在游戏和模拟中，四元数通常用于表示三维实体的方向，而不是矩阵。四元数只需要 4 个浮点数，而 3x3 矩阵则需要 9 个浮点数。四元数乘法也只需要 16 次乘法和 12 次加法，而矩阵乘法则需要 27 次乘法和 18 次加法。
尽管有这些优点，但为基于四元数的实体实现能够最大化时间效率的代码仍然很棘手。在本文中，我们将探讨在性能至关重要的实时应用程序中使用四元数时如何实现最佳性能。
向量变换
虽然四元数乘法在计算上相对便宜，但对 3D 向量进行四元数变换则不然。在这种情况下，等效的矩阵运算实际上计算起来更便宜，只需要 3 次点积，总共 9 次乘法和 6 次加法。即使是优化版本的四元数运算也需要 2 次叉积，总共 15 次乘法和 8 次加法。因此，许多 AI 和游戏程序员会为每个实体的方向保留一个单独的矩阵副本以及四元数副本。
让我们考虑一个典型的 AI 函数“updatePursuitAction”，其中 AI 实体必须确定其位置到它想要追逐的目标位置的方向。然后它会改变方向以拦截目标。此函数在每一帧都会被调用，直到 AI 系统决定实体应切换到其他 AI 操作。为了确定方向，我们必须将实体与其目标之间的世界空间向量变换到实体的局部空间。
在 示例代码 中，我们有两个类，它们以各自不同的方式实现相同的 AI 函数。FastGameEntity 类使用四元数实现，而 SlowGameEntity 类使用矩阵实现，该矩阵表示为对应于等效矩阵的 3 行（或按列主序矩阵的 3 列）的三个单独的 3D 向量。
图 1。
virtual void FastGameEntity::updatePursuitAction( const D3DXVECTOR3 &targetPos )
{
//get vector from my pos to the target
D3DXVECTOR3 toTarget = targetPos - pos_;
//transform into my local space - 15 mults 8 adds
D3DXQUATERNION conjQ;
D3DXQuaternionConjugate( &conjQ, &ori_ );
rotateVectorWithQuat( conjQ, toTarget );
//update direction to intercept target
//...
}
virtual void SlowGameEntity::updatePursuitAction( const D3DXVECTOR3 &targetPos )
{
//get vector from my pos to the target
D3DXVECTOR3 worldToTarget = targetPos - pos_;
//transform into my local space
//transform vector with orthonormal basis - 3 dot products - 9 mults 6 adds
D3DXVECTOR3 localToTarget;
localToTarget.x = D3DXVec3Dot( &side_, &worldToTarget );
localToTarget.y = D3DXVec3Dot( &up_, &worldToTarget );
localToTarget.z = D3DXVec3Dot( &dir_, &worldToTarget );
//update direction to intercept target
//...
}
对于 FastGameEntity，我们可以通过简单地使用目标的当前位置调用“updatePursuitAction”函数来更新其 AI。对于 SlowGameEntity，我们还必须在每一帧执行另一个函数，“UpdateRotation”。此函数将实体的四元数方向转换为矩阵形式。必须这样做才能使矩阵与四元数保持同步，确保两者始终表示相同的方向。此额外操作至少需要 12 次额外的乘法和 12 次额外的加法。
图 2。
virtual void FastGameEntity::updateAI( )
{
D3DXVECTOR3 targetPos;
updatePursuitAction( targetPos );
}
virtual void SlowGameEntity::updateAI( )
{
D3DXVECTOR3 targetPos;
updatePursuitAction( targetPos );
UpdateRotation();
}
如果我们使用 AMD CodeAnalyst 分析这些函数，我们会发现 FastGameEntity 版本确实比 SlowGameEntity 版本运行得更快，尽管它使用了更昂贵的四元数变换。这是因为从四元数转换为矩阵的额外步骤抵消了矩阵变换可能提供的任何优势。
在图 1 中，我们看到了分析器输出，FastGameEntity 调用了函数，用绿色下划线标出；SlowGameEntity 调用了函数，用红色下划线标出。现在我们可以看到 SlowGameEntity 函数占用的时间更多。
图 1
CS:EIP,符号 + 偏移,64 位,定时器样本,
"0x401c90","D3DXQuaternionConjugate","","2.2",
"0x4017b0","D3DXVec3Cross","","9.4",
"0x401b10","D3DXVec3Dot","","10.67",
"0x401780","D3DXVECTOR3::D3DXVECTOR3","","7.31",
"0x401ab0","D3DXVECTOR3::operator-","","13.92",
"0x403900","FastGameEntity::FastGameEntity","","0.12",
"0x401db0","FastGameEntity::updateAI","","0.12",
"0x401de0","FastGameEntity::updatePursuitAction","","0.12",
"0x4039d0","GameEntityBase::GameEntityBase","","15.89",
"0x401600","main","","0.23",
"0x403200","operator new","","0.12",
"0x4012f0","quatToMatrix","","25.17",
"0x4010e0","rotateVectorWithQuat","","10.21",
"0x403810","SlowGameEntity::SlowGameEntity","","0.23",
"0x4018c0","SlowGameEntity::updateAI","","0.12",
"0x401a40","SlowGameEntity::updatePursuitAction","","0.12",
这是否意味着在处理基于四元数的实体时，我们永远不应使用矩阵变换？不，因为在某些情况下，它们会产生更好的性能结果。在上面的 AI 示例中，我们每帧只需要进行一次变换，但如果我们必须进行数千次呢？例如，一个需要由实体当前旋转变换的数千个顶点的网格。如果使用四元数运算来完成，将需要比使用矩阵更多的计算。因此，在这种情况下，先将四元数转换为矩阵会更有意义，这样所有的顶点都可以用矩阵进行变换。
在图 3 中，我们有两个不同版本的“transformManyVertices”函数，一个使用四元数，一个使用从四元数转换的矩阵。
图 3。
virtual void SlowGameEntity::transformManyVertices( unsigned int numVerts )
{
D3DXVECTOR3 *vertices = new D3DXVECTOR3[ numVerts ];
D3DXVECTOR3 transformedVertex;
D3DXQUATERNION conjQ;
D3DXQuaternionConjugate( &conjQ, &ori_ );
for ( unsigned int i=0; i< numVerts; i++)
{
//transform into my local space - 15 mults 8 adds
transformedVertex = vertices[i];
rotateVectorWithQuat( conjQ, transformedVertex );
}
delete [] vertices;
}
virtual void FastGameEntity::transformManyVertices( unsigned int numVerts )
{
UpdateRotation();
D3DXVECTOR3 *vertices = new D3DXVECTOR3[ numVerts ];
D3DXVECTOR3 col1( side_.x, up_.x, dir_.x );
D3DXVECTOR3 col2( side_.y, up_.y, dir_.y );
D3DXVECTOR3 col3( side_.z, up_.z, dir_.z );
for ( unsigned int i=0; i< numVerts; i++)
{
//transform into my local space
//multiply vector with rotation matrix - 3 dot products - 9 mults 6 adds
D3DXVECTOR3 transformedVertex;
transformedVertex.x = D3DXVec3Dot( &col1, &vertices[i] );
transformedVertex.y = D3DXVec3Dot( &col2, &vertices[i] );
transformedVertex.z = D3DXVec3Dot( &col3, &vertices[i] );
}
delete [] vertices;
}
如果我们对此进行分析，我们会发现现在矩阵版本比四元数版本快，即使我们必须执行转换为矩阵的额外步骤。因此，是否使用矩阵而不是四元数取决于您尝试实现的具体功能。一如既往地进行优化，我们应该使用分析器来确定代码中的实际瓶颈，从而确定真正需要优化的内容。
图 2
CS:EIP,符号 + 偏移,64 位,定时器样本,
"0x4018a0","`vector constructor iterator'","","0.12",
"0x4026f0","D3DXQUATERNION::D3DXQUATERNION","","0.64",
"0x401800","D3DXVec3Cross","","21.36",
"0x401b60","D3DXVec3Dot","","1.17",
"0x4017d0","D3DXVECTOR3::D3DXVECTOR3","","18.78",
"0x403c50","FastGameEntity::FastGameEntity","","0.18",
"0x401ea0","FastGameEntity::transformManyVertices","","0.23",
"0x403ca0","GameEntityBase::GameEntityBase","","8.07",
"0x401600","main","","0.06",
"0x403360","operator new","","0.06",
"0x4010e0","rotateVectorWithQuat","","47.63",
"0x403bf0","SlowGameEntity::SlowGameEntity","","0.12",
"0x401ba0","SlowGameEntity::transformManyVertices","","0.12",
更新方向
当涉及到改变实体的方向时，许多 AI 和游戏程序员依赖于欧拉角和方向的矩阵形式来计算实体每一帧的新方向。这需要将新的欧拉角转换为四元数形式，然后才能渲染实体，这个操作在计算上相对昂贵。它需要使用大量的正弦和余弦，或者乘法三个四元数，这会导致大量的乘法和加法。我们如何避免这种情况？另一种选择是使用角速度来计算对象的角运动，每个旋转轴一个。这些速度可以存储为单个 3D 向量。这种方法的好处是更新实体方向所需的计算量大大减少，只需要与速度向量进行一次四元数乘法和一个四元数加法。
SlowGameEntity 类和 FastGameEntity 类都有自己的“calcOrientation”函数版本，如图 4 所示。
图 4。
virtual void calculateOrientation( float dt )
{
//calculate angular velocity
//...
//update quaternion with angular velocity vector
ori_ += ( (ori_ * angularVel_) * 0.5f * dt );
}
virtual void calculateOrientation( float dt )
{
//calculate new euler angles
//...
//update current orientation with new quaternion formed from euler angles
D3DXQUATERNION tempQ;
//D3DXQuaternionRotationYawPitchRoll( &tempQ, yaw_, pitch_, roll_ );
quatFromEuler( tempQ, yaw_, pitch_, roll_ );
ori_ = tempQ * ori_;
}
再次查看分析器输出，我们发现角速度方法速度稍快。
图 3
CS:EIP,符号 + 偏移,64 位,定时器样本,
"0x406eb8","_cos_pentium4","","1.32",
"0x407428","_sin_pentium4","","1.15",
"0x404410","calcAllEntitysOrientation<SlowGameEntity>","","0.33",
"0x405240","cos","","0.16",
"0x401980","cosf","","1.65",
"0x401870","D3DXQUATERNION::D3DXQUATERNION","","0.82",
"0x401ec0","D3DXQUATERNION::operator*","","0.16",
"0x402230","D3DXQUATERNION::operator*","","0.33",
"0x4021d0","D3DXQUATERNION::operator+=","","3.62",
"0x402170","FastGameEntity::calculateOrientation","","0.16",
"0x403c80","GameEntityBase::GameEntityBase","","23.39",
"0x4032f0","operator new","","0.16",
"0x401000","operator*","","25.86",
"0x401450","quatFromEuler","","29.16",
"0x405370","sin","","0.33",
"0x4019a0","sinf","","3.95",
"0x401e50","SlowGameEntity::calculateOrientation","","2.64",
"0x403a60","SlowGameEntity::SlowGameEntity","","0.49",
与缓存交好
最后，让我们看看如何使四元数更具缓存友好性，鉴于从缓存访问内存的速度更快，这通常是提高性能的好方法。由于缓存的设计原则是空间局部性，我们将把四元数组织在连续的内存中，使它们始终相邻。缓存能够对这些数据进行操作，减少缓存未命中，因为它不是一次只加载一个四元数，而是加载所有相邻的字节以填充一个缓存行。缓存行的大小取决于硬件，但通常为 64 字节。因此，如果所有四元数都相邻，加载一个四元数也会同时加载其他四元数。如果我们编写按顺序处理四元数的代码，当需要它们时，很可能它们已经在缓存中了。
因此，在示例代码中，我们有两个不同的类：SlowCacheObject 和 FastCacheObject。SlowCacheObject 包含两个四元数，一个用于对象的局部空间变换，另一个用于其世界空间变换。FastCacheObject 不直接包含这些四元数，而是包含一个指向包含它们的结构的指针。这样，所有 FastCacheObjets 的变换都可以保存在这些结构的连续数组中。
图 6 显示了这两个类。
图 6。
class SlowCacheObject : public ObjectBase
{
public:
virtual void updateWorldTransform( SlowCacheObject *parent )
{
if ( parent )
D3DXQuaternionMultiply( &worldTransform_, &localTransform_, parent->getWorldTransform() );
}
D3DXQUATERNION *getWorldTransform() { return &worldTransform_; }
protected:
D3DXQUATERNION localTransform_;
D3DXQUATERNION worldTransform_;
};
class FastCacheObject : public ObjectBase
{
public:
struct Transforms
{
D3DXQUATERNION localTransform_;
D3DXQUATERNION worldTransform_;
};
Transforms *getTransforms() { return transforms_; }
void setTransforms( Transforms *transforms )
{
transforms_ = transforms;
}
virtual void updateWorldTransform( FastCacheObject *parent ){}
protected:
Transforms *transforms_;
};
我们将创建两个树，一个包含 SlowCacheObject 实例，一个包含 FastCacheObject 实例。每个树都有一个根节点，它有两个子节点。每个根子节点又会有四个子节点。两个树中的节点都将单独分配，因此它们在内存中不会相邻。SlowCacheObject 树的四元数将存储在每个节点中。对于 FastCacheObject 节点，将有三个 Transforms 结构数组，每个数组对应树中的一个级别。这些数组将包含每个节点在连续内存中的四元数。
为了更新树中每个对象的世界变换，我们必须将其局部变换与父节点的世界变换相乘，然后将其存储在对象自己的世界变换四元数中。对于两个树，我们将以自顶向下的方式进行，从根节点开始向下工作。图 4 显示了 SlowCacheObject 树的过程，图 5 显示了 FastCacheObject 树的过程。
在示例代码中，更新 SlowCacheObject 树的所有代码都包含在 Node.h 和 SlowCacheObject.h 文件中。对于 FastCacheObject 树，更新树的所有功能都包含在 QuatDemoCode.cpp 文件中的“updateWorldTransforms”函数中。正如您从上面的图表中看到的，SlowCacheObject 树中的方法需要来回交替地处理树的级别。处理完所有左节点叶子后，我们必须返回到第二级，然后从右节点开始重复此过程。在 FastCacheObject 中，我们只需迭代两个数组并执行四元数乘法。
如果我们对这段代码进行分析，就会得到图 6 所示的结果。
图 6。
CS:EIP,符号 + 偏移,64 位,定时器样本,
"0x40423a","D3DXQuaternionMultiply","","1.2",
"0x40423a","D3DXQuaternionMultiply+0","","1.2",
"0x401c10","FastCacheObject::getTransforms","","0.76",
"0x401de0","Node<FastCacheObject>::getNumObjects","","0.54",
"0x402120","Node<SlowCacheObject>::updateAllObjects","","7.61",
"0x401f20","Node<SlowCacheObject>::updateWorldTransform","","3.7",
"0x401f80","SlowCacheObject::getWorldTransform","","1.2",
"0x401f50","SlowCacheObject::updateWorldTransform","","4.67",
"0x402500","std::_Aux_cont::_Getcont","","3.8",
"0x4024d0","std::_Iterator_base_aux::_Getmycont","","7.17",
"0x402510","std::_Iterator_base_aux::_Has_container","","16.41",
"0x402e00","std::_Iterator_base_aux::_Iterator_base_aux","","2.28",
"0x402580","std::_Iterator_base_aux::_Same_container","","3.26",
"0x402cb0","std::_Iterator_base_aux::_Set_container","","1.09",
"0x402de0","std::_Iterator_with_base<std::random_access_iterator_tag,FastCacheObject *,int,FastCacheObject * const *,FastCacheObject * const &,std::_Iterator_base_aux>::_Iterator_with_base<std::random_access_iterator_tag,FastCacheObject *,int,FastCacheObject * const *,Fa","","2.61",
"0x402dc0","std::_Ranit<SlowCacheObject *,int,SlowCacheObject * const *,SlowCacheObject * const &>::_Ranit<SlowCacheObject *,int,SlowCacheObject * const *,SlowCacheObject * const &>","","1.96",
"0x4025c0","std::_Vector_const_iterator<FastCacheObject *,std::allocator<FastCacheObject *> >::operator*","","4.35",
"0x402530","std::_Vector_const_iterator<FastCacheObject *,std::allocator<FastCacheObject *> >::operator==","","6.2",
"0x402d30","std::_Vector_const_iterator<SlowCacheObject *,std::allocator<SlowCacheObject *> >::_Vector_const_iterator<SlowCacheObject *,std::allocator<SlowCacheObject *> >","","6.09",
"0x402260","std::_Vector_const_iterator<SlowCacheObject *,std::allocator<SlowCacheObject *> >::operator!=","","4.89",
"0x402cd0","std::_Vector_const_iterator<SlowCacheObject *,std::allocator<SlowCacheObject *> >::operator++","","4.89",
"0x4025a0","std::_Vector_iterator<FastCacheObject *,std::allocator<FastCacheObject *> >::_Vector_iterator<FastCacheObject *,std::allocator<FastCacheObject *> >","","1.52",
"0x402290","std::_Vector_iterator<SlowCacheObject *,std::allocator<SlowCacheObject *> >::operator*","","1.09",
"0x4022b0","std::_Vector_iterator<SlowCacheObject *,std::allocator<SlowCacheObject *> >::operator++","","3.7",
"0x4024b0","std::_Vector_iterator<SlowCacheObject *,std::allocator<SlowCacheObject *> >::operator++","","0.65",
"0x402200","std::vector<FastCacheObject *,std::allocator<FastCacheObject *> >::begin","","1.09",
"0x402230","std::vector<SlowCacheObject *,std::allocator<SlowCacheObject *> >::end","","2.07",
"0x402100","std::vector<SlowCacheObject *,std::allocator<SlowCacheObject *> >::size","","1.3",
"0x401630","testFastCacheObject","","0.22",
"0x401670","testSlowCacheObject","","0.33",
"0x401580","updateWorldTransforms","","3.37",
即使不计算 SlowCacheObject 使用的所有 STL 运算符，我们也能看到 FastCacheObject 方法在性能上具有显著优势。FastCacheObject 在树的构造/析构期间不使用任何 STL 运算符。然而，这种方法的缺点是它非常静态。如果您正在处理一个非常动态的系统，其中新对象将不断添加，旧对象将被删除，那么在运行时维护和更新所有 Transforms 数组将是必要的。这可能比它本身的麻烦更大，要么因为难以实现，要么因为性能成本过高。相比之下，SlowCacheObject 系统本质上非常动态，并且可以在其当前形式下处理树中的插入和删除，而无需编写新代码。与所有优化技术一样，您必须考虑项目的需求和分析器数据，以确定真正需要优化什么以及如何进行。
结论
与矩阵相比，四元数在内存空间和时间效率方面无疑具有优势。但仍有必要知道如何精确实现每种运算，然后再决定使用哪一种。当然，应用程序的设计需求始终优先于任何性能考虑。因此，如果设计需要一些功能，如平滑插值，那么您可能不得不使用四元数，尽管它们的性能。当然，一如既往，使用一个好的分析器来确定代码中的实际瓶颈和热点，以便最大限度地发挥您的优化工作。
祝你编码愉快！
Gabriel T. Delarosa
参考文献
Svarovsky, Jan，“游戏编程中的四元数，”Game Programming Gems，Charles River Media，2000