散乱点云线性八叉树结构在GPU中的实现.pdf

《散乱点云线性八叉树结构在GPU中的实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2013年4月机械设计与制造工程Apr．2013第42卷第4期MachineDesignandManufacturingEn~neefingV01．42No．4DOI：10．3969／j．issn．2095—509X．2013．04．002散乱点云线性八叉树结构在GPU中的实现徐万银，刘胜兰(南京航空航天大学机电学院，江苏南京210016)摘要：为快速建立散乱点云的空间邻接关系。研究了更快速构建线性八叉树。采用Morton码描述八叉树的节点，并按照层次顺序对叶节点进行遍历，通过建立两个查询表，实现对节点相邻信息的快速查询。算法利用了GPU架构的并行度，实验表明，该算法有较高的效率。关键

2、词：八叉树；Morton码；并行算法；GPU中图分类号ITP391文献标识码：A文章编号：2095—509X(2013)04—0005—03八叉树数据结构以其结构简单、易于遍历、算的Morton码3个部分。法实现方便成为建立散乱点云的空间邻近关系，是b．节点数组创建，包括排序Morton码，压缩近年来科研人员研究的热点。其实现方式主要有Morton码，扩充八叉树节点，生成每层节点数组和指针八叉树、线性八叉树。指针八叉树采用一组指生成邻节点算法。针来记录节点父子之间的关系，由于指针高效的随数据点编码机访问特性，用这种方式查询效率高，但需要大量并行节点数组创建的指针存储空间。线性八叉树只保

3、存叶节点的空计算排压生间位置和属性，其中空间位置通过编码来表示。查输每序缩扩生个MM充成生询过程就是对编码的遍历和比较-1]，查询效率较入八每成散成点OO层低，但结构更紧凑，可以直接访问任一叶节点。乱—■包—-的_h—-r-IP叉—-节—’邻点围Mtt树节盒oO特点点随着图形处理器(GPU)性能的大幅度提高，五点数rnn组使得GPU的应用受到研究人员的关注。指针八叉t码码0树中的指针，在GPU中用父节点对子节点的索引n码来记录指针，利用GPU中的纹理存储器来存储这些索引，实现八叉树的构建。线性八叉树在图1线性八叉树算法流程图GPU中实现的关键是如何编码以及对节点进行访问，利用Morto

4、n码实现完全在GPU中构建并遍历1．1数据点编码八叉树J，在GPU中创建八叉树的节点、边、面等Morton码是一种实现多维数据到一维映射的信息【4』，并将其应用于散乱数据的曲面重建。有效方法，它通过交叉存储多个维数的位产生一个本文研究一种线性八叉树在GPU中的实现方数。本文中将深度为层的八叉树节点的Morton法，通过与CPU算法的比较可知，本文利用GPU码记为：1Y1z12y2z2"'x^fYJIf。深度为层的八叉大大加快了八叉树建立，提高了查询的效率。树Morton码有3M位，本文中规定Morton码是32位的，因此可表示的八叉树的最大深度为1O，其中1线性八叉树的GPU实现未用到

5、的位(31，32位)设为0。本文建立的线性八叉树算法流程主要包括2采样点在，，l(1≤m≤M)层的位的值按如个步骤(如图1所示)：下公式计算：a．对数据点进行Morton编码，包括输入散乱f0，if口．

6、层的状态值有Morton码节点的父节点有8个子节点。利用即Y，z也可以按上述方法同样计算得到。scan_6算法得到对应的节点地址数组nodeaddress。采用并行方法计算Morton码，首先计算第一c．生成每层的节点数组OctreeNode。层节点的中心，直至第层的中心，其中第一层节算出扩充后新增节点的Morton码，将这些节点中心可根据包围盒的大小来计算，具体算法流程点的ptnumbers设为0。通过nodeaddress和3位为：XMy^f的Morton码定位UniqueNode中的每个节if(线程中的索引小于点云数量)点在OctreeNode村中的对应元素。采样点的初始Mort

7、on码置为0；根据第层节点数组，依次建(—1)层，直至for(m=1到M)第一层节点数组。在OctreeNode中，将每个节点计算节点中心坐标c；Morton码中XMYMZJIf位设为000，即生成(肘一1)层比较数据点坐标与对应节点中心坐标的节点的Morton码。如同第二步那样扩充节点，最终大小，得到，Y，的状态值；生成OctreeNode一。。按相同方式依次建立其他层将状态值左移位，得到Morton码。节点数组，直至第一层。根据每层的Uni