Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes
Authors: Qin, Y., Yu, H. and Zhang, J.
Journal: Computer Graphics Forum
Volume: 36
Issue: 5
Pages: 93-104
eISSN: 1467-8659
ISSN: 0167-7055
DOI: 10.1111/cgf.13248
Abstract: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.
https://eprints.bournemouth.ac.uk/29652/
Source: Scopus
Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes
Authors: Qin, Y., Yu, H. and Zhang, J.J.
Journal: Computer Graphics Forum
Volume: 36
Issue: 5
Pages: 93-104
ISSN: 0167-7055
Abstract:© 2017 The Author(s) Computer Graphics Forum © 2017 The Eurographics Association and John Wiley & Sons Ltd. Published by John Wiley & Sons Ltd. 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.
https://eprints.bournemouth.ac.uk/29652/
Source: BURO EPrints