基于GPU的并行八叉树生成算法
|
摘要
提出了一种新颖的完全在GPU端以并行方式构造八叉树的算法。克服了以往GPU八叉树生成算法难以构建结点间的邻接关系以及对应用领域的局限性等困难,适用于在GPU中对散乱点云数据、三角网数据以及离散数据场数据构建八叉树。该方法以紧密排列的方式线性存储各层八叉树结点同时避免存储空结点信息,有效节约了存储空间并且提高了逐层并行遍历八叉树的效率。与传统的CPU单线程递归分割构造八叉树的算法相比较,速度可以提高一个数量级。
A new method for GPU octree construction is proposed.Existing GPU octree construction methods are difficult to construct adjacent information of octree nodes and generally have limited applications.The method overcomes this difficulty and is applicable to octrees for discrete point clouds,data fields and triangular meshes.The data is stored in linear arrays excluding empty nodes and is therefore suitable for parallel processing.The GPU-based approach is approximately an order of magnitude faster than previous CPU algorithms which using recursive partitioning method on a single thread.
A new method for GPU octree construction is proposed.Existing GPU octree construction methods are difficult to construct adjacent information of octree nodes and generally have limited applications.The method overcomes this difficulty and is applicable to octrees for discrete point clouds,data fields and triangular meshes.The data is stored in linear arrays excluding empty nodes and is therefore suitable for parallel processing.The GPU-based approach is approximately an order of magnitude faster than previous CPU algorithms which using recursive partitioning method on a single thread.
引文
[1]赵磊,赵罡,谈敦铭.基于八叉树的复杂产品模型实时绘制技术[J].图学学报,2011,32(3):69-74.
[2]贾世宇,张维忠.基于八叉树的柔性体切割仿真中并行化的碰撞算法[J].计算机辅助设计与图形学学报,2017,(12):2180-2188.
[3]张文胜,解骞.基于八叉树邻域分析的光线跟踪加速算法[J].图学学报,2015,36(3):339-344.
[4]Ju T.Robust repair of polygonal models[J].Acm Transactions on Graphics,2004,23(3):888-895.
[5]李红波,刘昱晟,吴渝,等.基于二次误差度量的大型网格模型简化算法[J].计算机工程与设计,2013,34(9):3158-3162.
[6] Ummenhofer B,Brox T.Global,Dense Multiscale Reconstruction for a Billion Points[J].International Journal of Computer Vision,2017,125(1-3):82-94.
[7]任威,梁晓辉.大规模三维云实时模拟方法[J].计算机辅助设计与图形学学报,2010,22(4):662-669.
[8] Ferrando N,Gosálvez M A,CerdáJ,et al.Octree-based,GPU implementation of a continuous cellular automaton for the simulation of complex,evolving surfaces[J].Computer Physics Communications,2011,182(3):628-640.
[9] Zhou K,Gong M,Huang X,et al.Data-Parallel Octrees for Surface Reconstruction[J].IEEE Transactions on Visualization&Computer Graphics,2010,17(5):669-681.
[10]Ju T,Losasso F,Schaefer S,et al.Dual contouring of hermite data[J].Acm Transactions on Graphics,2002,21(3):339-346.
[11]Ju T,Udeshi T.Intersection-free contouring on an octree grid[C]//Pacific Graphics,IEEE Computer Society Press,Los Alamitos.2006.
[12]Schaefer S,Ju T,Warren J.Manifold dual contouring[J].IEEE Transactions on Visualization&Computer Graphics,2007,13(3):610-619.
[2]贾世宇,张维忠.基于八叉树的柔性体切割仿真中并行化的碰撞算法[J].计算机辅助设计与图形学学报,2017,(12):2180-2188.
[3]张文胜,解骞.基于八叉树邻域分析的光线跟踪加速算法[J].图学学报,2015,36(3):339-344.
[4]Ju T.Robust repair of polygonal models[J].Acm Transactions on Graphics,2004,23(3):888-895.
[5]李红波,刘昱晟,吴渝,等.基于二次误差度量的大型网格模型简化算法[J].计算机工程与设计,2013,34(9):3158-3162.
[6] Ummenhofer B,Brox T.Global,Dense Multiscale Reconstruction for a Billion Points[J].International Journal of Computer Vision,2017,125(1-3):82-94.
[7]任威,梁晓辉.大规模三维云实时模拟方法[J].计算机辅助设计与图形学学报,2010,22(4):662-669.
[8] Ferrando N,Gosálvez M A,CerdáJ,et al.Octree-based,GPU implementation of a continuous cellular automaton for the simulation of complex,evolving surfaces[J].Computer Physics Communications,2011,182(3):628-640.
[9] Zhou K,Gong M,Huang X,et al.Data-Parallel Octrees for Surface Reconstruction[J].IEEE Transactions on Visualization&Computer Graphics,2010,17(5):669-681.
[10]Ju T,Losasso F,Schaefer S,et al.Dual contouring of hermite data[J].Acm Transactions on Graphics,2002,21(3):339-346.
[11]Ju T,Udeshi T.Intersection-free contouring on an octree grid[C]//Pacific Graphics,IEEE Computer Society Press,Los Alamitos.2006.
[12]Schaefer S,Ju T,Warren J.Manifold dual contouring[J].IEEE Transactions on Visualization&Computer Graphics,2007,13(3):610-619.