An efficient algorithm for approximate Voronoi diagram construction on triangulated surfaces

作     者：Wenlong Meng Pengbo Bo Xiaodong Zhang Jixiang Hong Shiqing Xin Changhe Tu Wenlong Meng;Pengbo Bo;Xiaodong Zhang;Jixiang Hong;Shiqing Xin;Changhe Tu

作者机构：School of Computer Science and TechnologyHarbin Institute of TechnologyWeihai 264209China School of Computer Science and TechnologyShandong UniversityQingdao 266237China 

出 版 物：《Computational Visual Media》 (计算可视媒体（英文版）)

年 卷 期：2023年第9卷第3期

页      面：443-459页

核心收录：

学科分类：08[工学] 081104[工学-模式识别与智能系统] 080203[工学-机械设计及理论] 0802[工学-机械工程] 0835[工学-软件工程] 0811[工学-控制科学与工程] 

基　　金：supported in part by the Youth Teacher Development Foundation of Harbin Institute of Technology(IDGA10002143) the National Natural Science Foundation of China(62072139,62272277,62072284) the National Key R&D Program of China(2021YFB1715900) the Joint Funds of the National Natural Science Foundation of China(U22A2033). 

主　　题：geodesic Voronoi diagrams(GVDs) triangular surfaces mesh surfaces approximate geodesics Apollonius diagrams 

摘      要：Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics.Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric.However,exact geodesic computation is time-consuming and has high memory usage,limiting wider application of geodesic Voronoi diagrams(GVDs).In order to overcome this issue,instead of using exact methods,we reformulate a graph method based on Steiner point insertion,as an effective way to obtain geodesic distances.Further,since a bisector comprises hyperbolic and line segments,we utilize Apollonius diagrams to encode complicated structures,enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples.Based on these strategies,we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces.We also suggest a measure for evaluating similarity of our results to the exact GVD.Although our GVD results are constructed using approximate geodesic distances,we can get GVD results similar to exact results by inserting Steiner points on triangle edges.Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods.