译者： 崔嘉艺（milan21）   审校：王磊（未来的未来）

原文地址：https://blog.molecular-matters.com/2013/02/22/adventures-in-data-oriented-design-part-2-hierarchical-data/

在游戏开发中非常常见的一个任务是根据某种层次的布局来变换数据。今天，我们想看一下这类任务中最著名的例子：根据骨骼层次结构来变换关节。

具体来说，我们将研究本书里面一个简单的面向对象编程实现和更面向数据的设计之间的区别。我们将介绍实现和性能方面的差异。再一次，我们将看到面向数据的设计和面向对象的编程并不是相互矛盾的！

骨骼动画

在我们开始考虑一个可能的实现之前，我们需要通过快速确定骨骼动画所需的步骤先来覆盖一些基础知识。

通常，一个带动画的网格，比如说是一个角色带有几个同一层次相互连接的关节。动画数据为每个不同组件指定了动画曲线，这组成了一个关节的变换，比如位移所需的X，Y和Z值（也包括了缩放，如果支持缩放的话），还有旋转所需的X，Y、 Z和W值。

由96个关节组成的骨骼。

每个关节的动画曲线的数据存储在他们的本地帧（=本地坐标系统）中，这是因为在本地坐标系统中更容易做动画，并能够做出更自然的动画。这意味着，每当你对动画曲线进行采样的时候，所有的变换都存储在局部坐标系中，需要变换成全局坐标系以渲染关节或皮肤的特征。因此，采样动画曲线能够给出我们每个关节的变换信息，这称为局部位置。

请注意，如果我们想要在不同的关节变换之间做混合（通常使用LERP或是SLERP），那些地方的混合是对局部位置进行混合。混合后，分层等事情已经完成，所有关节都变换到全局坐标空间中。这是使用关节的层次结构完成的。

回顾一下，这些是骨骼动画需要执行的步骤：

1.     计算出在什么时候我们想采样动画曲线。这取决于动画的速度，以及这个动画是否是循环的，等等。得到的结果成为局部位置。

2.     这一步是一个可选地行为，混合不同的局部位置，以平滑动画。

3.     按层次将局部位置变换为全局位置。

我故意没有提到其他步骤，比如像是布娃娃，可能会影响全局位置的步骤和需要和局部位置来回修改的步骤（IK，FK）以及其他一些步骤，这么做的目的只是为了可以专注于这篇文章的关键部分。

演示程序的设置

我们用来测量不同实现之间的差异的演示程序只需对1000个角色执行上面的的步骤。我们的计时将测量执行步骤3（遍历层次结构和变换关节的位置）一千次需要多长时间。我们将使用96个关节组成的角色（如上所示）。

一个有1000个角色的军队，所有的角色都在不同的时间点进行采样。

最初的实现

一个简单的、过于简化的分层骨骼数据结构的实现可以如下所示：

struct Joint
｛
  math::matrix4x4_t globalPose;
  math::matrix4x4_t localPose;
  std::vector<Joint*> children;
｝;

这是一个足够简单的版本：每个关节都有一个局部位置、一个全局位置和一组子关节。然后骨骼变成关节的数组，就是这样了。为了从根节点开始变换骨骼，可以使用一个简单的递归函数：

class Skeleton
｛
public:
  void LocalToGlobalPose(void)
  ｛
   ＼＼ start at the root
    LocalToGlobalPose(&joints[0], math::MatrixIdentity());
  ｝
private:
  void LocalToGlobalPose(Joint* joint, math::matrix4x4_arg_t parentTransform)
  ｛
    joint->globalPose = math::MatrixMul(parentTransform, joint->localPose);
   ＼＼ propagate the transformation to the children
    for (size_t i=0; i < joint->children.size(); ++i)
    ｛
      LocalToGlobalPose(joint->children[i], joint->globalPose);
    ｝
  ｝
  Joint* joints;
｝;

上面的代码将从根结点开始遍历整个层次结构，并将父节点的变换传递到子节点那里。这是通过首先存储产生的关节的整体位置，然后把这个位置信息传递给子节点们做到的。这里的代码很短，应该是非常容易看懂的。

