基于稀疏体素有向无环图的光照计算加速结构

发布时间：2019-11-14 19:13

【摘要】：提出了一种基于稀疏体素有向无环图(SVDAG)的光照计算加速结构。通过自下而上地合并相同节点,将稀疏体素八叉树转化为SVDAG;同时,利用给定节点的遍历路径和子掩码,消除了空间位置的多义性。针对闭合几何体,基于双层深度图算法可自适应合并位于闭合区域的节点,在保证光照计算性能的前提下,进一步减小了存储开销。提出了一种基于时域相关性的SVDAG帧间复用方法,利用动态场景的全部帧构成SVDAG加速结构整体,提高了更新速度。实验结果表明,新算法提高了三维场景的绘制效率,在面对高分辨率的动态场景时,仍能获得较高的帧速率。
【图文】：

示意图,指针,排列顺序,二维

区域对应的节点，避免了对空白节点的存储。在ＳＶＯ构建过程中，每个节点的子掩码一共８ｂｉｔ，“０”表示子节点为空，“１”表示子节点为实节点。因此，指向空节点的指针可以完全被剔除，仅需要保留指向第一个非空子节点的指针，其子节点可以按照约定顺序（如广度优先顺序）连续地存储在内存空间中，层级内部可采用Ｍｏｒｔｏｎ码顺序，也不需要保留指针，从而达到减小存储开销的目的，如图１所示。因此，只要知道子掩码和约定的遍历顺序，，就可以通过节点的连续存储顺序恢复出ＳＶＯ的完整结构。图１ＳＶＯ节点排列顺序及指针安排的二维示意图Ｆｉｇ．１Ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｓｃｈｅｍａｔｉｃｏｆｏｒｄｅｒａｎｄｐｏｉｎｔｅｒｓｅｔｔｉｎｇｏｆｎｏｄｅｓｉｎＳＶＯ０８２０００１－２

示意图,叶子,节点,子树

合并操作，某些节点可能拥有多个父节点，因此，ＳＶＯ就从树形结构扩展为ＳＶＤＡＧ。按照上述思路，将ＳＶＯ转化为ＳＶＤＡＧ最简单的方法就是从根节点开始，搜索是否存在完全相同的子树，并继续递归每一个子树，直至遇到叶子节点。这个方法虽然简单，但是递归操作需要将整个场景的所有节点推入堆栈后进行回溯，分辨率较高时内存开销的峰值很大。因此，为了避免递归，提出了如下一种自下而上的方法以实现从ＳＶＯ到ＳＶＤＡＧ的转换。１）从ＳＶＯ的底部开始，搜索相同的叶子节点并进行合并，如图２所示。在ＳＶＯ中，由于叶子节点仅表示对应空间位置上是否存在对应体素，因此合并后的叶子节点最多两种。图２搜索相同叶子节点并进行合并Ｆｉｇ．２Ｓｅａｒｃｈｉｎｇｆｏｒｓａｍｅｌｅａｆｎｏｄｅｓａｎｄｍｅｒｇｉｎｇ２）继续往上层处理，搜索子掩码和指针完全相同的节点，这样的节点具有相同的子树，可以进行合并，如图３所示。需要注意的是，压缩这些层级的节点时，只要考虑子树的根节点，这是因为合并操作是自下而上进行的，节点本身具有相同的子掩码和指针即说明它们的下级子树直至叶子节点都是相同的。图３自下而上地将ＳＶＯ转化为ＳＶＤＡＧ的示意图Ｆｉｇ．３ＳｃｈｅｍａｔｉｃｏｆｃｏｎｖｅｒｔｉｎｇＳＶＯｔｏＳＶＤＡＧｆｒｏｍｂｏｔｔｏｍｔｏｔｏｐ３）自下而上进行搜索和合并操作，参与合并的节点越来越多，直到没有节点可以合并或到达根节点，获得最终的ＳＶＤＡＧ，如图４所示。该算法同样适用于深度不均匀的ＳＶＯ，同时也可对不同子树分别进行转化操作然后再组合。由于整个ＳＶＯ的数据规模可能远大于对应的ＳＶＤＡＧ的数据规模，可以利用

【相似文献】