场景图
场景图主要包含节点管理、场景遍历、场景更新等功能。
1、节点管理
节点管理功能包括：
- 添加节点：
template<class TNode, class ...Args>
std::shared_ptr<TNode> addNode(Args&& ... args)
template<class TNode>
std::shared_ptr<TNode> addNode(std::shared_ptr<TNode> tNode)
其中TNode是节点（Node）的派生类型，Args则对应节点构造过程所需要的参数:
- 删除节点：
void deleteNode(std::shared_ptr<Node> node);
2、场景遍历
场景图（SceneGraph）将节点抽象为有向无环图（Directed Acyclic Graph）中的顶点，数据的连接则抽象为顶点之间的有向边。因此一个简单的包含四个节点的场景可以用如下的有向无环图来表示：
对场景图节点的遍历可采用类似DAG的遍历算法来完成，目前主要提供两类接口：
- 先序遍历，调用方式为:
void traverseForward(Action* act);
或者:
template<class Act, class ... Args>
void traverseBackward(Args&& ... args)
对应上图的场景，先序遍历得到的节点序列如下：
- 后序遍历:
void traverseBackward(Action* act);
或着:
template<class Act, class ... Args>
void traverseBackward(Args&& ... args)
对应上图的场景，后序遍历得到的节点序列如下：
Action为遍历过程中对每个节点进行的操作，可用于更新节点、获取特定类型模块等操作。
整个场景图的遍历采用广度优先算法完成：
void BFS(Node* node, NodeList& nodeQueue, std::map<ObjectId, bool>& visited) {
visited[node->objectId()] = true;
nodeQueue.push_back(node);
auto exports = node->getExportNodes();
for (auto port : exports) {
auto exNode = port->getParent();
if (exNode != nullptr && !visited[node->objectId()]) {
BFS(exNode, nodeQueue, visited);
}
}
auto outFields = node->getOutputFields();
for each (auto f in outFields) {
auto& sinks = f->getSinks();
for each (auto sink in sinks) {
if (sink != nullptr) {
auto exNode = dynamic_cast<Node*>(sink->parent());
if (exNode != nullptr && !visited[exNode->objectId()]) {
BFS(exNode, nodeQueue, visited);
}
}
}
}
};
void SceneGraph::updateExecutionQueue()
{
if (!mQueueUpdateRequired)
return;
mNodeQueue.clear();
std::map<ObjectId, bool> visited;
for (auto& nm : mNodeMap) {
visited[nm.first] = false;
}
for (auto& n : mNodeMap) {
if (!visited[n.first]) {
Node* node = n.second.get();
DFS(node, mNodeQueue, visited);
}
}
visited.clear();
mQueueUpdateRequired = false;
}
3、局部遍历
以上述有向无环图为例，当节点B的内容发生变化时，我们需要对依次更新B及B以后的节点C和D，同时注意到A的数据并不依赖于B。因此B的内容更新不应该影响A的内容。为了实现场景图的局部更新，提供如下接口用于更新特定节点及后续节点：
void traverseForward(std::shared_ptr<Node> node, Action* act);
或者:
template<class Act, class ... Args>
void traverseForward(std::shared_ptr<Node> node, Args&& ... args);
采用广度优先算法完成：
//Used to traverse the scene graph from a specific node
void BFS(Node* node, NodeList& nodeQueue, std::map<ObjectId, bool>& visited) {
visited[node->objectId()] = true;
nodeQueue.push_back(node);
auto exports = node->getExportNodes();
for (auto port : exports) {
auto exNode = port->getParent();
if (exNode != nullptr && !visited[node->objectId()]) {
BFS(exNode, nodeQueue, visited);
}
}
auto outFields = node->getOutputFields();
for each (auto f in outFields) {
auto& sinks = f->getSinks();
for each (auto sink in sinks) {
if (sink != nullptr) {
auto exNode = dynamic_cast<Node*>(sink->parent());
if (exNode != nullptr && !visited[exNode->objectId()]) {
BFS(exNode, nodeQueue, visited);
}
}
}
}
};
void SceneGraph::traverseForward(std::shared_ptr<Node> node, Action* act)
{
std::map<ObjectId, bool> visited;
for (auto& nm : mNodeMap) {
visited[nm.first] = false;
}
NodeList list;
BFS(node.get(), list, visited);
for (auto it = list.begin(); it != list.end(); ++it)
{
Node* node = *it;
act->start(node);
act->process(node);
act->end(node);
}
list.clear();
visited.clear();
}
4、场景更新
- 更新运行队列:
void updateExecutionQueue();
更新的时机主要依赖于场景图中的节点以及连接关系是否发生变动，一旦任意一项发生改变，场景的节点执行队列会在下次执行节点功能的时候优先更新运行队列。
- 更新节点状态:
void propagateNode(std::shared_ptr<Node> node);
当某个特定节点的运行状态发生改变时，如节点的配置参数发生改变，场景图可以通过调用propagateNode()函数对后续所有依赖该节点的节点的状态进行更新。
5、其他功能
参见SceneGraph.h和SceneGraph.cpp相应实现。