所以问题是，用上面的代码来设置1000个角色的全局位置需要多长时间？答案是：3.8毫秒。我们还不能确定这个结果是好的还是坏的，但我们一定能做得更好，否则我不会写一篇关于这个内容的帖子。

面向数据的方法

这里要注意的第一件事很简单，不会让大多数人感到惊讶：我们不必为每个关节存储子结点，而是可以把问题转到head上去，只为每个关节存储一个父关节。因此，我们不再存储一个std::vector<Joint*> children，而是存储Joint* parent作为代替。

下一个优化也很简单：我们将一个骨骼的所有节点都保存在数组中，那么为什么不存储索引而是用指针呢？假设骨骼不会有超过65536个关节的情况（我想说这是一个安全的假设），我们可以存储 uint16_t parent来代替前面提到的指针。

那么这么做的好处是什么呢？

l  存储uint16_t来代替指针需要较少的空间，特别是在64位系统中更是如此。我们节省了内存，在构建全局位置的时候要访问的内存更少。

l  一个完整的骨骼，现在可以很容易的进行复制，而且可以使用例如memcpy的方法来在内存中进行移动。同样，一个完整的骨骼可以从磁盘中加载，而不必担心指针需要修正或是要使用一个类似的单一二进制读取。仅此一项就值得进行这个数据变换。

剩下的问题是：我们如何改变代码，使我们仍然可以按照适当的顺序遍历层次结构，以及我们如何摆脱递归？

为了解决这个问题，我们需要做一个非常关键的观察：只要我们总是按照相同的顺序遍历层次结构，我们就可以按照精确的顺序来分配和存储关节，然后就可以将层次结构扁平化来线性遍历关节数组。查看上面的递归代码，我们可以看到代码用所谓的深度优先顺序遍历层次结构。

现在想象一下遍历层次结构，用一个单调递增的数字来对被访问的关节进行编号。关节0将是根关节，关节合1将是深度优先遍历的层次结构中的下一个关节，等等。这意味着，如果我们遍历关节数组，只有在j < i的情况下，关节i才能让关节j成为它的父关节，这大大简化了遍历代码，并摆脱了递归。

剩下要做的最后一件事是将布局从AoS（结构数组）改为SOA（数组结构），留给我们的结构如下所示：

class Skeleton
｛
private:
  uint16_t* hierarchy;
  math::matrix4x4_t* localPoses;
  math::matrix4x4_t* globalPoses;
｝;

这种变化的好处是，每当我们使用hierarchy[i]来访问一个关节的父关节的时候，几十个可能的下一个父节点也将被读取到具有相同高速缓存行的缓存中。如果我们访问 localPoses[i]的话也会发生同样的事情。

那么变换的代码现在是什么样子的呢？其实这里需要的代码会变得出奇的简单：

void LocalToGlobalPose(void)
｛
  // the root has no parent
  globalPoses[0] = localPoses[0];
  for (unsigned int i=1; i < NUM_JOINTS; ++i)
  ｛
    const uint16_t parentJoint = hierarchy[i];
    globalPoses[i] = math::MatrixMul(globalPoses[parentJoint], localPoses[i]);
  ｝
｝

这段代码很漂亮，而且已经不能再简化了。

如上所述，这样的代码能够工作是因为parentjoint < i,，这意味着我们只会访问那些全局位置已经计算的关节。我们之前使用的递归已经不再需要了，现在隐式地给出数组中关节的位置，我们以深度优先遍历的方式进行编号。

这样做在性能上有什么区别吗？有着相同数量的变换，现在这个代码只需要3.1毫秒的执行时间。之前的实验中我们需要3.8毫秒的执行时间，这带来了超过18%的速度提升！

结论

我们的简单更改不仅带来了性能的良好提高，而且大大简化了代码本身。我们不必放弃面向对象编程原则，我们甚至不需要更改调用代码。我们仍然有我们的框架类，并用它来调用localtoglobalpose()方法。

这样实现非常的简洁，快速，而且非常的简单。

【版权声明】

原文作者未做权利声明，视为共享知识产权进入公共领域，自动获得授权。