并行化的双轮廓算法

发布时间：2021-01-07 18:19

　　提出一种新颖的适用于GPU且支持化简的并行化的双轮廓方法。通过使用新的GPU八叉树生成算法,克服了传统的八叉树数据结构难以完全在GPU端并行生成与存储的困难,适用于对三维离散点云、数据场及三角网格模型构建（包含等值面或原模型的）八叉树。上述方法逐层并行生成八叉树结点,线性存储每层结点信息同时避免存储空结点信息,有效节约了存储空间并且便于后续对各层结点并行处理。以并行八叉树生成方法为基础,提出了对原始双轮廓算法的GPU加速实现。与在CPU上单线程执行的算法相比,速度可以提高1个数量级。 

【文章来源】：计算机仿真. 2020,37(06)北大核心

【文章页数】：6 页

【部分图文】：

顶点树数据结构示意图

对于从符号距离场[19-21]构造等值面的情况,通过离散差分计算出的交点法向量并不精确。如图2所示,若重构出的轮廓面不在采样网格正中心,则在采样点o处由差分计算所得的梯度不等于0,导致解得的特征点位置不准确。对此,本文对于一个立方体内每条具有符号变化的边,用符号为正的端点在轮廓面上对应的距离最近的点(不一定是边与轮廓面的交点)来构造QEF。4.3 化简八叉树

在执行第二步前,要为surf_indices数组分配存储空间,数组元素的数量取边数组元素数量的6倍。因为每一条最小边最多产生两个三角形。对于边数组的每个元素(边),4个相邻结点的存储顺序应如图3所示。当边的首端点符号为“负”时,箭头方向指向生成表面的外侧。按照右手定则,所构造的三角形在邻结点数组中的索引为0,1,2和(或)0,2,3。当首端点标识符为1时,三角形绕向取反。第二步:并行处理边数组中的每个元素。按照边的邻结点数组中的索引值依次找到每个结点所关联的顶点树结点。若顶点树结点被标记为“被合并” (即is_collapsed为true),则递推跟踪parent索引值直到遇到第一个没有被标记为“被合并”的父结点,取出该顶点树结点的x_id构建三角形。经化简后,4个结点的x_id可能重复,并不一定能组成两个三角面片,这里只存储有效的三角面片索引。

【参考文献】：
期刊论文
[1]基于GPU的并行八叉树生成算法[J]. 王吉强,贾世宇.  青岛大学学报(自然科学版). 2018(04)
[2]基于八叉树的柔性体切割仿真中并行化的碰撞算法[J]. 贾世宇,张维忠,于晓康,潘振宽.  计算机辅助设计与图形学学报. 2017(12)
[3]基于八叉树邻域分析的光线跟踪加速算法[J]. 张文胜,解骞,钟瑾,刘俊平,郝青,郭广利.  图学学报. 2015(03)
[4]大规模三维云实时模拟方法[J]. 任威,梁晓辉,马上,沈旭昆.  计算机辅助设计与图形学学报. 2010(04)



本文编号：2963019