Parallel Computation of 3D Clipped Voronoi Diagrams

doi:10.1109/TVCG.2020.3012288

CORC > 自动化研究所 > 中国科学院自动化研究所 > 模式识别国家重点实验室 > 三维可视计算

	Parallel Computation of 3D Clipped Voronoi Diagrams
	Liu, Xiaohan 1,2; Ma, Lei 3; Guo, Jianwei 1,2; Yan, Dong-Ming 1,2,4
刊名	IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS
	2022-02-01
卷号	28 期号:2 页码:1363-1372
关键词	Three-dimensional displays Graphics processing units Heuristic algorithms Two dimensional displays Robustness Approximation algorithms Euclidean distance Parallel algorithm Voronoi diagram clipping
ISSN号	1077-2626
DOI	10.1109/TVCG.2020.3012288
通讯作者	Yan, Dong-Ming(yandongming@gmail.com)
英文摘要	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.
资助项目	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]
WOS关键词	TESSELLATIONS
WOS研究方向	Computer Science
语种	英语
出版者	IEEE COMPUTER SOC
WOS记录号	WOS:000736740300012
资助机构	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
内容类型	期刊论文
源URL	[http://ir.ia.ac.cn/handle/173211/47115]
专题	模式识别国家重点实验室_三维可视计算
通讯作者	Yan, Dong-Ming
作者单位	1.Univ Chinese Acad Sci, Sch Artificial Intelligence, Beijing 100049, Peoples R China 2.Chinese Acad Sci CASIA, Inst Automat, Natl Lab Pattern Recognit NLPR, Beijing 100190, 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.