| 本文已被：浏览 3702次 下载 6849次 |
码上扫一扫！ |
|
|
| 基于K-D树快速精确排序的四面体可视化 |
|
李昕1,2, 吴福理3, 童琪杰3, 陈伟锋2, 华炜2, 陈为2
|
|
1.中国石油大学(华东) 计算机与通信工程学院,山东 青岛 266555;2.CAD & CG 国家重点实验室(浙江大学),浙江 杭州 310058;3.浙江工业大学 计算机学院,浙江 杭州 310032
|
|
| 摘要: |
| 投影四面体法是四面体体数据可视化的一种重要方法.为了保证绘制结果准确,每一帧都需要对所有四面体按照遮挡关系进行排序,然而四面体之间强烈的依赖性不仅导致排序效率很低,而且很难并行实现.提出了一种基于K-D树空间划分的快速精确的四面体排序策略,在每个叶节点内逐层并行提取互不遮挡的四面体,层与层之间自然有序,且各叶节点的操作彼此独立进行.最后将结果按照叶节点之间的空间遮挡顺序组织在一起.通过两个级别的并行,在保证精确排序的同时极大地提高了效率,且数据结构易于图形处理单元GPU实现.实验结果表明,基于K-D树快速精确排序策略的GPU 实现极大地缩短了排序时间. |
| 关键词: 体绘制 四面体投影 K-D树空间划分 图形处理单元 精确排序 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金(61003193, 81172124); 国家高技术研究发展计划(863)(2012AA120903); 浙江省科技厅公益项目(2011C21058) |
|
| Quick and Accurate Sorting for Visualization of Tetrahedral Volume Datasets Based on K-D Tree |
|
LI Xin1,2, WU Fu-Li3, TONG Qi-Jie3, CHEN Wei-Feng2, HUA Wei2, CHEN Wei2
|
|
1.College of Computer and Communication Engineering, China University of Petroleum (East China), Qingdao 266555, China;2.State Key Laboratory of CAD & CG (Zhejiang University), Hangzhou 310058, China;3.College of Information Engineering, Zhejiang University of Technology, Hangzhou 310032, China
|
| Abstract: |
| The Projected Tetrahedra is a popular method in the field of tetrahedra database visualization. Tretrahedra must be sorted according to obstruction between them to achieve an accurate rendering image, but strong dependency among tetrahedra results in not only inefficient sorting, but also poor parallel execution. This paper proposes a tetrahedra sorting algorithm which is based on K-D tree spatial partitioning. The database in one leaf node are peeled into layers in natural order, and the tetrahedra in the same layer are unobstructed . The peeling of different leaf node is independent, and their sorted tetrahedra are organized together according to the obstruction between leaf nodes. The sorting efficiency has improved greatly through two-level parallelism and guarantees accurate sorting. The data structure can be implemented easily in a graphics processing unit (GPU). The experimental results show that the quick and accurate sorting based on K-D tree processed in GPU shortens the sorting time greatly. |
| Key words: volume rendering tetrahedra projection K-D tree spatial partitioning GPU (graphics processing unit) exact sorting |
