Scene Management ---Node Update (2)
作者：clayman
仅供个人学习使用，请勿转载，勿用于任何商业用途。
上一篇文章，我介绍了"理想"状态下的节点更新方法。所谓"理想"，指的是除了父子节点之间的依赖关系外，节点之间不再有其他依赖关系。不幸的是，横向依赖通常广泛存在于游戏系统中，最明显的例子就是物理/碰撞检测系统。假设下图中，所有节点都有相应的物理模拟对象，并且所有节点间都是"可碰撞的"，因此，更新a节点位置的时候，可能需要知道b节点的状态，反过来，更新b节点的，又需要a节点的信息，形成了一种死锁状态。
此外，每一次更新开始之前，所有物体状态都处于上次更新的时间T_last之后。无论用什么方法解决上述横向依赖问题，也不管是单线程还是多线程的更新方式，同一时刻T下，只能对某一个或者几个对象进行更新，这就必然导致了整个更新过程中对象状态不一致的情况。比如，假设每次更新过后，下一次更新之前，所有物体都处于T_current时刻的状态。当在T时刻更新节点c时，可能看到a已经处于T_current状态，但b尚未更新，仍处于T_last状态，为了避免之前介绍的死锁依赖状态，c不得不在a,b等周围对象状态不一致的情况下，做出更新。
可见，节点更新并非简单遍历所有节点即可，对于物体间相互依赖，状态不一致，也很难有完美的解决方案。本想对这个问题仔细进行深入讨论，可Jason Gregory已经在<<Game Engine Architechture>>中进行了比我更加专业的讨论，更幸运的是这部分刚好作为试读章节，下面就是我从试读章节中扒下来的内容-_-#.............................
14.6.3
Object State Inconsistencies and One-Frame-Off Lag
Let's revisit game object updating, but this time thinking in terms of each object's local notion of time.The state of game object i at time t can be denoted by a state vector Si(t). When we update a game object, we are converting its previous state vector Si(t1) into a new current state vector Si(t2) (where t2 = t1 + Δt).
In theory, the states of all game objects are updated from time t1 to time t2 instantaneously and in parallel, as depicted in Figure 14.15. However, in practice, we can only update the objects one by one -- we must loop over each game object and call some kind of update function on each one in turn. If we were to stop the program half-way through this update loop, half of our game objects' states would have been updated to Si(t2), while the remaining half would still be in their previous states, Si(t1). This implies that if we were to ask two of our game objects what the current time is during the update loop, they may or may not agree! What's more, depending on where exactly we interrupt the update loop, the objects may all be in a partially updated state. For example, animation pose blending may have been run, but physics and collision resolution may not yet have been applied. This leads us to the following rule:
The states of all game objects are consistent before and after the update loop, but they may be inconsistent during it.
In theory, the states of all game objects are updated instantaneously and in parallel during each iteration of the game loop.
In practice, the states of the game objects are updated one by one. This means that at some arbitrary moment during the update loop, some objects will think the current time is t2 while others think it is still t1. Some objects may be only partially updated, so their states will be internally inconsistent. In effect, the state of such an object lies at a point between t1 and t2.
Object State Caching
As described above, one solution to this problem is to group the game objects into buckets (Section 14.6.3.2). One problem with a simple bucketed update approach is that it imposes somewhat arbitrary limitations on the way in which game objects are permitted to query one another for state information. If a game object A wants the updated state vector SB(t2) of another object B, then object B must reside in a previously updated bucket. Likewise, if object A wants the previous state vector SB(t1) of object B, then object B must reside in a yet-to-be-updated bucket. Object A should never ask for the state vector of an object within its own bucket, because as we stated in the rule above, those state vectors may be only partially updated.
One way to improve consistency is to arrange for each game object to cache its previous state vector Si(t1) while it is calculating its new state vector Si(t2) rather than overwriting it in-place during its update. This has two immediate benefits. First, it allows any object to safely query the previous state vector of any other object without regard to update order. Second, it guarantees that a totally consistent state vector (Si(t1)) will always be available, even during the update of the new state vector. To my knowledge there is no standard terminology for this technique, so I'll call it state caching for lack of a better name.
Another benefit of state caching is that we can linearly interpolate between the previous and next states in order to approximate the state of an object at any moment between these two points in time. The Havok physics engine maintains the previous and current state of every rigid body in the simulation for just this purpose.
The downside of state caching is that it consumes twice the memory of the update-in-place approach. It also only solves half the problem, because while the previous states at time t1 are fully consistent, the new states at time t2 still suffer from potential inconsistency. Nonetheless, the technique can be useful when applied judiciously.
Time-Stamping
One easy and low-cost way to improve the consistency of game object states is to time-stamp them. It is then a trivial matter to determine whether a game object's state vector corresponds to its configuration at a previous time or the current time. Any code that queries the state of another game object during the update loop can assert or explicitly check the time stamp to ensure that the proper state information is being obtained.
Time-stamping does not address the inconsistency of states during the update of a bucket. However, we can set a global or static variable to reflect which bucket is currently being updated. Presumably every game object "knows" in which bucket it resides. So we can check the bucket of a queried game object against the currently updating bucket and assert that they are not equal in order to guard against inconsistent state queries.
----Quote from <<Game Engine Architecture>> 14.6.3 ，author：Jason Gregory