MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes

Yipeng Qin National Centre for Computer Animation, Bournemouth University Hongchuan Yu National Centre for Computer Animation, Bournemouth University Jianjun Zhang National Centre for Computer Animation, Bournemouth University

Computational Geometry mathscidoc:1804.09001

Computer Graphics Forum, 36, (5), 2017.8
Geodesic based Voronoi diagrams play an important role in many applications of computer graphics. Constructing such Voronoi diagrams usually resorts to exact geodesics. However, exact geodesic computation always consumes lots of time and memory, which has become the bottleneck of constructing geodesic based Voronoi diagrams. In this paper, we propose the window-VTP algorithm, which can effectively reduce redundant computation and save memory. As a result, constructing Voronoi diagrams using the proposed window-VTP algorithm runs 3-8 times faster than Liu et al.’s method [LCT11], 1.2 times faster than its FWP-MMP variant and more importantly uses 10-70 times less memory than both of them.
No keywords uploaded!
[ Download ] [ 2018-04-03 15:55:05 uploaded by yipeng_qin ] [ 1069 downloads ] [ 0 comments ] 
@inproceedings{yipeng2017fast,
  title={Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes},
  author={Yipeng Qin, Hongchuan Yu, and Jianjun Zhang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20180403155505905725022},
  booktitle={Computer Graphics Forum},
  volume={36},
  number={5},
  year={2017},
}
Yipeng Qin, Hongchuan Yu, and Jianjun Zhang. Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes. 2017. Vol. 36. In Computer Graphics Forum. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20180403155505905725022.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved