Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models

doi:10.1016/j.cagd.2020.101848

CASIA OpenIR > 多模态人工智能系统全国重点实验室 > 三维可视计算

	Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models
	Wang, Pengfei 1; Xin, Shiqing 1; Tu, Changhe 1; Yan, Dongming2 ; Zhou, Yuanfeng 1; Zhang, Caiming 1
发表期刊	COMPUTER AIDED GEOMETRIC DESIGN
ISSN	0167-8396
	2020-05-01
卷号	79 页码:12
通讯作者	Xin, Shiqing(xinshiqing@163.com) ; Tu, Changhe(chtu@sdu.edu.cn)
摘要	Voronoi diagram based partitioning of a 2-manifold surface in R-3 is a fundamental operation in the field of geometry processing. However, when the input object is a thin-plate model or contains thin branches, the traditional restricted Voronoi diagrams (RVD) cannot induce a manifold structure that is conformal to the original surface. Yan et al. (2014) are the first who proposed a localized RVD (LRVD) algorithm to handle this issue. Their algorithm is based on a face-level clustering technique, followed by a sequence of bisector clipping operations. It may fail when the input model has long and thin triangles. In this paper, we propose a more elegant/robust algorithm for computing RVDs on models with thin plates or even tubular parts. Our idea is inspired by such a fact: the desired RVD must guarantee that each site dominates a single region that is topologically identical to a disk. Therefore, when a site dominates disconnected subregions, we identify those ownerless regions and re-partition them to the nearby sites using a simple and fast local Voronoi partitioning operation. For each site that dominates a tubular part, we suggest add two more sites such that the three sites are almost rotational symmetric. Our approach is easy to implement and more robust to challenging cases than the state-of-the-art approach. (C) 2020 Elsevier B.V. All rights reserved.
关键词	Geometry processing Restricted Voronoi diagram Thin plate Tubular shape
DOI	10.1016/j.cagd.2020.101848
关键词[WOS]	TRIANGULAR MESHES ; TESSELLATIONS ; RESOLUTION
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61772318] ; National Natural Science Foundation of China[61772016] ; National Natural Science Foundation of China[61772312] ; National Natural Science Foundation of China[61772523] ; NSFC-Zhejiang Joint Fund for the Integration of Industrialization and Informatization[U1609218] ; NSFC-Zhejiang Joint Fund for the Integration of Industrialization and Informatization[U1909210]
项目资助者	National Natural Science Foundation of China ; NSFC-Zhejiang Joint Fund for the Integration of Industrialization and Informatization
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:000533516400006
出版者	ELSEVIER
引用统计	被引频次：10[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.ia.ac.cn/handle/173211/39461
专题	多模态人工智能系统全国重点实验室_三维可视计算
通讯作者	Xin, Shiqing; Tu, Changhe
作者单位	1.Shandong Univ, Jinan, Peoples R China 2.Chinese Acad Sci, Inst Automat, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Wang, Pengfei,Xin, Shiqing,Tu, Changhe,et al. Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models[J]. COMPUTER AIDED GEOMETRIC DESIGN,2020,79:12.
APA	Wang, Pengfei,Xin, Shiqing,Tu, Changhe,Yan, Dongming,Zhou, Yuanfeng,&Zhang, Caiming.(2020).Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models.COMPUTER AIDED GEOMETRIC DESIGN,79,12.
MLA	Wang, Pengfei,et al."Robustly computing restricted Voronoi diagrams (RVD) on thin-plate models".COMPUTER AIDED GEOMETRIC DESIGN 79(2020):12.