节点图线程安全,效率高

我会尽量明确地expression自己的意思,并为自己的语法表示歉意。

我正在研究一个游戏引擎(特别是渲染部分),而且我正面临着一些涉及大量代码的概念select,我希望能够在第一次尝试时做出好的select。 我实际上在场景图上工作。 我必须指定引擎必须是线程安全的,并且符合c ++ 11/14,同时限制用户的错误(不允许引擎用户移动不应移动的指针…)。 所以我的问题是,我不知道如何让访问引擎的用户太多,并保持线程的安全性,而不会造成10000次caching未命中的性能,或者如果需要能够search特定的节点(当您构建树你不知道你会用什么节点?)。

其实我从一棵树的东西开始非常标准

每个节点知道所有的孩子,他们知道他们的父母。 为了提高效率,每个将包含网格的节点以及相关的纹理都将存储在一个Scene对象中,该对象将在每个拥有一个网格的节点(用于查询网格的场景变换matrix)上创建一个指针。 场景还将包含场景的根节点。

我的问题是,我应该如何处理A节点和它的家庭之间的链接?

我想到的解决scheme之一是使用Observerdevise模式。 在Node和它的系列之间使用shared_ptr,然后只向引擎用户提供NodeObserver。 但有了这个解决scheme,我不知道如何将场景资源连接到节点上,因为shared_ptr将引入不可破坏的循环,而wear_ptr将引入多lesscache_miss和多less同步(至less每个节点上每个帧都有一个锁。 。)我可以使用存储在Scene对象中的裸指针,并且在其生命周期结束时,Node析构函数应该从Scene中移除?

如果有人知道如何做,我会非常高兴。 提前感谢您的时间和您的帮助。

像场景图这样的树状结构与multithreading编程的操作截然相反。 如果有人添加或删除单个节点会发生什么? 整个事情崩溃了。 这也有点不愉快,因为它已经导致大量的caching未命中。

所以首先我忘了使用场景图,或者至less直接使用场景图。 使用它的任何安全的方式将会太慢。 但这并不是说你不能同时拥有场景图和特定的碰撞结构。

我会推荐一个平面结构,即具有计算出的所有变换的区域。 然后,每一帧重新计算第二个缓冲区中的所有内容(可能是您用作实际场景图的内容),然后将所有内容都复制到一个记忆体中。

回答一个在线问题是一个很大的话题,如果没有任何意义,那么这是一个开始的好地方: http : //realtimecollisiondetection.net/

我无法给你一个完整的解决scheme,因为我从来没有想过要制作一个通用的,线程安全的场景图(考虑到我与之合作的团队和环境有点过于雄心勃勃),但我认为这个答案将提供巨大的潜力一块拼图。

杀死场景根!

我不使用“场景根”的概念。 如果我这样做了,我插入到场景中的每一个东西都必须插入到场景根目录中,并存储各种具有各种共享数据的链接。 我有这样一个树组件:

struct CTreeNode { // I often need bottom-up traversal where the user // selects a child/leaf and then wants immediate access // to its parent, so I store a parent link. int parent; int next_sibling; int first_child; }; 

…但我只是用它,并附加到一个实体,当我真的需要养育子女,就像骨头或刚体层次。 而根源不是场景根,所以共享数据很less。 机器人的根可能是它的骨盆/臀部,而不是整个场景的根部。 我们基本上是这样的:

在这里输入图像说明

…把它变成这样:

在这里输入图像说明

而这可能看起来只是交易一个“平面场景列表”的“场景根子列表”,但第二个并不一定是一个链接结构; 它可以是完全不同的数据结构和数据types。 你可以使用一个展开列表或tbb::concurrent_vector或其他非常友好的并发和memcpy等等,如果你的目的是试图使这些中央数据结构线程安全。 如果这个扁平的“根子列表”存储在与树节点分离的数据结构中,那么您不必为了使整个树和单个节点上的操作线程安全而对隧道进行远景规划。

不同特点,常见案例与罕见案例

根子们的名单在本质上与其他分支机构/子女非常不同,因为它通常会存储大量的类比子女,插入/删除子女可能是一个非常普遍的情况(可能发生在每一个单一的框架中),而在现场的分支往往会有更less的孩子,可能很less需要修改层次结构。 根节点需要的孩子的平均数量可能在几十万到几百万的范围内,而其他所有需要作为父节点的孩子的平均数量是3个。这些是完全不同的要求。

几乎没有什么原因可以改变骨骼层次结构。 你可能只是加载一个字符的骨架数据,这就是说,父/子关系永远不会改变这一点。 同时,您可能会每帧多次插入和移除元素。 当你具有完全不同的使用特性时,使用不同的数据结构通常会有所帮助。

如果不尝试使用一个节点数据结构在这里统一它们,并将“平面场景列表”视为单独的概念/数据结构而没有实际的“场景根”,则事情变得更容易,因为再次,数据结构和使用情况以及常见情况/罕见情况特征在类比场景根子列表和儿童的孩子之间有很大不同。 试图把所有东西都塞进一个类比的“节点”结构中,可能会比帮助更让人感到悲伤, 特别是如果你正在尝试多层次的操作和遍历。

multithreading

而且我认为,如果您从消除场景/游戏世界中每一件事物的场景根的想法开始,如果您尝试对graphics进行multithreading操作和访问,则应该有很大的帮助。 这会给你很多独立的graphics,只有很less的共享数据,而不是一个共享根数据的graphics。

隐式场景根

如果你想实际上做类似的“整个场景转换”,你可以特殊情况下,并通过matrix乘以所有的东西,而不存储你的场景中的每一件事的父/子链接。 如果您需要在关卡编辑器中显示场景大纲,则可以通过对场景中没有附加树节点组件的实体进行平面迭代,来再现特殊情况并假装场景根存在, -1存储parent (在我的情况下表示一个根)。 实际上,你并不需要为整个场景建立一个真正的根节点,并将所有的东西都链接到它并存储所有这些额外的共享数据。 你可以隐式地推断出没有附加树节点或者有空父节点(或者如果你使用像我这样的索引的parent设置为-1)的每个实体是类比场景根节点的直接子节点(事实上它并不是作为节点在内存中)。

caching预置遍历

另一个缓解caching未命中的事情,因为链接的结构遍历本质上不是非常caching友好的通常是我有一个函数,输出一个扁平的索引序列使用树的前序遍历(这也是一个小的树,以场景为根,不以整个大场景为根),并对每组子索引进行sorting。 我通常不会遍历树,除非在树已经改变的时候输出这个扁平的索引数组。 由于索引是使用前序遍历来收集的,因此您可以按顺序更新运动matrix,并以正确的顺序处理事件(父母在子女之前)。

shared_ptr/weak_ptr

在使用shared_ptr/weak_ptr ,我通常不会打扰,只是在组件相互依赖的时候,通过索引来引用它们。 再次与我的树节点:

