An efficient algorithm for approximate Voronoi diagram construction on triangulated surfaces  

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

机构地区：[1]School of Computer Science and Technology,Harbin Institute of Technology,Weihai 264209,China [2]School of Computer Science and Technology,Shandong University,Qingdao 266237,China

出　　处：《Computational Visual Media》2023年第3期443-459,共17页计算可视媒体（英文版）

基　　金：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).

摘　　要：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.

关 键 词：geodesic Voronoi diagrams(GVDs) triangular surfaces mesh surfaces approximate geodesics Apollonius diagrams 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程] TP391.41[自动化与计算机技术—控制科学与工程]