并行化的双轮廓算法

A Parallel Dual Contouring Algorithm

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

A novel method for parallel Dual Contouring Algorithm on GPU is proposed. It is difficult using traditional octree construction and storage methods to efficiently implemented on GPU. Our method overcomes this difficulty and is applicable to octrees for discrete point clouds, data fields, triangular meshes and iso-surfaces. Octree nodes were constructed level by level. For each level, only data related to previous level and current level were retained to save storage space. The data were stored in linear arrays excluding empty nodes and therefore suitable for parallel processing. A GPU-accelerated dual contouring algorithm based on our method was implemented and it is approximately an order of magnitude faster than a single-threaded CPU implementation.