小技巧之利用脏标记优化计算复杂度

  • Post author:
  • Post category:其他

        脏标记其实就是在程序逻辑控制中设置一个dirty布尔变量,通过设置它的布尔值,来决定是否进行一些计算工作,也就是将计算工作推迟到必要时进行以避免不必要的计算工作。这样就可以尽可能的节省计算资源,在大规模,高频率的计算中这个小方法非常有用。

        比如说我们游戏引擎的渲染工作过程中,实体的位置,缩放,旋转角度等都需要依赖父节点的转置矩阵来进行计算。在不使用脏标记的情况下,我们会在每一帧针对场景树上的节点进行相关矩阵的计算,会有关于父节点矩阵重复计算,这是在浪费CPU的计算周期。如果实体很多的话,这是一个恐怖的过程,会直接影响我们的游戏性能。如果我们通过设置dirty标记来记录父节点的变换矩阵是否变化来确定计算相应子节点时是否要从新计算父节点的变换矩阵进而计算自己的变缓矩阵。这样就可以节省很多重复的计算,对于这种高频的复杂计算优化很有帮助。脏标记其实就是标记是否使用一个缓存值。

        这个小技巧在很多地方都很有用,我们可以给出下面一个通用的流程。

1. 一组原始数据随时间变化。

2. 一组衍生数据经过一些代价昂贵的操作由这些原始数据确定。

3. 一个脏标记跟踪这个衍生数据是否和原始数据同步。它在原始数据改变时被设置。如果它被设置了,那么当需要衍生数据时,它们就会被重新计算并且标记被清除。否则就使用缓存的数据。

        在游戏引擎中,它是很常用的。不信你打开cocos2dx的源码搜索dirty,会找到很多关于这个小技巧的应用。比如下面是我从cocos2dx 3.9中摘录的源码:

bool dirty = (parentFlags & FLAGS_TRANSFORM_DIRTY) || _transformUpdated;
if(dirty) {
  //根据脏标记来确定是否计算变换矩阵
  _modelViewTransform = this->transform(parentTransform);
}
    
//........
//此处省略一些中间的代码段
//........

if(_gridTarget) {
  //向子节点传递脏标记
  _gridTarget->visit(renderer, _modelViewTransform, dirty);
}

它还有下面一些应用:

1.可以利用脏标记来跟踪浏览器中有变动并根据需要提交到服务端的数据。

2.物理引擎跟踪着物体的运动和空闲状态。一个空闲的物体直到受到力的作用才会移动,它在受力之前不需要处理。这个“是否在移动”就是一个脏标记,用来标记哪些物体受到了力的作用并需要计算它们的物理状态。

参考: Dirty Flag · Optimization Patterns · Game Programming Patterns


版权声明:本文为DebuggingLife原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。