Knowledge Commons of Institute of Automation,CAS
Parallel Computation of 3D Clipped Voronoi Diagrams | |
Liu, Xiaohan1,2![]() ![]() ![]() | |
发表期刊 | IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS
![]() |
ISSN | 1077-2626 |
2022-02-01 | |
卷号 | 28期号:2页码:1363-1372 |
摘要 | Computing the Voronoi diagram of a given set of points in a restricted domain (e.g., inside a 2D polygon, on a 3D surface, or within a volume) has many applications. Although existing algorithms can compute 2D and surface Voronoi diagrams in parallel on graphics hardware, computing clipped Voronoi diagrams within volumes remains a challenge. This article proposes an efficient GPU algorithm to tackle this problem. A preprocessing step discretizes the input volume into a tetrahedral mesh. Then, unlike existing approaches which use the bisecting planes of the Voronoi cells to clip the tetrahedra, we use the four planes of each tetrahedron to clip the Voronoi cells. This strategy drastically simplifies the computation, and as a result, it outperforms state-of-the-art CPU methods up to an order of magnitude. |
关键词 | Three-dimensional displays Graphics processing units Heuristic algorithms Two dimensional displays Robustness Approximation algorithms Euclidean distance Parallel algorithm Voronoi diagram clipping |
DOI | 10.1109/TVCG.2020.3012288 |
关键词[WOS] | TESSELLATIONS |
收录类别 | SCI |
语种 | 英语 |
资助项目 | National Natural Science Foundation of China[61772523] ; National Natural Science Foundation of China[61802406] ; Beijing Natural Science Foundation[L182059] ; CCF-Tencent Open Research Fund[RAGR20190105] ; Open Research Fund Program of State key Laboratory of Hydroscience and Engineering, Tsinghua University[sklhse-2020-D-07] ; Open Project Program of State Key Laboratory of Virtual Reality Technology and Systems, Beihang University[VRLAB2019B02] ; PKUBaidu Fund[2019BD001] |
项目资助者 | National Natural Science Foundation of China ; Beijing Natural Science Foundation ; CCF-Tencent Open Research Fund ; Open Research Fund Program of State key Laboratory of Hydroscience and Engineering, Tsinghua University ; Open Project Program of State Key Laboratory of Virtual Reality Technology and Systems, Beihang University ; PKUBaidu Fund |
WOS研究方向 | Computer Science |
WOS类目 | Computer Science, Software Engineering |
WOS记录号 | WOS:000736740300012 |
出版者 | IEEE COMPUTER SOC |
七大方向——子方向分类 | 计算机图形学与虚拟现实 |
国重实验室规划方向分类 | 视觉信息处理 |
是否有论文关联数据集需要存交 | 否 |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.ia.ac.cn/handle/173211/47116 |
专题 | 多模态人工智能系统全国重点实验室_三维可视计算 |
通讯作者 | Yan, Dong-Ming |
作者单位 | 1.Chinese Acad Sci CASIA, Inst Automat, Natl Lab Pattern Recognit NLPR, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Sch Artificial Intelligence, Beijing 100049, Peoples R China 3.Peking Univ, Natl Engn Lab Video Technol, Beijing 100000, Peoples R China 4.Tsinghua Univ, State Key Lab Hydrosci & Engn, Beijing 100084, Peoples R China |
第一作者单位 | 模式识别国家重点实验室 |
通讯作者单位 | 模式识别国家重点实验室 |
推荐引用方式 GB/T 7714 | Liu, Xiaohan,Ma, Lei,Guo, Jianwei,et al. Parallel Computation of 3D Clipped Voronoi Diagrams[J]. IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS,2022,28(2):1363-1372. |
APA | Liu, Xiaohan,Ma, Lei,Guo, Jianwei,&Yan, Dong-Ming.(2022).Parallel Computation of 3D Clipped Voronoi Diagrams.IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS,28(2),1363-1372. |
MLA | Liu, Xiaohan,et al."Parallel Computation of 3D Clipped Voronoi Diagrams".IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 28.2(2022):1363-1372. |
条目包含的文件 | 下载所有文件 | |||||
文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
2022_TVCG_Parallel C(1520KB) | 期刊论文 | 作者接受稿 | 开放获取 | CC BY-NC-SA | 浏览 下载 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论