 struct CTreeNode { int parent; int next_sibling; int first_child; }; 

…链接只是使用普通的旧整数作为实体的索引。 我所做的是当节点被销毁(我可以通过组件registry注册析构函数 – 不能直接使用C ++ dtors,因为ECS使用C API与许多不同的语言进行交互),我只是更新链接来排除节点,将其从父节点中删除,并将其子节点的链接设置为-1 (空,即)。

现在我可以看到shared_ptr在multithreading上下文中可能会变得非常有用,以确保资源的生命周期一直延续到线程完成处理之后,但是我总是发现shared_ptr的好处往往被它的缺点所掩盖(easy引入逻辑泄漏意外,昂贵的primefaces参考计数,不得不分配包括ref计数器在内的所有东西)。 相反,我经常发现确保所有系统都是从“进程”callback/事件处理,甚至是在其他线程中运行的系统,都是非常有用的。 如果他们试图在这些处理事件期间销毁/删除任何实体/组件,则当系统不再处理时,将该删除推迟到一小段时间片(非常短暂的锁)。

我发现,处理起来要容易得多,而且要便宜得多,而且要有更多的可预测性来推断什么时候应该在系统处理之间而不是在所有共享指针的细粒度级别上销毁资源。如果您使用共享所有权,则可以预测复杂代码库中的何时/何处)。 我发现有一个明显的“去除”function可以让我更加容易地去除组件和实体,但是也知道它的使用是安全的,因为如果系统仍在处理中,它实际上不会去除一个组件线程或其他线程)。 如果你可以通过这种方式统一你的代码库,而不是让“stream氓线程”把自己的持久引用存储到游戏状态,谁知道这个游戏状态会持续多久,那么生活就变得容易多了。

因为至less在我的情况下,当用户请求从编辑器中删除场景实体/组件时,应该删除场景实体/组件, 除非系统还在处理中,此时应该尽快删除它们。 在这些情况下明确的删除比隐含的要容易得多,希望系统的每个相关部分都能在不久之后发布这些强大的引用。

至less在团队环境中有关shared_ptr另外一件事情是,一旦你公开地将某个shared_ptr暴露给某个接口的某个东西(使用shared_ptr来实现细节几乎没有问题),你就无法阻止它的传播。 你不能阻止人们(至less不是强有力地,也许有非常小心的标准)将更多的shared_ptrs存储到相同的资源上,包括第三方插件开发者完全在你的团队的控制之外编写代码,而只需要其中的一个不小心忘了释放shared_ptr来延长资源的使用寿命,将逻辑泄漏引入到您的应用程序中,过去我也遇到过这种情况,第三方最终将shared_ptr存储到像mesh这样昂贵的东西上在这一点上,在用户请求删除它(甚至不closures)的时候,它并没有被释放。 所以我一直对它的用法感到厌倦,因为它很容易被可怕的方式滥用到无法推断什么时候什么东西会被释放和销毁的地步,因为甚至在你的团队的控制之下的代码可能是延长对象的生命周期,比他们应该坚持的时间要长。